A Typed Lisp in Elm
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.