Chapter 2.1 (Introduction to Data Abstraction)
In this chapter we are gonna look at more complex data compared to simple numerical data. The same thing we did with procedures, namely build them from other more simpler procedures is possible with regards to data. Data that exists out of other combined data objects is called compound data. Which is also nothing more than 1 or more abstraction layers covering in essence very simple data.
Why do we want this? That is also very similar to procedures. By using compound data we can design on a higher level, enhancing the expressive power.
As an example, lets consider the idea of forming a linear combination $ax + by$
We might like to write a procedure that takes in 4 arguments $a, x, b$, and $y$ and that returns the value of $ax + by$. This is trivial if the arguments are numbers:
(define (linear-combination a b x y)
(+ (* a x) (* b y)))
But suppose we are not concerned about numbers, but about some abstract data type instead. We could express such a procedure as :
(define (linear-combination a b x y)
(add (mul a x)(mul b y)))
Where add and mul do not represent the primitive + and * operations, but rather more complex things that will perform the appropriate
oeprations for whatever kind of data that we pass in as $a, b, x$, and $y$.
Example: Arithmetic Operations for Rational Numbers
The analogous notion for compound data is also called data abstraction which signifies the overlap with procedure abstraction. Data abstraction is the methodology that enables us to isolate how a compound data object is used from the details of how it is constructed.
Suppose we want to do arithmetic with rational numbers such as $\frac{1}{3}$. We want to be able to add, subtract, multiply, and divide them and to test whether two rational numbers are equal. The ONE THING we do not want to do is the just deal with just numbers, and have every procedure that deals with rational numbers accept twice the arguments as normal numbers. So no:
(define (add a b c d)
(/(+ (* a d)(* c b))(* b d))
This is prone to errors and makes reasoning about very hard. What we instead want to do is capture the concept of rational numbers into some higher level data objects. Maybe something like:
(define (add-rat a b)
(make-rat (+ (* (numer x)(denom y))
(* (numer y)(denom x)))
(* (denom x) (denom y))))
Where a and b represent rational numbers. Once again we employ wishful thinking. We have not yet decided on how we should implement procedures like make-rate, numer, or denom. Only what we expect from them to accept as arguments and what to return.
Now we can start implementing them. But we need some way to glue together a numerator and a denominator to form a rational number.
Pairs
Lisp provides a compound structure called a pair, which can be constructed using the primitive constructor cons.
(define x (cons 1 2))
(car x)
1
(cdr x)
2
This is nothing more than a tuple. Pairs can then (and this is very important) be used to create new pairs:
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
z = ((1 2)(3 4))
This simple structure, is the only glue that is needed.
Representing rational numbers.
Pairs offer a natural way to complete the rational-number system. We can implement them (a bit overkill, but it is for educational purposes):
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
Exercise 2.1 Define a better version of make-rat that handles both positive and negative arguments. If the rational number is positive, both the numerator and denominator are positive. If the rational number is negative, only the numerator is negative
(define (make-rat n d)
(let ((g (gcd n d))
(denom-sign (if (> d 0) 1 (- 1))))
(cons (* (/ n g) denom-sign)
(* (/ d g) denom-sign))))
2.1.2 Abstraction Barriers
Let us consider some of the issues raised by the rational-number example above. We defined the rational-number operations in terms of make-rat numer, and denom.
In general, the underlying idea of data abstraction is to identify for each type of data object a basic set of operations in terms of which all manipulations of data will be expressed, and then only use those operations in manipulating the data.
This simple idea has many advantages. One advantage is that it makes programs much easier to maintain and to modify. We don’t have to reason about underlying structures, we can just assume they do what they should do.
Exercise 2.2 Consider the problem of representing line segments. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and -end-segment that define the representation of segments in terms of points, so do the same for the points construct.
(define (make-segment a b)
(cons a b))
(define (start-segment s)
(car s))
(define (end-segment s)
(cdr s))
(define (make-point x y)
(const x y))
(define (x-point p)
(car p))
(define (y-point p)
(cdr p))
Finally, using the above, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint
(define (midpoint-segment s)
(let ((start (start-segment s))
(end (end-segment s)))
(make-point (/ (+ (x-point end) (x-point start)) 2)
(/ (+ (y-point end) (y-point end))) 2)
))
Exercise 2.3 Implement a representation for rectangles in a plane. In terms of constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle.
(define (make-rect h v)
(cons h v))
(define (horiz r)
(car r))
(define (vert r)
(cdr r))
(define (horiz-length r)
(let ((horiz-vect)(horiz r))
(- (x-point (cdr horiz-vect))(x-point (car horiz-vect)))
(define (vert-length r)
(let ((vert-vect)(vert r))
(- (y-point (cdr vert-vect))(y-point (card vert-vect))))
(define (perimeter r)
(+ (* 2 (horiz-length r)) (* 2 (vert-length r)))
(define (area r)
(* (horiz-length r)(vert-length r)))
2.1.3 What is meant by data?
In general, we can think of data as defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfull in order to be a valid representation.
This does mean that with regards to the rational numbers, any triple of procedures that satisfies the conditions can be used. It is entirely possible to implement cons, car, and cdr without any data structures whatsoever:
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1"))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
In this case the return value of cons is not a pair, but a procedure with the x and y baked in. The z in car, and cdr is thus also a procedure. But that does not matter, this is a completely valid implementation. And thus, if we would only use cons, car, and cdr, we would not know (and not have to know) anything about these implementation details. We should not care about the inner workings of these procedures, we just use them to build other, even more useful and interesting stuff.
Exercise 2.4 Here is an alternative procedural representation of pairs:
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
In this case cons returns a lambda procedure that takes a procedure as an argument and applies that procedure to x and y. car and cdr are then nothing more than procedures that tell cons to return the first or the second element.
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$.
So apparently it is possible to “encode” any pair of nonnegative integers $a$ and $b$ by taking 2 distinct prime numbers, and applying the following: $prime1^a * prime2^b$. This can then be decoded by how many times the resulting number is divisable again by those same prime numbers. Lets take (2, 3) as an example:
(2, 3) can be encoded by: $2^2 * 3^3 = 108$ . if we want to decode, we count how many times 108 can de divided by 2: $108 / 2 = 54$ $54 / 2 = 27$ 27 can no longer be cleanly divided by 2, so the first value of the pair is 2.
Dividing 108 by 3: $108 / 3 = 36$ $36 / 3 = 12$ $12 / 3 = 4$ 4 can no longer be cleanly divided by 3, so the second value of the pair is 3. The decoded pair is (2, 3)
The above explanation would make the cons quite easy to implement:
(define (cons x y)
(* (expt 2 x) (expt 3 y)))
car would now have to check how many times a value can be cleanly divided by 2:
(define (car x)
(define (count a n)
(let ((result (/ a 2)))
(if (integer? result)
(count result (+ n 1))
n)))
(count x 0))
and cdr would do the same for 3 (allowing for some repetition)
(define (cdr x)
(define (count a n)
(let ((result (/ a 3)))
(if (integer? result)
(count reslt (+ n 1))
n)))
(count x 0))
Exercise 1.26 Taking it a step further, consider that in a language that can maniplate procedures, we can get by without numbers 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 Chruch Numerals
Define one and two directly (not in terms of zero and add-1)
(define one (lambda (f) (lambda(x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x))))))
Give a direct definition of the addition procedure + (not in terms of repeated application add-1)
(define (add a b)
(lambda (f) (lambda (x) ((a f) ((b f) x)))))
2.1.4 Extended Exercise: Interval Arithmetic
Exercise 2.7 Define selectors upper-bound and lower-bound to complete the implementation
(define (upper-bound i)
(cdr i))
(define (lower-bound i)
(car i))
Exercise 2.8 Describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure called sub-interval.
The difference between 2 intervals is set to be (lower-bound a - upperbound b, upper-bound a - lower-bound b). This interval would then contain all possible values that can result from subtracting ANY value in interval B from any value in interval A.
(define (sub-interval a b)
(make-interval
(- (lower-bound a)(upper-bound b))
(- (upper-bound a)(lower-bound b))))
Exercise 2.9 The width of an interval is half of the difference between its upper and lower bounds. This is considered a measure of uncertainty.
(define (width i)
(/ (- (upper-bound i)(lower-bound i)) 2))
Exercise 2.10