The recursive procedure as a single semantic level.

Dijkstra was in favor of several kinds of abstraction, one of which is operational abstraction. This kind of abstraction is best illustrated by means of the subroutine concept.

In the relation between main program and subroutine we can distinguish quite clearly two different semantic levels. On the level of the main program the subroutine represents a primitive action; on that level it is used on account of "what it does for us" and on that same level it is irrelevant "how it works". On the level of the subroutine body we are concerned with how it works but can --and should-- abstract from how it is used. [EWD302]

But when dealing with a recursive procedure, the two semantic levels "what it does" and "how it works" overlap. This observation, in turn, explains why a different mental skill is required when writing a recursive procedure. [EWD302]

Tags: 

3 Comments

Links to EWDs

It would be nice if the EWDs that are cited are also linked (probably to PDF at the UTAustin's EWD Archive). One can then immediately check it out. 

Difficult?

The snippet that leads one to this post asks "Why, exactly, is programming a recursive procedure difficult?". But the post itself does not make any reference to the "difficulty", instead just alludes to the need for a "different mental skill". They are not the same. In fact, an essential argument for declarative programming is that it is easier to program in a recursive manner, than to avoid it, particularly when it's natural to express the solution recursively. If this post was somehow intended to point out Dijkstra's take on declarative programming, I hope a subsequent post will elaborate the point.All this, unless you mean something else by "programming a recursive procedure". 

Difficult?

Great point! Your comment on declarative programming is well taken. The context here is imperative programming: ALGOL60, ALGOL68, PL/I, Pascal, etc.  "Programming a recursive procedure" alludes to any of the aforementioned programming languages and ALGOL60 in particular. (Check out my paper "Dijkstra's Rallying Cry..." for more context on this particular topic.)

In declarative programming, the programmer describes what computation should be performed, not how. In imperative programming, a good programmer (according to Dijkstra and others -- anno 1971) separates the "what" from the "how" by means of operational abstraction (cf. subroutines, procedures). This separation of concerns is, however, not possible when dealing with a recursive procedure: both the "what" and the "how" are intertwined in this case. That is, when programming a recursive procedure imperatively, one has to deal with both concerns together. In this sense, it makes the job of the programmer harder. And, indeed, one does not have this problem when programming recursively in a declarative language.