From Wikisource
Jump to: navigation, search
This page has been proofread, but needs to be validated.
Guy L. Steele Jr.
LAMBDA: The Ultimate Declarative

On pages 8–9 of Dijkstra's excellent book [Dijkstra 76] he says: "In a recent educational text addressed to the PL/I programmer one can find the strong advice to avoid procedure calls as much as possible 'because they make the program so inefficient'. In view of the fact that the procedure is one of PL/I's main vehicles for expressing structure, this is a terrible advice, so terrible that I can hardly call the text in question 'educational'. If you are convinced of the usefulness of the procedure concept and are surrounded by implementations in which the overhead of the procedure mechanism imposes too great a penalty, then blame these inadequate implementations instead of raising them to the level of standards!" {Note GCD(111,259)}
This marvelous passage occurs on page 4 of [Dijkstra 76]:

"Instead of considering the single problem of how to compute the GCD(111,259), we have generalized the problem and have regarded this as a specific instance of the wider class of problems of how to compute GCD(X,Y). It is worthwhile to point out that we could have generalized the problem of computing GCD(111,259) in a different way: we could have regarded the task as a specific instance of a wider class of tasks, such as the computation of GCD(111,259), SCM(111,259), 111*259, 111+259, 111/259, 111-259, 111<super>259</super>, the day of the week of the 111th day of the 259th year B.C., etc. This would have given rise to a '111-and-259 processor' and in order to let that produce the originally desired answer, we should have had to give the request 'GCD, please' as its input! ...

"In other words, when asked to produce one or more results, it is usual to generalize the problem and to consider these results as specific instances of a wider class. But it is no good just to say that everything is special case of something more general! If we want to follow such an approach we have two obligations:

  1. We have to be quite specific as to how we generalize ...
  2. We have to choose ('invent' if you wish) a generalization which is helpful to our purpose."

The IF-THEN-ELSE construct can be expressed rather clumsily in terms of sequencing and WHILE-DO by introducing a control variable; this is described by Bob Haas in [Presser 75]. A general discussion of the relative complexities of various sets of control structures appears in [Lipton 76].

Hewitt has performed similar experiments on PLASMA programs [Hewitt 76], by converting PLASMA programs to a form which uses only ==> and <== transmission arrows. A subsequent uniform replacement of these arrows by => and <= preserves the semantics of the programs.

{Note PLASMA Reduction}
Since this was written, there were two changes to the PLASMA implementation. The first, in mid-summer, was a change in terminology, in