Graduate Program KB

Building Abstractions with Data

Table of Contents

Introduction to Data Abstractions

  • Data Abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed from more primitive data objects.
  • We do this by structuring the programs that are to use compound data objects so that they operate on "abstract data."
  • The concrete data representation is defined independent of the programs that use the data.
  • The interface between these to parts (the definition and the programs implemented by this definition) will be a set of procedures called selectors and constructors.
  • What Is Data?
    • In general, data is defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfill in order to be a valid representation.

Pair

  • A way to create a compound structure using the cons keyword.
  • Takes 2 arguments and returns a compound data object that contains the 2 arguments as parts.
  • We can extract the individual parts with car and cdr
  • Notice that cons can be used to create pairs of pairs and so on.
(define x (cons 1 2))
(car x) ;1
(cdr x) ;2

  • Defining cons with our own dispatch method:

    (define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1: CONS" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

  • Key things to notice with above:

    • The value returned by (cons x y) is a procedure.
    • (car z) is defined to apply z to 0.
    • If z is the procedure formed by (cons x y), then z applied to 0 will yield x.
    • We have shown that (car (cons x y)) yields x, as desired.
    • Similarly, (cdr (cons x y)) applies the procedure returned by (cons x y) to 1, which returns y.

Abstraction Barriers

  • Abstraction barriers refer to each level of abstraction.
  • In terms of the rational numbers package, the barriers could be looked at as (from highest level to lowest):
    • Rational numbers in problem domain: programs that use rational numbers.
    • Rational numbers as numerators and denominators: add-rat, sub-rat, mul-rat, etc.
    • Rational numbers as pairs: make-rat, numer, denom.
    • However pairs are implemented: cons, car, cdr.
  • An advantage of having these levels of abstraction is that it makes programs easier to maintain and modify due to any complex data structure being able to be represented in a variety of ways with the primitive data structures provided by the programming language.

Hierarchical Data and the Closure Property

box-and-pointer notation: Each object is shown as a pointer to a box. The box for a primitive object contains a representation of said object.

  • Some examples to help visualise this:

    • Box for a number contains a numeral.
    • Box for a pair is a box containing 2 smaller boxes. The left inner box contains a pointer to the car of the pair and the right part containing a pointer to the cdr of the pair.

  • Power of pairs: they provide a universal building block from which we can construct lots of other data structures in different shapes.

  • The ability to create pairs whose elements are pairs is the essence of the list structure's importance as a representational tool, this ability is referred to as the closure property of cons.

  • Generalisation: An operation for 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.

  • Closure is the key to any means of combination as it permits us to create hierarchical structures.

  • The use of the word "closure" here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set.

Representing Sequences

  • A sequence is an ordered collection of data objects.
  • We can do this with pairs by chaining them together.
  • Thinking of box-and-pointer notation and a sequence of numbers as an example, each number is the car of the pair and cdr is the pointer to the next pair. The last elements cdr is nil (the empty list).
  • You can think of car as selecting the first item in the list and cdr selecting the the sublist consisting of all but the first item.
  • This example is demonstrated below and is commonly known as a list and is built into Lisp, however under the hood this is what it is doing.
(cons 1
  (cons 2
    (cons 3
      (cons 4 nil))))

(list 1 2 3 4)
  • Don't confuse the (list 1 2 3 4) with (1 2 3 4). The second is the result obtained from the first one evaluating.
    • Attempting to evaluate (1 2 3 4) results in an error as 1 is not an operator.
  • Nested car and cdr can be cumbersome to write so it is common to abbreviate them and save it to a variable. All names start with c and end with r and then alternate between a and d to show the order of operations.
(define (cadr x) (car (cdr x)))
(define (caadadr x) (car (car (cdr (car ( cdr x))))))

List Operations

  • list-ref is a method with arity of 2 for extracting an elements from a list.
  • Essentially "cdring down".
  • Arguments: a list and an index.
  • Base case for the recursion: For n=0, list-ref should return car of the list.
  • Recursive nature: list-ref should return the (n-1)-st item of the cdr of the list.
(define (list-ref items n)
  (if (= n 0)
    (car items)
    (list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(list-ref squares 3)
;16
  • length & null?
  • It's common to cdr down a whole list, to aid in this there is a built-in primitive predicate null? which tests whether its argument is the empty list.
  • This can help us create a length procedure which returns the length of a list.
(define (length items)
  (if (null? items)
    0
    (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))
(length odds)
;4
  • append takes 2 lists and returns one list of the 2 combined (second added on top of the first).
  • Recursive plan:
    • Base case: If list1 is the empty list, then the result is just list2.
    • Otherwise append the cdr of list1 and list2, and cons the car of list1 onto the result.
(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2))))

Mapping over lists

  • A common operation is to apply some transformation to every element in a list and return a new list. (like map in JavaScript)
  • Below is an example of scaling every item in a list by some factor:
(define (scale-list items factor)
  (if (null? items)
    nil
    (cons (* (car items) factor)
      (scale-list (cdr items)
        factor))))
(scale-list (list 1 2 3 4 5) 10)
;(10 20 30 40 50)
  • We can abstract this procedure to a higher-order procedure called map with an arity of 2.
  • It takes a procedure that takes 1 arg, and it takes a list.
  • map applies the given procedure to every item in the given list.
(define (map proc items)
  (if (null? items)
  nil
  (cons (proc (car items))
    (map proc (cdr items)))))
(map abs (list -10 2.5 -11.6 17))
;(10 2.5 11.6 17)
(map (lambda (x) (* x x)) (list 1 2 3 4))
;(1 4 9 16)
  • Scheme provides a built in map function but it is a bit different. It takes an n procedures and n lists.
  • It applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on.
(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))
;(741 852 963)
(map (lambda (x y) (+ x (* 2 y)))
  (list 1 2 3)
  (list 4 5 6))
;(9 12 15)
  • map helps us establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined.
  • This abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences.

Hierarchical Structures

  • We can construct lists of lists.
  • (cons (list 1 2) (list 3 4)) --> ((1 2) 3 4)
  • This forms a different structure, it introduces nesting.
  • We want a way to get the number of elements (or nodes/leaves in the tree) in the structure.
(define x (cons (list 1 2) (list 3 4))) ; ((1 2) 3 4)
(length x) ; 3
(count-leaves x) ; 4

(define y (list x x)) ; (((1 2) 3 4) ((1 2) 3 4))
(length y) ; 2
(count-leaves y) ; 8

Count Leaves Procedure:

(define (count-leaves x)
  (cond ((null? x) 0)
    ((not (pair? x)) 1)
    (else (+ (count-leaves (car x))
              (count-leaves (cdr x))))))

Mapping Over Trees

  • Similarly with mapping sequences, it is very powerful and possible to map trees.
  • We can do it in a very similar fashion, see the scale-tree procedure below:
(define (scale-tree tree factor)
  (cond ((null? tree) nil)
    ((not (pair? tree)) (* tree factor))
    (else (cons (scale-tree (car tree) factor)
                (scale-tree (cdr tree) factor)))))
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)
; (10 (20 (30 40) 50) (60 70))
  • A different implementation using built in map, is to regard the tree as a sequence of sub-trees.
    • We map over the sequence scaling each sub-tree in turn.
    • We then return the list of results.
    • For the base case, where the tree is a leaf, we simply multiple by the factor.
    (define (scale-tree tree factor)
  (map (lambda (sub-tree)
    (if (pair? sub-tree)
      (scale-tree sub-tree factor)
      (* sub-tree factor)))
  tree))

