## **3.6 Summary**

The use of generic procedures introduced in this chapter is both powerful and dangerous—it is not for the faint of heart. Allowing the programmer to dynamically change the meanings of the primitive operators of the language can result in unmanageable code. But if we are careful to extend operators to only new types of arguments, without changing their behavior on the original types, we can get powerful extensions without breaking any old software. Most programming languages do not allow the freedom to modify the existing behavior of primitive operators, for good reason. However, many of the ideas here are portable and can be safely used. For example, in many languages, as diverse as C++ and Haskell, one can overload operators to have new meanings on userdefined types.

Extensions of arithmetic are pretty tame, but we must be aware of the problems that can come up, and the subtle bugs that can be evoked: addition of integers is associative, but addition of floatingpoint numbers is not associative; multiplication of numbers is commutative, but multiplication of matrices is not. And if we extend addition to be concatenation of strings, that extension is not commutative. On the good side, it is straightforward to extend arithmetic to symbolic expressions containing literal numbers as well as purely numerical quantities. It is not difficult, but lots of work, to continue to expand to functions, vectors, matrices, and tensors. However, we eventually run into real problems with the ordering of extensions—symbolic vectors are not the same as vectors with symbolic coordinates! We also can get into complications with the typing of symbolic functions.

One beautiful example of the power of extensible generics is the almost trivial implementation of forward-mode automatic differentiation by extending each primitive arithmetic procedure to handle differential objects. However, making this work correctly with higher-order functions that return functions as values was

difficult. (Of course, most programmers writing applications that need automatic differentiation do not need to worry about this complication.)

In our system the "type" is represented by a predicate that is true of elements of that type. In order to make this efficient we introduced a predicate registration and tagging system that allowed us to add declarations of relationships among the types. For example, we could have prime numbers be a subset of the integers, so numbers that satisfy the user-defined prime? predicate automatically satisfy the integer? predicate.

Once we have user-defined types with declared subset relationships, we enter a new realm of possibilities. We demonstrated this with a simple but elegantly extensible adventure game. Because our generic procedures dispatch on the types of all of their arguments, the descriptions of the behaviors of the entities in our adventure game are much simpler and more modular than they would be if we dispatched on the first argument to produce a procedure that dispatched on the second argument, and so on. So modeling these behaviors in a typical single-dispatch objectoriented system would be more complicated.

We used tagged data to efficiently implement extensible generic procedures. The data was tagged with the information required to decide which procedures to use to implement the indicated operations. But once we have the ability to tag data, there are other uses tags can be put to. For example, we may tag data with its provenance, or how it was derived, or the assumptions it was based on. Such audit trails may be useful for access control, for tracing the use of sensitive data, or for debugging complex systems [128]. So there is power in the ability to attach arbitrary tags to any data item, in addition to the use of tags to determine the handlers for generic procedures.

<sup>1</sup> ODE means "ordinary differential equation," meaning a differential equation with a single independent variable.

- 2 Because we anticipated varying the meanings of many operators in the MIT/GNU Scheme system, we made a special set of operators that name primitive procedures we might need later. We named the copies with the prefix n:. In MIT/GNU Scheme the original primitive procedures are always available, with their original names, in the system-global-environment, so we could have chosen to get them from there.
- 3 A recent Scheme standard [109] introduced "libraries," which provide a way to specify bindings of the free references in a program. We could use libraries to connect an arithmetic with the code that uses it. But here we demonstrate the ideas by modifying the read-eval-print environment.
- 4 The procedure pp prints a list "prettily" by using line breaks and indentation to reveal the list's structure.
- 5 You may have noticed that in these symbolic expressions the additions and multiplications are expressed as binary operations, even though in Scheme they are allowed to take many arguments; the installer implements the *n*-ary versions as nested binary operations. Similarly, the unary - is converted to negate. Subtractions and divisions with multiple arguments are also realized as nested binary operations.
- 6 The procedure default-object produces an object that is different from any possible constant. The procedure defaultobject? identifies that value.
- 7 Another difference you may have noticed is that the constantgenerator and operation-generator procedures for the numeric arithmetic have only one formal parameter, while the generator procedures for the symbolic extender have two. The symbolic arithmetic is built on a base arithmetic, so the constant or operation for the base arithmetic is given to the generator.
- 8 The call (any-arg 3 p1? p2?) will produce an applicability specification with seven cases, because there are seven ways that

```
this applicability can be satisfied: ((p2? p2? p1?) (p2? p1?
p2?) (p2? p1? p1?) (p1? p2? p2?) (p1? p2? p1?) (p1?
p1? p2?) (p1? p1? p1?))
```

