Ex 2.73

The data-directed derivative operation simplifies the deriv procedure, and allows for a more modular system. Instead of having a conditional statement that must be modified every time a new operation is added, all expressions involving operators are handled by the dispatch table. This makes it easy to add new operators to the table and to modify the existing ones by simply changing the table entry.

Numbers and variables are not handled by the dispatch table, because the dispatch operation requires expressions in the form of (operator operands) — which is to say a list or pair. Changing this would require changing the expression format, so that every number or variable would require a ‘type’ tag, and make the expressions overly complex. This demonstrates that although the data-directed method does allow for a lot of flexibility, the interface must still remain consistent, and this does impose some restrictions on what can be used in the table.

For part b, I made a slight change to the accessors for the math operators. Rather than operating on an expression, they operate on a list of operands (again, since that is what the dispatch table uses). As with the original operators, these are restricted to two arguments only. It is conceivable that an existing system might impose the restriction that the accessors cannot be changed at all, and they’d have to remain how they were but still use the table. I leave how to accommodate this as an extended exercise.

In part c, I extended the system using exponentiation according to the power rule (assuming integer exponents). The resulting derivative procedure looks like this:

(define (deriv-exponentiation operands var)
  (let ((u (base operands))
        (n (exponent operands))
        )
    (make-product (make-product n
                                (make-exponentiation u (- n 1))
                                )
                  (deriv u var)
                  )
    )
  )

This relies on the constructors and accessors for exponentiation, which can be defined as desired. The symbol for exponentiation is the only thing then required for insertion into the table, which must be the same used by make-exponentiation in creating expressions. In theory multiple entries in the dispatch table could map to the same operation (e.g. both ‘X’ and ‘*’ could indicate multiplication), but the constructors can only create expressions of one type.

The final part asks what needs to change if the order of arguments to get are altered. Since our table allows for ‘type’ and ‘operator’ to be anything, there will be no problem if the values are stored in the table in that fashion. The only required change is to the installation of the operations (calls to put) so that they match the new ordering.

Ex 2.74

When I created a rudimentary version of the system in question, I made some assumptions about what information is required, and how it might be presented. You may have interpreted the questions differently, as they are intended to provoke consideration before actually encountering a working system. Multiple systems might well be operating on another set of assumptions entirely. As it is, I’m only able to talk about my approach to the system I created.

The first procedure required is get-record, which will retrieve an employee record from a personnel file. We have to stop and ask exactly what is this ‘record’ being returned. There is seemingly deliberate confusion in the problem statement, as it states that employee records are structured differently from division to division, but then asks how the records must be structured for the implementation to work. One approach might be to construct a new high-level ‘record’ from the information stored in the disparate divisions. Another is to keep track of the division from which the record was retrieved, in order to know how to properly access it.

My solution goes with the option of keeping track of the division. I made it a hard requirement that the personnel files (not necessarily the records) must have some way that they can be identified by division, and the interface to finding it must be the same for all of them. I call this ‘division-ID’, on the basis that using a unique identifier for each division makes the most sense here as new divisions are added or each one changes its own implementation. There are other approaches that could work, such as a different procedure call interface, or a higher-level table storing the division ID instead of keeping it in the division files. The latter is arguably a better approach than what I did, although I have kept what I wrote as it is.

Once the division is known, a dispatch table can be used to find which operation to use. This table stores a procedure for each personnel file that will retrieve a given employee’s record, given their name. The exercise kind of implies that an employee’s name is sufficient to identify them throughout a division or the entire company, i.e. all employee names are unique. Such is the case in my small example.

Using this approach the employee records have no requirements on them other than that they actually have information about the salary. Then each division has its own procedure that can determine the salary, given a record from that division. As a result, my version of get-salary takes both the record and the personnel file as arguments, since the personnel file is needed to determine how to access the record.

The procedure find-employee-record is perhaps the most straightforward. It depends on get-record returning a value of ‘false’ if no employee is found in the file passed to it. With that approach, it can just iterate over the list of files until something returns true:

