Demystifying Jeremy's Interfaces

[rupert]

@pit

it doesn’t use tail recursive functions, or does it?

Maybe the problem only shows up with the specific combination of TCO and returning a lambda - I don’t know. I get a little suspicious sometimes if you push the Elm compiler to do something weird thats all. Might take a little time this week to investigate this bug more fully and understand exactly what is needed to cause it.

[pit]

Change #3: Separate Interface from Implementation

Remember that the characters in the story are purely fictional…

---

Time has passed, and Rupert is using interfaces in more and more places. He even wrote a blog post about it. Reflected as he is, he notices that his role in the interface business has shifted recently. He is mainly defining the interfaces, leaving the implementation to others, for example to Pit, who loves to use Lists for everything, just as in the listCounter example.

Just like Jeremy managed to hide the “raise” function from the users of his init function in the last part, Rupert would love to hide the “raise” function from the folks implementing his interfaces.

Applying the “raise” function is something which has to be repeated in each interface implementation:

intCounter : Int -> Counter
intCounter start =
    impl Counter
        (\raise rep ->
            { up = \n -> raise (rep + n)
            , down = \n -> raise (rep - n)
            , value = rep
            }
        )
        start


listCounter : Int -> Counter
listCounter start =
    impl Counter
        (\raise rep ->
            { up = \n -> raise (List.repeat n () ++ rep)
            , down = \n -> raise (List.drop n rep)
            , value = List.length rep
            }
        )
        (List.repeat start ())

Wouldn’t it be nice, if he could somehow hide the call of the “raise” function, so that the code would look more like

intCounter : Int -> Counter
intCounter start =
    impl Counter
        (\rep ->
            { up = \n -> rep + n
            , down = \n -> rep - n
            , value = rep
            }
        )
        start


listCounter : Int -> Counter
listCounter start =
    impl Counter
        (\rep ->
            { up = \n -> List.repeat n () ++ rep
            , down = \n -> List.drop n rep
            , value = List.length rep
            }
        )
        (List.repeat start ())

As always in a situation like this, he calls Jeremy and tells him about his new idea. Jeremy is skeptical at first, but promises to get back to Rupert.

Indeed, just a few days later, Jeremy calls back and says:

Jeremy

Rupert, I’m sorry, but this isn’t something I can do for you, because there’s no general way to define this behavior for each and every interface. But if you are willing to tell me which fields of the operations record need a “raise” call and which don’t, then I can change the impl function in a way that lets you completely hide the “raise” function from the implementers of your interfaces.

Of course, Rupert would gladly provide this information to the Interface module, so Jeremy sends him the new version of the module and guides him in the process to transform Rupert’s existing code to the new version.

Jeremy

OK Rupert, let’s start: first, you need to add a type parameter to the operations record. And could you rename the operations record from CounterRecord to, say, CounterOperations? In my mind they are always interface “operations”…

Rupert is fine with the name change. After all, he doesn’t know yet how the code will look like in the end, so he trusts Jeremy that the new name will be well chosen. The new types look like this:

type Counter
    = Counter (CounterOperations Counter)


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

Jeremy

Now you have to use a new function from the Interface module. The new version of the module doesn’t expose an impl function anymore, but a new interface method. You’ll see why I renamed the function, soon.

Jeremy’s new method has the following signature:

interface :
    (ot -> t)
    -> ((r -> t) -> or -> ot)
    -> (r -> or)
    -> (r -> t)

Rupert has worked with Jeremy’s code long enough to easily map the abstract type names to his concrete use cases. Here’s the mapping for the Counter example:

Abstract	Concrete
t	Counter
r	hidden type, for example Int or List ()
ot	CounterOperations Counter
or	CounterOperations r

Rupert

Ok, Jeremy, I can translate the types to the counter example. What should I do with the function?

---

Jeremy

You as the interface designer should publish the interface function partially applied with the first two parameters.

Oh-K… Rupert looks at the first two parameters in more detail.

Rupert

The first parameter of type ot -> t (in my example CounterOperations Counter -> Counter) is the constructor function (Counter).

---

Jeremy

Right. I can tell you a little bit about the second parameter of type (r -> t) -> or -> ot.

It is a function that takes the well-known “raise” function of type r -> t and an operations record, parameterized with the type r (in your example CounterOperations r).

The function should return the same operations record, but now parameterized with the type t (in your example CounterOperations Counter).

