Archive for the ‘Gödel’ Tag

SICP – Section 2.1.1 – 2.1.3   Leave a comment

I’ve done a few exercises from chapter 2. This chapter has been a really enlightening one for me, as I’ve learned so much about abstraction that I’ll never even realized before.

;;Exercise 2.1

(define (make-rat n d)
  (let ((n (if (< d 0)
               (- n)
        (d (if (< d 0)
               (- d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g)))))

;;Exercise 2.2
This one is just a gentle exercise, get us used to using lists, car, and cdr…

;;Segment constructor and selectors
(define (make-segment a b) (cons a b))
(define (start-segment s) (car s))
(define (end-segment s) (cdr s))
;;Point constructor and selectors
(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)))
              (/ (+ (y-point (start-segment s))
                    (y-point (end-segment s)))

;;Exercise 2.3
This exercise introduces us to making good abstractions; if we do so, changing the base representation doesn’t need to change the predefined operators.

(define (make-dim l h) (cons l h))
(define (length-dim d) (car d))
(define (height-dim d) (cdr d))

;;First implementation of make-rect.
;;Represented as a top-left corner, and a height and length
(define (make-rect top-left dim) (cons top-left dim))
(define (top-left-rect r) (car r))
(define (dim-r r) (cdr r))
(define (length-rect r) (length-dim (dim-rect r)))
(define (height-rect r) (height-dim (dim-rect r)))

;;Second implementation of make-rect
;;Implemented as a top-left and bottom-right corner
(define (make-rect top-left bottom-right) (cons top-left bottom-right))
(define (top-left-rect r) (car r))
(define (bottom-right-rect r) (cdr r))
(define (length-rect r)
  (- (point-x (bottom-right-rect r))
     (point-x (top-left-rect r))))
(define (height-rect r)
  (- (point-y (bottom-right-rect r))
     (point-y (top-left-rect r))))
;;Area and perimeter of either rect
(define (area-rect r)
  (* (length-rect r) (height-rect r)))
(define (perimeter-rect r)
  (+ (* (length-rect r) 2)
     (* (height-rect r) 2)))

;;Exercise 2.4

(define (cons x y) (lambda (m) (m x y)))

(define (car z) (z (lambda (p q) p)))

The complimentary definition of cdr, is of course, obtained by replacing the p with q in the lambda expression in the car definition.

(define (cdr z) (z (lambda (p q) q)))

We can see why this works, by, as suggested by the authors, applying the substitution model:
Let’s apply car to (cons 4 8)

;;(car (cons 4 8))
;;(car (lambda (m) (m 4 8)))
;;((lambda (m) (m 4 8)) (lambda (p q) p))
;;((lambda (p q) p) 4 8)

Exercise 2.5
I really enjoyed exercise 2.5 :)

I sat down for about an hour, trying various calculations before I figured out a way to get the numbers back out of the expression. Here’s the code:

(define (divisible-by-2 x)
  (if (not (integer? x))
      (= (remainder x 2) 0)))

(define (divisible-by-3 x)
  (if (not (integer? x))
      (= (remainder x 3) 0)))

(define (int-cons a b)
  (* (expt 2 a)
      (expt 3 b)))

(define (int-car p)
  (define (try q n)
    (if (not (divisible-by-2 q))
        (try (/ q 2) (+ n 1))))
  (try (/ p 3) 0))

(define (int-cdr p)
  (define (try q n)
    (if (not (divisible-by-3 q))
        (try (/ q 3) (+ n 1))))
  (try (/ p 2) 0))

This is related to a method for encoding numbers known as “Gödelization”. This method was invented/(discovered) by Kurt Gödel, a famous logician/mathematician. It encodes numbers by raising sequences of prime numbers to them, and getting the product,in much the same way we have.

eg. (4,6,9,12) would become 24*36*59*712 = 315321824047781250000

I found out about this method in the book “Computational Beauty of Nature”, a really great read for anyone who’s interested in math, computation, and the amazingness of nature (it’s a great book!), not just computer scientists. Eventually, I hope to implement a Gödelization algorithm, perhaps when we begin on actual lists, and not just conses.

Posted 23/03/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , ,