The Essence of Algol

Elsewhere [10] I considered ways in which programming languages could be different. One of these ways is expressed by asking the question Does the language have an essence? The possibility of an affirmative answer is suggested by the title of John Reynolds’s paper: “The essence of Algol” [7]. Reynolds used what he perceived to be the essence of Algol to make distinctions among members of what is usually considered to be a single family. Thus he argues that Algol 60 is a carrier of the essence, whereas this is not the case for other members of that family: Algol W, Euler, Algol 68, and Pascal.

What is judged to be essence is in the eye of the beholder. I am more interested in what the members of the Algol family have in common and perhaps even with languages not usually considered as members. For example, Prolog. Soon after completion of this language in Marseille, Robert Kowalski wrote a paper (published as [6]) that established a procedural interpretation of a form of first-order predicate logic. Let us examine this interpretation to see whether this gives a hint concerning the essence of Algol as a procedural language.

 

Kowalski considered logic in the form of clauses, with resolution as inference rule. A clause is a set of atomic formulas, each possibly negated. Here is an example of a clause with three atomic formulas, two of which are negated:

{sibling(X,Y), ~parent(Z,X), ~parent(Z,Y)}

A Horn clause is a clause with at most one unnegated formula. It is a positive Horn clause if there is such a unnegated formula, as is the case here. These are of special interest because they can be read as a rule with a conclusion followed by zero of more conditions. The above example can be read as

sibling(X,Y) if there exists Z such that
parent(Z,X) & parent(Z,Y)

which actually makes sense if one accepts half brothers and half sisters as siblings. Note the “there exists” qualifying the variable Z that occurs in a condition, and not in the conclusion.

Another example, more typical of programming, is the Horn clause

sort(X,Y) if there exist X1, X2, Y1, Y2 such that
split(X, X1, X2) &
sort(X1, Y1) & sort(X2, Y2) &
merge(Y1, Y2, Y)

In his paper [6]) on the procedural interpretation of Horn clauses, Kowalski pointed to the following similarities:

  • A positive Horn clause looks like a procedure declaration, with the positive atomic formula as procedure heading and possibly present negated atoms as procedure body.
  • A negative Horn clause looks like a set of procedure calls.
  • A resolution inference step looks like the execution of a procedure call. In general, resolution combines a negated atom with an unnegated one. Within a set of Horn clauses, resolution combines a procedure call (a negated atom) with the head of a procedure declaration (an unnegated atom). The unification that comes with the resolution matches the formal parameters of the procedure heading with the actual parameters of the call.

Kowalski claimed that these similarities showed not only that logic can be a programming language, but even a procedural one. At this point in the argument a typical member of Kowalski’s IFIP 74 audience must have dismissed the claim as preposterous: surely something more than definitions and calls to procedures is needed to make a procedural programming language. What about branching? What about iteration? According to Kowalski a program would never do anything but call procedures. Of course procedures were widely acknowledged to help in organizing one’s code. But, from the conventional point of view, a procedure is overhead in the sense that it postpones the computation that is the purpose of the code. A logic program would forever be calling procedures and would anything ever happen?

The punch line of Kowalski’s paper [6]) is the observation that a language such as the one he described actually existed [1]. By the time the paper was published in 1974, this language had been used to

  • write a program for man-machine communication in natural language,
  • write a program for symbolic computation,
  • write a program for robot plan formation,
  • implement a compiler for a toy-size imperative programming language, and
  • implement a sizeable part of its own translator.

That language is Prolog.

Kowalski’s characterization can be regarded as the view that logic is the essence of at least one procedural language. If logic is the essence of one procedural language, could it be that it is the essence of another one, for example Algol? To see if this is the case let us see what happens if one removes inessential features from Algol. In choosing what to eliminate I will be guided by what would make Algol more like Prolog.

In spite of its succinct definition in 34 pages [6a], Algol 60 is a deep and complex affair [7,8]. This mainly because of its call-by-name parameter mechanism. Here I make a drastic simplification: only allow actual parameters that are primitive data: Booleans, integers, and reals. In this way labels, procedure names, and arrays are excluded. What remains I call “first-order Algol”. Furthermore, to keep things simple, I assume that procedures are closed, that is, names in procedure bodies name either local variables or formal parameters.

To get at the essence, let us consider what remains of first-order Algol after we omit those of its features that are replaceable.

  • Labels and goto statements are an easy victim—this topic has been debated exhaustively after Dijkstra’s letter [2].
  • Replace “if…then” and “if…then else…” by the “if…fi” of Dijkstra’s guarded-command language [3]. That this does not entail an undue limitation of expressiveness is amply substantiated by [4].
  • Replace iteration by (tail) recursion.
  • Eliminate function procedures: results can be returned by parameters.

Is there anything left? Yes, declarations of and calls to procedures. Aren’t they dispensable as well? Of course they are. This is proved by the first Fortran and by other pre-Algol languages. But here I am concerned with procedural languages.

My next step is to replace “if…fi” with the help of Floyd’s proposal [5] for introducing nondeterminism into imperative languages. The following quote summarizes the proposal.

Nondeterministic algorithms resemble conventional programs as represented by flowcharts, programming languages, machine-language programs, etc., except that

  1. One may use a multiple-valued function, choice(X), whose values are the positive integers less than or equal to X. (Other multiple-valued functions may be used, but this one is adequate.)
  2. All points of termination are labeled as successes or failures.

Floyd’s goal was to be applicable to flowcharts as well as to programs written in machine language or in a high-level language. As we want to do as much as possible with procedures, Floyd’s “points of termination” are returns from procedures. There must be two kinds of return: successful and failed. We can identify the conventional return with success. We add a statement of the form

if <condition> FAIL

to return with failure. When a procedure p calls a procedure q that returns with failure, then p itself returns with failure.

After this detour into nondeterministic primitives, we return to what to do with the branching of Algol. We already proposed to replace it by the if…fi of Dijkstra’s guarded-command language. In turn we propose to replace this in a way that we illustrate with the example:

if G1 -> B1 | G2 -> B2 fi

where G1 and G2, the guards, are Boolean expressions and B1 and B2 are statements, possibly compound. To eliminate if…fi, we replace this example of the alternative construct by the procedure call p(…) and add the declarations for the new procedure name p:

p(…) { if (not G1) FAIL; B1 }
p(…) { if (not G2) FAIL; B2 }

Note that these are two declarations with identical procedure headings. The effect of a call to procedure p is the usual one, except it is left undetermined which of multiple matching declarations responds to the call. In this way we replace Floyd’s nondeterministic operator choice(X) by defining procedure call as the nondeterministic operator.

With these changes in place, first-order Algol has reached the degree of similarity to Prolog that I aimed at. The above declarations in this version of Algol correspond to the Prolog declarations

p(…) :- G1, B1.
p(…) :- G2, B2.

where the arguments in each heading are pairwise different variables.

The semantics of a deterministic procedure is a function from states to states. The semantics of a nondeterministic procedure is a multivalued function from states to states; that is, it is a relation on states. With the assumption that procedures be closed, the behaviour of a procedure p is characterized by the values of the actual parameters after completion of a successful call. In first-order Algol these values are restricted to be Booleans, integers, or reals. Each possible terminating successful call to procedure p contributes one n-tuple (or, because of the possibility of nondeterminism, more n-tuples) to the relation that is the proposed meaning of p. Thus the special case of Algol 60 represented by first-order Algol was already in 1960 a method of defining n-ary relations by mutual recursion. I’m not sure how one would go about this task when given only conventional mathematical notation and the axioms for set theory.