Sequences as Conventional Interfaces

  • The key point of this section was to figure out a way to standardise a way of doing something and create reusable pieces that can be re-arranged to solve different problems.
  • Thinking like a signal engineer can be very helpful to see what is going on in procedures to find similarities.
  • We will build up our pieces based off the following 2 examples:

Summing Odd Squares:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
    ((not (pair? tree))
      (if (odd? tree) (square tree) 0))
      (else (+ (sum-odd-squares (car tree))
                (sum-odd-squares (cdr tree))))))

Even Fibonacci Numbers:

(define (even-fibs n)
  (define (next k)
    (if (> k n)
      nil
      (let ((f (fib k)))
        (if (even? f)
          (cons f (next (+ k 1)))
          (next (+ k 1))))))
  (next 0))

How the programs work as signal diagrams:
Summing Odd Squares: enumerate: tree leaves --> filter: odd? --> map: square --> accumulate: +, 0.
Even Fibonacci Numbers: enumerate: integers --> map: fib --> filter: even? --> accumulate: cons, ().

  • Here we can see some similarities:
    • enumerate.
    • map.
    • filter.
    • accumulate.

The Puzzle Pieces

ENUMERATE:

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
    ((not (pair? tree)) (list tree))
    (else (append (enumerate-tree (car tree))
                  (enumerate-tree (cdr tree))))))
