This post is fairly short, as much of my attention for chapter 9 was spent on trying to just understand the Y-Combinator material in Chapter 9. My YouTube video has lots of content on this point.
Some stuff I looked at while making my video and writing this post:
Selected Portions of Dialogues
I decided to refer to these as dialogues since the book doesn’t really have exercises per se.
looking & keep-looking
My tentative initial guess about how all this works is that the procedures involved use the numbers that appear as the elements of the list to figure out which elements of the lat to check as being possible matches for a.
Ok I think I figured it out.
looking first checks the initial element of the list. If that element is a match for a.
looking returns true. If it’s a word that’s not a match for a,
looking returns false. If it’s a number, looking uses that number and then checks the element of the list that corresponds to that number (starting from 1), and then runs the same checks.
At this point, I tried writing
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
(lambda (a sel lat)
((equal? a sel) #t)
(keep-looking a (pick sel lat) lat))
It seems to work 🙂
After looking at their version, I realized mine was overly complicated:
Their structure is basically: if you know it’s a number, continue on with a recursive call, but if you know it’s not, just check whether a is equal to sorn (their sel). That else is gonna be true or false, so it covers both cases.
A pair is a list with only two s-expressions.
needed the book’s help on this one
Why does it work? Seems worth analyzing a brief example since I couldn’t write the procedure on my own.
for a pora of ‘((a b) c)), the
atom? test fails, so the procedure recursively calls
length\* twice – once on (a b) and once on c. c is an atom so that branch returns 1. (a b) isn’t an atom and so it recursively gets passed to
length*again as a and b respectively. These are atoms and so they get added up to 2, and then that 2 is added to the 1 from c and we get 3.
I did not really understand the rationale for the
weight* procedure. I did analyze it though. They want to “weigh” the first part of the argument given to
align more heavily for some reason, and not just count the number of atoms.
This is 7 because
- the a gets 2X as the first element of (a b)
- The (a b) gets 2X as the first element of the whole x
and then it’s just arithmetic
The function is partial. For the input ((a b)(c d)), it will loop endlessly, because it will keep reversing the order of the pairs and invoking
shuffle on them.
They wind up guiding you towards logically proving that
will-stop? can’t be defined for logical reasons. See the video above for details, as I found this part difficult to summarize.