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 con­stant in Scheme. This is prob­a­bly the worst de­f­i­n­i­tion ever given for it. Please read about it in your lit­tle schemer book.
• List: is the main Scheme type. It rep­re­sents a list of ex­pres­sions.
• DottedList: this is the bizarre Scheme way to pass op­tional pa­ra­me­ters
• Number: is a num­ber 🙂 You will dis­cover which kind of num­ber when we talk about the parser
• String : is a string
• Bool: #t, #f
• PrimitiveFunc: is the rep­re­sen­ta­tion for the prim­i­tive op­er­a­tors/​func­tions that are burned into the in­ter­preter. It is just a func­tion that takes a list of LispVal and re­turns a LispVal
• Func: is a user de­fined func­tion. Notice that the body of it is sim­ply a list of LispVal. This is why LISP is so pow­er­ful. Also no­tice that a clo­sure gets passed to it for the ‘captured’ vari­ables.
• Port: is a slightly goofy rep­re­sen­ta­tion of an in/​out stream
• Anything else (i.e. macros) is not sup­ported, 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 eval­u­a­tor
• The parser
• The sym­bol table
• Error han­dling

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.