Just ‘let’ Me Be Already!

[Part 2 of the FScheme series ]  

Still working through Bill Hails’ awesome book. Adding to the FScheme interpreter from this previous post. Now we’ll add ‘let’. To do this we’re changing the evaluation model into an environment-passing one.

Environment Passing

So now the environment isn’t going to just be a single global map. It’s now going to be a list of maps. Each time a new scope is created, the environment will be extended. When looking up symbols, the whole chain is searched. We’ll add a couple of helper functions for this and the global environment will become an extension of empty (plus we’ll go ahead and add a mapping for our yet-to-be-defined ‘let’):

let extend env bindings = (Map.ofList bindings) :: env let
lookup env symbol =
    match List.tryPick (Map.tryFind symbol) env with
    | Some(e) –> e | None -> sprintf "No binding for '%s'." symbol |> failwith

and environment =
    extend [] [
        "*", Function(Multiply)
        "-", Function(Subtract)
        "if", Special(If)
        "let", Special(Let) ]

Then special forms change to take an environment (which is a Map<string, Expression> list):

type Expression =
    | Number of BigInteger
    | String of string
    | Symbol of string
    | List of Expression list
    | Function of (Expression list -> Expression)
    | Special of (Map<string, Expression> list -> Expression list -> Expression)

Then eval and apply change to thread the environment through. Also symbols need to be looked up with our helper and the REPL needs to thread in the global initially:

and eval env expression =
    match expression with
    | Expression.Number(_) as lit –> lit
    | Expression.String(_) as lit –> lit
    | Expression.Symbol(s) -> lookup env s
    | Expression.List(h :: t) –>
        match eval envh with
        | Function(f) -> apply envf t
        | Special(f) -> f envt
        | _ -> failwith "Malformed expression."
    | _ -> failwith "Malformed expression."

and apply envfn args = fn (List.map ( eval env) args)

let rep = List.ofSeq >> parse >> List.head >> ( eval environment) >> print

Finally, we need to continue this plumbing work through ‘If’ which needs to just pass it along to eval:

let rec If env= function
    | [condition; t; f] –>
        match eval envcondition with
        | List([]) | String("") -> eval envf // empty list or empty string is false
        | Number(n) when n = 0I -> eval envf // zero is false
        | _ -> eval envt // everything else is true
    | _ -> failwith "Malformed If."

Finally, ‘let’

Sheesh, finally we can implement ‘let’. We just map the bindings onto a new (extended) environment frame and eval the body within that:

and Let env = function
    | [List(bindings); body] – >
        let bind = function List([Symbol(s); e]) -> s, (eval env e) | _ -> failwith "Malformed 'let' binding."
        let env' = List.map bind bindings |> extend env
        eval env' body | _ -> failwith "Malformed Let."

Tests

Add a couple test cases:

    case "(let ((x 2)) x)" "2" // simple let
    case "(let ((a 00) (b 10) (c 20)) (if a b c))" "20" // conditional eval

Next>

Comments

• Anonymous
  August 12, 2011
  Great stuff. I must say I like your f# implementation over the perl one from Bill Hails! Much more clean without all the oop. It also doesn't help that his version doesn't use modern perl practices such Moose instead of traditional perl oop.