Archive for October, 2010

Exercise 2.77

In order to trace through the procedures called in evaluating the expression (magnitude z) we can use the substitution model:

(magnitude '(complex rectangular 3 4))                =>
(apply-generic 'magnitude '(complex rectangular 3 4)) =>
(apply magnitude '(rectangular 3 4))                  =>
(apply-generic 'magnitude '(rectangular 3 4))         =>
(apply magnitude '(3 4))                              =>

Apply-generic is invoked twice – once for each of the tags complex and rectangular.

The first time apply-generic is invoked it strips off the tag complex of its argument and passes the rest of the argument to the generic magnitude procedure.

Generic magnitude invokes apply-generic again. This time the tag rectangular is stripped from the argument and the rest of it is passed to the internal magnitude procedure defined in the rectangular package. At this stage the desired computation is finally carried out without further calls to apply-generic.

Exercise 2.78

Modified definitions of attach-tag, type-tag, and contents:

(define (attach-tag type-tag contents)
  (if (eq? type-tag 'scheme-number)
      (cons type-tag contents)))

(define (type-tag datum)
  (cond ((number? datum) 'scheme-number)
        ((pair? datum) (car datum))
        (else (error "Bad tagged datum --TYPE-TAG" datum))))

(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Bad tagged datum --TYPE-TAG" datum))))

Exercise 2.79

Definition of a generic equ? predicate:

(define (equ? x y) (apply-generic 'equ? x y))

Code we need to add to the scheme-number package:

(put 'equ? '(scheme-number scheme-number)
       (lambda (x y) (= x y)))

Code we need to add to the rational package:

(define (equ? x y)
    (= (* (numer x) 
          (denom y))
       (* (numer y)
          (denom x))))

(put 'equ? '(rational rational) equ?)

Code we need to add to the complex package:

(define (equ? z1 z2)
    (and (= (real z1)
            (real z2))
         (= (imag z1)
            (imag z2))))

(put 'equ? '(complex complex) equ?)

After these modifications the new operation equ? should work for ordinary numbers, rational numbers, and complex numbers.

Exercise 2.80

Definition of a generic =zero? predicate:

(define (=zero? x) (apply-generic '=zero? x))

Code we need to add to the scheme-number package:

(put '=zero? '(scheme-number) (lambda (x) (= x 0)))

Code we need to add to the rational package:

(define (=zero? x)
    (= (numer x) 0))

(put '=zero? '(rational) =zero?)

Code we need to add to the complex package:

(define (=zero? z)
    (< (mag z) 0.0000001))

(put '=zero? '(complex) =zero?)

Read Full Post »

Exercise 2.73

The old version of deriv uses an explicit dispatch on type. The new version tends to use the more sound data-directed style of dispatching on type.

We must realize though, that our deriv procedure actually dispatches on two completely different kinds of “types”.

One of these types is determined by the algebraic operator symbol at the front of the expression – if such exists. The new version of the deriv procedure applies the data-directed style of dispatching on type only with respect to this particular kind of type.

The other kind of type we are dispatching on is determined by the predicates number? and variable? (implemented in terms of the primitive predicate symbol?). This kind of primitive type is built into the Scheme system. This prevents us from naturally assimilating these predicates in our table.

The new definition of deriv allows us to add differentiation rules without changing any existing code.

For example we can add rules for differentiation of sums and products:

(define (install-deriv-package)
  ;;internal procedures
  (define (make-sum a1 a2) (list '+ a1 a2))
  (define (addend s) (car s))
  (define (augend s) (cadr s))
  (define (deriv-sum exp var)
    (make-sum (deriv (addend exp) var)
              (deriv (augend exp) var)))
  (define (make-product m1 m2) (list '* m1 m2))
  (define (multiplier p) (car p))
  (define (multiplicand p) (cadr p))
  (define (deriv-product exp var)
    (make-sum (make-product (multiplier exp)
                            (deriv (multiplicand exp) var))
              (make-product (deriv (multiplier exp) var) 
                            (multiplicand exp))))
  ;;interface to rest of system
  (put 'deriv '+ deriv-sum)
  (put 'deriv '* deriv-product)

And to add a rule for differentiation of exponents we insert the appropriate code in the install-deriv-package (note that the code for sums and products has been omitted for clarity):

(define (install-deriv-package)
  ;;internal procedures
  (define (make-exponential base exponent)
    (list '** base exponent))
  (define (base e) (car e))
  (define (exponent e) (cadr e))
  (define (deriv-exponential exp var)
    (make-product (exponent exp)
                   (make-exponential (base exp) (- (exponent exp) 1))
                   (deriv (base exp) var)))) 
  ;;interface to rest of system
  (put 'deriv '** deriv-exponential)

The proposed new change at the end of the exercise can not be incorporated in the existing system additively. One way to introduce it would be to adopt a convention that the first argument to both get and put is the type of the expression, determined by the algebraic operator, and the second argument is the name of the procedure – deriv in our case. This would imply going over the existing code and changing get and put to meet the requirements of the new convention.

Exercise 2.74

Let’s have each division implement its own package. Each package should contain the necessary procedures to access and search the records specific to the division. Packages should also be responsible for installing these procedures into a global registry/table keyed under operation and division names. For example let’s consider a company with two divisions – division-1 and division-2:

(define (install-division-1-package)
  (let ((file '((Joe ((address town) (salary 123)))
                (Pooh ((address forest) (salary -1))))))
    ;;internal procedures
    (define (get-name record)
      (car record))
    (define (get-salary record)
      (cadr (assoc 'salary (cadr record))))
    (define (get-record employee-name)
      (define (search records)
        (cond ((null? records) #f)
              ((eq? employee-name (get-name (car records))) (car records))
              (else (search (cdr records)))))
      (search file))
    (define (tag x) (attach-tag 'division-1 x))
    ;;interface to rest of system
    (put 'get-record 'division-1
         (lambda (employee-name) 
           (let ((record (get-record employee-name)))
             (if record
                 (tag record)
    (put 'get-salary 'division-1 get-salary)

(define (install-division-2-package)
  (let ((file '((Bill ((salary 1000000) (address bigtown) (age 101)))
                (Boss ((salary 9876543) (address bigtown) (age 42))))))
    ;;internal procedures
    (define (get-name record)
      (car record))
    (define (get-salary record)
      (cadr (assoc 'salary (cadr record))))
    (define (get-record employee-name)
      (define (search records)
        (cond ((null? records) #f)
              ((eq? employee-name (get-name (car records))) (car records))
              (else (search (cdr records)))))
      (search file))
    (define (tag x) (attach-tag 'division-2 x))
    ;;interface to rest of system
    (put 'get-record 'division-2
         (lambda (employee-name) 
           (let ((record (get-record employee-name)))
             (if record
                 (tag record)
    (put 'get-salary 'division-2 get-salary)

Having this strategy in place we can define a generic get-record procedure that retrieves a specified employee’s record from the database of the corresponding division:

(define (get-record employee-name file)
  ((get 'get-record file) employee-name))

The implementation of the generic get-salary procedure relies on each retrieved record being tagged with the name of the division it comes from:

(define (get-salary record)
  ((get 'get-salary (type-tag record)) (contents record)))

Definition of the procedure find-employee-record:

(define (find-employee-record employee-name divisions)
  (if (null? divisions)
      (let ((record (get-record employee-name (car divisions))))
        (if (null? record)
            (find-employee-record employee-name (cdr divisions))

Adding a new division to this model would require implementing and installing a new package specific to the division. This can be done without making any changes to the existing system.

Exercise 2.75

Implementation of the constructor make-from-mag-ang in message-passing style:

(define (make-from-mag-ang r a)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          ((eq? op 'mag) r)
          ((eq? op 'ang) a)
          (else (error "Unkonown op -- MAKE-FROM-MAG-ANG" op))))

Exercise 2.76

Adding new operations to a system that uses generic operations with explicit dispatch can be done without any changes to existing code. However, adding a new type would require adding extra code to all procedures (operations) that can be performed on that type.

In the case of a system implemented in data-directed style, both adding new operations and new types can be done without changes to existing code.

A system implemented in message-passing style allows for addition of new types without changes to existing code. However, adding a new operation would require adding code to all existing types which have to support this operation.

For a system that will require a frequent addition of new types both data-directed style and message-passing style could be adequate choices.

On the other hand, for a system that will require frequent addition of new operations, either data-directed style or generic operations with explicit dispatch might be considered.

Read Full Post »

Should a programming language be small or large? A small programming language might take but a short time to learn. A large programming language may take a long, long time to learn, but then it is less hard to use, for we then have a lot of words at hand—or, I should say, at the tips of our tongues—to use at the drop of a hat. If we start with a small language, then in most cases we can not say much at the start. We must first define more words; then we can speak of the main thing that is on our mind.

… if you want to get far at all with a small language, you must first add to the small language to make a language that is more large.

… if I want to help other persons to write all sorts of programs, should I design a small programming language or a large one? I stand on this claim: I should not design a small language, and I should not design a large one. I need to design a language that can grow. I need to plan ways in which it might grow—but I need, too, to leave some choices so that other persons can make those choices at a later time.

… a main goal in designing a language should be to plan for growth. The language must start small, and the language must grow as the set of users grows.

… the key point is that in the bazaar style of building a program or designing a language or what you will, the plan can change in real time to meet the needs of those who work on it and use it.

Does this mean, then, that it is of no use to design? Not at all. But in stead of designing a thing, you need to design a way of doing. And this way of doing must make some choices now but leave other choices to a later time.

My point is that a good programmer in these times does not just write programs. A good programmer builds a working vocabulary. In other words, a good programmer does language design, though not from scratch, but by building on the frame of a base language.

… the sole way to win is to plan for growth with help from users.

Guy Lewis Steele Jr.

“Growing a Language”

Talk given at the 1998 ACM OOPSLA Conference



Read Full Post »

The Constitution on the United States is one of my favorite systems design. Think of it: millions and millions of mutually incompatible parts, running without completely breaking for more than 200 years. It’s pretty amazing, you can hold it in your hand. The reason you can hold it in your hand is they were wise enough to not put any laws in it. It’s not a law-based thing, it’s not a case-based thing, it’s a principle-based thing. It’s a kernel.

Alan Curtis Kay

“First Courses in Computing Should be Child’s Play”

Turing Award lecture, OOPSLA 2004



Read Full Post »

… the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them.

… there is a desperate need for a powerful methodology to help us think about programs, and no conventional language even begins to meet that need. In fact, conventional languages create unnecessary confusion in the way we think about programs.

For twenty years programming languages have been steadily progressing toward their present condition of obesity …

Discussions about programming languages often resemble medieval debates about the number of angels that can dance on the head of a pin instead of exciting contests between fundamentally differing concepts.

… basic defects in the framework of conventional languages make their expressive weakness and their cancerous growth inevitable, …

John Warner Backus

“Can Programming Be Liberated from the von Neumann Style?”

1977 Turing Award Lecture

Read Full Post »

Older Posts »