So, basically, this is just a map function on the operations record.

---

Rupert

OK, a map function seems to be easy.

---

Jeremy

If I might add another naming proposal: I’d name the partially applied function “xxxInterface”.

Rupert writes the following counterInterface function:

counterInterface =
    interface Counter <|
        \raise ops ->
            { up = ops.up >> raise
            , down = ops.down >> raise
            , value = ops.value
            }

His IDE shows that the function signature is

counterInterface : (r -> CounterOperations r) -> (r -> Counter)

Rupert

Hey, I’m starting to understand how your new interface function helps to separate the interface definition from the implementation:

The second parameter tells the Interface module that the up and down fields of the CounterOperations record need a “raise” call, but the value field doesn’t. This is exactly the information I wanted to hide from the interface implementers.

Plus, I think I also understand why you named the function “interface”: the interface designers use it to define their interfaces.

So what can the interface implementers do with my counterInterface function?

---

Jeremy

They need to provide the next parameter, the one with type r -> CounterOperations r. This implements the counter operations for one specific internal representation type.

---

Rupert

No problem. I can easily extract the logic from the previous implementations for Int and List ().

As these will be the interface implementations, I’d probably name them counterImplInt and counterImplList. What do you think?

---

Jeremy

The names sound great. Go ahead.

Rupert writes the following implementations:

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


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

Rupert

Yes! This is exactly what I wanted to achieve: the implementers just have to be concerned with their internal type and nothing else. No need to call a “raise” function. All they need to do is to implement the interface operations using their internal type.

---

Jeremy

You’ve got it.

Now look again at the signature of the interface function. The last remaining part is r -> t.

When the implementers pass one of the “implementation” functions to the provided “interface” function, they get a function of type r -> t, which lets them create “objects” implementing the interface.

---

Rupert

Let’s just do this for the listCounter example. I really want to see the final result.

He writes:

listCounter : Int -> Counter
listCounter start =
    counterInterface counterImplList <|
        List.repeat start ()

Rupert

It compiles!

What do you think? Should I reverse the order? Let’s see…

intCounter : Int -> Counter
intCounter start =
    start
        |> counterInterface counterImplInt

Rupert

I’ll have to play with this a little bit more. At least the code is very modular now. Thank you very much, Jeremy.

---

Jeremy

I’m glad I could help you.

If you’re not sure about the “look-and-feel” of the code: there are many more options to structure the code. The only important thing is that you somehow collect the three values needed by the interface function and that you know how to combine them to get the r -> t function in the end.

---

Rupert

Ok, let me summarize the three values…

Rupert writes:

Type	Contents
ot → t	Constructor function
(r → t) → or → ot	“map” function for the operations record
r → or	Implementation of the interface operations

Rupert

Done. But how could I structure the code differently?

---

Jeremy

I’ll show you an example soon, but let’s first look at the implementation of the interface function to see how these three values can be combined:

interface : (ot -> t) -> ((r -> t) -> or -> ot) -> (r -> or) -> (r -> t)
interface ott rtorot ror =
    let
        rt : r -> t
        rt r =
            ott (rtorot rt (ror r))
    in
    rt

With the abstract names representing the types, it’s easy to visually type-check the code. The implementation of this new function looks very similar to the implementation of the previous impl function. Jeremy’s magic shines again!

---

Jeremy

OK, with that out of the way, here’s another possible syntax / DSL for the counter interface example:

The Counter and CounterOperations types stay the same as above.

The interface designer could supply her information in this way:

counterOperations : IF2.Operations r Counter (CounterOperations r) (CounterOperations Counter)
counterOperations =
    IF2.defineOperations <|
        \raise ops ->
            { up = ops.up >> raise
            , down = ops.down >> raise
            , value = ops.value
            }

Jeremy

I’m using an opaque type Operations here which could be defined in an Interface2 module and a function defineOperations to create such a value. I can show you their implementation later.

I’m sure you see what kind of value this type holds?

---

Rupert

Of course. It’s the “map” function for the CounterOperations record used to “raise” the parameterized record from the internal representation type to the Counter type.

---

Jeremy

Right. The interface implementers could use this to add their knowledge, too:

counterImplInt : IF2.Implementation Int Counter (CounterOperations Int) (CounterOperations Counter)
counterImplInt =
    IF2.implement counterOperations <|
        \rep ->
            { up = \n -> rep + n
            , down = \n -> rep - n
            , value = rep
            }


