Exercise 2.74 · 习题

Exercise 2.74: Insatiable Enterprises, Inc., is
a highly decentralized conglomerate company consisting of a large number of
independent divisions located all over the world. The company’s computer
facilities have just been interconnected by means of a clever
network-interfacing scheme that makes the entire network appear to any user to
be a single computer. Insatiable’s president, in her first attempt to exploit
the ability of the network to extract administrative information from division
files, is dismayed to discover that, although all the division files have been
implemented as data structures in Scheme, the particular data structure used
varies from division to division. A meeting of division managers is hastily
called to search for a strategy to integrate the files that will satisfy
headquarters’ needs while preserving the existing autonomy of the divisions.

Show how such a strategy can be implemented with data-directed programming. As
an example, suppose that each division’s personnel records consist of a single
file, which contains a set of records keyed on employees’ names. The structure
of the set varies from division to division. Furthermore, each employee’s
record is itself a set (structured differently from division to division) that
contains information keyed under identifiers such as address and
salary. In particular:

Implement for headquarters a get-record procedure that retrieves a
specified employee’s record from a specified personnel file. The procedure
should be applicable to any division’s file. Explain how the individual
divisions’ files should be structured. In particular, what type information
must be supplied?

Implement for headquarters a get-salary procedure that returns the
salary information from a given employee’s record from any division’s personnel
file. How should the record be structured in order to make this operation
work?

Implement for headquarters a find-employee-record procedure. This
should search all the divisions’ files for the record of a given employee and
return the record. Assume that this procedure takes as arguments an employee’s
name and a list of all the divisions’ files.

When Insatiable takes over a new company, what changes must be made in order to
incorporate the new personnel information into the central system?

Message passing

The key idea of data-directed programming is to handle generic operations in
programs by dealing explicitly with operation-and-type tables, such as the
table in Figure 2.22. The style of programming we used in
2.4.2 organized the required dispatching on type by having each operation
take care of its own dispatching. In effect, this decomposes the
operation-and-type table into rows, with each generic operation procedure
representing a row of the table.

An alternative implementation strategy is to decompose the table into columns
and, instead of using “intelligent operations” that dispatch on data types,
to work with “intelligent data objects” that dispatch on operation names. We
can do this by arranging things so that a data object, such as a rectangular
number, is represented as a procedure that takes as input the required
operation name and performs the operation indicated. In such a discipline,
make-from-real-imag could be written as

(define (make-from-real-imag x y)
(define (dispatch op)
(cond ((eq? op 'real-part) x)
((eq? op 'imag-part) y)
((eq? op 'magnitude)
(sqrt (+ (square x) (square y))))
((eq? op 'angle) (atan y x))
(else
(error "Unknown op:
MAKE-FROM-REAL-IMAG" op))))
dispatch)

The corresponding apply-generic procedure, which applies a generic
operation to an argument, now simply feeds the operation’s name to the data
object and lets the object do the work:

(define (apply-generic op arg) (arg op))

Note that the value returned by make-from-real-imag is a procedure—the
internal dispatch procedure. This is the procedure that is invoked when
apply-generic requests an operation to be performed.

This style of programming is called

message passing. The name comes

from the image that a data object is an entity that receives the requested

operation name as a “message.” We have already seen an example of message

passing in 2.1.3, where we saw how cons, car, and

cdr could be defined with no data objects but only procedures. Here we

see that message passing is not a mathematical trick but a useful technique for

organizing systems with generic operations. In the remainder of this chapter

we will continue to use data-directed programming, rather than message passing,

to discuss generic arithmetic operations. In Chapter 3 we will return to

message passing, and we will see that it can be a powerful tool for structuring

simulation programs.

练习 2.74：Insatiable Enterprises, Inc. 是一家高度分散化的跨国联合企业，由分布在世界各地的大量独立分部组成。公司的计算机设施刚刚通过一种巧妙的网络接口方案互连起来，使整个网络对任何用户看起来都像是一台单一的计算机。Insatiable 的总裁在首次尝试利用网络从各分部文件中提取行政信息时，沮丧地发现：尽管所有分部的文件都以 Scheme 中的数据结构实现，但各分部使用的具体数据结构因部门而异。一场分部经理会议被紧急召开，以寻求一种既能满足总部需求又能保留各分部现有自治权的文件整合策略。

说明如何用数据导向编程实现这样的策略。作为示例，假设每个分部的人事记录由一个文件组成，该文件包含以员工姓名为键的记录集合。记录集合的结构因分部而异。此外，每个员工的记录本身也是一个集合（各分部结构不同），其中包含以 address 和 salary 等标识符为键的信息。具体而言：

为总部实现 get-record 过程，用于从指定的人事文件中检索指定员工的记录。该过程应能适用于任何分部的文件。解释各分部的文件应如何组织。特别地，必须提供哪些类型信息？

为总部实现 get-salary 过程，用于从任何分部的人事文件中给定员工记录里返回薪资信息。记录应如何组织才能使此操作正常工作？

为总部实现 find-employee-record 过程。该过程应在所有分部的文件中搜索给定员工的记录并返回该记录。假设此过程以员工姓名和所有分部文件的表为参数。

当 Insatiable 收购一家新公司时，为了将新公司的人事信息纳入中央系统，必须作出哪些改动？

消息传递

数据导向编程的核心思想是：通过显式处理操作-类型表（如图 2.22 中的表），在程序中处理通用操作。2.4.2 节所用的编程风格通过让每个操作自行处理分派来组织所需的按类型分派——实际上，这是将操作-类型表按行分解，每个通用操作过程代表表的一行。

另一种实现策略是将表按列分解，不是使用“智能操作”对数据类型分派，而是使用“智能数据对象”对操作名分派。实现这一点的方法是：将数据对象（如一个直角坐标形式的复数）表示为一个过程，该过程以所需操作名为输入并执行相应操作。在这种规范下，make-from-real-imag 可以写成：

(define (make-from-real-imag x y)
(define (dispatch op)
(cond ((eq? op 'real-part) x)
((eq? op 'imag-part) y)
((eq? op 'magnitude)
(sqrt (+ (square x) (square y))))
((eq? op 'angle) (atan y x))
(else
(error “Unknown op:
MAKE-FROM-REAL-IMAG” op))))
dispatch)

相应的 apply-generic 过程将通用操作应用于参数，现在只需将操作名传递给数据对象，让对象自行完成工作：

(define (apply-generic op arg) (arg op))

注意，make-from-real-imag 返回的值是一个过程——内部的 dispatch 过程。当 apply-generic 请求执行某操作时，被调用的正是这个过程。

这种编程风格被称为消息传递 (message passing)。这个名称来自这样的形象：数据对象是一个实体，它接收所请求的操作名作为“消息”。我们在 2.1.3 节已经见过消息传递的一个示例——在那里，我们看到 cons、car 和 cdr 可以不用任何数据对象、仅用过程来定义。在这里我们看到，消息传递不是一种数学技巧，而是一种用于组织具有通用操作的系统的有效技术。在本章余下部分，我们将继续使用数据导向编程而非消息传递来讨论通用算术操作。在第 3 章，我们将回到消息传递，并看到它可以成为构建模拟程序的强大工具。