This post is fairly short, as much of my attention for chapter 9 was spent on trying to just understand the YCombinator 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:
https://catonmat.net/derivationofycombinator
https://mvanier.livejournal.com/2897.html
https://github.com/ggandor/ycombinatortutorial
https://www.youtube.com/watch?v=9T8A89jgeTI
https://www.macadie.net/2020/02/02/chapter9ofthelittleschemer/
https://wyounas.medium.com/derivingycombinatorinschemedd68a02973f9
Selected Portions of Dialogues
I decided to refer to these as dialogues since the book doesn’t really have exercises per se.
looking & keeplooking
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 keeplooking
:
1
2
3
4
5
6
7
8
9
10
11
12

(define looking
(lambda (a lat)
(keeplooking a (pick 1 lat) lat)))
(define keeplooking
(lambda (a sel lat)
(cond
((equal? a sel) #t)
((number? sel)
(keeplooking a (pick sel lat) lat))
(else #f))))

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.
Shift
A pair is a list with only two sexpressions.
length*
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.
weight*
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
shuffle
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.
willstop?
They wind up guiding you towards logically proving that willstop?
can’t be defined for logical reasons. See the video above for details, as I found this part difficult to summarize.