A Typed Lisp in Elm

by XKCD

As a fun exercise, I decided to try to make a Lisp using Elm … not the whole deal, of course, but just a little piece to see what is possible and how one would do it. The result, which I will describe here, is a skeleton of a very small typed Lisp. Of course Lisp itself doesn’t have types, so this is a different beast. In any case, one needs to construct two functions, parse and eval. Here is how the parser works:

> parse "(+ 1 2)"
Just (LIST [Str "+",Num 1,Num 2])
    : Maybe AST

And here is eval:

> eval "(+ 1 2)"
VNum 3 : Value

Note that nonsense inputs produce the value Undefined:

> eval "(+ 1 a)"
Undefined : Value

You can find the code for all of this on GitHub.

Constructing the Parse Function

The first step in constructing the parse function is to define the type of the abstract syntax tree (AST):

type AST
    = Str String
    | Num Int
    | LIST (List AST)

Thus, in this little Lisp, there are two primitive types, one for strings, one for integers. The type is recursive, so lists can be nested within lists:

> parse "(1 2 (3 4))"
Just (LIST [Num 1,Num 2,LIST [Num 3,Num 4]])

The top-level parser, which is built out of combinators using the elm/parser library, is a one-liner:

parser : Parser AST
parser =
    oneOf [ lazy (\_ -> list), string, integer ]

TheoneOf combinator chooses among the alternative parsers, list, string, and integer : one parser for each part of the definition of the AST type. The lazy phrase is needed for recursion to work.

The list parser is defined this way, out of the sequencing combinators (|.) and (|=):

list : Parser AST
list =
    (succeed identity
        |. symbol "("
        |. spaces
        |= many parser
        |. spaces
        |. symbol ")"
        |. spaces
    )
        |> map LIST

The resulting parser pipeline works by first recognizing a left parenthesis, then spaces, if any. The many combinator is then applied to the top-level parser so as to run it as many times as necessary to consume the input. Finally, the pipeline, taking care of whitespace as needed, recognizes the final trailing parenthesis.

In more detail, the combinator (|.) says “ignore the result of running the following parser,” while the combinator (|=) says “keep the result of running the following parser.” The output of the pipeline is fed as a bunch of arguments into succeed whatever, where whatever is a function that can accept those arguments. In the case at hand, there is just one argument, and the function used is the identity function. If running the pipeline is successful, its output is piped into the function LIST so that the type of the output is AST. That’s it!

For more details on construction of the parser, please, please see the GitHub repo.

Constructing the Eval Function

First, the type, which is eval : String -> Value . Recall that we will be doing things like the below:

> eval "(+ 1 2)"
VNum 3 : Maybe Lisp.Value
> eval "(if (> 4 1) bigger smaller)"
Just (VStr "bigger") : Maybe Lisp.Value

Thus the Value type enumerates the kind of values that eval can produce:

type Value
    = VStr String
    | VNum Int
    | VList (List Value)
    | Undefined
    | ParseError

The first two take care of primitive types — strings, and integers. The next one takes care of lists of values, while the last two deal with errors. Undefined is the value of an expression that was correctly parsed but which cannot be evaluated, as in eval (+ 1 a). Undefined can occur as a value because our Lisp, while it has types, does not do much in the way of type checking.

The eval function is essentially the composite of parse : String -> AST and evalAst: AST -> Value, as in the below:

eval : String -> Value
eval str =
    case str |> parse |> Maybe.map evalAst of
        Just val ->
            val
        Nothing ->
            ParseError

The eval function itself is implemented as a huge case statement, which in outline form looks like this:

evalAst : AST -> Value
evalAst ast =
    case ast of
        Num k ->
            VNum k
        Str s ->
            VStr s
        LIST list ->
            case List.head list of
                Just (Str "+") ->
                   code to handle addition
                Just (Str "-") ->
                    code to handle subtraction
                ...
                _ ->
                    List.map evalAst list |> VList

As an example of how we might handle addition, we could say this:

Maybe.map2 (-) (getNumArg 1 list) (getNumArg 2 list) |> wrapVNum

The getNumArg function grabs a value form the given position in list and unwraps it, converting, say Num 5 into Just 5 . In this way the arguments are prepared for the standard (+) function, except that we have to apply Maybe.map2 because the values are now wrapped as Maybe values. Note that if the argument in position 1 were Str "haha!", then getNumArg 1 would return Nothing, as would Maybe.map2. If successful, the Maybe.map2 call produces Just someInteger. In accord with the type signature of evalAst, it must be converted to something of type Value, which is what wrapVNum does. You can find the code for all these details in Lisp.elm on GitHub.

I’ve kept the code for Lisp.elm as simple as possible, so the eval function defined there does very little. Slightly more capable is List2.elm, which features things like the below:

> eval "(if (> 4 2) bigger smaller)"
Just (VStr "bigger") : Maybe Lisp2.Value
> eval "(element 2 red green blue white black)"
Just (VStr "blue") : Maybe Lisp2.Value
> eval "(a b 1 2)"
Just (VList [VStr "a",VStr "b",VNum 1,VNum 2])

Comments

In a future post, I’ll discuss some other ways of writing a small Lisp in Elm. The present approach has the advantage of simplicity, but the disadvantage of inflexibility: the kinds of things that can be evaluated are hardcoded into the design.

I wish to thank Andrew Thompson for comments on a draft of this article.