Ex 2.4

To verify this for ‘any’ x and y, we need to understand how this process works. Although punching in a few possible values and examining the results is by no means a complete verification process, it can be a useful starting point. So, for a first pass, a handful of objects of different types are thrown at it. All of them return exactly what we’d expect for cons and car. The last test is to check that we can build structures out of our structures, and it still works, though I’ll expand on the returned value in a moment.

Part of the exercise is to define cdr. Simply looking at the pattern of the procedures suggests how to create it in this style. Since car returns the first of its arguments p, it seems natural to let cdr return the second one q. That is a solution that is just as simple as those already defined.

We still need to verify it though. To get back to poking at how it works, take a look at what the result is when we add a second layer, building a structure out of our new structures. The following shows how, once you start looking at the structure itself, you get a glimpse of the internals:

; Using built-in procedures
>(car (cons (cons 0 1) (cons 2 3)))
(0 . 1)                            

; Using as defined in the exercise
>(car (cons (cons 0 1) (cons 2 3)))
#<procedure:...s/2-1-3_sol.scm:7:19>

Now that is an intriguing difference. This is still the correct answer, it’s just that x in this case is one of our procedures. That can be verified by simply executing cons(0 1) on its own. As for the response itself: DrRacket uses the # to indicate special values that are not to be read literally (#t as Boolean true, for instance). This one tells us that the value returned is a procedure defined at the given location in a particular file. Looking up that location, we find it to be the lambda expression in our custom cons. That makes sense, since this is what the custom cons procedure returns.

The picture is becoming a bit clearer. Another step to understanding, then, is to use the suggested method of working out the procedure by hand using the substitution model. This gets us closer to how the expression is actually processed. It’s always a tool we have to fall back on The substitution model has limits we’ll discover later as it lets us go through a simple, step-by-step approach and end up with the correct result.

That is sufficient for verifying for any x or y, since x and y are not modified or evaluated during this process, and the values could then be anything. Hopefully it gets us to a better understanding of how this approach to cons works.

Ex 2.5

This one involves a bit of math, but the math is fairly intuitive. This representation is only going to be useful if, once we have a number x of the form 2 ^a 3 ^b, we can recover a and b. In other words, any given pair (a, b) must map to a unique value. All we need do is demonstrate that to be the case.

Now, we know that any non-prime number greater than 1 can be written as the product of its prime factors. The uniqueness of that product is guaranteed by the Fundamental Theorem of Arithmetic. Outside of the case where a and b are 0, the value x will only have 2 and/or 3 as factors, and thus be non-prime and have a unique prime factorization. The additional requirement is that 2 and 3 are relatively prime. That way, our prime factor expression can always be grouped into some number of factors of 2, and some other number of factors of 3. In fact, the respective numbers of those factors is exactly what we want to get back, namely a and b. The special case of (0, 0) can be separately verified as unique, since it only maps to 1, and no other pair of values (a, b) can map to that.

As for implementing numerical pairs, it’s not that hard to do. cons simply generates the value x by multiplying the numbers together. To get car or cdr, we only need to determine how many factors are 2 or 3 respectively. This can be accomplished by successively dividing x by 2 (or 3) and counting the number of times we had to do it until there were no more of that factor. Like so (I did rename these since they only apply to integers):

(define (cdr-int p)
  (define (cdr-iter p i)
    (if (= 0 (remainder p 3))
        (cdr-iter (/ p 3) (+ 1 i))
        i
        )
    )
  (cdr-iter p 0)
  )

Ex 2.6

A great deal of further information can be found on Church numerals all around the internet if you’re interested, as they form an important part of the lambda calculus. If you’ve been introduced to them already, then this exercise isn’t all that hard. Although I have to admit that even knowing what’s going on, the expressions always twist my mind a bit.

Put simply, Church numerals are a way of saying, “take a function f and apply it n times” for a given Church numeral n. Actually, to be more accurate, it should be “take a function f and create a new function that applies f n times”. It’s valuable to keep in mind that the return value is always a new function that itself takes a function as its argument.

That can be deduced (with some effort) by looking at the definitions of zero and add-1 in the text. What zero is is a procedure of one argument f that returns a procedure of one argument x. It does nothing but return x and never applies f. Any numeral n incremented with add-1 gets as a result a procedure with argument x that applies f once to whatever n returns (note that n is given f as an argument). I doubt that’s abundantly clear, but we at least can see that add-1 expects that f is a procedure, and calls it one more time than what was passed to it. Another way is to go back to the substitution model. To figure out one, step through the expression add-1(zero), which is straightforward but I won’t detail it.

Figuring out addition isn’t all that hard if you hold to the idea that any Church numeral n represents a function that applies a given function n times, and returns a Church numeral (i.e. a function that takes a function as argument). Thus, to add two values a and b, simply produce a function that will apply the given function a plus b times. My solution first handles b, and then uses a on the result of that.

If this is still proving difficult to understand, it might be best to first work some examples, and then maybe work by hand using the substitution model. Just remember that the way to use a Church numeral in an expression is ((__n__ #proc) x) — the result is #proc, repeated n times with x as the first argument, i.e. if two is our numeral, ((two square) 5) is equivalent to (square(square 5)). The procedure #proc and the argument x do not need to be numeric functions, either, but they do need to be able to return a value that can be passed back to the same function as an argument, which is natural for the numeric functions. That’s why ((two display) "hello") doesn’t give us “hellohello” as output: it resolves to (display (display "hello")) and in the outermost call, the interpreter will display the result of a display.

Solutions 2.1.3