In the previous part we learned the basics of how to represent compound data and how to work with two types of hierarchical data structures: lists and trees. However, we worked with numbers only. We can also work with symbols and build powerful abstractions too, for instance we can build programs that differentiate algebraic expressions or do arithmetic on polynomials. We are also going to learn how to represent in multiple ways an specific compound data, complex numbers as an example, and how to implement generic operations that work on different types of data.
Scheme allows us to work with symbols and create compound data as the following list:
((norah 12) (molly 9) (anna 7) (lauren 6) (charlotte 4))
Where each element of the list is another list containing a name and a number representing an age. Notice that those names are symbols and not variables. If we were to build those elements like the following line:
>(list norah 12) Unbound variable: norah >(define norah 100) >(list norah 12) (100 12)
Then the interpreter would store the value of the variable norah rather than the symbol itself. In order to manipulate symbols we need a new element in our language: the ability to quote. In order to quote, we have to use the single quote symbol ‘ at the beginning of the element.
>(list 'norah 12) (norah 12)
Here are some examples of how quotation works:
; typing lists using quotation >(car '(a b 2)) a >(cdr '(a b 2)) (b 2) ; equivalence >(define x 1) >(define y 1) >(define z 'x) >(eq? x y) true >(eq? 'x 'y) false >(eq? z 'x) true >(eq? z 1) false ; member of >(memq 'apple '(pear banana prune)) false >(memq 'apple '(z pear apple prune)) (apple prune)
To illustrate some useful fetures about symbol manipulation, we are going to design a procedure that performs symbolic differentiation of algebraic expressions. We would like the procedure to take as arguments an algebraic expression and a variable and to return the derivative of the expression with respect to the variable. For example, if the arguments are ax² + bx + c and x, the output of the procedure should be 2ax + b. We will design this program the same way as we did with rational numbers in part 1 of this review. First, by wishful thinking, we are going to assume there is a representation for algebraic expressions to work on, with its own selectors and constructors. Then, we focus on the behaviour of derivatives:
This rules can be expressed as the following deriv procedure:
(define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) (make-sum (deriv (addend exp) var) (deriv (augend exp) var))) ((product? exp) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var)) (make-product (multiplicand exp) (deriv (multiplier exp) var)))) (else (error "Unknown expression type: DERIV" exp))))
Now that the differentiaton algorithm is complete, we have to implement the interface for algebraic expression, in other words we have to define the selectors, constructors and predicates used in the algorithm that erect the abstraction barrier between behavior and representation. One straightfoward choice to represent algebraic expressions is to use the same parenthesized prefix notation that Scheme uses for combinations: that is, to represent ax + b as (+ (* a x) b).
; predicates (define (variable? x) (symbol? x)) (define (same-variable? x y) (and (variable? x) (variable? y) (eq? x y))) ; constructors (define (make-sum a1 a2) (list '+ a1 a2)) (define (make-product m1 m2) (list '* m1 m2)) ; sum predicate (define (sum? x) (and (pair? x) (eq? (car x) '+))) ; sum selectors (define (addend s) (cadr s)) (define (augend s) (caddr s)) ; product predicate (define (product? x) (and (pair? x) (eq? (car x) '*))) ; product selectors (define (multiplier p) (cadr p)) (define (multiplicand p) (caddr p))
Let us look at some examples of the algorithm behavior:
>(deriv '(+ x 3) 'x) (+ 1 0) >(deriv '(* x y) 'x) (+ (* x 0) (* 1 y))
The program produces answers that are correct but unsimplified. I encourage you to read from page 202 in order to check how to obtain simplified results and also to check another interesting examples about symbolic data (Huffman Encoding Trees).
Multiple Representations for Abstract Data
We have learned that one of the advantages of data abstraction barriers is that they make programs easier to maintain and modify. But what if there is more than one useful representation for a data object and we want to design programs that can deal with multiple representations? Let us take for example complex numbers, they may be represented in rectangular form (real and imaginary parts) and in polar form (magnitude and angle). It is plausible to imagine a system which complex numbers are represented in both ways, and in which the procedures for manipulating complex numbers work with either representation.
That is why, in addition to abstraction barriers that isolate representation from behavior, we also need barriers that isolate different representation form each other (Figure 2) and allow them to coexist in a single program. In order to accomplish this we are going to design generic procedures, this are procedures that operate on data that may be represented in more than one way. We are also going to use type tags.
Again, let focus on the behavior of complex numbers and later on the implementation of the interface for rectangular and polar representations. Addition of complex numbers is straightforward If we think in terms of their real and imaginary parts, the sum of 2 complex numbers is the sum of their real parts and their imaginary parts. What about multiplication? It is easier to multiply two complex numbers if we know their magnitude and angles. Then the multiplication of those numbers is just the product of their magnitudes and the sum of their angles.
Then, the procedure to add and multiply complex numbers can be defined as these:
(define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) (define (mul-complex z1 z2) (make-from-mag-ang (* (magnitude z1) (magnitude z2)) (+ (angle z1) (angle z2))))
Now that we can sum and multiply complex numbers, let us focus on the implementation of the interface for both rectangular and polar representation. The rectangular representation can be defined as this:
;selectors (define (real-part-rectangular z) (car z)) (define (imag-part-rectangular z) (cdr z)) (define (magnitude-rectangular z) (sqrt (+ (square (real-part-rectangular z)) (square (imag-part-rectangular z))))) (define (angle-rectangular z) (atan (imag-part-rectangular z) (real-part-rectangular z))) ; constructors (define (make-from-real-imag-rectangular x y) (attach-tag 'rectangular (cons x y))) (define (make-from-mag-ang-rectangular r a) (attach-tag 'rectangular (cons (* r (cos a)) (* r (sin a)))))
And the polar representation as this:
;selectors (define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z)))) (define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z)))) (define (magnitude-polar z) (car z)) (define (angle-polar z) (cdr z)) ; constructors (define (make-from-real-imag-polar x y) (attach-tag 'polar (cons (sqrt (+ (square x) (square y))) (atan y x)))) (define (make-from-mag-ang-polar r a) (attach-tag 'polar (cons r a)))
We can notice that we added the keywords rectangular or polar at the end of each procedure, because this way both representation will not have name conflicts. But did you notice that the constructors attached the symbol rectangular or polar to the number? This means we are creating tagged data, which a way to distinguish what procedure to apply depending on the tag. The reason we are creating tagged data is to allow us to define generic selectors that will work on both representations. attach-tag works as explained now:
(define (attach-tag type-tag contents) (cons type-tag contents)) (define (type-tag datum) (if (pair? datum) (car datum) (error "Bad tagged data: TYPE-TAG" datum))) (define (contents datum) (if (pair? datum) (cdr datum) (error "Bad tagged data: CONTENTS" datum)))
Using these procedures, we can define predicates rectangular? and polar? which recognize rectangular and polar numbers, respectively:
(define (rectangular? z) (eq? (type-tag z) 'rectangular) (define (polar? z) (eq? (type-tag z) 'polar))
Now that we can recognize and work with different representations for complex numbers, we define generic selectors:
(define (real-part z) (cond ((rectangular? z) (real-part-rectangular (contents z))) ((polar? z) (real-part-polar (contents z))) (else "Unknown type: REAL-PART" z))) (define (imag-part z) (cond ((rectangular? z) (imag-part-rectangular (contents z))) ((polar? z) (imag-part-polar (contents z))) (else "Unknown type: IMAG-PART" z))) (define (magnitude z) (cond ((rectangular? z) (magnitude-rectangular (contents z))) ((polar? z) (magnitude-polar (contents z))) (else "Unknown type: MAGNITUDE" z))) (define (angle z) (cond ((rectangular? z) (angle-rectangular (contents z))) ((polar? z) (angle-polar (contents z))) (else "Unknown type: ANGLE" z)))
Now we can use the procedures add-complex and mul-complex in data from either representation. This strategy of checking the type of a datum and calling an appropriate procedure is called dispatching on type. It is a powerful strategy for obtaining modularity in system design but it has two significant weaknesses:
- Generic interface procedures (as our generic selectors) must know about all the different representations. If we were to add a new representation, we would need to modify each generic procedure to add a new clause to check the type and apply the corresponding selector.
- We must guarantee that no two procedures in the entire system have the same name (we had to add rectangular or polar to each selector in the representations).
Because of the former weaknesses it is known that this technique is not additive. What we need is a means for modularizing the system design even further. This can be achieved by the programming technique known as data-directed programming. Whenever we deal with a set of generic operations that are common to a set of different types we are, in effect, dealing with a two-dimensional table that contains the possible operations on one axis and the possible types on the other axis, as shown in Figure 4.
Data-directed programming is the technique of designing programs to work with such a table directly. We will implement the interface as a single procedure that looks up the combination of the operation name and argument type in the table to find the correct procedure to apply. This means that adding a new representation does not require to change any existing procedures, we only need to add a new entry to the table. To implement this plan, assume that we have two procedures, put and get, for manipulating the operation-and-type table:
- (put <op> <type> <item>) installs the <item> in the table, indexed by the <op> and the <tpye>.
- (get <op> <type>) looks up the <op>, <type> entry in the table and returns the item found there. If no item is found, it returns false.
The book does not show how to implement these methods until Chapter 3, so we will not concern about the definition either. Let us implement the rectangular and polar packages using this new method:
; ------rectangular numbers------ (define (install-rectangular-package) ; internal procedures (define (real-part z) (car z)) (define (imag-part z) (cdr z)) (define (make-from-real-imag x y) (cons x y)) (define (magnitude z) (sqrt (+ (square (real-part z)) (square (imag-part z))))) (define (angle z) (atan (imag-part z) (real-part z))) (define (make-from-mag-ang r a) (cons (* r (cos a)) (* r (sin a)))) ; interface to the rest of the system (define (tag x) (attach-tag 'rectangular x)) (put 'real-part '(rectangular) real-part) (put 'imag-part '(rectangular) imag-part) (put 'magnitude '(rectangular) magnitude) (put 'angle '(rectangular) angle) (put 'make-from-real-imag '(rectangular) (lambda (x y) (tag (make-from-real-imag x y))) ) (put 'make-from-mag-ang '(rectangular) (lambda (r a) (tag (make-from-mag-ang r a))) ) 'done ) ; ------polar numbers------ (define (install-polar-package) ; internal procedures (define (magnitude z) (car z)) (define (angle z) (cdr z)) (define (make-from-mag-ang r a) (cons r a)) (define (real-part z) (* (magnitude z) (cos (angle z)))) (define (imag-part z) (* (magnitude z) (sin (angle z)))) (define (make-from-real-imag x y) (cons (sqrt (+ (square x) (square y))) (atan y x)) ) ; interface to the rest of the system (define (tag x) (attach-tag 'polar x)) (put 'real-part '(polar) real-part) (put 'imag-part '(polar) imag-part) (put 'magnitude '(polar) magnitude) (put 'angle '(polar) angle) (put 'make-from-real-imag '(polar) (lambda (x y) (tag (make-from-real-imag x y))) ) (put 'make-from-mag-ang '(polar) (lambda (r a) (tag (make-from-mag-ang r a))) ) 'done ) (install-polar-package) (install-rectangular-package)
We do not have to worry anymore about name conflicts between the procedures of both implementations. Our generic selectors can be defined as the following:
(define (real-part z) (apply-generic 'real-part z)) (define (imag-part z) (apply-generic 'imag-part z)) (define (magnitude z) (apply-generic 'magnitude z)) (define (angle z) (apply-generic 'angle z))
apply-generic is a procedure that accesses the table and looks up for the correct procedure accordingly to the name of the procedure and the type of the data:
(define (apply-generic op . args) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (apply proc (map contents args)) (error "No method for these types: APPLY-GENERIC") (list op type-tags)))))
We can also extract from the table the constructors to be used by the program external to the packages in making complex numbers from real and imaginary parts and from magnitudes and angles.
(define (make-from-real-imag x y) ((get 'make-from-real-imag '(rectangular)) x y)) (define (make-from-mag-ang r a) ((get 'make-from-mag-ang '(polar)) r a))
Now we have two packages that allow us to represent complex numbers in either rectangular or polar form, whose procedures do not have conflicts with each other, and allow another representation for complex numbers without having to modify the generic procedures. Looks like we are done with generic procedures. But we are far from being done…
What if we wanted to create the generic procedure add that works with rational, complex and real numbers? What if we wanted to work with complex number, and simplify the result to real numbers if the resulting complex has an imaginary part equal to zero? Coercion, Hierarchies of types and Arithmetic on polynomials are the last topics that are learned in chapter 2 and explain the former questions. I encourage you to read about those, you can find them starting at section 2.5, the last part of this chapter.