counterImplList : IF2.Implementation (List ()) Counter (CounterOperations (List ())) (CounterOperations Counter)
counterImplList =
    IF2.implement counterOperations <|
        \rep ->
            { up = \n -> List.repeat n () ++ rep
            , down = \n -> List.drop n rep
            , value = List.length rep
            }

Jeremy

Again, I’m using an opaque type Implementation and a function implement from a possible Interface2 module.

---

Rupert

Nice. Here you add the type-specific implementations of the interface operations.

But didn’t we miss the first value that is needed, the type constructor function?

---

Jeremy

I left it for the last part where we put all three things together. If the constructor function is named like the interface type, in your case Counter for both the type and the constructor, then the following code reads nicely:

intCounter : Int -> Counter
intCounter start =
    IF2.createInstanceOf Counter <|
        IF2.implementedBy counterImplInt <|
            IF2.fromValue <|
                start


listCounter : Int -> Counter
listCounter start =
    IF2.createInstanceOf Counter <|
        IF2.implementedBy counterImplList <|
            IF2.fromValue <|
                List.repeat start ()

Jeremy

I know that this is a very contrived example, but I wanted to show you what is possible.

---

Rupert

Ok, ok. This reads very nicely, indeed. I’m not sure I like the syntax with the many backward pipe operators, but I understand what you wanted to teach me: that we have many ways to design the interface API.

Can you show me the implementation of those types and functions?

---

Jeremy

Sure. Here they are:

type Operations r t or ot
    = Operations ((r -> t) -> or -> ot)


type Implementation r t or ot
    = Implementation
        { rtorot : (r -> t) -> or -> ot
        , ror : r -> or
        }


type Instance r t or ot
    = Instance
        { rtorot : (r -> t) -> or -> ot
        , ror : r -> or
        , r : r
        }


type Value r
    = Value r


defineOperations :
    ((r -> t) -> or -> ot)
    -> Operations r t or ot
defineOperations =
    Operations


implement :
    Operations r t or ot
    -> (r -> or)
    -> Implementation r t or ot
implement (Operations rtorot) ror =
    Implementation
        { rtorot = rtorot
        , ror = ror
        }


createInstanceOf :
    (ot -> t)
    -> Instance r t or ot
    -> t
createInstanceOf ott (Instance inst) =
    let
        rt : r -> t
        rt r =
            ott (inst.rtorot rt (inst.ror r))
    in
    rt inst.r


implementedBy :
    Implementation r t or ot
    -> Value r
    -> Instance r t or ot
implementedBy (Implementation impl) (Value r) =
    Instance
        { rtorot = impl.rtorot
        , ror = impl.ror
        , r = r
        }


fromValue :
    r
    -> Value r
fromValue =
    Value

---

Rupert

Oh, wow. I have to look at this in more detail, but I think I see how you use the types to gradually collect the needed values and finally put them all together in the… wait… the createInstanceOf function.

I’m sure I could change the DSL syntax, for example, to use forward pipe operators now.

Once again: thank you, Jeremy. You gave me a lot to play with.

---

Jeremy

Once again: I’m glad I could help. Feel free to ask me if you get stuck.

---

Is this the end of the story? A happy end?

Maybe… maybe not…

Here’s an Ellie with the new code and another one with the DSL like syntax.

[rupert]

What are the practical benefits of doing it this way versus Jeremeny’s original code? Is it simply so that implementors of interfaces do not have to use raise?

My other comment is that I find this highly unreadable. Its all the rt rtor or r t oror stuff, both in type var name and fields. I know the exact choice of names for these things is hard to come up with, and that you chose these names to represent how the parts compose together, but I think the original set of names was also good. I mean rep is the representation of the data structure, raise raises the representation into its higher level hidden form, and so on. I can speak these names and attach meaning to them, which helps me a lot when building up a mental picture of what is going on. I might have a go at doing some renaming on it and see if I can get it back to something a bit more sane…

-- JEREMY'S MAGIC INTERFACE MODULE


type Operations r t or ot
    = Operations ((r -> t) -> or -> ot)


type Implementation r t or ot
    = Implementation
        { rtorot : (r -> t) -> or -> ot
        , ror : r -> or
        }


type Instance r t or ot
    = Instance
        { rtorot : (r -> t) -> or -> ot
        , ror : r -> or
        , r : r
        }


type Value r
    = Value r


