SICP 2.1 exercises cont.


I uh.. tried to prove the fundamental theorem of arithmetic which turned out to be beyond me. Anyway it’s easily found on wikipedia or somewhere else.

My implementation is kind of silly as I never even made an exponent procedure, and it uses none of the speedups in the last chapter.

(define (cons-2 x y)
  (if (= x 0)
      (if (= y 0)
          (* 3 (cons-2 x (- y 1))))
      (* 2 (cons-2 (- x 1) y))))

(define (car-2 z)
  (if (not (= 0 (remainder z 2)))
      (+ 1 (car-2 (/ z 2)))))

(define (cdr-2 z)
  (if (not (= 0 (remainder z 3)))
      (+ 1 (cdr-2 (/ z 3)))))


This… was crazy. I again needed some help from the internet. The key is realizing that the function takes in a function and returns a function which takes an input and applies the input function however many number of times depending on what number it’s representing. I may rewrite the previous sentence some time.

So we’re given these two functions and need to create a function that represents one.

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

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

We’re told to use substitution, so that’s what we do.

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

Hence the definition of one is

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

Similarly for two

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

And as for addition

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

The key is that all the procedures that represent numbers transform functions into function that repeat however many number of times. That is, (four f) would become (f (f (f (f x)))). Therefore we replace f from add-1 with (m f).

Comments: The insanity was strong within this question. I did the substitution at least five times before I was clear about what was happening. I used Bill the Lizard’s site which omits some of the steps in between, but without which I would not have finished this for a much longer amount of time.


(define (upper-bound x)
  (car x))

(define (lower-bound x)
  (cdr x))


(define (sub-interval x y)
  (make-interval (- (upper-bound x) (lower-bound y))
                 (- (lower-bound x) (upper-bound y))))

Comments: Sped through two more questions. I used the scheme wiki a bit, which explains things very well.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s