Using a continuation-passing interpreter to make an interactive read operation for the browser with Elm

I recently started working through Essentials of Compilation: An Incremental Approach in Racket (EOC) by Jeremy G. Siek as part of my self-study plan to learn more about programming language theory, design, and implementation.

Since I've been having great success implementing the interpreters from EOPL in Elm I decided to continue using Elm, instead of Racket, for the interpreters and compilers in EOC.

In the first chapter, we're given the language L_Int which has the following concrete syntax:

exp   ::= int | (read) | (- exp) | (+ exp exp) | (- exp exp)
L_Int ::= exp

Of particular interest to us, for this article, is the read operation. The read operation is supposed to prompt the user of the program for an integer.

Racket supports the read operation, so an interpreter for L_Int in Racket is trivial to write. The obvious question facing me was,

How can I implement an interpreter for L_Int in Elm?

I'm happy to share that I came up with two practical solutions to my question which I will explain in the rest of this article.

Solution 1: Use a fixed input buffer

The first solution I came up with was to use a fixed input buffer.

The read operation, though it presents an interesting implementation challenge in a pure functional language like Elm, is not particularly a point of interest from the perspective of the book. The incremental approach to compiler development is supposed to be the focal point.

With that in mind, any interpreter implementation that gives a satisfactory semantics to read is good enough.

How does it work?

The interpreter is given an input buffer that is prepopulated with all the user's input that the program needs.

type alias Input =
    List Int

run : String -> Input -> Result Error Int

When a read operation is encountered one item from the input buffer is taken and used as the user's input for that interpretation of read.

interpretExpr : Expr -> Input -> ( Result RuntimeError Int, Input )
interpretExpr expr input =
    case expr of
        ...

        Prim Read ->
            case input of
                [] ->
                    ( Err MissingInput
                    , input
                    )

                n :: restInput ->
                    ( Ok n
                    , restInput
                    )

        ...

It accomplishes the goal and I have tests to prove it.

suite : Test
suite =
    describe "Ch1.L_Int.Interpreter" <|
        List.map testRun
            [ ( "(+ 10 32)", [], 42 )
            , ( "(+ 10 (- (+ 12 20)))", [], -22 )
            , ( "(+ (read) (- 8))", [ 50 ], 42 )
            ]

Here's the full source code of the interpreter.

As I explained above, this solution is good enough for the purposes of the book. However, I had a nagging feeling to explore and try to figure out how I might interpret the read operation to make it actually wait for user input. The new question facing me was,

How do I run the interpreter, wait for the user's input when I encounter the read operation, and then resume running the interpreter after I get the user's input?

The second solution I came up with involves continuation-passing interpreters and Online Python.

Continuation-Passing Interpreters

In Chapter 5: Continuation-Passing Interpreters of EOPL, Daniel P. Friedman and Mitchell Wand present a master class on continuation-passing interpreters that is, exquisite. In that chapter they introduce the concept of a continuation as an abstraction of the control context. And, they teach you how to write interpreters that take a continuation as an argument so that you can make the control context explicit.

What is meant by control context?

They never explicitly define what they mean by control context but I understand it to mean, all the state that you have to remember in order to continue with the rest of the computation once you're finished with the current computation.

So for e.g. the control context associated with (+ (read) (- 8)) when you're interpreting the read operation is (+ _ (- 8)) since you have to remember to do the negation and the addition once you get the user's input.

What does that get us?

It gets us ultimate control of the computation. We can now capture the control context surrounding any read operation in order to pause the computation before performing the read operation and then resume the computation after getting the user's input.

Online Python

Online Python simply showed me that what I wanted to do was reasonable and possible.

If you type the following Python program into their editor,

def sum(a, b):
    return (a + b)

a = int(input('Enter 1st number: '))
b = int(input('Enter 2nd number: '))

print(f'Sum of {a} and {b} is {sum(a, b)}')

and hit the "Run" button you see that it pauses and waits for you to enter your input when it executes the input function. That's exactly what we want to achieve when we encounter a read operation in our language.

