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

Very of­ten my code ends up hav­ing the fol­low­ing form: parse an in­put to cre­ate an in­ter­me­di­ate data struc­ture and eval­u­ate the struc­ture to pro­duce an out­put. Strangely, many years ago, when my code was ob­ject ori­ented, that was­n’t the case. Or at least I was­n’t ex­plic­itly aware of it.

When you write an in­ter­preter or a com­piler, things al­ways work out like that, but I see the same pat­tern in al­most every­thing I pro­duce: from fi­nan­cial back­test­ing to chart li­braries. Sometimes when, out of lazi­ness or stu­pid­ity, I forego the in­ter­me­di­ate struc­ture, I end up in the end hav­ing to retro­fit it in. Simply pro­cess­ing in­put and gen­er­at­ing out­put at the same time rarely cuts it. But it is tempt­ing be­cause you get go­ing pretty fast and I’m tricked into it oc­ca­sion­ally.

Hence the first thing that I find my­self rea­son­ing about is of­ten the par­tic­u­lar form of such in­ter­me­di­ate struc­ture. In this case it looks like the fol­low­ing:

type Env = (string * LispVal ref) list ref
and FuncRecord = { parms: string list; varargs: string option; body: LispVal list; closure: Env}
and LispVal =
    | Atom of string
    | List of LispVal list
    | DottedList of LispVal list * LispVal
    | Number of int
    | String of string
    | Bool of bool
    | PrimitiveFunc of (LispVal list -> LispVal)
    | Func of FuncRecord
    | Port of System.IO.FileStream

This LispVal struc­ture has one con­struc­tor for each kind of ex­pres­sion (production) that is al­lowed in Scheme. Or at least that ones I sup­port …

It is im­por­tant that each one stores all the in­for­ma­tion that is nec­es­sary for the eval­u­a­tor to eval­u­ate the ex­pres­sion. No more, no less. Here is a brief de­scrip­tion:

• Atom: it is a kind of a constant in Scheme. This is probably the worst definition ever given for it. Please read about it in your little schemer book.
• List: is the main Scheme type. It represents a list of expressions.
• DottedList: this is the bizarre Scheme way to pass optional parameters
• Number: is a number 🙂 You will discover which kind of number when we talk about the parser
• String : is a string
• Bool: #t, #f
• PrimitiveFunc: is the representation for the primitive operators/functions that are burned into the interpreter. It is just a function that takes a list of LispVal and returns a LispVal
• Func: is a user defined function. Notice that the body of it is simply a list of LispVal. This is why LISP is so powerful. Also notice that a closure gets passed to it for the ‘captured’ variables.
• Port: is a slightly goofy representation of an in/out stream
• Anything else (i.e. macros) is not supported, but this would be the first piece to change if they were.

The only re­main­ing code to ad­dress is:

type Env = (string * LispVal ref) list ref

This is the sym­bol table and it is ugly. It is not mul­ti­thread safe ei­ther. But it works and it is close enough to the Haskell ver­sion so I de­cided to re­tain it. A proper code re­view would ‘strongly sug­gest’ rewrit­ing the code to pass it around to each func­tion in­stead of us­ing ‘ref’ or us­ing the state monad en­cap­su­lated in a com­pu­ta­tion ex­pres­sion. Any of these so­lu­tions is left as an ex­er­cise to the reader (use the test­cases to val­i­date that you get it right).

We could go in many dif­fer­ent di­rec­tion from here. We could talk about:

• The evaluator
• The parser
• The symbol table
• Error handling

To keep with the top — down ap­proach I’ve been es­pous­ing. I’ll prob­a­bly talk about the eval­u­a­tor next.

Tags

• FSHARP
• LAMBDA EXPRESSIONS
• PARSING

4 Comments

Comments

Youssef

2012-05-10T09:34:13Z

hello Luca,
I did not know how to reach you by mail so I post a com­ment here.
I be­came re­ally fan of f# since I saw your talk so thanks for that.
We are try­ing to build up some map re­duce large frame­work based on agents but I can not find any­where how to down­load the la­gent frame­work you wrote back in your mi­crosoft life.
Can you please let me know where I can find this ?
Thanks,
Youssef Allaoui

lucabol

2012-05-10T16:50:32Z

Here: http://​code.msdn.mi­crosoft…. , you might also want to read the blog posts about it.

chris

2012-05-25T06:23:14Z

Luca, Does the link ac­tu­ally work for you? This is what I see:
This item is not yet pub­lished.
If you are the owner of this pro­ject, please sign in with the ap­pro­pri­ate ac­count.

lucabol

2012-05-25T21:23:52Z

I be­lieve I pressed the but­ton now. Try the link.