The Little Schemer book club met for the second time last night, albeit without several people who'd planned to be there, leaving seven of us to continue from where we left off last time.
We began by discussing chapter 2 of The Little Schemer. Everyone was comfortable with the explanation of recursion, but again we found ourselves confused by the deliberate vagueness of the book's presentation, particularly the distinction between bold "keywords" (e.g. `define` and `cond`) and italic "primitive operations" (e.g. `car`, `cdr` and `cons`).
We speculated that the difference between these things is in the rules of evaluation: each "keyword" gets its own special case in the evaluation function (e.g. `define` treats its first argument as a variable name when it updates the environment; `cond` evaluates its arguments' conditions one at a time until it finds one that returns `#t`, leaving the others unevaluated), whereas "primitive operations" all fall within the same case where every argument gets evaluated before we even look at what the operation is.
So while the actual implementation of each "primitive operation" is in Ruby rather than Scheme, their evaluation is treated in the same way as any user-defined operation (e.g. `lat?` and `member?`), whereas each "keyword" gets its own custom evaluation rules.
There was more discussion of whether it was appropriate to try to build a Scheme interpreter by working through the book. Its style of teaching introduces important concepts early on (e.g. variables having values; `define`; `lambda`) which are easy to hand-wave away but perhaps tricky to implement, and the book doesn't tell us how to implement them. The general consensus was that we are being perverse in trying to build a Scheme interpreter in this way, because we have to invent our own interpretation of the book's ideas (e.g. what does "where l is `(a b c)`" mean? what does `(define ... (lambda ...))` in a box mean?) and then invent our own strategies for implementing them. We agreed that this sounded like fun.
I admitted that I'd made the chapter 2 tests pass by just adding more hard-coded cases to my evaluation function (`elsif op.name
== 'lat?' ...`) rather than actually implementing `define` and `lambda`. We had a few ideas about how it might be possible to implement them, either by storing Ruby procs in the environment (cf. https://github.com/jgwhite/little-schemer/blob/master/little_scheme.rb
) or by keeping lambdas represented as S-expressions and then writing a special evaluation rule for lambdas applied to arguments (e.g. `((lambda (x y) (+ x y)) 5 6)` evaluates to whatever `(+ x y)` evaluates to, where x is `5` and y is `6`). Ultimately we decided to park that discussion since we didn't yet have a working interpreter.
After the discussion we split into two groups to work on code:
* @thattommyhall et al finished the Treetop parser from last time (I don't think this got uploaded by itself)
* @floehopper et al finished the AST evaluator from last time: https://gist.github.com/floehopper/8548547/3b37345fd4fc39d5b2a4f228b1698e5650a64682
Once both pieces were working, we connected them together into a rudimentary Scheme interpreter: https://gist.github.com/zetter/8792095
. Everyone got very excited when it ran successfully for the first time.
At the moment our interpreter only supports `car` and `cdr`, but it gives us a working foundation upon which to build more sophisticated functionality. In principle we could spend the next meeting getting all of the tests for chapter 1 passing, and then devising a strategy for dealing with `define`/`lambda` so that we can start work on chapter 2's tests.
Another great meeting, thanks everyone. See you next time!