Image for post
Image for post
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:

And here is eval:

Note that nonsense inputs produce the value Undefined:

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

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:

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

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 (|=):

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:

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

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:

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

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

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:

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.

Written by

jxxcarlson on elm slack, http://jxxcarlson.github.io

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store