Round up from meeting 12 of the Little Schemer book club

[Joel Chippindale]

Hi,

We had the 12th meeting of the Little Schemer book club on Mon 1st Sep. 5 of us were there and there was some trepidation (at least from me) that some of us have lost patience with the authors of the book.

We began by looking at the various implementations of `#curry` that we had written in Ruby (and the Rubinius implementation).

My solution [1] supported a much more restrictive version of `#curry` than Ruby has, in that the solution only allows you to call it multiple times with a single argument once curried, whereas Ruby allows you to call with as many arguments as you like. It also relies on string munging and eval which seemed less than optimal.

Chris Z. and Tom S.'s solutions [2][3] were much more similar and both explicitly collected arguments until enough had been provided before calling the original proc. @tomstuart had gone further and built some spec's [4] to reflect the ruby docs and had handled optional parameters. Here we noted that ruby overloaded `arity` to indicate the presence of optional parameters by making the `arity` negative in these cases i.e. an `Proc` with 2 required parameters and some optional ones will have an `arity` of `-3`.

Finally we looked at the Rubinius implementation [5] which was similar in essence to Chris Z. and Tom Stuart's. However it looked to us like there was a bug in it that meant that the curried version of a `Proc` with optional parameters would not work correctly when called. It seemed like the ruby spec [6] did not include a test for this. A potential homework would be for one of us to check that it is broken and if it is, raise issues/pull requests with the ruby spec and rubinius.

Then we got onto Chapter 9 "Again and again and again..."

This chapter introduces partial functions by giving an example of a `looking` function which does not return for some inputs.

Following this the chapter becomes increasingly obtuse (sigh) and it was hard for us to imagine what it might be like to read the book if you were unfamiliar with the concepts it introduced.

From our discussions we felt that the book introduced a`looking` function to give an example of 'unnatural recursion' i.e. recursions that do not necessarily reduce the inputs with each recursion (and therefore it is not clear whether they will complete for a particular input) 

Then it introduces an `align` function which reminded us how difficult it is for us to read scheme, but after some discussion we decided that it returned a 'right aligned' binary tree from the input binary tree (as represented by nested pairs in scheme. This was introduced n order to show that you can prove a 'unnaturally recursive' function is total by defining a non-negative function on it's arguments that always reduces in the recursion (in this case `weight`)

There was some discussion around the Ackerman function which is an example of a total computable function that is not naturally recursive (showing that although all naturally recursive functions are total the reverse is not true i.e. no every total computable function has a naturally recursive representation).

We skipped the book's explanation of the halting problem because this was something we felt we all understood and we were not confident the book would be illuminating.

We tried out best to make sense of the explanation given for how the Y combinator works however again the Little Schemer really didn't seem to be helping, although Tom S. gave a reasonable broad brush strokes explanation.

Chris Z. and Tom S. suggested watching Jim Weirich's talk "Y Not- Adventures in Functional Programming" [7] as a far more engaging and easier to follow explanation (and which Chris L. has since sent round and recommended too).

Chris L. suggested another 'homework' of instrumenting a scheme (or indeed) ruby implementation of the Y-combinator in order to demonstrate how it worked.

Having battled through to the end of Chapter 9 we thought we had well and truly done enough for the evening and all slipped away home.

Cheers,

J.

[1] https://gist.github.com/mocoso/aa9b8d85e6d5ac48dd6c

[2] https://github.com/zetter/currying-proc

[3] https://github.com/tomstuart/curry/compare/master...solution

[4] https://github.com/tomstuart/curry/blob/master/spec/curry_spec.rb

[5] https://github.com/rubinius/rubinius/blob/58d397733b6ec1ae003b296ba4ab27a65e8629dc/kernel/common/proc.rb#L78

[6] https://github.com/rubyspec/rubyspec/blob/master/core/proc/curry_spec.rb

[7] https://www.youtube.com/watch?v=FITJMJjASUs

[Jamie White]

Hi Guys

Really sorry to have missed this one. Sounds like it was exhausting but you covered a lot of interesting ground.

Goofy side note: I listened to Brendan Eich’s appearch on Javascript Jabber [1] and was tickled to discover that “Scheme in the browser” was Netscape’s original plan before JavaScript was conceived.

See you at the next one.

Jamie

[1] http://javascriptjabber.com/124-jsj-the-origin-of-javascript-with-brendan-eich/

--
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/CAAUHvmjPXvm44CvJkdygCqc2V5yD2WEHmWz%2BK3ZHmyznj%2BuWxQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.