I don't know exactly how they did it but I do know that when it's waiting for user input it's simply using an HTML input element to gather the user's input.

Solution 2: Use a continuation-passing interpreter

The second solution I came up with was to use a continuation-passing interpreter together with a user interface like the one from the Online Python website.

I converted my original interpreter into a continuation-passing interpreter for L_Int using the standard techniques I learned from Chapter 5 of EOPL.

The run function changed from:

run : String -> Input -> Result Error Int

to:

type Effect
    = Value Int
    | ReadInt Continuation

type Continuation
    = EndCont
    | NegateCont Continuation
    | Add1Cont AST.Expr Continuation
    | Add2Cont Int Continuation
    | Sub1Cont AST.Expr Continuation
    | Sub2Cont Int Continuation

run : String -> Result Error Effect

The idea behind it is that when we encounter a read operation we can now return ReadInt cont signifying that the interpreter is interpreting a read operation and as such is waiting for the user's input.

interpretExpr : Expr -> Continuation -> Effect
interpretExpr expr cont =
    case expr of
        ...

        Prim Read ->
            ReadInt cont

        ...

When the user hits the "Run" button in my UI, we interpret the source code in the textarea. If the interpreter encounters a read operation, we display an HTML input element to collect the user's input.

update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        ...

        ClickedRun ->
            case I.run model.source of
                Ok effect ->
                    case effect of
                        I.Value n ->
                            ( { model | lines = model.lines ++ [ Success <| String.fromInt n ] }
                            , Cmd.none
                            )

                        I.ReadInt readIntCont ->
                            ( { model | maybeReadIntState = Just { value = "", cont = readIntCont } }
                            , focus readInputId
                            )

                Err (I.SyntaxError _) ->
                    ( { model | lines = model.lines ++ [ Error "Syntax Error" ] }
                    , Cmd.none
                    )

        ...

view : Model -> H.Html Msg
view { ..., lines, maybeReadIntState } =
    H.div []
        [ ...
        , let
            outputLineViews =
                List.map viewOutputLine lines

            inputLineView =
                case maybeReadIntState of
                    Nothing ->
                        []

                    Just { value } ->
                        [ H.form
                            [ HA.class "console__line console__line--input"
                            , HE.onSubmit SubmittedValue
                            ]
                            [ H.span [] [ H.text ">" ]
                            , H.input
                                [ HA.id readInputId
                                , HA.type_ "text"
                                , HA.value value
                                , HE.onInput InputValue
                                ]
                                []
                            ]
                        ]
          in
          H.div [ HA.class "console" ] ( outputLineViews ++ inputLineView )
        ]

Remember, how I said:

... the control context associated with (+ (read) (- 8)) when you're interpreting the read operation is (+ _ (- 8)) ...

Well that's exactly what the continuation represents at this point in the interpretation,

Add1Cont (Prim (Negate 8)) EndCont -- (+ _ (- 8))

When the user submits their input, we try to convert it to an Int and if we're successful we resume interpretation.

update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        ...

        SubmittedValue ->
            case model.maybeReadIntState of
                Just { value, cont } ->
                    case String.toInt value of
                        Just m ->
                            let
                                valueLine =
                                    Success <| "> " ++ String.fromInt m
                            in
                            case I.resume m cont of
                                I.Value n ->
                                    ( { model
                                      | lines = model.lines ++ [ valueLine, Success <| String.fromInt n ]
                                      , maybeReadIntState = Nothing
                                      }
                                    , Cmd.none
                                    )

                                I.ReadInt readIntCont ->
                                    ( { model
                                      | lines = model.lines ++ [ valueLine ]
                                      , maybeReadIntState = Just { value = "", cont = readIntCont }
                                      }
                                    , focus readInputId
                                    )


                        Nothing ->
                            ( model, Cmd.none )

                Nothing ->
                    ( model, Cmd.none )

        ...

Here's the full source code of the continuation-passing interpreter.

Conclusion

This was a fun challenge for me to solve because I was able to leverage what I learned about continuation-passing interpreters from EOPL and combine it with my web development knowledge to come up with, what I think is, a satisfying solution to the problem.