- 9 disjoin\* is a predicate combinator. It accepts a list of predicates and produces the predicate that is their disjunction.
- 10 Making this arbitrary choice is not really reasonable. For example, a vector's zero is not only distinct from the numerical zero, but also is not the same for vectors of different dimension. We have chosen to ignore this problem here.
- 11 At the APL-79 conference Joel Moses is reported to have said: "APL is like a beautiful diamond—flawless, beautifully symmetrical. But you can't add anything to it. If you try to glue on another diamond, you don't get a bigger diamond. Lisp is like a ball of mud. Add more and it's still a ball of mud—it still looks like Lisp." But Joel denies that he said this.
- 12 A mechanism of this sort is implicit in most "object-oriented languages," but it is usually tightly bound to ontological mechanisms such as inheritance. The essential idea of extensible generics appears in SICP [1] and is usefully provided in tinyCLOS [66] and SOS [52].A system of extensible generics, based on predicate dispatching, is used to implement the mathematical representation system in SICM [121]. A nice exposition of predicate dispatching is given by Ernst [33].The idea that generic procedures are a powerful tool has been percolating in the Lisp community for decades. The fullest development of these ideas is in the Common Lisp Object System (CLOS) [42]. The underlying structure is beautifully expressed in the Metaobject Protocol [68]. It is further elaborated in the "Aspect-oriented programming" movement [67].
- 13 generic-metadata-getter and generic-metadatadefault-getter retrieve the get-handler procedure and the

- get-default-handler procedure from the dispatch-store instance stored in the metadata of the generic procedure.
- 14 The term *automatic differentiation* was introduced by Wengert [129] in 1964.
- 15 The derivative here is the derivative of a function, not the derivative of an expression. If *f* is a function, the derivative *Df* of *f* is a new function, which when applied to *x* gives a value *Df* (*x*). Its relation to an expression derivative is:

$$Df(t) = \frac{d}{dx}f(x)\Big|_{x=t}$$

- 16 The automatic differentiation code we present here is derived from the code that we wrote to support the advanced classical mechanics class that Sussman teaches at MIT with Jack Wisdom [121, 122].
- 17 Differential objects like these are sometimes referred to as *dual numbers*. Dual numbers, introduced by Clifford in 1873 [20], extend the real numbers by adjoining one new element *E* with the property *є* <sup>2</sup> = 0. However, in order to conveniently compute multiple derivatives (and derivatives of functions with multiple arguments) it helps to introduce a new infinitesimal part for each independent variable. So our differential algebra space is much more complicated than the single-*E* dual number space. Our differential objects are also something like the hyperreal numbers, invented by Edwin Hewitt in 1948 [59].
- 18 This idea was "discovered" by Dan Zuras (then of Hewlett Packard Corporation) and Gerald Jay Sussman in an all-night programming binge in 1992. We assumed at the time that this had also been discovered by many others, and indeed it had [129, 12], but we were overjoyed when we first understood the idea

- ourselves! See [94] for a formal exposition of automatic differentiation.
- 19 We will get to binary functions soon. This is just to make the idea clear before things get complicated. We will extend to *n*-ary functions in section 3.3.2
- 20 We are showing the definitions of handlers but we are not showing the assignment of the handlers here.
- 21 For an alternative strategy, see exercise 3.8 on page 113.
- 22 The procedure iota returns a list of consecutive integers from 0 through (length args).
- 23 The formal algebraic details were clarified by Hal Abelson around 1994, as part of an effort to fix a bug. The code was painfully reworked in 1997 by Sussman with the help of Hardy Mayer and Jack Wisdom.
- 24 A nicer version would use record structures, but that would be harder to debug without having a way to print them nicely.
- 25 The fact that any factor of any highest-order term in the series can be used was a central insight of Hal Abelson in the 1994 revision of this idea.
- 26 A bug of this class was pointed out to us by Alexey Radul in 2011. The general problem was first identified by Siskind and Perlmutter in 2005 [111]: the differential tags created to distinguish the infinitesimals incrementing an argument for a derivative calculation can be confused in the evaluation of a derivative of a function whose value is a function. The deferred derivative procedure may be called more than once, using the tag that was created for the outer derivative calculation. More recently, Jeff Siskind showed us another bug that plagued our patch for the first one: there was a potential collision between a tag occurring in an argument and a tag inherited from the lexical scope of a derivative function. These very subtle bugs are

- explained, along with a careful analysis of ways to fix them, in a beautiful paper by Manzyuk et al. [87].
- 27 This is carefully explained in Manzyuk et al. [87].
- 28 The trie data structure was invented by Edward Fredkin in the early 1960s.
- 29 The names printed for predicates by with-predicate-counts do not end in a question mark; for example the name printed for the predicate number? is simply number. The reason for this is obscure, and the curious are welcome to track it down in the code.
- 30 The procedure is-generic-handler-applicable? abstracts the handler checking that we previously did using predicatesmatch? in get-handler on page 98. This gives us a hook for later elaboration.
- 31 In languages such as Haskell and Smalltalk, multiple arguments are handled by dispatching on the first argument, producing an object that then dispatches on the second argument, etc.
- 32 The make-property procedure uses a helper called guarantee to do argument checking. The first argument to guarantee is a predicate (preferably a registered predicate) and the second argument is an object to be tested. There may be a third argument, to identify the caller. If the object doesn't satisfy the predicate, guarantee signals an error. The procedure guarantee-list-of works similarly except that it requires the object to be a list of elements satisfying the predicate.
- We have used assert earlier in this text. assert is more convenient for posing assertions that must be true where they are made. guarantee is preferable for the more restricted case of argument type checking.