Here's a quick summary of what happened at Monday's inaugural meeting of the Little Schemer book club, which was formed to continue the momentum of the Understanding Computation book club.
Roughly 20 people showed up, and we began by discussing chapter 1 of The Little Schemer. A few people said they'd found the book's style difficult to understand because of its technical vagueness, although it wasn't clear whether this was the majority view. There was some confusion about what programming language (if any) is actually being described, given the footnotes containing disclaimers and real-world syntax for users of Lisp and Scheme. However, there was general enthusiasm for the challenge/response format of the book, as well as for the idea of us trying to build a Scheme interpreter in Ruby based on the "tests" it contains.
We then talked a bit about how the Scheme language separates cleanly into "brackety notation for hierarchical data structures" and "rules for evaluating hierarchical data structures", and discussed how we could collectively make practical progress towards building an interpreter.
Then, because there were so many people in the room, we split into four independent groups to build stuff:
* @thattommyhall et al partially implemented a Scheme parser using Treetop: https://github.com/thattommyhall/littleT-J
* @threedaymonk et al implemented a recursive descent parser, along with a Graphviz visusaliser for the resulting abstract syntax trees: https://gist.github.com/threedaymonk/8528281
* @bishboria et al implemented a recursive descent parser too: https://gist.github.com/bishboria/8544144
* @chrislowis et al partially implemented an AST evaluator: https://gist.github.com/chrislo/8543385
As a result, we now almost have the pieces of a Scheme interpreter that can handle some of chapter 1 (syntax, `car`, `cdr`). We just need to polish those pieces and connect them together.
Here are some ideas for self-contained things that anyone could work on between now and the next meeting if they were sufficiently interested:
* Make the Treetop parser build an abstract syntax tree. The grammar's rules (https://github.com/thattommyhall/littleT-J/blob/master/scheme.treetop
) are correct, but right now the parser generates a concrete syntax tree which contains too much irrelevant information. The trick is to put an inline method definition (see http://treetop.rubyforge.org/semantic_interpretation.html
) on the `list` and `atom` rules so that we can call some method (e.g. `to_ast`) on the root node of the concrete syntax tree to convert it into an abstract one. There's an example of this on pages 58-62 of Understanding Computation, which you can download from http://computationbook.com/sample
* Disregarding the visualisation code, the recursive descent parser from @threedaymonk's group looks longer and more complicated than the one from @bishboria's group. Can it be made simpler? (I don't know.)
* Wrap up the top-level parsing methods from @bishboria's group in a nice Parser class so that the state can be stored in an instance variable instead of the $EXPR global.
* Make the evaluator from @chrislowis's group pass its tests. They began to change the representation of S-expressions (from `[:cdr, :l]` to `List.new(Atom.new(:cdr), Atom.new(:l))`) but ran out of time. Is the #evaluate function correct, and can it be improved? (FWIW, I don't believe that `(car (a b c))` is meant to evaluate to `a`.)
* The parser from @threedaymonk's group supports the idea of parsing a _program_, i.e. a whitespace-separated sequence of S-expressions. Add this feature to one or both of the other parsers.
* Once the evaluator is working, combine it with one of the parsers to build a working interpreter, and get it to pass some tests adapted from the book. If you don't want to spend time transcribing tests, @jgwhite has already put some minitest tests online at https://github.com/jgwhite/little-schemer/blob/master/little_scheme_test.rb
, and I've put some RSpec examples at https://github.com/tomstuart/little_scheme/blob/chapter-one/spec/01_toys_spec.rb
Does anyone else have any ideas for fun stuff to try?
I really enjoyed the meeting and was incredibly impressed by the level of enthusiasm and the amount of progress that got made in such a relatively short time. Thanks everyone. Looking forward to the next one!