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,
eval. Here is how the parser works:
> parse "(+ 1 2)"
Just (LIST [Str "+",Num 1,Num 2])
: Maybe AST
And here is
> eval "(+ 1 2)"
VNum 3 : Value
Note that nonsense inputs produce the value
> 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):
= 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
oneOf [ lazy (\_ -> list), string, integer ]
oneOf combinator chooses among the alternative parsers,
integer : one parser for each part of the definition of the AST type. The
lazy phrase is needed for recursion to work.
list parser is defined this way, out of the sequencing combinators
list : Parser AST
|. symbol "("
|= many parser
|. symbol ")"
|> 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
Value type enumerates the kind of values that
eval can produce:
= VStr String
| VNum Int
| VList (List Value)
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.
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 ->
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
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])
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.