It may be that Algol 60 represented an innovation in this respect. What, apart from conventional mathematical notation, do we have in addition to Algol as formalism for talking about n-ary relations? There is a simple and widely known such formalism, first-order predicate logic: the semantics of a predicate with n free variables is an n-ary relation over the domain of discourse. This logic therefore seems the natural home for the definition of n-ary relations. <!– I would be interested in hearing about such a method that dates from before 1974. I mention this year because that is the year Kowalski published [6]. –> Among other things, Kowalski’s paper [6] describes the formal use of first-order predicate logic for defining n-ary relations, possibly recursive, possibly mutually so.

Thus we have at least two formalisms for the definition of relations, Algol 60 and logic, in chronological order. Of course there may be more. But why would one need any formalism? Can’t we just use the informal mathematics in which the Zermelo-Fraenkel axioms for set theory are expressed? Relations are defined as subsets of Cartesian products. To justify the existence of such subsets one appeals to the Axiom of Separation. This axiom uses a formula of first-order predicate logic. Thus it appears that for the definition of relations one can’t get around logic. Apparently Kowalski did not add logic as just another formalism in which relations can be defined: he was down to bedrock.

Yet Kowalski only defined relations over Herbrand universes. His predecessor in the definition of relations, Algol 60, defined relations over Booleans, integers, or reals. That stimulates my interest in defining relations over arbitrary data types. This has resulted in [9]. This paper relies on logic more than it turned out to be necessary. Subsequent work gives informal set theory an important role, but formal logic still plays a part.

We started out looking for an Essence of Algol in an inclusive sense, looking for a characterization of Algol that was shared as much as possible by subsequent procedural languages. Prolog is a suitable sample for comparison because it is, as characterized by Kowalski, the most extreme procedural language. I argued that that which unites all procedural languages is that they define n-ary relations in definitions that may be recursive and possibly mutually so. Therefore the essence of Algol is shared with other procedural languages and consists in their being formalisms for the definition of relations. Thus relations play the role in procedural languages that is played by functions in functional programming languages. Procedural languages are relational programming languages.

In this sweeping conclusion I left some loose ends. For example, I considered using Algol without branching and iteration, but what about assignment? I left that in, while Prolog does not have assignment. Also, I assumed that the behaviour of a procedure is characterized by the tuples of values of the actual parameters upon successful completion. However, this is getting rather long. Another time, perhaps.

Acknowledgements

I am grateful to Paul McJones for his valuable suggestions.

References

[1] Alain Colmerauer: “Un système de communication homme-machine en Français” http://tinyurl.com/j4fknrf consulted October 14, 2016.
[2] E.W. Dijkstra: “Goto statement considered harmful.” Communications of the ACM 11.3 (1968): 147-148.
[3] E.W. Dijkstra: “Guarded commands, nondeterminacy and formal derivation of programs.” Communications of the ACM 18.8 (1975): 453-457.
[4] E.W. Dijkstra: A discipline of programming. Prentice-Hall, 1976.
[5] Floyd: “Nondeterministic algorithms.” Journal of the ACM (JACM) 14.4 (1967): 636-644.
[6] R.A. Kowalski: “Predicate logic as a programming language”. Proceedings of IFIP 1974, North-Holland, pp. 569-574.
[6a] Peter Naur (editor): “Revised report on the algorithmic language Algol 60.” Numerische Mathematik 4.1 (1962): 420-453.
[7] John C. Reynolds: “The Essence of Algol”. In Jaco W. de Bakker and J. C. van Vliet, editors, Algorithmic Languages, pp. 345-372. North-Holland, Amsterdam, 1981.
[8] Gauthier van den Hove: “Dissolving a Half Century Old Problem about the Implementation of Procedures”. To appear Science of Computer Programming. http://www.fibonacci.org/GHE8.pdf
[9] M.H. van Emden. “Logic programming beyond Prolog”.
https://arxiv.org/pdf/1412.3480.pdf
[10] M.H. van Emden: “Kinds of programming languages”. http://tinyurl.com/j99lqlz

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: