Demystifying Jeremy's Interfaces

Show and Tell
23

Change #4: Add Implicit Laziness

This is one of the last parts of the story, I promise…

In the meantime, Rupert’s colleague Pit finally wants to understand the interface technology Rupert keeps talking about. As always, he starts to do so by modifying the existing code.

He adds a reset operation to the CounterOperations record, meaning to set the counter value to zero:

type alias CounterOperations t =
    { up : Int -> t
    , down : Int -> t
    , value : Int
    , reset : t
    }

and adds a utility function for the Counter users:

reset : Counter -> Counter
reset (Counter counterOperations) =
    counterOperations.reset

He handles the new operation in the map-like counterOps function:

counterOps : (rep -> typ) -> CounterOperations rep -> CounterOperations typ
counterOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    , reset = ops.reset |> raise
    }

ops.reset is a value of type rep, so he has to pipe the value with |> into the raise function, rather than using the function composition operator >> as in the up and down operations.

It’s easy for him to add the new operation to both the Int and List () counter implementations:

counterImplInt : Int -> CounterOperations Int
counterImplInt rep =
    { up = \n -> rep + n
    , down = \n -> rep - n
    , value = rep
    , reset = 0
    }


counterImplList : List () -> CounterOperations (List ())
counterImplList rep =
    { up = \n -> List.repeat n () ++ rep
    , down = \n -> List.drop n rep
    , value = List.length rep
    , reset = []
    }

The counter value “zero” is represented by the integer value 0 or by the empty list [], respectively.

Everything compiles, but trying to create a new Counter he immediately gets an error:

Initialization Error

RangeError: Out of memory

Since he has no idea what could be wrong, he asks Rupert for help. Rupert hasn’t seen this error in the context of interfaces before, but it looks like an endless recursion to him.

Unfortunately, Jeremy is visiting the type system demons and wizards conference and therefore isn’t available. Rupert and Pit have to help themselves.

It’s clear that the culprit must be the new reset operation, because without it everything works fine. Rupert and Pit try the example with both versions of Jeremy’s magic function they have seen before, but both versions exhibit the same behavior.

What :interrobang: happens upon creating an instance of the modified Counter interface?

Rupert suggests:

Let’s write down the steps of the evaluation.

Pit

I wouldn’t be able to do this, but if you can do it… May be we’ll see where the problem is. How do you want to proceed?

Rupert

Let’s remove all the code which isn’t relevant to the problem. Let’s use a Counter type with just a single reset function.

Rupert chooses the magic impl function from the fifth post (because the code is shorter):

impl : (ops -> typ) -> ((rep -> typ) -> rep -> ops) -> (rep -> typ)
impl constructor map =
    let
        raise : rep -> typ
        raise rep =
            constructor (map raise rep)
    in
    raise


type Counter
    = Counter CounterOperations


type alias CounterOperations =
    { reset : Counter }


intCounter : Int -> Counter
intCounter start =
    impl Counter (\raise rep -> { reset = raise 0 }) start


myCounter : Counter
myCounter =
    intCounter 12

He starts to write the following evaluation steps:

Creating the Counter:

  1. intCounter 12

Using the body of intCounter:

  1. impl Counter (\raise rep -> { reset = raise 0 }) 12

The body of impl:

  1. raise 12

Definition of raise:

  1. Counter ((\raise rep -> { reset = raise 0 }) raise 12)

Evaluation of the function call:

  1. Counter { reset = raise 0 }

Definition of raise:

  1. Counter { reset = Counter ((\raise rep -> { reset = raise 0 }) raise 0) }

Evaluation of the function call:

  1. Counter { reset = Counter { reset = raise 0 } }

Definition of raise:

  1. Counter { reset = Counter { reset = Counter ((\raise rep -> { reset = raise 0 }) raise 0) } }

Evaluation of the function call:

  1. Counter { reset = Counter { reset = Counter { reset = raise 0 } } }

Pit

Oh, I can see the recursion! If we look at steps 5, 7, and 9:

Counter { reset = raise 0 }

Counter { reset = Counter { reset = raise 0 } }

Counter { reset = Counter { reset = Counter { reset = raise 0 } } }

it’s clear that this never ends. Elm tries to create an endlessly nested structure. But why didn’t it happen before?

Rupert

I think I understand now. Just as an exercise: why don’t you write down the steps for a version of Counter where the interface just has a single up operation?

Pit

Having you on my side, I can try it.

He more or less copies Rupert’s steps from aboove:

Creating the Counter:

  1. intCounter 12

Using the body of intCounter, now with an up operation:

  1. impl Counter (\raise rep -> { up = \n -> raise (rep + n) }) 12

The body of impl:

  1. raise 12

Definition of raise:

  1. Counter ((\raise rep -> { up = \n -> raise (rep + n) }) raise 12)

Evaluation of the function call:

  1. Counter { up = \n -> raise (12 + n) }

Definition of raise:

Rupert

Stop! We don’t need more steps. Elm stops the evaluation right here. We now have a record where the up field is a function. This function is only evaluated when it is called.

Pit

OK, but don’t we have a function in the reset case, too?

  1. Counter { reset = raise 0 }

Rupert

