Unique function IDs

Hi everyone.

I’m trying to create an Elm-like desktop GUI with the same three components as The Elm Architecture. (A model storing application data, a view function that displays what is in the model and an update function that returns a new model.)

Here is a short usage example (can easily be git-cloned and run on your local machine) to help explain what I’m trying to do.

The run_app function that takes a view and a model is implemented with a recursive loop (display the view to the screen, update the model if needed and then call itself with the same view-function and the new model).

The view-function just contains further functions describing the UI (like Rect.widget).

The problem is that some controls like an indeterminate progress bar (as in the example) need to be stateful (the current position is state) and I’m trying to implement a non-verbose way of uniquely identifying each control.

The progress bar example takes a key (just an integer that the library auto-increments each time) to uniquely identify each control. This key has to be generated outside the view-function or else a new key is generated each time (losing state).

I was wondering if anyone had any better ideas to achieve the same goal (uniquely tracking each stateful control with an ID). Function equality can’t work because the model might modify some property of the function as in the second example.

Appreciate any help.

(I didn’t know how to express the topic in a succinct and accurate way which is the reason for the inaccurate title.)

How about letting users pass in a unique key? This way you don’t need to worry about it, let the library user take care of it. This paradigm works quite well in HTML and React land.

1 Like

Thanks; I think that’s an approach worth considering.

I thought it might be bad for modularity because the user might give the same key to two components, but I can provide some helpers to “provide a new context” and that should work well.

Will refactor the progress bars to use this method. Thanks again.

1 Like

The immediate mode GUI community (including React) has a long history of using optional identifiers to preserve widget internal state. This only works if maintaining the widget’s identifier is easier than storing its internal state in the model. As a result, those libraries defines adhoc rules to offer flexibility in “how unique” the identifiers really are (by implicitly looking at parent identifiers, or draw order, etc). This is worth looking into for inspiration as they have spent a long time thinking about it! I think this works well on small examples, but one has to be very familiar with the rules for more advanced situations involving dynamic collection of widgets (or risk loosing state). React notoriously disallow reparenting a widget for example.

The Elm Architecture clearly cheats on this aspect: a text input is expected to maintain the cursor position / selection, yet this internal state doesn’t have to be passed and updated from the model. It would extremely inconvenient if it did! But since TEA can’t explain how this magic works, user-defined widgets don’t have the same luxury as primitive widgets and so their internal state must leak everywhere.

I find this question super interesting from a purely functional design point of view, and I have a personal take on the subject – which is far from being usable – but there’s a playground tutorial available to experiment with :slight_smile: It’s not too far away from what TEA advocates, but the view and update function are bundled together to define the type of widgets:

type 'model widget =
  { view : 'model -> image
  ; update : event -> 'model -> 'model
  } (* for some [image] and [event] type defined by the GUI impl *)

This is a bit less straightforward to use than first-order toplevel functions like TEA, but it has the advantage of keeping the view and update function in sync automatically. We can combine widgets together, etc, and it’s pretty concise (at the cost of point-free style).

To explain how this allows for inner state in widgets, consider how we would define a “stateful” function in a purely functional way. For example, a function that counts the number of call that were made. Since we can’t do magical side effects to acquire the state, it follows that the previous state has to be passed as an argument and that the new state will be produced as a result:

let view_counter input state =
  let output = Printf.sprintf "input is %S and state is %i" input state in
  let new_state = state + 1 in
  output, new_state

So boring!.. But how do we hide the state from users now?

type ('input, 'output) stateful_function =
  Stateful : { state : 'state
             ; fn : 'input -> 'state -> 'output * 'state
             } -> ('input, 'output) stateful_function

This is a GADT, which hides the internal 'state type (and the initial/current state value). It does expose that this is a stateful function and not a regular 'input -> 'output pure function. To hide the internal state of such a function, we need to provide an initial value:

let view_counter = Stateful { state = 0 ; fn = view_counter }

We can do some nice things with the internal state type being hidden, like memoïzation in a similar way to SAC/FRP to avoid recomputing a result when the input hasn’t changed:

let memo fn =
  Stateful {
    state = None ;
    fn = fun input cache ->
           let output = match cache with
             | Some (prev_input, prev_output) when prev_input = input ->
                 prev_output
             | _ ->
                 fn input
           in
           output, Some (input, output)
  }

Using this idea to represent internal state in a GUI, the type of widgets is actually closer to:

type 'model widget =
  Widget :
    { state : 'state
    ; view : 'model -> 'state -> image
    ; update : event -> 'model -> 'state -> 'model * 'state
    }
    -> 'model widget

(And with the same idea, we can memoïze the view function to avoid rerendering unchanged portions of the GUI.) There are more examples in the playground on what this enables, and how to move/reparent stateful widgets in the GUI hierarchy. Contrary to unique identifiers, I’m especially happy that this explanation of widget’s internal state plays by the same rule as the rest, so one can duplicate a widget and its state, or rollback a widget state history in the same way that one can do all of this easily with the immutable model :slight_smile:

8 Likes

That’s very interesting @art-w. I appreciate all the information.

I am guessing that, in the web development world, some of the state would be offloaded to CSS (such as animating button changes on hover with a CSS pseudo class).

That would make things easier for React and Elm, although I’m not sure how a key can be optional for a purely functional IMGUI.

I thought about the problem for some time before opening this topic and considered a “bridge” approach that would store state in the model (which is one of the alternatives you mentioned).

A bridge is something that:

  1. Takes a function to extract a sub-model from a model (so to child widgets of the bridge, the root model isn’t what’s being passed).
  2. Takes a function to rejoin the sub-model to the parent model.
  3. Carries its own state holders so key-conflicts are restricted within this bridge (unless another bridge is defined further down, providing a new independent key-state).

That seemed complicated to implement and to use in my opinoin though so I just went with a mutable solution (sounds like cheating :sweat_smile:) that came to my mind after @yawaramin’s reply which I feel is easier to use and maintain.

In that approach, the stateful widgets themselves are generated by a functor and the functor generates a new hashtable (with a mutable has_changed boolean in a record. The boolean is set to true on state changes and reset to false at the end of each render loop). The user registers (appends to an internal mutable array) it with the library to indicate if we need to redraw.

I think that’s a scalable approach because all you need to do to modularise keys and prevent key-conflicts is to generate a control with a functor, and functors could also be used to provide different default values if you want a different design from default. Short usage example here - can easily be git-cloned and run.

I’m definitely cheating though and taking the easy way out. :sweat_smile: So can’t help but look up to those taking the harder road. All the best with your project.

I got a bit carried away, I didn’t mean that cheating is bad, it works well and is pragmatic! Regarding your question on optional keys, an easy trick is to add a mutable counter in your State.Make functor to record the draw order of the widgets: When the key is not specified, we increment the counter and use this as the implicit key (One needs to reset all the counters to 0 before rendering.) This way, the third progress bar always get the third state automatically. It works well for the common case where widgets are always displayed in the same order :slight_smile: (but you need explicit keys when doing conditional rendering or when dealing with a dynamic collection of widgets)

1 Like

I’m just updating this thread with a blog post describing the solution I settled on before abandoning the project. I think the solution is okay, and it might be helpful in some way to someone other there, as @yawaramin’s and @art-w’s replies were helpful to me (thanks again).

I mentioned before in the thread that I would probably go with a hash table approach, but the main issue there was garbage collection. The key/value pairs would live in that hash table until the application closed, which meant higher memory usage than needed.

It might have been possible to use two hash tables per widget type, swapping the inactive one with the active one on every render/update loop and copying state between, but that sounded kind of expensive so I didn’t go with that approach.