defineOperations :
    ((r -> t) -> or -> ot)
    -> Operations r t or ot
defineOperations =
    Operations


implement :
    Operations r t or ot
    -> (r -> or)
    -> Implementation r t or ot
implement (Operations rtorot) ror =
    Implementation
        { rtorot = rtorot
        , ror = ror
        }


createInstanceOf :
    (ot -> t)
    -> Instance r t or ot
    -> t
createInstanceOf ott (Instance inst) =
    let
        rt : r -> t
        rt r =
            ott (inst.rtorot rt (inst.ror r))
    in
    rt inst.r


implementedBy :
    Implementation r t or ot
    -> Value r
    -> Instance r t or ot
implementedBy (Implementation impl) (Value r) =
    Instance
        { rtorot = impl.rtorot
        , ror = impl.ror
        , r = r
        }


fromValue :
    r
    -> Value r
fromValue =
    Value

[pit]

Hi Rupert, thank you once more for your valuable feedback

My other comment is that I find this highly unreadable. Its all the rt rtor or r t oror stuff, both in type var name and fields.

I’m sorry if it gave the impression that I would recommend the current state of the implementation. You’re absolutely right that Jeremy’s names are a much better fit. In fact, here’s the version I used in my experiments:

interface : (opsTyp -> typ) -> ((rep -> typ) -> opsRep -> opsTyp) -> (rep -> opsRep) -> (rep -> typ)
interface constructor mapOps impl =
    let
        repTyp : rep -> typ
        repTyp rep =
            constructor (mapOps repTyp (impl rep))
    in
    repTyp

(You could rename repTyp to raise to remove the last “abstract” name.)

But up to this point, I used the abstract names only. They helped me personally to come up with other possibilities to structure the code. Only when I felt I had reached the end of my experiments, I thought about better names.

But in this series of posts, I’m not finished yet, so I’m still using the abstract names.

What are the practical benefits of doing it this way versus Jeremeny’s original code? Is it simply so that implementors of interfaces do not have to use raise?

Yeah, until now, this is the only reason. But remember, I’m not finished yet…

[rupert]

@pit

But up to this point, I used the abstract names only. They helped me personally to come up with other possibilities to structure the code. Only when I felt I had reached the end of my experiments, I thought about better names.

I see, you are using these strange names as mathematical tools to explore the possibilities, very clever. I will hold off doing any renaming then, until you have finished.

[pit]

It seems that I’m not able to change the table of contents in the first post anymore. If I find no other way, I’ll post the final table of contents after the last part of this series.

Intermezzo #1: Back to the Real World

I love happy ends, so it’s a perfect time to end the story of Jeremy, Rupert, and Pit.

---

The last thing for me to do is to apply the new interface technique to my introductory example: a list of different things. If you remember, I wanted to create a list with Strings, Ints, and Bools:

myListOfThings : List Thing
myListOfThings =
    [ AString "one", AnInt 1, AnInt 12, ABool True ]

and then be able to apply functions like

thingSize : Thing -> Int

thingDouble : Thing -> Thing

to the list elements. The problem with the original implementation was that, in order to add yet another wrapped type, for example Char, we needed to

1. Implement the type-specific functions (charSize, charDouble)
2. Add the new subtype to the wrapper type
3. Add a new case branch to the wrapper functions (thingSize, thingDouble)

I promised that it’s possible to omit tasks #2 and #3, and this is exactly what Jeremy’s magic interface technique enables us to achieve.

---

First, we have to define the interface type and the operations:

type Thing
    = Thing (ThingOperations Thing)


type alias ThingOperations t =
    { size : Int
    , double : t
    }

I add some convenience functions for the users of the Thing type:

thingSize : Thing -> Int
thingSize (Thing ops) =
    ops.size


thingDouble : Thing -> Thing
thingDouble (Thing ops) =
    ops.double

---

As the designer of the interface, I have to provide:

• the constructor function: Thing
• a map function for the operations record:

thingOps : (r -> t) -> ThingOperations r -> ThingOperations t
thingOps raise ops =
    { size = ops.size
    , double = raise ops.double
    }

---

As an implementer of the interface, I have to implement the operations for my internal representation type:

thingImplString rep =
    { size = stringSize rep
    , double = stringDouble rep
    }


thingImplInt rep =
    { size = intSize rep
    , double = intDouble rep
    }


thingImplBool rep =
    { size = boolSize rep
    , double = boolDouble rep
    }

