Write Yourself a Scheme in 48 Hours in F# – Part VII

Let’s talk about the en­vi­ron­ment now.  This is the part of the in­ter­preter that I like the least. It is a global vari­able and it con­tains a list of  (string, LispVal) where the LispVal is mu­ta­ble.

type Env = (string * LispVal ref) list ref

This is pretty bad. First of all, it im­me­di­ately cuts off any op­tion of run­ning in­ter­preters in dif­fer­ent threads. Moreover, it makes a lot of func­tions in the eval­u­a­tor to have side ef­fects. That makes it much harder to rea­son about them.

In a world where I am pro­vided with in­fi­nite time and en­ergy, I would change it. In this world, I won’t. If you try your hand at do­ing it, make sure that you pass all the test­cases be­fore de­clar­ing vic­tory. The scope rules of Scheme are not all that ob­vi­ous. A code re­viewer called them the Italian scop­ing rules be­cause he thought I got them wrong …

In any case, there is­n’t much to the sym­bol table man­age­ment.  You can cre­ate an empty one:

let nullEnv (): Env = ref List.empty

Check if a vari­able is bound:

let keyEq name (k, _) = name = k
let isBound var (env: Env) = !env |> List.exists (keyEq var)

Get a vari­able out:

let getVar var (env: Env) =
    let result = !env |> List.tryFind (keyEq var)
    match result with
    | None -> throw (UnboundVar("Getting an unbound variable: " , var))
    | Some(_, r) -> !r

Set the value of an ex­ist­ing vari­able:

let setVar var value (env:Env) =
    let result = !env |> List.tryFind (keyEq var)
    match result with
    | Some(_, v) -> v := value ; value
    | None -> throw (UnboundVar("Setting an unbound variable: " , var))

Or de­fine a new vari­able in the en­vi­ron­ment. Note that if the vari­able al­ready ex­ist, its value gets set.

let define (env:Env) var value =
    let result = !env |> List.tryFind (keyEq var)
    match result with
    | Some(_, v) -> v := value ; value
    | None ->
        env := [var, ref value] @ !env; value

You can also bind a list of (string, LispVal) to the environment by prepending it to the existing ones:

let bindVars bindings (env:Env) =
   ref ((bindings |> List.map (fun (n, v) -> n , ref v)) @ !env)

Once you ac­cept the evil of the global mu­ta­ble vari­able scheme, these func­tions are easy enough.

The only piece left is er­ror man­age­ment. This is where my im­ple­men­ta­tion dif­fers from the Haskell ver­sion the most. In essence, I throw ex­cep­tion and catch them to re­port er­rors, while the Haskell ver­sion uses a monad to prop­a­gate the er­ror in­for­ma­tion.

I have a LispError that rep­re­sents every­thing that can go wrong:

type LispError =
    | NumArgs of int * LispVal list
    | TypeMismatch of string * LispVal
    | ParseError of string * FParsec.Error.ParserError
    | BadSpecialForm of string * LispVal
    | NotFunction of string * string
    | UnboundVar of string * string
    | Default of string
    | IOError of string

I wrap it in an ex­cep­tion:

exception LispException of LispError

This is what I throw in var­i­ous places in the code.

let throw le = raise (LispException(le))

I then catch it at the outer layer:

let evalString env expr =
    try
        expr |> readExpr |> eval env
    with
    | LispException(error) -> String (showError error)

And dis­play the er­ror by us­ing the be­low func­tion:

let showError = function
    | NumArgs(expected, found) -> "Expected " + expected.ToString() + " args; found values " + unwordsList found
    | TypeMismatch(expected, found) -> "Invalid type: expected " + expected + ", found " + showVal found
    | ParseError(msg, _) -> "Parse Errror" + msg
    | BadSpecialForm(message, form) -> message + showVal form
    | NotFunction(message, func) -> message + func
    | UnboundVar(message, varName) -> message + varName
    | Default(message) -> message
    | IOError(message) -> message

And that’s all there is to it. I hope you guys and gals en­joyed this seven part ex­trav­a­gance. Cheers.

Tags

• FSHARP
• LAMBDA EXPRESSIONS
• PARSING