For reset, we have a function application, or a function call. For up, we have a function definition. A function call can be evaluated immediately, if the arguments of the function call are constant, as they are in the reset case.

Pit

I see. So this is the difference between the up and the reset operations?

Rupert

Yes, I think this is it. Do you have an idea now what we could try to make the reset case work?

Pit

Hmm. From what you said, we should try to use a function definition for reset, too. But how do we do this?

Rupert

Do you know the lazy functions in the Json.Decode and Parser modules? They use a function of type () -> ..., sometimes called a “thunk”, to prevent endless recursions. You could do the same for the reset operation.

Pit changes his code accordingly…

He modifies the reset operation in the CounterOperations record to be a function:

type alias CounterOperations t =
    { up : Int -> t
    , down : Int -> t
    , value : Int
    , reset : () -> t
    }

The utility function for the Counter users has to be changed, too:

reset : Counter -> Counter
reset (Counter counterOperations) =
    counterOperations.reset ()

In the map-like counterOps function, he uses the function composition operator in the reset field, too, because now ops.reset is a function:

counterOps : (rep -> typ) -> CounterOperations rep -> CounterOperations typ
counterOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    , reset = ops.reset >> raise
    }

Finally the Int and List () counter implementations:

counterImplInt : Int -> CounterOperations Int
counterImplInt rep =
    { up = \n -> rep + n
    , down = \n -> rep - n
    , value = rep
    , reset = \() -> 0
    }


counterImplList : List () -> CounterOperations (List ())
counterImplList rep =
    { up = \n -> List.repeat n () ++ rep
    , down = \n -> List.drop n rep
    , value = List.length rep
    , reset = \() -> []
    }

Fingers crossed, they try the new code, and… it works! Success!

:+1:

A few days later, Jeremy returns from the demons and wizards conference. Rupert tells him about Pit’s problem and shows him the new code.

Jeremy

Yeah, I’ve already heard of your experiment. Congratulations that you were able to fix the problem on your own!

I have been thinking about it. Are you satisfied with the solution?

Rupert

Hmm, I thought that I am, but if you ask me like that… Can the code be improved, again?

Jeremy

Do you remember when we separated the interface definition from the implementation in order to hide the raise function from the interface implementations?

Rupert

Of course I do. Do you think that we can hide the laziness from the implementations, too?

Jeremy

Not only that, we can hide it even from the counterOps function.

But we have to change other things, above all the function in the Interface module. Have you decided which name the function should have, finally?

Rupert

You mean your “magic” function? Currently I tend to name it make or create because I like create Counter ...

Jeremy

OK. We’ll name it create.

In order to hide the laziness, we have to add the additional () parameter to the definition of the raise function. This makes the create function look like this:

create : (opsTyp -> typ) -> ((rep -> () -> typ) -> opsRep -> opsTyp) -> (rep -> opsRep) -> (rep -> typ)
create constructor mapOps impl rep =
    let
        raise : rep -> () -> typ
        raise rep_ () =
            constructor (mapOps raise (impl rep_))
    in
    raise rep ()

Can you see why this works?

Rupert

Hmm. It looks a little bit different than the “normal” lazy functions. You added the () as the second parameter to the raise function, not as the first.

Jeremy

Yes. In order to have the desired effect, in the end it is necessary to have a partially applied function call where only the () argument is missing.

We call raise in the counterOps function and pass the current internal state called “rep” into it. Thus, the missing () argument has to come after the “rep” parameter.

With this change, each raise call in the counterOps function is missing the final () argument. Evaluation is guaranteed to stop there.

Rupert

I see. Just to be sure, can you show me the new counterOps function?

Jeremy

Of course. Here it is:

counterOps : (rep -> typ) -> CounterOperations rep -> CounterOperations typ
counterOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    , reset = ops.reset |> raise
    }

Rupert

Wait - this looks exactly like Pit’s original code, including the forward pipe operator and even the function signature! How can this work? Don’t we have to change the function signature at least, because we changed the type of the raise function?

Jeremy

You are right. I cheated a little bit. To be precise, the function signature should be

counterOps : (rep -> () -> typ) -> CounterOperations rep -> CounterOperations (() -> typ)

As you can see from this version of the function signature, we also have to change the main interface type to

type Counter
    = Counter (CounterOperations (() -> Counter))

But if we want to, we can totally hide this from the counterOps function by generalizing the type () -> typ to simply typ. It still compiles, because it’s still just a map function from CounterOperations a to CounterOperations b.

Rupert

Magic :sparkles:

Jeremy

Oh, it’s more a little bit of cheating than magic here.

Because of the change in Counter, we have to change the utility functions, too, those which return a new Counter:

up : Int -> Counter -> Counter
up n (Counter counterOperations) =
    counterOperations.up n ()


down : Int -> Counter -> Counter
down n (Counter counterOperations) =
    counterOperations.down n ()


reset : Counter -> Counter
reset (Counter counterOperations) =
    counterOperations.reset ()

But besides that, the implicit laziness is completely hidden from the remaining code.

Rupert

I stand by my opinion: it’s magic :sparkles:

If you want to try the magic for yourself, here’s an Ellie with implicit laziness.

3 Likes