Exercise 2.6: Church Numerals

Exercise 2.6 Define one and two directly (not in terms of zero and add-1).

The exercise gives the following definitions of zero and add-1

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

OK. Not that I understand how these represent zero and add-1, because trying to evaluate them just returns a procedure.

zero

;Value 22: #[compound-procedure 22 zero]

(add-1 zero)

;Value 23: #[compound-procedure 23]

Still, I'll play along. I'll use the substitution rules to figure out one and two.

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f (lambda (x1) x1) x)))
(lambda (f) (lambda (x) (f x)))

(define one
  (lambda (f) (lambda (x) (f x)))

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) f x) x))))
(lambda (f) (lambda (x) (f (f x))))

(define two
    (lambda (f) (lambda (x) (f (f x))))

At this point i can see a pattern emerge. I'm going to venture a guess that three would look like this:

(define three
    (lambda (f) (lambda (x) (f (f (f x)))))

So I don't really know what I did or how to verify whether its right. A little googling reveals a great page on this exercise by Bill the Lizard. And (surprise!) it looks like my substitutions above came out OK.

Reading over Bill's solution, I realize I forgot to define add. So I try not to look at Bill's solution, and work on my own. I do crib Bill's suggestion on how to test these numbers with inc.

So, I start looking at the pattern closer. I know that

(add zero one)

should result in

(lambda (f) (lambda (x) (f x)))

and that

(add one one)

should result in

(lambda (f) (lambda (x) (f (f x))))

And just to make sure I understand what's going on, I define add-2

(define (add-2 n)
  (lambda (f) (lambda (x) (f (f ((n f) x))))))

This seems to work based on my
inc test.

(((add-2 zero) inc) 0)

;Value: 2

I have a procedure to increase the value of a number. I need to generalize it so that I can increase it value of a number a b times. As it turns out, this "number" b is a procedure which repeats another procedure. So I'll just apply b to (a f) like this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      (f ((b (a f)) x)))))

This look promising at first, but, until I get to adding two and two.

(((add zero one) inc) 0)

;Value: 1

(((add one one) inc) 0)

;Value: 2

(((add one two) inc) 0)

;Value: 3

(((add two two) inc) 0)

;Value: 5

(((add two zero) inc) 0)

;Value: 1

(((add two one) inc) 0)

;Value: 3

So I played around with it until my head hurt. In the end, I read the end of Bill's article. The final solution is this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      ((b f) ((a f) x)))))

Now that I see it, it makes sense. I need b applications of f to ((a f) x), and the way to do this is with the procedure(b f), which will result in the application of procedure f b times. The repeated application of this procedure should be applied to ((a f) x).

Definitely one of the hardest problems I've encountered. I'll have to do some study on church numbers and come back to it.

Exercise 2.5: Yet another definition of cons, car, cdr

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

This is possible because any number 2ⁿ will not contain 3 as a factor. Similarly, any number 3ⁿ will not contain 2 as a factor.

cons is a straightforward application of what the exercise describes.

(define (cons3 a b)
  (* (expt 2 a) (expt 3 b)))

car and cdr just repeatedly divide by 2 (car) or 3 (cdr) until the number no longer divides evenly. Count the number of even divisions, and return the count as the result.

(define (cdr3 c)
  (define (helper x count)
    (if (= 0 (remainder x 3))
        (helper (/ x 3) (+ 1 count))
        count))
  (helper c 0))

(define (car3 c)
  (define (helper x count)
    (if (= 0 (remainder x 2))
        (helper (/ x 2) (+ 1 count))
        count))
  (helper c 0))

;;tests
(car3 (cons3 23 67))
;Value: 23

(cdr3 (cons3 23 67))
;Value: 67

Exercises 2.1 - 2.4

Exercise 2.1 Define a better version of make-rat that handles both positive and negative arguments. make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

The main trick in this problem was to get the signs to line up after your number comes through the gcd procedure. I could have redefined gcd to return only a positive number, but that seemed to be cheating. So I came up with the method below which calls make-rat again. I could have added more conditional checking to get the signs to work, but somehow this was the first solution to come to me.

;;;from chapter 1
(define (square x) (* x x))

;;;from section 1.2.5, for Section 2.1.1
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

;; from section 2.1
(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

;; original make-rat
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

;;new, improved make-rat
(define (make-rat n d)
  (let ((g (abs (gcd n d))))
    (cond
     ((and (< n 0) (< d 0)) (make-rat (abs n) (abs d)))
     ((and (> n 0) (< d 0)) (make-rat (- n) (- d)))
     (else (cons (/ n g) (/ d g))))))

Exercise 2.2 Specify a constructor make-point and selectors x-point and y-point that define this representation (of a line segment).

;; Exercise 2.2

(define (make-segment a b) (cons a b))

(define (start-segment a) (car a))

(define (end-segment b) (cdr b))

(define (make-point x y) (cons x y))

(define (x-point p) (car p))

(define (y-point p) (cdr p))

(define (midpoint-segment s)
  (make-point (/ (+ (x-point (start-segment s)) (x-point (end-segment s))) 2)
              (/ (+ (y-point (start-segment s)) (y-point (end-segment s))) 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

;;; test out the procedure

(define s1 (make-point 0 0) (make-point 2 4)

(print-point (midpoing s1))

(1,2)
;Unspecified return value

Exercise 2.3 Implement a representation for rectangles in a plane.

I wasn't sure what I was supposed to provide in term of "abstraction barriers." I decided that was the selectors for the width and height of the rectangles. The first definition of rectangle is defined in terms of two points: the top left and the bottom right. Then I define height and width to calculate those values based on the two points.

;; exercise 2.3
;;first definition
(define (make-rect tl br) (cons tl br))

(define (top-left-rect r) (car r))
(define (bottom-right-rect r) (cdr r))

(define (width-rect r)
    (- (x-point (bottom-right-rect r))
       (x-point (top-left-rect r))))

(define (height-rect r)
    (- (y-point (top-left-rect r))
       (y-point (bottom-right-rect r))))

The second definition of rectangle is defined in terms of an origin point and the size. I use coordinates to represent size, which isn't ideal. The data matches up, but it isn't quite right to talk about the x-point of the width. Still, I didn't think it was necessary to define a new kind of size pair for the purpose of this exercise. Height and width selectors return the values of height and width from the size pair.

;; exercise 2.3

;;second definition
(define (make-rect origin size) (cons origin size))
(define (origin-rect r) (car r))
(define (size-rect r) (cdr r))
(define (width-rect r) (x-point (size-rect r)))
(define (height-rect r) (y-point (size-rect r)))

Finally, calculating area and perimeter in terms of size.

;; these procedures work on either representation of rectangle above
(define (perimeter-rect r) (+ (* 2 (width-rect r)) (* 2 (height-rect r))))
(define (area-rect r) (* (width-rect r) (height-rect r)))

Exercise 2.4 What is the corresponding definition of cdr?

This I just worked through with standard substitution rules until the application became clear.

;;exercise 2.4

(define (cons2 x y)
  (lambda (m) (m x y)))

(define (car2 z)
  (z (lambda (p q) p)))

;;substitution for (car (cons 1 2))

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
(lambda (1 2) 1)
1
;; resulting definition of cdr

(define (cdr2 z)
  (z (lambda (p q) q)))

Section 2.1: Intro Data Abstraction

Notes from Book section 2.1 and Youtube lecture 2B.

Compound data. So far we've been operating on numbers for a lack of other data types to work on. This chapter introduces data. The basic datatype in Scheme is the pair.

Make pairs with cons.

(cons x y) -> pair (x, y)

Retrieve the first element with car. Retrieve the second element with cdr.

(car (cons x y)) -> x

(cdr (cons x y)) -> y

This is true for any x and y, even if x and y are themselves pairs. The ability to combine not just primitives (like numbers) but also compound data is called closure. Pairs would be limited an uninteresting if we could only crate them with a limited set of primitive data.

Suppose you have a data type of point, defined as a pair created by cons.

(define (make-point x y) (cons x y))

(define (x-coordinate p) (car p))

(define (y-coordinate p) (cdr p))

You can combine the points into a pair to define the endpoints of a line segment...

(define (make-segment a b) (cons a b))

(define (start-segment s) (car s))

(define (end-segmenet s) (cdr s))

...and then define computations based on the points.

(define (midpoint s)
    (make-point (average (x-coordinate (start-segment))
                         (x-coordinate (end-segment)))
                (average (y-coordinate (start-segment))
                         (y-coordinate (end-segment)))))

This definition also make a layered approach to the problem of lines, something like this:

Segments
------------
make-seg, seg-start, seg-end
------------
Points
------------
make-point, x-coordinate, y-coordinate
------------
Pairs, Numbers

The definition of points could change, and as long as the constructors and accessors make-point, x-coordinate, y-coordinate are updated to match the new definition, the line segment procedures don't need to change.

The pair data structure can be represented as procedures:

(define (cons x y)
    (lambda (pick)
        (cond ((= pick 1) x)
              ((= pick 2) y))))

(define (car z) (z 1))

(define (cdr z) (z 2))

Mind-blowing! There is no data, just procedures. Still, it's a valid representation of pairs because it fulfills the contract

(car (cons a b)) -> a

(cdr (cons a b)) -> b

So in some sense you can build data abstractions without data.