Using a continuation-passing interpreter to make an interactive read operation for the browser with Elm
Tags: continuations, plt, elm
Published: 2024-05-23 11:27:26

---
title: Using a continuation-passing interpreter to make an interactive read operation for the browser with Elm
published: true
description: I explain how I implemented a continuation-passing interpreter with Elm to make a read operation for a programming language that reads the user's input via a browser.
tags: continuations, plt, elm
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2024-05-23 11:08 +0000
---

I recently started working through [Essentials of Compilation: An Incremental Approach in Racket](https://mitpress.mit.edu/9780262047760/essentials-of-compilation/) (EOC) by [Jeremy G. Siek](https://www.youtube.com/watch?v=43VA_QaTRT8) 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](https://github.com/dwayne/elm-eopl3) 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](https://github.com/IUCompilerCourse/public-student-support-code/blob/7f28a214629867edc8d48c480c075e221e8c3233/interp-Lint.rkt#L18-L21) 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.

```elm
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`.

```elm
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](https://github.com/dwayne/elm-eoc/blob/45313341ada4872ae4c98a21b5edab147cdc1f17/tests/Test/Ch1/L_Int/Interpreter.elm) to prove it.

```elm
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](https://github.com/dwayne/elm-eoc/blob/45313341ada4872ae4c98a21b5edab147cdc1f17/src/Ch1/L_Int/Interpreter.elm) 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](https://www.online-python.com/).

## Continuation-Passing Interpreters

In [Chapter 5: Continuation-Passing Interpreters](https://github.com/dwayne/elm-eopl3/tree/714cee1267b4d745697b83c431e5b40a8cd63e94/src/Ch5) of [EOPL](https://mitpress.mit.edu/9780262062794/essentials-of-programming-languages/), [Daniel P. Friedman](https://en.wikipedia.org/wiki/Daniel_P._Friedman) and [Mitchell Wand](https://www.khoury.northeastern.edu/home/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](https://www.online-python.com/) simply showed me that what I wanted to do was reasonable and possible.

If you type the following Python program into their editor,

```python
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](https://www.online-python.com/) website.

![The UI for Ch1: L_Int](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c5gkvh322haf766in42h.png)

I converted [my original interpreter](https://github.com/dwayne/elm-eoc/blob/6da9b77aaf112c416516f9e176c59b9044264c2d/src/Ch1/L_Int/Interpreter.elm) into [a continuation-passing interpreter for `L_Int`](https://github.com/dwayne/elm-eoc/blob/6da9b77aaf112c416516f9e176c59b9044264c2d/src/Ch1/L_Int/CPSInterpreter.elm) using the standard techniques I learned from Chapter 5 of EOPL.

The `run`  function changed from:

```elm
run : String -> Input -> Result Error Int
```

to:

```elm
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.

```elm
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.

```elm
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 )
        ]
```

![The UI for Ch1: L_Int with an input of 50](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o3tn1dh3hh0furbo1epv.png)

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,

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

![The state of model when the UI for Ch1: L_Int has an input of 50](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/44qu9kffkk4ux1nuc1kb.png)

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

```elm
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](https://github.com/dwayne/elm-eoc/blob/6da9b77aaf112c416516f9e176c59b9044264c2d/src/Ch1/L_Int/CPSInterpreter.elm) of the continuation-passing interpreter.*

{% embed https://youtu.be/8XxqiLZD0Y8 %}

## 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.