Using the three parts (constructor, map for operations record, implementation of operations), I can provide functions to create the various kinds of things:

aString : String -> Thing
aString =
    IF.createInstanceOf Thing thingOps thingImplString


anInt : Int -> Thing
anInt =
    IF.createInstanceOf Thing thingOps thingImplInt


aBool : Bool -> Thing
aBool =
    IF.createInstanceOf Thing thingOps thingImplBool

I really like the look-and-feel of the code

(Note that I used the interface function from the last part of the story, but renamed it to createInstanceOf. I’m still experimenting with the Interface API…)

---

Now I can put on the interface user’s hat and create a list of different things:

myListOfThings : List Thing
myListOfThings =
    [ aString "one", anInt 1, anInt 12, aBool True ]

Instead of the constructor functions AString, AnInt, and ABool from the former wrapper type, I now use the instance creation functions aString, anInt, and aBool. Nice and easy!

I create a small test program (here’s an Ellie with the code):

main : Html msg
main =
    myListOfThings
        |> List.map thingSize
        |> Debug.toString
        |> Html.text

I start elm reactor, navigate to my source file, and get:

Initialization Error

RangeError: Out of memory

---

---

What ??? Has all this just been a fairy tale ???

No, no, no. I need a happy end! The story has to be continued…

[rupert]

Did it blow the stack?

[pit]

It’s an infinite recursion, and depending on how you run the code you get different errors (for example, in elm-test, I get a JavaScript error).

FYI: unfortunately, this would happen in Jeremy’s original code, too.

Stay tuned

[MarkHamburg]

Maybe this is known and just awaiting prose, but the sense left in the last few messages isn’t clear.

You are pre-computing the doubled object which in turn has a doubled-object to pre-compute, etc. The interface should have a function from unit to the doubled object and the top-level Thing wrapper can have a function which hides. (If Elm 0.19 had not removed lazy values, you could put a lazy object into the interface and force it in the top-level wrapper to avoid recomputes.)

[pit]

Hi Mark, thank you for your remark. Nice to see your name again.

The next parts of this series are in the works, but unfortunately I have a lot of other things to do currently, so it will take me a few more days to publish the next part. Sorry about that.

Your post not only contained a hint how to deal with the last problem, but also gave me a few more days before this topic will be closed

[pit]

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 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:

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

The body of impl:

3. raise 12

Definition of raise:

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

Evaluation of the function call:

5. Counter { reset = raise 0 }

Definition of raise:

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

Evaluation of the function call:

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

Definition of raise:

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

Evaluation of the function call:

9. 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:

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

The body of impl:

3. raise 12

Definition of raise:

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

Evaluation of the function call:

5. 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?

5. 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!

---

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

---

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

---

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

[rupert]

So, you boiled the whole thing down to basically 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 ()

Very clever

[rupert]

This part could be code generated (by say an elm-review rule):

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
    }

[pit]

Before I started to write all this I briefly talked to Jeremy (the real one ) about a couple of things, and he had functions/operations which returned for example a tuple of ( model, Cmd msg ) where the model was the thing which needed to be raised, so it might be more complicated in general than in my simple examples, but I, too, think the raising code (the map function) could be generated.

As always: thank you Rupert for your comments!

[rupert]

@pit

I briefly talked to Jeremy (the real one ) about a couple of things, and he had functions/operations which returned for example a tuple of ( model, Cmd msg ) where the model was the thing which needed to be raised

Yes, I realised after my comment about the codegen, that the patterns could be more complex that just the three variants in this example.

I also experimented with a (model, Cmd Msg) type structure. Works but you need a global Msg type accross all the object-oriented variants. An alternative might be to do something with (model, Cmd Value), but with the overhead of having to write codecs for Value for all events in the system. Gives you “sealed” TEA components like web components, but perhaps that is not really so useful.

This pattern is useful for data structures (like your counters). I would be interested benchmarking it versus the same implementation without the interface hiding the implementation type.

Also useful I have found for creating extensible systems in an OO way within Elm. I shall try and convert my elm-oo-style code to your single create interface function and see how I get on.

[pit]

Intermezzo #2: Back to Real Laziness

OK. We’re back again in the real world. Let’s see whether my Thing example works with the implicit laziness variant…

---

I have to add laziness to the interface type:

type Thing
    = Thing (ThingOperations (() -> Thing))

The convenience function returning a Thing has to be changed, too:

