In chapter 1 we learned about procedures and how to build complex procedures on top of other high-order procedures. Chapter 2 gives us new eyes to appreciate and work with data in a similar way as we did with procedures, building compound data. In part 1 of this review, we are going to learn how to build abstractions with data, build sequences and hierarchical structures (specifically lists and trees).
Introduction to Data Abstraction
Do you remember the notion of Black-Box abstraction viewed in chapter 1? The same idea appears for compound data and is called data abstraction. It enables us to isolate how a compound data object is used from its construction based on other data objects. This isolation is possible thanks to an interface, which is a set of procedures called selectors and constructors and its usage is explained in the following example.
Let us imagine we want to do basic arithmetic with rational numbers, being able to add and multiply for now. According to the previous paragraph, we must define two fundamental parts:
- The implementation of the interface of rational numbers
- The way rational numbers will behave when we sum or multiply
We are going to begin with the second part, and assume the first part is done. This is called wishful thinking, it is a powerful design practice that allows us to work on different layers of abstraction without concerning with the details of the other ones. Thus, let the interface for rational number be the following selectors and constructor:
- (make-rat <n> <d>) : returns a rational number whose numerator is n and denominator is d (constructor).
- (numer <x>) : returns the numerator of the rational number x (selector).
- (denom <x>) : returns the denominator of the rational number x (selector).
Having these, let us focus on the behavior of addition of multiplication of rational numbers. It is known that addition and multiplication are governed by the following relations:
These relations can be defined as the following procedures using the interface provided:
(define (add-rat x y) (make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) (define (mul-rat x y) (make-rat (* (numer x) (numer y)) (* (denom x) (denom y))))
Now that we know how to add and multiply rational numbers, we have to define the selectors and the constructor. In other words, we need to find a way to glue together a numerator and a denominator. This is possible using pairs, which is a compound structure that contains two elements. Scheme provides the procedure cons in order to build pairs, and the primitives car and cdr to retrieve its elements.
>(define some-data (cons 10 20)) >(car some-data) 10 >(cdr some-data) 20
Then, implementing the interface is straightforward using pairs:
(define (make-rat numer denom) (cons numer denom) ) (define (numer x) (car x) ) (define (denom x) (cdr x) )
We can try our rational numbers with the following code:
(define (print-rat x) (newline) (display (numer x)) (display "/") (display (denom x)) ) >(define one-half (make-rat 1 2)) >(print-rat one-half) 1/2 >(define one-third (make-rat 1 3)) >(print-rat (add-rat one-half one-third)) 5/6 >(print-rat (mul-rat one-half one-third)) 1/6
We can observe the structure of the rational numbers as shown in the following figure:
The horizontal lines represent abstraction barriers that isolate different levels of the system, thus we can infer that the interface of the rational numbers is an abstraction barrier. One of the advantages of having these barriers is that they make programs easier to maintain and modify. For example, if we were to change the way make-rat works, not using cons but another procedure to glue a numerator and a denominator, this change won’t interfere with the definitions of add-rat and mul-rat.
Hierarchical Data and the Closure Property
The procedure cons may combine not only numbers but pairs as well:
>(define x (cons 1 2)) >(define y (cons 3 4)) >(define z (cons x y)) >(car (car z)) 1 >(car (cdr z)) 3
The ability to create pairs whose elements are pairs is referred as the closure porperty of cons. An operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. This permits us to create hierarchical structures, made up of parts which themselves are made up of parts, and so on.
One of the useful structures we can build with pairs is a sequence, an ordered collection of data objects, as one can see in figure 3. This sequence is constructed by nested cons operations, where the end of the sequence is the value of nil.
(cons 1 (cons 2 (cons 3 (cons 4 nil))))
The previous sequence of pairs can also be constructed with Scheme’s primitive procedure list:
(list 1 2 3 4)
There are useful operations one can do with lists:
(define one-through-four (list 1 2 3 4)) ; get the first value of the list >(car one-through-four) 1 ; insert a value >(cons 7 one-through-four) (7 1 2 3 4) ; get the 'tail' two-through-four >(cdr one-through-four) (2 3 4) ; length of a list >(length one-through-four) 4 ; joining two lists >(define five-through-eight (list 5 6 7 8)) >(append one-through-four five-through-eight) (1 2 3 4 5 6 7 8)
I encourage you to implement length and append in a recursive and iterative way, and check your answer with the implementation done in the book (pages 137-139).
We can also represent sequences whose elements may themselves be sequences, for instance let us observe the following figure:
This structure is a list of 3 items, whose first element is the list (1, 2).
(define one-through-four-tree (cons (list 1 2) (list 3 4)))
Sequences of sequences are also called trees, it is said that elements of the sequence are the branches of the tree, and those elements that are themselves sequences are subtrees. It is extremely useful to use recursion when dealing with trees, because one can operate on their branches and the branches of the branches as they are also trees. The following example illustrates a recursive way to count the elements (leaves) of a tree.
(define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x)))))) ; counting on the previous tree >(count-leaves one-through-four-tree) 4
There are 4 important operations that help us organize our programs and view them as stages in a process: map, filter, accumulate and enumerate.
Map is a procedure that transforms a list into another list of the same length, applying a procedure to each of its elements. For instance, if we wanted to square all the elements of a list, we can simply do the following:
(map square one-thorugh-four) >(1 4 9 16)
Filter is helpful to select from a list only those elements that satisfy a given predicate:
(define (even? number) (= (remainder number 2) 0)) >(filter even? one-through-four) (2 4)
Accumulate combines the elements of a list using a given procedure, starting with an initial value:
>(accumulate + 0 one-through-four) 10 >(accumulate * 1 one-through-four) 24
Enumerate gives us a sequence of integers in a given range:
>(enumerate 2 7) (2 3 4 5 6 7)
We can combine these procedures to build complex programs in a very intuitive way. For example, we want to construct the list of all the even Fibonacci numbers Fib(k), where k is less than or equal to n ( or 7 in this example):
>(even-fibs 7) (0 2 8)
The process and the stages of even-fibs can be viewed as:
Thus, we can define the procedure even-fibs as:
(define (even-fibs n) (accumulate cons nil (filter even? (map fib (enumerate 0 n)))))
where fib is a procedure that computes fibonacci numbers, just like the one we saw in chapter 1.
Finally, there is a great example on the book that puts it all together to illustrate what’s been shown on this review, I strongly encourage you to check out the Picture Language Example on page 172.