SICP 2.4.3 Solutions

May 24, 2015 10:44

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), that 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 allows for greater 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 (which 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 and they’d have to remain how they were. 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. Since the personnel file is said to vary by division, once we have a file we must be able to determine which division it is from in order to process it properly. I made that a hard requirement: the personnel files must have some way that they can be identified, and the means of 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.

If for some reason the personnel files can’t be changed, one method might be a ‘container file’ that could be created to hold the division ID along with the personnel file. An alternate approach, however, would be to pass a division-specific procedure to get-record along with the file as an argument. Then the files are simply referenced by division in the table. I happen to think this might be a better way than what I went with, but only thought of it while writing up this post. Of course this still requires a unique identifier for the divsion, but the difference is that the identifier can be determined at the company level, rather than stored in the division’s details (imagine what would happen if a new division is added that wants to keep their division name, but it’s identical to an existing one).

Once the division is known, a dispatch table can be used to find which operation to use. This table stores for each personnel file a procedure 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 company, i.e. all employee names are unique. Such is the case in my small example.

The second part of the exercise is somewhat confusingly stated. It was already assumed that each division structures its employee records in a different fashion, so I’m not sure what requirements should be placed on that structure now. Unless that was the point of the question. The way I see it, the employee records have no requirements on them other than that they actually have information about the salary. All that is needed is that each division has its own procedure that can determine the salary, given a record. I intentionally did not provide one for the Scranton division in my example, but can be based on what get-record returns, and is just the car of that.

The procedure find-employee-record is perhaps the most straightforward, assuming that get-record returns a value of ‘false’ if no employee is found in that file. Then the procedure can just iterate over the list of files:

(define (find-employee-record employee file-list)
  (if (null? file-list)
      (let ((found-record (get-record employee (car file-list))))
        (if 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.

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 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.

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)) 
           (error "Unknown op -- MAKE-FROM-MAG-ANG" op))

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. This also shows a slight advantage to using the checks in the test framework, as they do not rely on anything being printable in order to determine its correctness.

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