thingDouble : Thing -> Thing
thingDouble (Thing ops) =
    ops.double ()

If I got it right, then that should be all that’s needed to use the lazy variant of the Interface module. Can this be true?

---

Again, I start elm reactor, navigate to the source file with my little example program …

myListOfThings : List Thing
myListOfThings =
    [ aString "one", anInt 1, anInt 12, aBool True ]


main : Html msg
main =
    myListOfThings
        |> List.map thingSize
        |> Debug.toString
        |> Html.text

… and get:

[3,1,4,1]

Success! I really can create a list of different Things now without getting into an endless recursion!

---

Let’s see if the problematic double operation works, too:

main : Html msg
main =
    myListOfThings
        |> List.map thingDouble
        |> List.map thingSize
        |> Debug.toString
        |> Html.text

I reload the page and get

[6,2,5,0]

It works! If you want to try it on your own, here’s an Ellie with the code.

---

To be honest, I don’t know whether I can use the interface technology in my own Elm code… yet. But it’s good to have it available as another tool.

While thinking about possible use cases, I had an idea I’d like to explore in one more part of the story. After that, a little recap with the three variants of the “magic” function we encountered so far, and then we’re finally done.

Stay tuned…

[pit]

Thought Experiment: Interfaces in APIs

We’re still in story-telling mode…

---

Rupert is thinking about new use cases for the interface technology. The technology itself can be used to hide an internal type behind an interface. But we can make the interface type itself opaque and hide the usage of the whole interface technology behind a module API.

Rupert wants to try this with a real example, and it doesn’t take him long to implement something. He shows the new module to his colleague Pit.

---

Rupert

Hey Pit, let me show you my new “BitShifter” service! Here’s the module definition:

module BitShifter exposing
    ( BitShiftable, Operations
    , shiftLeftBy, shiftRightBy, toBitShiftable
    )

It lets you turn any type you like into a BitShiftable, a value that you can then shift left and shift right, just like the bit shift methods in the Bitwise core module.

The type BitShiftable is opaque. You don’t need to know the exact implementation in order to use it. Such a value can be shifted bitwise with the functions

shiftLeftBy : Int -> BitShiftable -> BitShiftable

shiftRightBy : Int -> BitShiftable -> BitShiftable

Isn’t this great?

You just have to tell the service a little bit about your type. The Operations record specifies what the service wants to know about your type in order to be able to to turn it into a BitShiftable:

type alias Operations a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    }

toBitShiftable : (a -> Operations a) -> a -> BitShiftable

So if you tell me how to create the up, down, and value fields for any value of your type a, plus a concrete a value, I can turn the latter into a BitShiftable!

---

Pit

Hey, this is nice, Rupert! But you can’t trick me The Operations record told me your secret: you are using an interface behind the scenes, aren’t you?

---

Rupert

Hmm…

---

Pit

No problem. Let’s pretend I don’t know. I’ll test your service right away with my favorite type: a list of units…

Let me see… I’ll give you the operations and you turn my List () into a BitShiftable…

---

He writes:

myBitShiftable : BitShifter.BitShiftable
myBitShiftable =
    BitShifter.toBitShiftable
        (\list ->
            { up = \n -> List.repeat n () ++ list
            , down = \n -> List.drop n list
            , value = List.length list
            }
        )
        [ (), (), () ]

---

Pit

And now I can shift it left and right, right?

shifted : BitShifter.BitShiftable
shifted =
    myBitShiftable
        |> BitShifter.shiftLeftBy 2
        |> BitShifter.shiftRightBy 1

Nice! But what can I do with the shifted result? Can I get it back as a List () to be able to look at it? What about a function like

fromBitShiftable : BitShiftable -> a

---

Rupert, who is a little disappointed about the course of the experiment, doesn’t want to give up yet, so he just says:

A function with this signature wouldn’t be possible, but let me think about it…

---

Of course he has been using the interface technology behind the scenes. Here’s his code:

type BitShiftable
    = BitShiftable (Operations BitShiftable)


type alias Operations a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    }


bitShiftableOps : (rep -> typ) -> Operations rep -> Operations typ
bitShiftableOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    }


toBitShiftable : (a -> Operations a) -> a -> BitShiftable
toBitShiftable impl =
    IF.create BitShiftable bitShiftableOps impl


shiftLeftBy : Int -> BitShiftable -> BitShiftable
shiftLeftBy n (BitShiftable ops) =
    ops.up (ops.value * (2 ^ max n 0) - ops.value)


