A useful technique: partial defunctionalization

Show and Tell
1

There is standing advice not to store functions in the model (or msg). However, when designing particularly package APIs this advice can be tricky to follow, particularly when we want to allow the user to specify some stateful computation that our library will evaluate. As a running example I will provide a simulation of physical forces.

In this example, the user will specify a collection of objects (Entity) that have an identity (comparable in the examples below), position and velocity. They will also configure our library with a collection of forces that they would like to have simulated. But here comes the tricky part: how do we specify what a force is? Conceptually it is something that takes the positions and velocities of the objects and modifies those velocities in some way, possibly based on some parameters.

type Force comparable
    -- modifies objects to have a global average position at these coords
    = Center Float Float 
    -- simulates rubber bands between nodes
    | Links (List {source : comparable, target: comparable, strength: Float})) 
    -- simulates charge/gravity with a strength param
    | ManyBody (Dict comparable Float)

The above representation is good because it obeys the advice given, but isn’t terribly flexible. If a user wants a force to behave slightly differently, the only way is to fork the library. We might be tempted to rather do:

type alias Force =
    List Entity -> List Entity

center : Float -> Float -> Force
center =  -- implementation

...

However, this throws out all the advantages that the advice gives us: serializablity, debugabillity, etc. Additionally, storing our model as data would allow us to potentially make certain optimisations - perhaps we can make a many body implementation that centers as a side effect and merge those two?

For a long time I have been caught between these two (indeed elm-visualization uses the first approach).

However, recently I realised that one can have their cake and eat it too, or rather provide a sensible compromise:

type Force comparable
    = Center Float Float 
    | Links (List {source : comparable, target: comparable, strength: Float})) 
    | ManyBody (Dict comparable Float)
    | Custom (List Entity -> List Entity)

This allows the typical user to use the provided functions and reap all the usual benefits of no functions, but allows the advance user to trade away those for unlimited flexibility.

As an aside: this only arises sometimes, as in many cases you can simply let the user provide the function as an argument and you do not need to store it. However, this is not always practical – in this example the forces need to be computed from the nodes, which are often dynamic in nature, and so the forces would need to be re-computed on each frame. This would be too inefficient.

12 Likes
2

Very interesting, not a technique I had thought of before, although you make it seem quite natural and obvious. :+1:

By chance, I read an article on defunctionalization yesterday evening, and although its a term I had heard before, I really could not remember much about it.

Am I right in thinking it simply means to replace all higher level functions with custom types, enumerating the actual implementations needed? I feel I could do with some examples of what plain-old defunctionalization is and can achieve in Elm.

1 Like
3

Yes exactly. So a simple example would be:


add1 : Int -> Int 
add1 = (+)

double : Int -> Int 
double n = 2 * n

calculate : Int -> Int
calculate n = add1 (double n)

turns into

type Op 
    = Add1
    | Double 

calculation : List Op
calculation = 
     [Double, Add1]

evaluate : Int -> List Op -> Int
evaluate = List.foldl eval

eval : Op -> Int -> Int
eval op inp =
     case op of
          Add1 -> inp + 1
          Double -> inp * 2

calculate : Int -> Int
calculate n = 
    evaluate n calculation

The second version represents the computation as data and deffers the evaluation to a later stage.

2 Likes
4

Thanks. That also answers something I was not sure about - its not just higher order functions you replace. So your add1 function is:

add1 : Int -> Int

and you made that into Add1.

I was thinking it was used only to describe when you replace higher order functions, so something like:


filter : (a -> Bool) -> List a -> List a
filter ... -- Filter a list as per List.filter

evenFilter : Int -> Bool
...

oddFilter : Int -> Bool
...

And you replace that with:

type Filter
    = Even
    | Odd

filterInts : Filter -> List Int -> List Int
5

I ran into this exact issue when working on a package elm-audio. I wanted to have a function like this loadAudio: (Result LoadError Source -> msg) -> AudioCmd msg which would store the user’s message until the audio was loaded and then call the user’s update with that msg. At first it seemed that this would mean storing Result LoadError Source -> msg in the model, but then I realized I could take this function and immediately enumerate every possible Result LoadError Source with it and store that list in the model instead. When the audio finishes loading, I’d find the correct version of the msg from that list and use it with the user’s update function.

This approach is pretty situational since it won’t work if it’s too memory/cpu intensive to enumerate all possible function parameters but when it does work it’s completely transparent to the user and delightfully hacky.

6

I used the same technique in the Camera module of my 2d game library:

Nice of you to name and share the pattern :smile:

1 Like
7

I use this for my work in Python machine learning code for easier configurations. Didn’t realize it has a name.

