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


Usually, when I do blog posts that are all about code, I write them bottom up’. I start talk­ing about the most prim­i­tive types and func­tions and build up from there to­ward higher ab­strac­tions. I think this is a pretty com­mon way of do­ing it.

For this se­ries I’m go­ing to try the op­po­site. I start with the code that cre­ates the REPL win­dow and move down from there to­ward the guts of the in­ter­preter. I hold the opin­ion that, if the code is writ­ten right, this should be ok. The nam­ing scheme and gen­eral struc­ture of it should al­low un­der­stand­ing it at dif­fer­ent lev­els.

Or at least I hope so.

Let’s start from the main func­tion. Depending on the num­ber of ar­gu­ments it ei­ther runs the REPL win­dow or ex­e­cutes what­ever is in the file passed in as the first ar­gu­ment us­ing the other ar­gu­ments as pa­ra­me­ters.

let main(args: string[]) =
    match Array.toList args with
    | [] -> runRepl ()
    | filename :: args -> runOne filename args

The lat­ter case is coded in the be­low func­tion. It first load all the prim­i­tive op­er­a­tors (i.e. +’, -’ etc…) and the stan­dard li­brary. The word load’ above is a lit­tle mis­lead­ing. In re­al­ity it adds them to the en­vi­ron­ment. It then pro­ceeds to add the ar­gu­ments that were passed on. As the last step, it eval­u­ates the load’ com­mand by us­ing the newly cre­ated en­vi­ron­ment, it trans­forms the re­turned to­ken to a string and prints it.

let runOne (filename : string) (args : list<string>) =
    let env = primitiveBindings ()
                |> loadStdLib
                |> bindVars [ "args", List (List.map String args) ]
    List [Atom "load"; String filename] |> eval env |> showVal |> printStr

Running the REPL win­dows is equally sim­ple. Load the prim­i­tive op­er­a­tors and the stan­dard li­brary, show a prompt and eval­u­ate the in­put un­til the in­put is Quit’.

let runRepl () =
    let env = primitiveBindings () |> loadStdLib
    until (fun s -> s = "Quit" || s = "quit") (fun () -> readPrompt "Lisp>>> ") (evalAndPrint env)

read­Prompt is pretty sim­ple:

let printStr (s: string) = Console.Write(s)
let readPrompt (s: string) = printStr s ; Console.ReadLine ()

EvalAndPrint is writ­ten as a chain of func­tions (lookup the >>’ op­er­a­tor in F#) and just eval­u­ate the string, trans­form the re­sult to a string, prints it and new­line it.

let newLine () = Console.WriteLine()
let evalAndPrint env = evalString env >> showVal >> printStr >> newLine

eval­String parses the string and eval­u­ates the ex­pres­sion. Note the ex­cep­tion man­age­ment. This is a re­sult of my de­ci­sion of throw­ing an ex­cep­tion every time some­thing goes wrong in­stead of us­ing a monad to pass the state around. I think it is pretty clear, but haskellers might dis­agre. This is one of the main dif­fer­ences from the Haskell ver­sion.

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

For the sake of com­plete­ness, here is un­til. Maybe there is a li­brary func­tion some­where that I could have used?

let rec until pred prompter evaluator =
    let result = prompter ()
    if not (pred result) then
        evaluator result
        until pred prompter evaluator

Back on the main flow of the code, load­St­dLib just loads the stan­dard file and re­turns the pop­u­lated en­vi­ron­ment.

let loadStdLib env =
    eval env (List [Atom "load"; String "stdlib.scm"]) |> ignore

prim­i­tive­Bind­ings cre­ates a new empty en­vi­ron­ment and adds a bunch of pairs (primitiveName, LispVal –> LispVal). LispVal is a rep­re­sen­ta­tion of a Scheme ex­pres­sion, so the sec­ond part of the tu­ple is sim­ply a re­duc­tion from one ex­pres­sion to an­other (hopefully sim­pler in some sense). We’ll talk more about LispVal in up­com­ing posts.

let primitiveBindings () =
    (nullEnv ()) |> bindVars [ for v, f in primitives -> v, PrimitiveFunc f ] 

There you have it. That’s the full im­ple­men­ta­tion for the REPL win­dow. Next post, we’ll look at LispEval and the eval­u­a­tor.