(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
; (1 2 3 4 5)

(define (enumerate-interval low high)
  (if (> low high)
    nil
    (cons low (enumerate-interval (+ low 1) high))))
(enumerate-interval 2 7)
; (2 3 4 5 6 7)

FILTER:

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
          (cons (car sequence)
                (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
(filter odd? (list 1 2 3 4 5))
; (1 3 5)

ACCUMULATE:

(define (accumulate op initial sequence)
  (if (null? sequence)
    initial
    (op (car sequence)
        (accumulate op initial (cdr sequence)))))
(accumulate + 0 (list 1 2 3 4 5))
; 15
(accumulate * 1 (list 1 2 3 4 5))
; 120
(accumulate cons nil (list 1 2 3 4 5))
; (1 2 3 4 5)

THE RESULT OF THIS NEW ABSTRACTION:

(define (sum-odd-squares tree)
  (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate
    cons
    nil
    (filter even? (map fib (enumerate-interval 0 n)))))
  • Now lets reuse these pieces for some other scenarios:
    • Constructing a list of the squares of the first n + 1 Fibonacci numbers:
    (define (list-fib-squares n)
  (accumulate
    cons
    nil
    (map square (map fib (enumerate-interval 0 n)))))
(list-fib-squares 10)
; (0 1 1 4 9 25 64 169 441 1156 3025)
    • Compute the product of the squares of the odd integers in a sequence:
    (define (product-of-squares-of-odd-elements sequence)
  (accumulate * 1 (map square (filter odd? sequence))))
(product-of-squares-of-odd-elements (list 1 2 3 4 5))
; 225
    • Finding the highest paid programmer in a series of records:
    (define (salary-of-highest-paid-programmer records)
  (accumulate max 0 (map salary (filter programmer? records))))

Symbolic Data

Huffman Encoding Trees

  • Used for representing data as sequences of bits.
  • An example is the ASCII standard code which is used to represent text in computers and encodes each character as a sequence of seven bits.
    • Using seven bits allows us to distinguish 128 possible different characters.
    • If you want to distinguish n different symbols, you use log2(n) bits per symbol.
  • The way a Huffman Tree works is that you have all the potential encodings at the root node.
  • Going left represents a 0 and going right represents a 1.
  • Each node will either have a set of potential encodings or a single number (leaf node.)
  • You continue to go left or right based on the number until you reach a leaf node, store that number and restart at the root node.
  • The algorithm for generating a Huffman tree involves merging nodes of the lowest weights recursively until you fully merge the tree.
    • This results in the nodes of least frequency being furthest away from the root node.

Representing Huffman Trees:

  • Leaves of the tree are represented by a list consisting of the symbol leaf, the symbol at the leaf, and the weight.
(define (make-leaf symbol weight) (list 'leaf symbol weight))
(define (leaf? object) (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))
  • The set of symbols will be a list of the symbols.
  • When we merge, we obtain the weight of the tree as the sum of the weights of the nodes, and the set of symbols as the union of the sets of symbols for the nodes.
(define (make-code-tree left right)
  (list left
    right
    (append (symbols left) (symbols right))
    (+ (weight left) (weight right))))

; Selectors
(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
    (list (symbol-leaf tree))
    (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
    (weight-leaf tree)
    (cadddr tree)))
  • The decoding procedure looks like the following:
(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
      '()
      (let ((next-branch
          (choose-branch (car bits) current-branch)))
        (if (leaf? next-branch)
          (cons (symbol-leaf next-branch)
            (decode-1 (cdr bits) tree))
          (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
    ((= bit 1) (right-branch branch))
    (else (error "bad bit: CHOOSE-BRANCH" bit))))
  • The following procedure takes a list of symbol-frequency pairs such as ((A 4) (B 2) (C 1) (D 1)) and constructs an initial ordered set of leaves, ready to be merged according to the Huffman algorithm.
(define (make-leaf-set pairs)
  (if (null? pairs)
    '()
    (let ((pair (car pairs)))
      (adjoin-set (make-leaf (car pair) ; symbol
                            (cadr pair)) ; frequency
                  (make-leaf-set (cdr pairs))))))

Multiple Representations for Abstract Data

  • We have been going over data abstraction which essentially is just a methodology for structuring systems so that programs can be specified independent of the choices involved in implementing data objects that the program manipulates.

  • A good example of this is the constant use of selectors throughout the book to abstract away how the data is actually being accessed, we just want the data.

  • These data-abstraction barriers are powerful tools for controlling complexity.

  • Everything up to this point might not always be enough, for example there may be more than one useful representation for a data object and we may want our system to be able to handle these multiple representations.

    • The example covered is complex numbers; you have rectangular form (real and imaginary parts) and polar form (magnitude and angle).

  • This section is all about how to cope with data that may be represented in different ways by different parts of a program.

    • This will require generic procedures - procedures that can operate on data that may be represented in multiple ways.
    • The main technique is to work in terms of data objects that have type tags, meaning data objects that include explicit information about hiw they are to be processed.
    • Data-directed programming is also discussed, it's a powerful and convenient implementation strategy for additively assembling systems with generic operations.

  • The horizontal barrier isolates "higher-level" operations from "lower-level" operations.

  • The vertical barrier gives us the ability to separately design and install alternative representations.

Representations for Complex Numbers

  • Similar to rational numbers, complex numbers can be represented as ordered pairs.
  • The set of complex numbers can be though of as a 2D space with two orthogonal axes, the "real" axis and the "imaginary" axis.
  • z = x + iy, x is the real coordinate and y is the imaginary coordinate.
  • Addition (rectangular form):
    • Real(x + y) = Real(x) + Real(y)
    • Imaginary(x + y) = Imaginary(x) + Imaginary(y)
  • Multiplication (polar form):
    • Magnitude(x * y) = Magnitude(x) * Magnitude(y)
    • Angle(x * y) = Angle(x) + Angle(y)
  • Although the above 2 methods may be the ideal operations for each form, someone may went to use the different representation.
  • Assume that the operations on complex numbers are implemented in terms of 4 selectors: real-part, imag-part, magnitude, and angle.
  • We have 2 procedures for constructing complex numbers: make-from-real-imag and make-from-mag-ang.
    • Both of these procedures have the property that for any complex number z both (make-from-real-imag (real-part z) (imag-part z)) and (make-from-mag-ang (magnitude z) (angle z)) produce complex numbers that are equal to z.
  • Using these constructors and selectors, we can implement arithmetic on complex numbers using abstract data specified by these constructors and selectors.
(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                        (+ (imag-part z1) (imag-part z2))))
(define (sub-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))))
(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                      (- (angle z1) (angle z2))))
  • Now we have to choose whether we represent our system in rectangular or polar form, let's say we choose rectangular.
  • Either way the following relations are needed: (x, y) refer to the real and imaginary parts and (r, A) refer to the magnitude and angle parts.
    • x=r*cos(A)
    • y=r*sin(A)
    • r=sqrt(x^2 + y^2)
    • A=arctan(y, x)
  • If you want to represent your system via rectangular coordinates you will have the following selectors and constructors:
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(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-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))
  • Alternatively if you represented the system with polar coordinates you would have the following selectors and constructors:
(define (real-part z) (* (magnitude z) (cos (angle z))))
(define (imag-part z) (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))
  • The idea is that all our arithmetic operations behave the same either way.
  • NOTE: atan is built into Scheme and is defined to take 2 arguments (y and x) and to return the angle whose tangent is y/x. The signs of the arguments determine the quadrant of the angle.

Tagged Data

  • We can apply the principle of least commitment when viewing data abstraction.
  • In the previous example we could use either representation, the abstraction barrier formed by the selectors and constructors permits us to defer to the last possible moment the choice of a concrete representation for data objects in our system.
  • Type tags will allows us to distinguish how to interpret the data and hence we can actually use both representations.
  • This is as simple as attaching a tag to each complex number, rectangular or polar, analysing the tag will tell us what selector to use.
  • We can implement tagging via a list structure:
(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum: TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum: CONTENTS" datum)))
  • Using these procedures we can define predicates as follows which recognise rectangular and polar numbers:
(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z) (eq? (type-tag z) 'polar))
  • Now we can have both representations in the same system (with a bit of renaming):
(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)))

(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)))))

