Dijkstra's Unifications versus the Case Distinctions of Irons & Feurzeig

Dated: 

1960

Toward the end of my paper `Dijkstra's Rallying Cry for Generalization ...' I briefly describe the work of Irons and Feurzeig. These two men had by 1960 also implemented ALGOL60's recursive procedure just like Dijkstra and Zonneveld. Their solution, however, was very different from the solution proposed by Dijkstra and Zonneveld.

In the Dijkstra-Zonneveld approach, no check was made during program execution to determine whether an activated procedure P was called a second time or not; that is, was recursive or not. Therefore, whenever P was to call another procedure Q, the conservative assumption was made that P was recursive and, hence, would be called again later. As a result, all the local variables and arrays of P had to be placed on the software stack prior to calling Q such that they could retain a unique identity for the special recursive case that the procedure were to be called again. In the Irons-Feurzeig run-time system, such expensive stack management was only carried out after it was determined that P would be called more than once.

The Irons-Feurzeig approach was hybrid in that the compiler assigned fixed storage to each procedure prior to program execution but, when, at run time, their system detected that a procedure was called upon for a second time, then that procedure would be treated dynamically; that is, it's data would be transferred to the general run-time stack in line with the Dijkstra-Zonneveld approach.

Irons and Feurzeig's run-time specialization was implemented by using several case distinctions. A first example is obviously the distinction that was made between recursive and non-recursive procedures. A second example is the distinction Irons and Feurzeig made between blocks and procedures. In their words:

Since a block cannot be entered more than one time without an intervening exit, unless it is contained in a recursive procedure, it suffices to maintain a counter only for each procedure, rather than for all blocks as well.

Dijkstra would have treated procedures and blocks in a unifying manner, not distinguishing between the two even if this came at the price of machine efficiency. A third example concerns the distinction between self-recursive procedures and procedures that are indirectly recursive. Irons and Feurzeig noted that by making this distinction, further optimizations could be achieved in terms of machine efficiency.

The several case distinctions in the Irons-Feurzeig run-time system were, from Dijkstra's point of view, unneeded sophistication. From an efficiency-driven perspective, however, the Irons-Feurzeig approach was outstanding in that it not only provided fast ALGOL60 programs, but it also did so without having to restrict the ALGOL60 language.

Tags: 

1 Comment

recursion contradictions

At the end of EWD 450 Dijkstra casts doubt upon recursion, and I don't understand why someone would want to build a compiler with a feature that people rarely ever use.. In Wirth's latest compilers (oberon) he removes features that are not used much. When people need to use the feature, it isn't there. It's a compromise issue.

http://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD450.html