# 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 ASTparser =    oneOf [ lazy (\_ -> list), string, integer ]`

The`oneOf` 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 ASTlist =    (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 -> Valueeval 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 -> ValueevalAst 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])`