(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))

(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)))
  • The only real difference other than the renaming is that we have to use our attach tag method when constructing our complex numbers (which is a trivial change).
  • Now using these new selectors and constructors we can complete our more flexible system by implementing our original methods with conditions that simply check the tag of the complex number and uses the appropriate method.
(define (real-part z)
  (cond ((rectangular? z)
          (real-part-rectangular (contents z)))
        ((polar? z)
          (real-part-polar (contents z)))
        (else (error "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 (error "Unknown type: IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
          (magnitude-rectangular (contents z)))
        ((polar? z)
          (magnitude-polar (contents z)))
        (else (error "Unknown type: MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
          (angle-rectangular (contents z)))
        ((polar? z)
          (angle-polar (contents z)))
        (else (error "Unknown type: ANGLE" z))))

Data-Directed Programming and Additivity

  • The general strategy of checking the type of a datum (single symbol of data) and calling an appropriate procedure is called dispatching on type, which is a powerful strategy for obtaining modularity in system design.
  • One weakness of what we did in previous section is that the generic interface procedures need to know about all the different representations, this can get messy pretty quickly if you have many different representations.
  • Another weakness we have to guarantee that no 2 procedures have the same name within the system.
  • Essentially both of these weaknesses come back to the implementation of the generic interfaces not being additive.
  • We need a means for modularizing the system design, which is what this section provides.
  • It can help to observe that whenever we deal with a set of generic operations that are common to a set of different types we are dealing with a 2D table that contains the possible operations on one axis and the possible types on the other axis.
  • Data-directed programming is the technique of designing programs to work with such a table directly.
    • The power of this is that if we wish to add a new representation we only have to add new entries to the table.
    • We simply need the operation, type and item we wish to put in the table to put stuff in, and just the operation and type to get stuff out of the table.
  • An example of how this may look with the rectangular representation is below, we have a package with all our methods and then we interface this to the system by adding them all into a table:
(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)
  • We can perform a lookup in the table and apply a procedure if one exists with the following:
(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))))))

