Round-up of the second Little Schemer book club meeting
67 views
Skip to first unread message
Tom Stuart
Feb 4, 2014, 5:47:57 AM2/4/14
to computa...@googlegroups.com
Hi,
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!
Cheers,
-Tom
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!
Cheers,
-Tom
Tom Hall
Feb 4, 2014, 6:17:55 AM2/4/14
to Tom Stuart, computa...@googlegroups.com
I am still rather excited, also - best minutes ever "Decided what we are doing is perverse, and that we liked it"
Tom
--
You received this message because you are subscribed to the Google Groups "Understanding Computation discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to computationbo...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Jamie White
Feb 4, 2014, 9:55:59 AM2/4/14
to Tom Hall, Tom Stuart, computa...@googlegroups.com
Sounds like a great meeting, really wish I could’ve made it. The implementation in the Gist is really nice.
Tom Hall
Feb 4, 2014, 10:12:40 AM2/4/14
to Jamie White, Tom Stuart, computa...@googlegroups.com
I am afraid I will miss the next two as I am learning to swim.
In the meantime I may try and create Tom's Perversely Minimal Lisp (tm)
Catch you all soon,
Tom
Tom Stuart
Feb 4, 2014, 6:52:34 PM2/4/14
to computa...@googlegroups.com
On Tuesday, February 4, 2014 10:47:57 AM UTC, Tom Stuart wrote:
we could spend the next meeting getting all of the tests for chapter 1 passing
In case anyone’s interested in doing this with my RSpec examples, I’ve merged our work-in-progress interpreter into the `master` branch of https://github.com/tomstuart/little_scheme (see attached commit graph). I've also cherry-picked the chapter 1 examples into `master` and written a few adapter classes to make the examples’ assumptions about the interpreter API match up with our actual implementation.
Right now, if you clone that repo and run `bundle exec rspec`, 32 out of the 64 examples from chapter 1 are passing. Not bad for the world’s noddiest Scheme interpreter.
This repo isn’t necessarily helpful, because translating the book’s examples into tests might be a fun/interesting exercise for us to do together, but since the examples were already sitting there I thought I’d wire everything up in case anyone wanted to get straight to the implementation without having to write any tests.
Cheers,
-Tom
Reply all
Reply to author
Forward
0 new messages