Round-up of the third Little Schemer book club meeting

[Tom Stuart]

Hi,

The Little Schemer book club met for the third time last night. Here’s roughly what happened.

Seven of us showed up, and we began by recapping the previous meeting for those who'd missed it. There was a general feeling that some of the discussion from last time had got ahead of the point we’d reached in the book — our collaboratively-built Scheme interpreter barely supported `car` and `cdr`, which meant that the more nuanced conversations (e.g. about how to implement `define` and `lambda`) lacked context.

We decided to work together to get the interpreter to fully support everything in chapter one, with the intention of revisiting the discussion of more complicated ideas once we were ready to actually implement them.

@floehopper cloned http://github.com/tomstuart/little_scheme onto his laptop and connected it to the projector, while the rest of us gathered round and shouted at him. Together we worked through the failing tests in book order:

* We made the parser support atoms containing non-alphanumeric characters (https://github.com/tomstuart/little_scheme/commit/10b85ef)

* We parked the uninteresting problem of how to parse things that aren’t single S-expressions (https://github.com/tomstuart/little_scheme/commit/8b00a2d) and will return to it if/when it becomes relevant

* We added support for evaluating an atom that isn’t inside a list (https://github.com/tomstuart/little_scheme/compare/8b00a2d...ee82005)

* We made `car` and `cdr` raise an exception when applied to an empty list (https://github.com/tomstuart/little_scheme/compare/12f16d6...51cc6bd), which is our way of reporting “no answer"

* We implemented `cons` on atoms and lists (https://github.com/tomstuart/little_scheme/compare/51cc6bd...de19f86)

* We added hacky support for evaluating `cons` (https://github.com/tomstuart/little_scheme/commit/a9016fa), although none of us were happy with the special-casing required to support an operation with two arguments

* Through a series of satisfying refactorings, we generalised list evaluation to support operations with any number of arguments (https://github.com/tomstuart/little_scheme/compare/cc8142c...40ad8f0), producing nice code except for a `#send` of a protected method

* We eliminated the nasty `#send` by pushing each case of the `#evaluate` method down onto the `Atom` and `List` classes (https://github.com/tomstuart/little_scheme/commit/9010aae), which had the added bonus of replacing a conditional with polymorphism

* We implemented `null?` on lists (https://github.com/tomstuart/little_scheme/compare/9010aae...0247aac), deciding that the `List#null?` predicate should return a Scheme boolean (a `#t` or `#f` atom) instead of a Ruby boolean

* We implemented `quote` (https://github.com/tomstuart/little_scheme/commit/df4b4dd), gaving us our first encounter with what Little Schemer calls a “keyword” (special-case behaviour inside `List#evaluate`) versus a “primitive operation” (instance method on `Atom` or `List`).

After doing all this, 52 out of the 64 examples were passing; the remaining examples concern `atom?` and `eq?`, which we didn’t have time to implement. Presumably these will be easy to get working at the next meeting, after which we can move on to implementing chapter two.

I enjoyed the meeting a lot. Although we were still working through the absolute basics of the book, it gave us ample opportunity to think about and discuss what we were trying to do in terms of our implementation; hopefully that’ll provide a firm practical grounding for the harder material in future chapters. Thanks everyone!

Cheers,
-Tom

[Murray Steele]

Oh, this sounds like it would have been really good.  Sorry to have missed it.  Thanks, as ever, for the great write up Tom!

Muz

On 25 February 2014 15:53, Tom Stuart <t...@codon.com> wrote:

Hi,

The Little Schemer book club met for the third time last night. Here's roughly what happened.

Seven of us showed up, and we began by recapping the previous meeting for those who'd missed it. There was a general feeling that some of the discussion from last time had got ahead of the point we'd reached in the book -- our collaboratively-built Scheme interpreter barely supported `car` and `cdr`, which meant that the more nuanced conversations (e.g. about how to implement `define` and `lambda`) lacked context.

--
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.

[Joel Chippindale]

One of the decisions we made during the third meeting was to implement support for `quote` in the evaluation phase rather than in the parsing phase.

I thought it might be interesting to explore an alternative implementation in the parser which you can see here https://github.com/tomstuart/little_scheme/pull/3

J.

[Tom Stuart]

On 16 Mar 2014, at 09:05, Joel Chippindale <jo...@joelchippindale.com> wrote:
> I thought it might be interesting to explore an alternative implementation in the parser which you can see here https://github.com/tomstuart/little_scheme/pull/3

This is cool! For me it raises two questions:

1. The footnote on page 9 says that we can write () instead of (quote ()) in Lisp, but in Scheme the abbreviation is '() (i.e. with an apostrophe). So this change makes our interpreter evaluate () to (), whereas the real Scheme interpreter I use (Chicken Scheme) treats evaluating () as an error. Does that matter?

2. By skipping ahead in the book (i.e. cheating), I can see that we'll need to use quote with other arguments (e.g. see page 97). Will we be able to do this in the parser too once we get to that part of the book, or will we find ourselves in a dead end?

It'd be fun to discuss this tomorrow.

Cheers,
-Tom

[Joel Chippindale]

On 16 March 2014 12:08, Tom Stuart <t...@codon.com> wrote:

On 16 Mar 2014, at 09:05, Joel Chippindale <jo...@joelchippindale.com> wrote:
> I thought it might be interesting to explore an alternative implementation in the parser which you can see here https://github.com/tomstuart/little_scheme/pull/3

This is cool! For me it raises two questions:

1. The footnote on page 9 says that we can write () instead of (quote ()) in Lisp, but in Scheme the abbreviation is '() (i.e. with an apostrophe). So this change makes our interpreter evaluate () to (), whereas the real Scheme interpreter I use (Chicken Scheme) treats evaluating () as an error. Does that matter?

It certainly makes it non-standard. Having barely used scheme to write any programs (I don't think I've done more than work on Chapter 1 of SICP) I don't feel I have enough context to tell whether it matters.

2. By skipping ahead in the book (i.e. cheating), I can see that we'll need to use quote with other arguments (e.g. see page 97). Will we be able to do this in the parser too once we get to that part of the book, or will we find ourselves in a dead end?

The first introduction to quote in the Little Schemer seems to be a bit of an edge case. I had imagined that we new class to express quoted elements in the abstract syntax tree, perhaps one to pick up once we get more examples.

The trigger for starting this exploration was thatI don't have a good sense of what trade offs are being made when deciding how complex to make the parser (vs. the evaluation).

It'd be fun to discuss this tomorrow.

Sounds good,

J.