shiftRightBy : Int -> BitShiftable -> BitShiftable
shiftRightBy n (BitShiftable ops) =
    ops.down (ops.value - (ops.value // (2 ^ max n 0)))

Nothing special so far. He even used the same operations as in the Counter interface to implement the bit shift operations. It’s no surprise that even Pit was able to see through the secret.

---

When he said that the fromBitShiftable function from above wouldn’t be possible, he was right. What type should the function result be? It can’t simply be an a like Pit suggested, because the a could be anything.

But Rupert has an idea: what if the BitShiftable type had a type parameter? A function like this would be possible to implement in Elm:

fromBitShiftable : BitShiftable a -> a

On the other hand, this would mean that the underlying type wouldn’t be hidden anymore, so it wouldn’t be possible to create a list of different BitShiftables anymore. For Rupert’s BitShifter service, this wouldn’t be a problem. The goal of the service is to enable bit-shifting-like operations for a user-supplied type, not to make multiple different BitShiftable values combinable.

Great. Rupert has a plan how to proceed.

---

So how could he implement the fromBitShiftable function? He starts with a version that looks like the value function from the Counter interface:

fromBitShiftable : BitShiftable a -> a
fromBitShiftable (BitShiftable ops) =
    ops.internal

OK. So he needs an Operations record with an additional internal field:

type alias Operations a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    , internal : a
    }

The new field has to be dealt with in the map-like bitShiftableOps function:

bitShiftableOps : (rep -> typ) -> Operations rep -> Operations typ
bitShiftableOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    , internal = ops.internal
    }

Hmm. This doesn’t compile. To make the compiler happy, Rupert would have to raise the internal value, too. But he doesn’t want to change the type of the internal value.

Rupert knows how to deal with this problem: he has to introduce an additional type parameter to the Operations record type, too:

type alias Operations i a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    , internal : i
    }

Now he can leave the internal value as it is without having to apply the raise function:

bitShiftableOps : (rep -> typ) -> Operations rep rep -> Operations rep typ
bitShiftableOps raise ops =
    { up = ops.up >> raise
    , down = ops.down >> raise
    , value = ops.value
    , internal = ops.internal
    }

This compiles! The BitShiftable type now looks like this:

type BitShiftable a
    = BitShiftable (Operations a (BitShiftable a))

Great! Now the toBitShiftable function:

toBitShiftable : (a -> Operations a a) -> a -> BitShiftable a
toBitShiftable impl =
    IF.create BitShiftable bitShiftableOps impl

Only the function signature had to be changed. Nice.

---

But Rupert knows: if I show Pit this new version, he’ll still be able to figure out what I’ve done just by looking at the types of the toBitShiftable function.

Wouldn’t it be nice if Rupert could use the same Operations record as before in his BitShifter API?

Here’s how the user-supplied impl parameter looked like in the old and in the new version:

old:
    a ->
        { up : Int -> a
        , down : Int -> a
        , value : Int
        }


new:
    a ->
        { up : Int -> a
        , down : Int -> a
        , value : Int
        , internal : a
        }

Wait… Rupert is sure that he can turn the former into the latter!

---

He defines two different operations record types: one which is externally visible and an internal one:

type alias Operations a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    }


type alias InternalOperations i a =
    { up : Int -> a
    , down : Int -> a
    , value : Int
    , internal : i
    }

Now he can convert the original impl parameter with the Operations record into a version using the new InternalOperations record:

internalImpl : (a -> Operations a) -> a -> InternalOperations a a
internalImpl impl a =
    { up = (impl a).up
    , down = (impl a).down
    , value = (impl a).value
    , internal = a
    }

Using this helper function, we get almost the original version of the toBitShiftable function:

toBitShiftable : (a -> Operations a) -> a -> BitShiftable a
toBitShiftable impl =
    IF.create BitShiftable bitShiftableOps (internalImpl impl)

After all, this was easy!

---

Rupert shows Pit the new version of the BitShifter module.

Rupert

Hi Pit. Do you remember the fromBitShiftable function you wanted to have to be able to get back at the shifted value?

I told you that it wouldn’t be possible to implement it in the way you suggested. But if we add a type variable to the BitShiftable type, then I can give you a function

fromBitShiftable : BitShiftable a -> a

---

Pit

Hmm, OK, so what would I have to change in my code?

