Scheme like language implemented in Elm

[akoppela]

Hey folks. I’ve beed having fun recently learning Scheme (and Lisps) and implemented very basic Scheme like interpreter in Elm. It’s environment-passing lambda calculus. It’s dynamically typed, with lexical scope and runtime exceptions So Elm is not safe anymore! Thought someone could enjoy it as I am. One can build everything with it. It’s Turing complete (though it was invented before Turing machine).

module Interpreter exposing (Env, Exp(..), Value(..), call, eval)

import Dict exposing (Dict)


type alias Env =
    Dict String Value


type Exp
    = Var String -- Variable
    | Lam String Exp -- Lambda
    | App Exp Exp -- Application


type Value
    = Int Int
    | Chr Char
    | Str String
    | Bln Bool
    | Cls String Exp Env -- Closure
    | Err String


eval : Exp -> Env -> Value
eval exp env =
    case exp of
        Var name ->
            Dict.get name env
                |> Maybe.withDefault (Err "Variable not found")

        Lam arg body ->
            Cls arg body env

        App rator rand ->
            call (eval rator env) (eval rand env)


call : Value -> Value -> Value
call fun x =
    case fun of
        Cls arg body env ->
            eval body (Dict.insert arg x env)

        _ ->
            Err "I can call only functions"

In a repo I started implementation of Core module as well with helper functions and Peano numbers, etc…

[alexkorban]

Another Scheme-related project: https://package.elm-lang.org/packages/bburdette/schelme/latest/

[akoppela]

Resources:
• Great video about scheme interpreter
• Great paper about scheme interpreter

[akoppela]

As an environment I’ve chosen Dict because it’s easy to extend and lookup items in Dict.

What can be done with this interpreter

---

Variable lookup

>  eval (Var "x") Dict.empty
Err ("Variable not found") : Value

Since environment is an empty Dict error is returned.

> eval (Var "x") (Dict.singleton "x" (Str "X"))
Str "X" : Value

When environment contains variable it’s value is returned.

---

Lambda functions

> eval (Lam "x" (Var "x")) Dict.empty
Cls "x" (Var "x") (Dict.fromList []) : Value

identity function. In Elm that would be \x -> x. When lambda is defined closure is created for it with current environment. So closure is a lambda with environment.

> eval (Lam "x" (Lam "y" (Var "x"))) Dict.empty
Cls "x" (Lam "y" (Var "x")) (Dict.fromList []) : Value

always function. In Elm that would be \x y -> x. Always return first argument ignoring second argument. Interesting that it’s also a true function. When working with conditions we want branching. In case of true we choose first branch, in case of false we choose second branch. Implement false yourself to see how it works.

---

Function application

> env = (Dict.singleton "z" (Str "Z value")) -- z = "Z value"
Dict.fromList [("z", ("Z value")] : Env -- "Z value" : String

> id = Lam "x" (Var "x") -- id = \x -> x
Lam "x" (Var "x") : Exp -- <function> : a -> a

> eval (App id (Var "z")) env -- id z
Str ("Z value") : Value -- "Z value" : String

Environment and identity function were extracted to env and id accordingly. Sure enough when we applied variable z to indentity function we got value for variable z back.

> env = (Dict.singleton "z" (Str "Z value")) -- z = "Z value"
Dict.fromList [("z", ("Z value")] : Env -- "Z value" : String

> true = Lam "x" (Lam "y" (Var "x")) -- true \x y -> x
Lam "x" (Lam "y" (Var "x")) : Exp -- <function> : a -> b -> a

> eval (App true (Var "z")) env -- true z
Cls "y" (Var "x") (Dict.fromList [("x",Str ("Z value")),("z",Str ("Z value"))]) : Value -- <function> : a -> String

> eval (App (App true (Var "z")) (Var "unknown")) env -- true z "unknown"
Str ("Z value") : Value -- "Z value" : String

Environment is the same, it contains only value for z variable. true function was extracted. Notice when we applied true function to one variable z we got back closure with extended environment. Because true is a function of two arguments we need to pass one more argument to fully apply it. Notice how environment was extended. It contains original value for z variable and also it contains now a value for x variable inside closure. The value for x variable equals to the value of z variable because we applied z variable to true function. That’s called lexical scoping. Environment was extended immutably only for that created closure. Outside of the closure environment is still the same. Also notice that it does not matter what second argument is. In our case it was not even defined in the environment. It’s just ignored.

[mfeineis]

There’s also a Make A Lisp implementation with Elm https://github.com/kanaka/mal/tree/master/impls/elm