(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))

(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))

Systems with Generic Operations

  • The idea for this section is to see how to define operations that are generic over different kinds of arguments.
  • We want to combine all our arithmetic into one package: primitives, rational numbers, and complex numbers.

Generic Arithmetic Operations

  • The generic arithmetic operations will look like the following with a generic tag attached to each one:
(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))
  • Next to install our scheme number package for our system, this is fairly trivial since it is th built in operations. We just need to apply our tag to each operations and put it in the table.
(define (install-scheme-number-package)
  (define (tag x) (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
    (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
    (lambda (x y) (tag (- x y))))
  (put 'mul '(scheme-number scheme-number)
    (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
    (lambda (x y) (tag (/ x y))))
  (put 'make 'scheme-number (lambda (x) (tag x)))
  'done)

(define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

Rational number package:

(define (install-rational-package)
  ;; internal procedures
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (define (add-rat x y)
    (make-rat (+ (* (numer x) (denom y))
                  (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (define (sub-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))))
  (define (div-rat x y)
    (make-rat (* (numer x) (denom y))
              (* (denom x) (numer y))))

  ;; interface to rest of the system
  (define (tag x) (attach-tag 'rational x))
  (put 'add '(rational rational)
    (lambda (x y) (tag (add-rat x y))))
  (put 'sub '(rational rational)
    (lambda (x y) (tag (sub-rat x y))))
  (put 'mul '(rational rational)
    (lambda (x y) (tag (mul-rat x y))))
  (put 'div '(rational rational)
    (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
    (lambda (n d) (tag (make-rat n d))))
  'done
)
(define (make-rational n d)
((get 'make 'rational) n d))

Complex number package:

(define (install-complex-package)
  ;; imported procedures from rectangular and polar packages
  (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))

  ;; internal procedures
  (define (add-complex z1 z2)
    (make-from-real-imag (+ (real-part z1) (real-part z2))
                          (+ (imag-part z1) (imag-part z2))))
  (define (sub-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))))
  (define (div-complex z1 z2)
    (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                        (- (angle z1) (angle z2))))

  ;; interface to rest of the system
  (define (tag z) (attach-tag 'complex z))
  (put 'add '(complex complex)
    (lambda (z1 z2) (tag (add-complex z1 z2))))
  (put 'sub '(complex complex)
    (lambda (z1 z2) (tag (sub-complex z1 z2))))
  (put 'mul '(complex complex)
    (lambda (z1 z2) (tag (mul-complex z1 z2))))
  (put 'div '(complex complex)
    (lambda (z1 z2) (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
    (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
    (lambda (r a) (tag (make-from-mag-ang r a))))
  'done
)

(define (make-complex-from-real-imag x y)
  ((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
  ((get 'make-from-mag-ang 'complex) r a))
  • In the complex number package we have a 2 level tag system, "complex" is used to determine that we are dealing with complex numbers, then either the "rectangular" or "polar" are used to determine the correct form.
  • Each time you go down a level, the outer layer tag is stripped away.

Return