---

Rupert

As I said: you have to add a type parameter.

---

Pit

Wait. That’s all I need to do? Everything else stays the same? If this is true, then you’re slowly but surely turning into a type system wizard like Jeremy!

Let me try it…

---

He adds the type parameter to his code:

myBitShiftable : BitShifter.BitShiftable (List ())
myBitShiftable =
    BitShifter.toBitShiftable
        (\list ->
            { up = \n -> List.repeat n () ++ list
            , down = \n -> List.drop n list
            , value = List.length list
            }
        )
        [ (), (), () ]


shifted : BitShifter.BitShiftable (List ())
shifted =
    myBitShiftable
        |> BitShifter.shiftLeftBy 2
        |> BitShifter.shiftRightBy 1

---

Pit

And now I can get back the original and the bit-shifted value?

---

He types:

myBitShiftable
    |> BitShifter.fromBitShiftable
--> [(), (), ()]


shifted
    |> BitShifter.fromBitShiftable
--> [(), (), (), (), (), ()]

---

Pit

Jeremy, um, I mean, Rupert, you are a genius!

I can’t wait until you explain your wizardry to me!

---

Rupert smiles. Mission completed.

-- ::: --

---

Ok, this was the last aspect of the interface technology I wanted to look at. I found it interesting that you can hide a set of user-supplied functions behind an easy-to-use interface type, and that you can hide them from both the users of a module as well as from the module code itself.

In the BitShifter example, both the module user as well as other module functions can use this simple interface:

type BitShiftable a

shiftLeftBy : Int -> BitShiftable a -> BitShiftable a

shiftRightBy : Int -> BitShiftable a -> BitShiftable a

---

In the next days, I’ll add a short recap with the three versions of Jeremy’s magic interface functions we’ve seen before, … and then one last thing.

[rupert]

@pit

fromBitShiftable : BitShiftable a -> a

On the other hand, this would mean that the underlying type wouldn’t be hidden anymore, so it wouldn’t be possible to create a list of different BitShiftables anymore. For Rupert’s BitShifter service, this wouldn’t be a problem. The goal of the service is to enable bit-shifting-like operations for a user-supplied type, not to make multiple different BitShiftable values combinable.

I think the goal of using interfaces is to hide the implementation. This allows you to program in Elm in a more open-ended way. New implementations can be added at a later time without changing existing code. I think as soon you want functions like this that recover the implementation type, it renders the technique a bit pointless. This is just going back to the “poor mans typeclass” approach.

Not that it isn’t without its uses. Consider List.map or other higher order utility functions:

map : (a -> b) -> List a -> List b

Separates the iteration over the list part from the mapping function. Its higher order, so the caller provides the mapping function, which is one of the more obvious ways in which Elm or functional programming in general allows implementation details to be hidden or deferred. In Elm the other obvious ways are modules and opaque types, and the package system which allows internal modules to not be exposed.

[pit]

Hi Rupert, thank you for your response.

I think the goal of using interfaces is to hide the implementation.

Yeah, maybe this wasn’t a good idea after all, but I found it interesting, so I added one more episode. I currently haven’t much time, so it will still take me some days to finish this series.

[Abastro]

@pit

interface : (opsTyp -> typ) -> ((rep -> typ) -> opsRep -> opsTyp) -> (rep -> opsRep) -> (rep -> typ)
interface constructor mapOps impl =
    let
        repTyp : rep -> typ
        repTyp rep =
            constructor (mapOps repTyp (impl rep))
    in
    repTyp

(You could rename repTyp to raise to remove the last “abstract” name.)

So with ops container, we would have

interface : (ops typ -> typ) -> ((rep -> typ) -> ops rep -> ops typ) -> (rep -> ops rep) -> (rep -> typ)

This part suspiciously looks like refold from recursion-scheme.

refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b 

Replace f with ops, a with rep, b with typ and you get

refold :: Functor ops => (ops typ -> typ) -> (rep -> ops rep) -> (rep -> typ)

Since Functor ops is effectively (a -> b) -> (f a -> f b), this refold is a slightly more general version of interface.
If Elm had ability to derive map function (Would not need typeclass for this), boilerplate for implementing this part could be condensed.

Interesting how a function analogous to refold could be used for hiding implementation.

By the way, the technique of constructing a data recursively is called “Typing the knot”. The object constructor (rep -> typ) is recursively referenced to attain the correct operation type for typ.