(define (find-employee-record employee file-list)
  (if (null? file-list)
      false
      (let ((found-record (get-record employee (car file-list))))
        (if found-record
            found-record
            (find-employee-record employee (cdr file-list))
            )
        )
      )
  )

It’s get-record that makes use of the data-driven methods, allowing the same procedure call to lead to a (possibly) different eventual method of retrieval for each division. To use it across different files, I also added a ‘find-first’ procedure that will apply a predicate to every member of a list, and return the first non-false value. By having negative results return false for the whole division, this will end the search as soon as a valid match is found.

When a new company (or division) is taken over, suitable procedures for record and salary retrieval are required within the division. Their arguments must match the ‘signature’ already used in the dispatch table. Additionally, the division-id information must be somehow added to the new company’s personnel file, or the aforementioned container approach must be used to store it. This is another reason why I would favor the alternative of storing division files in the table and using the divsion id as a table-level identifier; adding a new division is just a matter of adding the division file and its associated procedures to the table under the proper identifier, rather than modifiying the division records themselves.

Ex 2.75

Using message-passing for magnitude-angle complex numbers is fairly easy to implement by following the example of the real-imaginary numbers. Almost everything is the same, except that within the internal dispatch procedure, we use the operations using the magnitude r and angle a to calculate results.

(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 'magnitude) r)
          ((eq? op 'angle) a)
          ((eq? op 'print) (printf "~a e ^ (i ~a)" r a)) 
          (else
           (error "Unknown op -- MAKE-FROM-MAG-ANG" op))
          )
    )
  dispatch
  )

Because this number can receive the same messages as a real-imaginary number, we observe that the exact same procedures can be used to access the values. That makes it possible for all the math operations, and all our previous tests, to function exactly as before. Just as with the dispatch table, or with the previous explicit decisions on which implementation to use, the procedures that make use of the numbers are abstracted from knowing what they’re doing underneath. The difference here is that each number is a self-contained item, that determines ‘for itself’ how to execute the procedure.

One thing that does change with the message-passing numbers is that the numbers can no longer be displayed directly. For this reason, I added a ‘print’ message that allows for them to be displayed in readable format. It’s not actually required using the checks from the test framework, as they do not rely on anything being printable in order to verify correctness. A possibly better approach would be a ‘as-string’ method that returns the number in a formatted string, so that it could then be modified for printing, instead of printed immediately when the message is received.

Ex. 2.76

Looking back at the explicit dispatch approach, we see that even though it allows for an abstract interface, it becomes unwieldy when the system is expanded. Adding a new type, in general, requires changing all procedures that might make use of it so that they’re aware of it. Adding an operation requires adding procedures for each type that uses it, and an additional change to the places that dispatch to it, in order for them to decide which type to use.

The data-directed approach lets us add new types by adding entries to the table for that type, which has no effect on the other types in the table. Adding a new operation is essentially the same – the new operation just needs to be added to the table for each type that can use.

With message passing, each new type is its own entity. Types implement all their own operations, and adding types is just a matter of writing up the creation routine for that type. If a new operation is required, however, the type creation routine needs to be rewritten for all types that use it.

Looking at just these alternatives, the message-passing approach is the easiest for adding new types. New operations can be added most easily with the data-directed approach. There’s a slight ceding of control once we are no longer making the dispatch explicit, but the flexibility allowed by these methods makes them easier to use.

In the broader context of object-oriented languages, most of the time what we call objects operate in a message-passing fashion (where an object is the entity that determines how to respond to messages). Most languages make the constructors and message-passing interface a bit easier to deal with, and some even allow for dynamic changes to the allowed operations. Data-directed methods aren’t often used at a high level (or if they are, it’s with a limited set). This is often because there is a degree of care required in making sure the centralized table structure works properly, as a problem there affects every element of the system relying on it.

Solutions 2.4.3