8

I think that’s a great technique if, as an API maker, you want to make the most demanded cases easier for consumers. But even a partially functionalized API is still unserializable, so you cannot store all your forces in a config.

If you want both flexibility and serializability, you might want to consider a composable recursive type, as shown by James Koppel, e.g.:

type Filter
  = Even
  | Prime
  | Not Filter
  | And Filter Filter

(Not sure if you can write a recursive type in Elm just like that, it’s been a while :confused:)

9

Not unserialisable, but partially serializable. i.e. you can store suff in the config provided you do not use any custom functions.

10

How would that work? Sometimes you can save a config, and sometimes you can not? :slight_smile:

11

Exactly. It would be encoder that can fail. Not saying that’s something one would want, but…

Alternatively, you could track that in the type system:

module Thing exposing (Thing, defunctionalized, custom, encode)
type Thing isSerializable 
    = Defunctionalized 
    | Custom (Foo -> Bar)

type Serializable = Serializable

type NotSerializable = NotSerializable

defunctionalized : Thing Serializable
defunctionalized = Defunctionalized

custom : (Foo -> Bar) -> Thing NotSerializable
custom = Custom

encode : Thing Serializable -> Json.Value
encode thing = 
    case thing of
       Defunctionalized -> E.string "Defunctionalized"
       Custom _ -> 
             -- can't happen
             E.null
3 Likes
12

Yeah, but that would mean that in some cases value |> encode |> decode is equal to value, and in some cases it’s not.

13

Not really. It would just mean that encode could fail sometimes (either at runtime or build time depending on which technique you used). But once you successfully encoded you would get completely deterministic decoding again.

14

But wouldn’t it fail silently? And Json.Value as a return type does’t seem to tell anything about failure. Maybe if there was a Maybe or a Result in the signature…

On a more palpable level, I would probably want to tell a user his config won’t be saved.

15

It won’t fail silently, because the compiler ensures you can only call encode with a Thing Serializable, which can’t reach the silent failure branch.

16

Oh, right, I missed that part.

17

I really like the use of the phantom variable to prevent failing to encode it :ok_hand:

One thing that you do lose when you add Custom, is the ability to compare two Things using (==).
Since Elm can potentially crash when you compare functions or things that contain functions (it crashes when you compare functions where one is anonymous IIRC). Without Custom, you know Thing won’t contain functions, so you can compare it. As soon as you introduce Custom, it can contain a function and you open the possibility of crashing when you compare it.

And in this case, it will only crash at runtime when it contains a function, so depending on what you/the user tried out, they may notice the crash quite late.

2 Likes
18

As an aside: this only arises sometimes, as in many cases you can simply let the user provide the function as an argument and you do not need to store it.

To extend on that thought, there is a technique that can generally be used to go a step further and get the functions out of your data, though at the cost of a bit more abstraction. I guess this would amount to full defunctionalization? I’m curious if this would still have the performance issues alluded to above due to the dynamic nature of the nodes:

allow the caller to provide their own union type that can be mapped to a function later

For this technique, Force would get a new parameter, and the caller would provide the function later:

type Force customForce comparable
    = Center Float Float 
    | ... other built-in variants ...
    | Custom customForce

simulation :
    (customForce -> List Entity -> List Entity)
    -> List (Force customForce comparable)
    -> State comparable

If you still want to provide a simpler API for those who don’t need anything custom, you could rename the above to ForceWithCustom, simulationWithCustom, and add:

type alias Force comparable =
    ForceWithCustom Never comparable
simulation :
    List (Force comparable)
    -> State comparable
2 Likes
19

Really nice!

It is still possible for users to have customForce be/store a function though, which means that once again you will not be able compare Force (the ones that contain function, not the ones with Never).

20

In the example, Force already was not comparable due to Elm’s limitation of not being able to compare custom types. But yeah, the module defining Force could destructure the Force to turn it into something comparable. To deal with that in the customForce approach, you’d just have to require either that customForce be comparable, or that the caller provide customForce -> comparable, depending on which part of Elm’s limitation you want to put on the caller.

Similarly, this can also allow the custom forces to be serializable, such as with:

decodeForce :
    Json.Decoder customForce
    -> Json.Decoder comparable
    -> Json.Decoder (Force customForce comparable)

And note that for dealing with Never:

  • Json.Decode.fail "" satisfies type Json.Decoder Never
  • Basics.never satisfies types:
    • Never -> comparable
    • Never -> List Entity -> List Entity
    • Never -> Json.Encode.Value
    • etc

But yeah, even with all that, the caller still has the option of putting functions in the data, though they do now have the option to avoid functions in the data if they want to.