Round-up of the eighth Little Schemer book club meeting

[Tom Stuart]

Hi,

We had the eighth meeting of the Little Schemer book club last week. I think there were seven of us this time.

In the previous meeting we began making progress on numbers; this time we pretty much got stuck straight into continuing that work.

With @chrislowis driving, we made it to the end of chapter 4:

* We fixed up List#evaluate to raise an exception when environment lookup fails (https://github.com/tomstuart/little_scheme/commit/a92fc83) so that failing examples tell us the problematic identifier instead of just complaining about `nil` somewhere else

* We then made the same fix to identical code in Atom#evaluate (https://github.com/tomstuart/little_scheme/commit/de0ced4), which gave us the idea of removing this duplication by just calling Atom#evaluate from List#evaluate so that environment lookup only happens in one place

* We implemented `zero?` (https://github.com/tomstuart/little_scheme/commit/fc43cce)

* We eliminated duplication in the Atom class by extracting an Atom#integer method and using it in Atom#add1, #sub1 and #zero (https://github.com/tomstuart/little_scheme/commit/8a1f388)

* We eliminated more duplication by extracting an Atom.from_boolean class method to convert Ruby `true` and `false` into Atom::TRUE and Atom::FALSE (https://github.com/tomstuart/little_scheme/commit/9d15da7)

* We fixed the be_a_tup matcher (https://github.com/tomstuart/little_scheme/commit/4cfd35d), which I overlooked when removing the test adapters

* We made Atom#number? return Atom::TRUE/Atom::FALSE instead of Ruby `true`/`false` (https://github.com/tomstuart/little_scheme/commit/c134610)) in anticipation of implementing `number?`…

* …and then we implemented `number?` (https://github.com/tomstuart/little_scheme/commit/9e94612)

* We finished by implementing `and` (https://github.com/tomstuart/little_scheme/commit/6ad17bb), which made the rest of the chapter 4 tests pass

As a final exercise, we removed the definition of `rempick?` (https://github.com/tomstuart/little_scheme/blob/master/spec/04_numbers_games_spec.rb#L186) from the chapter 4 examples and successfully rewrote it from scratch.

While we were doing all this work, we noted two problems that we’d like to address before moving on:

1. It’s becoming increasingly difficult to keep track of which methods on Atom and List return Ruby booleans and which ones return Atom::TRUE and Atom::FALSE. The consensus seemed to be that it would make sense for all of these methods to just return Ruby booleans (https://github.com/tomstuart/little_scheme/issues/10) so that we don't have to think about it any more

2. It's difficult for us to write nontrivial function definitions in the examples because our parser is intolerant of extra whitespace. It would improve the clarity of the specs if we could include arbitrary whitespace (i.e. newlines and indentation) in our example programs (https://github.com/tomstuart/little_scheme/issues/11)

A few people threatened to attack one or both of these issues as “homework” before the next meeting.

So now we've finished chapter 4, and next time we'll be able to dive into chapter 5 if we want to, or we could take a breather and look for some more refactoring opportunities before we continue through the book. As Joel already announced, the next meeting’s on the 23rd of June (http://lanyrd.com/2014/the-little-schemer-book-club-meeting-9/) — hope to see you there!

Cheers,
-Tom

[James Adam]

Hello folks!

I have spent the weekend playing catchup and have implemented my own Little Scheme which passes everything in the examples for the first three chapters. Exciting times!

I’ve tried not to look too much at what’s already in the lib directory but I suspect that we’ve probably come up with a few similar ideas. Somewhat notably, I’ve used Parslet rather than Treetop to build the parser and evaluator. This has meant doing a bit of work to match the API expected by the specs (there’s no #to_ast method built in, for example, and you don’t get an evaluator quite for free, like you do with Treetop).

One other thing I’ve noticed is that my version seems to be considerably slower than the existing one. Running the examples for chapter three takes about 0.3 seconds on my machine again the mainline scheme implementation, but my version takes 1.4, almost 5 times slower! It would be interesting to figure out why, although I don’t want to look too closely at the existing version, mainly out of a perverse desire not to influence my approach (i.e. steal your good ideas).

Anyway, just thought I’d report in from afar. Hope you’re all doing well :)


— James

On Thursday, 12 June 2014 at 09:37, Tom Stuart wrote:

> Hi,
>
> We had the eighth meeting of the Little Schemer book club last week. I think there were seven of us this time.
>
> In the previous meeting we began making progress on numbers; this time we pretty much got stuck straight into continuing that work.
>
> With @chrislowis driving, we made it to the end of chapter 4:
>
> * We fixed up List#evaluate to raise an exception when environment lookup fails (https://github.com/tomstuart/little_scheme/commit/a92fc83) so that failing examples tell us the problematic identifier instead of just complaining about `nil` somewhere else
>
> * We then made the same fix to identical code in Atom#evaluate (https://github.com/tomstuart/little_scheme/commit/de0ced4), which gave us the idea of removing this duplication by just calling Atom#evaluate from List#evaluate so that environment lookup only happens in one place
>
> * We implemented `zero?` (https://github.com/tomstuart/little_scheme/commit/fc43cce)
>
> * We eliminated duplication in the Atom class by extracting an Atom#integer method and using it in Atom#add1, #sub1 and #zero (https://github.com/tomstuart/little_scheme/commit/8a1f388)
>
> * We eliminated more duplication by extracting an Atom.from_boolean class method to convert Ruby `true` and `false` into Atom::TRUE and Atom::FALSE (https://github.com/tomstuart/little_scheme/commit/9d15da7)
>
> * We fixed the be_a_tup matcher (https://github.com/tomstuart/little_scheme/commit/4cfd35d), which I overlooked when removing the test adapters
>

> * We made Atom#number? return Atom::TRUE/Atom::FALSE instead of Ruby `true`/`false` (https://github.com/tomstuart/little_scheme/commit/c134610)) in anticipation of implementing `number?`...
>
> * ...and then we implemented `number?` (https://github.com/tomstuart/little_scheme/commit/9e94612)

>
> * We finished by implementing `and` (https://github.com/tomstuart/little_scheme/commit/6ad17bb), which made the rest of the chapter 4 tests pass
>
> As a final exercise, we removed the definition of `rempick?` (https://github.com/tomstuart/little_scheme/blob/master/spec/04_numbers_games_spec.rb#L186) from the chapter 4 examples and successfully rewrote it from scratch.
>
> While we were doing all this work, we noted two problems that we'd like to address before moving on:
>
> 1. It's becoming increasingly difficult to keep track of which methods on Atom and List return Ruby booleans and which ones return Atom::TRUE and Atom::FALSE. The consensus seemed to be that it would make sense for all of these methods to just return Ruby booleans (https://github.com/tomstuart/little_scheme/issues/10) so that we don't have to think about it any more
>
> 2. It's difficult for us to write nontrivial function definitions in the examples because our parser is intolerant of extra whitespace. It would improve the clarity of the specs if we could include arbitrary whitespace (i.e. newlines and indentation) in our example programs (https://github.com/tomstuart/little_scheme/issues/11)
>
> A few people threatened to attack one or both of these issues as "homework" before the next meeting.
>

> So now we've finished chapter 4, and next time we'll be able to dive into chapter 5 if we want to, or we could take a breather and look for some more refactoring opportunities before we continue through the book. As Joel already announced, the next meeting's on the 23rd of June (http://lanyrd.com/2014/the-little-schemer-book-club-meeting-9/) -- hope to see you there!
>
> Cheers,
> -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 (mailto:computationbo...@googlegroups.com).
> For more options, visit https://groups.google.com/d/optout.

[Tom Stuart]

Hi James,

On 16 Jun 2014, at 05:40, James Adam <james...@gmail.com> wrote:
> I have spent the weekend playing catchup and have implemented my own Little Scheme which passes everything in the examples for the first three chapters. Exciting times!

This is great to hear! Congratulations on getting so far so quickly — it took us months to finish chapter three.

Is the code online anywhere or are you keeping it private for now? No worries if you're not ready to share it, but if you are, I'm sure some of us would be interested in seeing the difference between Treetop and Parslet parsers, and maybe someone would be able to get to the bottom of the performance difference while protecting you from spoilers.

Cheers,
-Tom

[James Adam]

I’ve pushed it here: https://github.com/lazyatom/little_scheme/tree/jga (on a branch so I can still pull/rebase etc).

The interesting parts should all be in lib; the changes I’ve made to the spec pull out some (but probably not all) of the assumptions the specs make about implementation (i.e. that the object returned by `evaluate(‘(a b c)’)` will have a method called `car`) into one place, so I can do a bit of (probably pointless) avoidance of having to implement those methods.

The actual parser is here: https://github.com/lazyatom/little_scheme/blob/jga/lib/little_scheme/parser.rb#L29 (https://github.com/lazyatom/little_scheme/blob/jga/lib/little_scheme/parser.rb#L21)

The rules take on a slightly different form than Treetop, and the output of the parser is just a tree (a Hash) of matched rules:

irb> LittleScheme::Parser.new.parse("((this is) fun)")
=> #<LittleScheme::ParseResult:0x007fabe50b9198 @tree={:list=>[{:list=>[{:atom=>"this"@2}, {:atom=>"is"@7}]}, {:atom=>"fun"@11}]}>


Parslet separates creating of objects from the parsing of that tree, so to get the `to_ast` method the specs expect, I need to implement the transformer: https://github.com/lazyatom/little_scheme/blob/jga/lib/little_scheme/parser.rb#L21

This takes the tree and returns actual objects instead of Parslet ‘slices’. The finally bit of hoop jumping is the `ParseResult` object, which actually implements the `to_ast` method by ‘transforming’ the ‘parsed’ data.

In the `Evaluator`, I’ve basically got a class for almost all of the operations, defining what happens when they are ‘applied’ (I am pretty sure the method name `apply` was subconsciously taken from the mainline implementation in the glances I did make early on). There’s probably some duplication in there to remove, and the fact that most arguments get ‘evaluated’ within the operation ‘apply’ method might be a little weird.

The weirdest one is `Quote`, but I am trusting that we haven’t actually seen (up to Chapter 3, at least) what that operation is really for, and so its implementation is really the minimum required to pass the specs.

The `Lambda::Compiled` class should probably be pulled out into something that’s a peer with `Atom` and `List`; there’s probably a pointer there towards `Lambda::Compiled` actually being the `Lambda`, and then what I have currently as the `Lambda` class being something more like a `LambdaKeyword` (again, I vaguely recall from glances that you folks have a `Keyword` class in the evaluator that’s probably doing this kind of work). I’m also not fully convinced that it wouldn’t be a bit simpler to have the parser itself handle these keywords and build the `Lambda` and `Cond` objects as part of the transformation to an AST, rather than using the environmental lookup to effectively treat “lambda” (or any of the others) as an Atom that magically returns some non-scheme object stashed into the environment at boot time. The environment at the moment contains a mixture of Scheme-ish objects (Lists and Atoms) and non-Scheme-ish ones (Lambdas, Conds, Ors, Cdrs, Cars, IsNulls, etc). I realise writing this that this segregation also describes objects that have an `evaluate` method, and objects that have an `apply` one. I don’t know if that’s interesting or not, or even if the distinction is useful.

What I’m very interested in are whether or not these are choices that you’ve already come up against and whether or not you feel like any insights have led you to feel like some choices are definitely “better” than others. I’m also particularly interested in the “A-ha!” moment that Tom describes here (http://codon.com/i-have-no-idea-what-im-doing#refactoring-toward-deeper-insight). Has the implementation in the mainline followed the same patterns as Tom’s? And if so, have you reached that refactoring yet? Would it be a spoiler to answer that question?

— James

On Monday, 16 June 2014 at 06:03, Tom Stuart wrote:

> Hi James,
>