Roundup of the final Little Schemer meeting

[Murray Steele]

Hi there,

The 13th and final meeting about Little Schemer happened last night with Chris Zetter, James Mead, Joel Chippindale, and me in attendance.  A reduced group for sure, but we were keen to get to the end.

We decided to follow the pattern of the previous meetings and go through Chapter 10 page by page up on the big screen discussing it as we went.

For those that haven’t read it, this chapter is the one that, as promised by Joel in his write up of meeting 10[1], has the reader implement a scheme interpreter in scheme.

We all found it quite refreshing that this chapter seemed to jettison much of the whimsical tone of the previous chapters, and even some of the hand-holding.  It’s certainly the most concrete of all the chapters and we wondered if when our scheme implementation got to the point where the tests for each chapter were just passing we should have skipped to the end and done this chapter rather than plodding through the intervening ones.  Alas, we can’t change the past so...

We spent a bit of time at the start baffled by the choice of data-structure for “entries” (what we’d call a hash): ((key1 key2 key3) (value1 value2 value3)) rather than what we considered more natural ((key1 value1) (key2 value2) (key3 value3)).  As we progressed it seemed to make more sense, but I don’t think we were hugely convinced that this structure made the most sense as both appear to be recursable.

We talked a bit about the approach taken in by lookup-in-entry[2]; instead of returning a magic “I didn’t find anything” value it takes a callback to execute when nothing is found.  It’s not an approach we use much as rubyists; we’d probably just raise an exception (hello Hash#fetch[3] - although we remembered that this can take a default value or block which is basically the same as the callback here).  Looking at lookup-in-table[4] which uses lookup-in-entry we realised that the callback in is actually how it recurses the data-structure and this seemed quite elegant, if unfamiliar.

Much of the implementation in this chapter simply aliases a function defined in a previous chapter with a new name.  E.g. (define make-entry build) to alias the build function for constructing pairs to ‘make-entry’ a function for making “entries”.  We talked a bit about how this was an interesting approach that we don’t really see much in ruby.  It felt like because everything is just a list and we only have a few actions for operating on them, it’s useful to rename those in a specific context so that the code reads more clearly.  We decided that as rubyists we’d not usually think of aliasing functions in this fashion, but there are parallels here with the idea of creating DSLs, something rubyists are very fond of.

We also talked about scope.  First we thought that in scheme we effectively have everything in a global scope - so if you define second as an alias for first then everyone has to deal with that.  But then we realised you could probably create scopes by defining things inside another list, which would put these definitions onto the “table” (the TLS name for what we’d call the environment) for evaluation of that list, but remove once we’d evaluated that list.  This discussion about scope was a bit wooly, without anyone who really knew what they were talking about, or any attempt to try and test it in a scheme repl, but we soldiered on.  We then considered how this might be a bit like refinements in ruby[5] and we digressed a bit talking about how refinements seemed interesting when announced, but actually seem a bit terrible now they’re available.

There was a brief moment of vindication for me in particular when the book said: “in the preface we talked about the typography, serif vs. sans-serif, well we hope you paid attention as it’s about to be really important” (I’m paraphrasing, I don’t have it in front of me).  There were lots of examples of what is the value of x vs. what is (value x) with x being the same bit of scheme, written in different typographic forms.  Also the what is (foo (bar)) vs. what is (baz q) where q is (qux) forms.  It turns out this was important and it felt like the book was preparing us for the idea of looking things up in environments.

As the chapter started getting into the details of evaluating scheme we started flipping between the book and our own implementation.  It was good to see that our implementation mirrored some of the book’s own.  We noticed that one key thing the book implementation doesn’t have to do compared to ours is convert a list of bytes into a data structure of lists and atoms.  We have to do this in our parser[6] and so we build an AST of List and Atom objects, but the book doesn’t.  It does however build an sort of AST by marking some bits of the list as primitive[7] or non-primitive[8] as a hint for how to handle it later in apply[9].  Something that our own implementation seems to have dealt with, albeit, less explicitly in our Evaluator[10].

We also talked about how the scheme code, through use of all the (define x y) aliases, was very readable compared to our own implementation where we have things like chaining of .car.cdr or arguments.first, etc.  We talked about how we could have defined more methods on our List or Atom objects to make it more reable, but that didn’t feel very elegant either.  We weren’t entirely sure what we’d do instead.

It was interesting that the book finishes by saying that define isn’t needed (so why the digression in Ch 9 about the Y combinator?) and then saying, but actually kinda is, please buy our next book!  The implementation provided doesn’t handle define, and, coincidentally, neither does ours.  Remembering earlier debates about whether to implement it or not we declared deciding not to a triumph of YAGNI!

We finished up by saying it might be a good final bit of homework to write a spec that sets up an environment with the book scheme implementation and then evaluate a few lines of scheme with it to see if our little scheme is scheme enough to evaluate the little scheme provided by the book.

And that, as they say, is that.

Onwards and upwards to whatever is next[11].

Muz

ps I didn’t take notes, so I may have forgotten or misrepresented a few discussions. I’m sure Chris, James, or Joel will chip in to keep it truthy.

[1]: https://groups.google.com/forum/#!topic/computationbook/fiLu2jDed60

[2]: https://github.com/pkrumins/the-little-schemer/blob/ee905df9ac2f13a2d6858be1a8247ccc4535ffbe/10-value-of-all-of-this.ss#L61-83

[3]: http://www.ruby-doc.org/core-2.1.3/Hash.html#method-i-fetch

[4]: https://github.com/pkrumins/the-little-schemer/blob/ee905df9ac2f13a2d6858be1a8247ccc4535ffbe/10-value-of-all-of-this.ss#L113-125

[5]: http://www.ruby-doc.org/core-2.1.3/doc/syntax/refinements_rdoc.html

[6]: https://github.com/tomstuart/little_scheme/blob/master/lib/scheme.treetop

[7]: https://github.com/pkrumins/the-little-schemer/blob/ee905df9ac2f13a2d6858be1a8247ccc4535ffbe/10-value-of-all-of-this.ss#L192-199

[8]: https://github.com/pkrumins/the-little-schemer/blob/ee905df9ac2f13a2d6858be1a8247ccc4535ffbe/10-value-of-all-of-this.ss#L225-228

[9]: https://github.com/pkrumins/the-little-schemer/blob/ee905df9ac2f13a2d6858be1a8247ccc4535ffbe/10-value-of-all-of-this.ss#L302-308

[10]: https://github.com/tomstuart/little_scheme/blob/master/lib/evaluator.rb

[11]: https://groups.google.com/forum/#!topic/london-computation-club/4ari5vK15Kc

[Joel Chippindale]

Looks great to me.

Thanks for writing this up,

J.

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.
To post to this group, send email to london-comp...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/CABUDGcp31Pw_Six%2B1%3DHcQ3eVfmq9q235%2BVMkwsvypLCQ%2B%3DhduA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.