Section 2.1.2 is about the significance of abstract data types. The obvious illustration in the book give me a very intuitive concept about it.
The book demonstrated an other way to encapsulate a rational number, as following:
(define (make-rat n d)
(cons n d))
(define (numer x)
(let ((g (gcd (car x) (cdr x))))
(/ (car x) g)))
(define (denom x)
(let ((g (gcd (car x) (cdr x))))
(/ (cdr x) g)))In the example, the call of gcd has been moved from the constructor to the property(?) accessors, providing a lazy evaluation interface, i.e. call by need. As an abstract data type, those built on the top of these don’t have to be modified to keep compatible.
All right, I already knew it. That’s why we keep building higher-level abstraction in computer programs, ranging from operating systems to programming languages, giving us benefit from easily maintaining and modifying programs. Take an common example. One of the use of operating system is to provide a compatibility layer above various hardwares. For the application built on the top of an specific OS, it can call a unified interface to control a hardware regardless what its manufactory or model is. Besides, those standards are there for this purpose of abstracting as well. Let’s say, Revised5 Report on the Algorithmic Language Scheme(R5RS/R5RS) specified a group of rules and interfaces. Basing on it, no matter guile, racket, or revo, no matter what language used to implement, a scheme program could run on them and produce the same result as specified.
Somehow one respect that programming attracts me is its abstraction feature. I can’t imagine in other social stuff, or even in some nature science that there are such clear and logical abstraction available. All right.
Exercise 2.2: Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor
make-segmentand selectorsstart-segmentandend-segmentthat define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectorsx-pointandy-pointthat define this representation. Finally, using your selectors and constructors, define a proceduremidpoint-segmentthat takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you’ll need a way to print points:
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))SICP - Page 127 (Chinese edition: page 60)
My solution is: {% codeblock My solution lang:scheme https://github.com/shouya/sicp-exercise/blob/master/2.2.ss view on github %}
(define (print-point p) (display “(”) (display (x-point p)) (display “,”) (display (y-point p)) (display “)”))
(define (print-point-newline p) (print-point p) (newline))
; Have fun :) (define (make-point x y) (lambda (q) (if q x y))) (define (x-point p) (p #t)) (define (y-point p) (p #f))
(define (make-segment p1 p2) (cons p1 p2)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg))
(define (midpoint-segment seg) (make-point (/ (+ (x-point (start-segment seg)) (x-point (end-segment seg))) 2) (/ (+ (y-point (start-segment seg)) (y-point (end-segment seg))) 2)))
(define (print-segment seg) (print-point (start-segment seg)) (display “-”) (print-point (end-segment seg))) (define (print-segment-newline seg) (print-segment seg) (newline))
; Test cases (let ((seg (make-segment (make-point 1 2) (make-point 3 4)))) (print-segment-newline seg) (print-point-newline (midpoint-segment seg)))
{% endcodeblock %}
Slightly long is it but looks much better than yesterday’s.
Here I used a glitch, with lambda’s power to form a tuple type(here it’s like a cons). This trick is from the next section but it looks cool so I just picked it into this code.
Exercise 2.3: Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?
SICP - Page 128 (Chinese edition: page 60)
My solution: {% codeblock solution lang:scheme https://github.com/shouya/sicp-exercise/blob/master/2.3.ss view on github %} ;; New (define (ver-dist-point p1 p2) (abs (- (y-point p1) (y-point p2)))) (define (hor-dist-point p1 p2) (abs (- (x-point p1) (x-point p2))))
;; Method 1 to define a rectangle ; (define (make-rect p1 p2) ; (cons p1 p2)) ; (define (start-rect rect) (car rect)) ; (define (end-rect rect) (cdr rect))
;; Method 2 (define (make-rect p1 p2) (list (x-point p1) (x-point p2) (y-point p1) (y-point p2))) (define (start-rect rect) (make-point (car rect) (caddr rect))) (define (end-rect rect) (make-point (cadr rect) (cadddr rect)))
(define (height-rect rect) (ver-dist-point (start-rect rect) (end-rect rect))) (define (width-rect rect) (hor-dist-point (start-rect rect) (end-rect rect)))
(define (circum-rect rect) (* 2 (+ (height-rect rect) (width-rect rect)))) (define (area-rect rect) (* (height-rect rect) (width-rect rect)))
;; Abstract Layers: ;; ;; 1. cons / list / car / cdr / cadr … ;; 2. make-rect / start-rect / end-rect ;; 3. width-rect / height-rect ;; 4. circum-rect / area-rect ;;
(let ((rect (make-rect (make-point 1 2) (make-point 3 4)))) (display (area-rect rect)) ;=> 4 (newline) (display (circum-rect rect)) ;=> 8 (newline)) {% endcodeblock %}
The abstraction layers are indicated in the code.
I demonstrated two types of implements to encapsulate a rectangle, on layer 2. Since both of them provide the same interfaces to construct a rectangle data type and to access its standard properties(in this case, they are start-rect and end-rect), other codes built upon it aren’t necessary to modify anything for compatibility.
Okay, let’s move on the next section, 2.1.3. What Is Meant by My Data?
Totally it’s talking about when we talk about data, what is we really referring to. The answer is a little unintuitive, that we only have to know a datum’s interfaces. Let me make a simple example from our daily life. When we say ‘water’, we know, or we parse the language ‘water’ as a transparent drinkable liquid, while we usually don’t think that it’s composed by a specific state of combination of molecules that is consist of two hydrogen atoms and an oxygen atom, because that is not important to us. Before the discovery in chemistry about the composition of water, people don’t know that, but they can still distinguish what water is. It’s interfaces decide how people see and feel it. That’s it, transparent liquid that’s drinkable, simply. If there’s another thing that has the same properties, we might probably be able to consider it as water, at least it has the same function as water. This, is what is meant by the datum water.
More interesting is it in examples of code, in fact, I think. Never mind that.
Exercise 2.4: Here is an alternative procedural representation of pairs. For this representation, verify that
(car (cons x y))yieldsxfor any objectsxandy.
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))SICP - Page 131, Chinese edition: page 62.
My proof, with lambda calculus, in the haskell syntax form. First let me rewrite the definition.
cons = \x -> \y -> \m -> m x y car = \z -> z (\p -> \q -> p)
Firstly, do a β reduction on cons. Let there’s a cons for a and b.
cons a b = \m -> m a b
Then do a β reduction on car, substitute the cons as the argument to car:
car (cons a b) = car (\m -> m a b) = (\m -> m a b) (\p -> \q -> p) = (\p -> \q -> p) a b = \q -> a = a
Proved.
Definition of cdr could be: > cdr = -> z (-> -> q)
Likewise.
I find it quite comfortable to do such lambda calculus. Let me talk about a thing related to lambda calculus today. I have SAT writing class today morning. The teacher is the founder, the institute. Although she seemed to be a good lecturer who knows how to attract people’s focus, she’s still boring for me since the content of the class, about Homer’s Epics, was not attractive for me at all. I pretending to be concentrated but actually I thought of things unrelated. I tried to challenge myself, to see if I’d be possible to deduce Church number and operators by my own. Then I took a piece of paper and a pencil and start to scratch on it. In fact yet before I have it done, the teacher noticed me and criticized me relentlessly. Funny is that I was still trying hardly deduce it in my mind, and pretending to be concentrated.
I can still remember how I feel about lambda calculus when I first touch it. It was Y-Combinator, a beautiful fixed point combinator, that firstly attracted me to such theoretical computer science field, as I found it incredibly beautiful. All right, let’s back to the topic.
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 2a 3b. Give the corresponding definitions of the procedures cons, car, and cdr.
SICP - Page 131, Chinese edition: page 62.
My solution(github):
(define (my-cons a b)
(* (expt 2 a)
(expt 3 b)))
(define (my-car x)
(if (= (modulo x 3) 0)
(my-car (/ x 3))
(/ (log x) (log 2))))
(define (my-cdr x)
(if (= (modulo x 2) 0)
(my-cdr (/ x 2))
(/ (log x) (log 3))))
(let ((cons1 (my-cons 1 5))
(cons2 (my-cons 0 3))
(cons3 (my-cons 7 8)))
(display cons1)
(newline)
(display (my-car cons1))
(newline)
(display (my-cdr cons1))
(newline)
(newline)
(display cons2)
(newline)
(display (my-car cons2))
(newline)
(display (my-cdr cons2))
(newline)
(newline)
(display cons3)
(newline)
(display (my-car cons3))
(newline)
(display (my-cdr cons3))
(newline)
(newline))It runs perfectly under both guile and revo. Very interesting code piece it is.
Oh gosh! The next question is about church number! Let me challenge it. (courageous!)
Exercise 2.6. In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.
Define one and two directly (not in terms of
zeroandadd-1). (Hint: Use substitution to evaluate(add-1 zero)). Give a direct definition of the addition procedure+(not in terms of repeated application of add-1).
One & two:
zero = \f -> \x -> x = \g -> y -> y ; alpha conversion
add-1 = \n -> \f -> \x -> f ((n f) x)
1 = add-1 zero
= \f -> \x -> f (((\g -> \y -> y) f) x)
= \f -> \x -> f ((\y -> y) x)
= \f -> \x -> f x
= \g -> \y -> g y ; alpha conversion
2 = add-1 1
= \f -> \x -> f (((\g -> \y -> g y) f) x)
= \f -> \x -> f (f x)
n = \f -> \x -> (f^n x)Plus:
n + m = \f -> \x -> (f^(m+n) x)
= \f -> \x -> (f^m (f^n x))
+ = \m -> \n -> \f -> \x -> m f (n f x)Deduced on today’s class already :)
Feel yet comfortable. I’d just carry on.