Can programming be liberated from the von Neumann style?
A paper written by John Backus in 1978. Available in pdf format from Stanford here.
In 1983, I was asked to read, study, analyse and comment on this important paper by Backus by some senior managers who were comfortable with Fortran (which John Backus created in 1954) and APL, who had heard well of, but were not conversant with Lisp, and, perhaps, who would be willing to play with LOGO.
My letter in May 9, 1983
In response to your request, here is perhaps a not too brief translation, with only a little bit of opinion at the end.
In the first part of the paper what Backus is proposing is a language (or a new class of languages) which does to Lisp what APL did to Fortran. For anyone not too familiar with Lisp, it would be instructive to learn the children's language LOGO, (a simplification of Lisp). In the meantime, think of LOGO as a language in which one may define many functions (programs) which may or may not have declared inputs and may or may not have an explicitly defined output. Each function definition may use within it any other defined function.
Now to understand Backus' language, conceive of a variant of LOGO whose function definitions do not use formal parameters, (i.e. declared inputs), yet whose functions always take an input and, without an explicit "OUTPUT", always generate an output.
Since the inputs are not defined, they may be arbitrarily large and complex (but structured just like "lists" in Lisp). Although functions are encouraged to accept as wide a variety of inputs as may be appropriate, there will obviously be some inputs which are outside of the domain of inputs which some functions know how to deal with; in this case the function generates a special output called "undefined". For example one function may invert a matrix. If given a matrix of any dimension, it will output the inverse; the function may even be generalized so that if given any number of matrices it will output the same number of matrices each an invert of its corresponding input matrix. If given something which is not a matrix, or given a sequence of objects of which only one is not a matrix, it will output "undefined".
Functions may be combined in various ways to create more powerful forms, for example, since each function takes an input and generates an output, two functions may be composed into a form where one function takes as input the output of another function. An example could be the invert-a-matrix function discussed above composed with itself where the result of applying the form to an input would result in the inverse of the inverse of a matrix.
All functions are defined as combinations of other functions using a small set of combination forming rules, with no reference at all to inputs or outputs. Starting with a small set of simple but powerful primitive functions that the system knows about and hence need not be defined by the programmer, and using the small set of combination forming rules, all the functions required for an application can be created by the programmer.
Since functions are mere combinations of other functions with no complicating references to inputs and outputs, a simple set of combination forming rules can be chosen that define a simple algebra. This allows, for example, taking an initial definition of a function, factoring it, and reducing it by combining common factors, replacing factors by simpler equivalents, etc., much as we do in simple high school algebra. This allows the algebraic proving of correctness of programs, that has been so elusive with existing languages, and by people who have a solid grasp of only high school algebra. (Unfortunately this excludes the majority of programmers today, but perhaps at BNR, a majority of our programmers would have this skill).
It also allows the proving of equivalence or nonequivalence of two functions and by the algebraic series expansion technique (remember in high school, 1/(1+x) = 1-x+x2-x3+. . . .) gives the ability to gain insight into nature of the function.
What I have described so far appears in sections 11 and 12 of the paper. Section 11 talks about a class, FP (functional programming), of languages and he gives a sample language with a set of about 14 primitive functions taken, with one exception, right out of standard Lisp primitives, and a set of 8 combination forming rules, 6 of which are basic and essential and 2 of which are questionable. Of the six basic rules all but one are APL-like and the exception is straight from Lisp (and is the important conditional construct). Obviously other languages in this FP class can be created by using different primitives and different forming rules, however one gets the feeling that the language chosen in the paper is at least the basic subset of the language Backus has spent some time evolving.
Section 12 shows the algebra that goes with the forming rules of his sample language and proves a number of fundamental theorems in that algebra that can then be used by the programmer to prove the correctness of his programs (function definitions). it also demonstrates the program proving for the (Lisp favourite) recursive "factorial” function definition, as well as several others.
In section 13 he expands the class of languages FP to a more powerful class he calls FFP. This extension adds concepts that in affect makes visible to the programmer the workings of an interpreter for the class FP. Specifically it shows how such an interpreter applies functions to objects, how defined functions may be represented in a real store and how objects and functions can be "named". In making these tools available to the programmer, the class of languages FFP now has the full power of Lisp where one may write a program that can actually write and then execute new programs, something that in reality some Lisp programmers do infrequently. What appears to have been lost in this step is the algebra and the program proving capabilities, shown in section 12 for languages of the FP class, for any programs which use those extensions. Perhaps this is an area that Backus is still exploring. It does, however give the capability to say some selected programmers to write an interpreter, to write programs that modify FP programs (FP programs cannot modify themselves, but FFP programs can), or more enticing perhaps, to write analyzers that can do FP language program proving.
Finally in section 14, he proposes using an FFP language to create a class, AST, of systems that are state transition systems. These are systems that have a "history" as he calls it or that "know where they are" as a result of sequences of inputs from an environment. This is clearly essential for something like a telephone switching system or anything else that acts based on something remembered, such as airline reservation systems, or in fact anything that maintains some data between major steps for some subsequent use. The advantage of the AST class of systems is the ability to write FP style programs to implement the "major steps" and let the state transition system take care of the "history". In fact the FP style programs for the major steps generate two outputs, one of which is the "next state" for the state transition system and the other is all the other required outputs. This leads us closer to the dream of being able to write a single equation for a switching system instead of a huge collection of interrelated programs. With this approach we could write a collection of equations, one for each major step.
Ideally one would pick an FP language, extend it to an FFP, use the FFP to build an AST framework and then let programmers write provable FP functions to implement the "major steps or state transitions. However Backus defines "next states" to be captured by changing appropriately the function definitions. Whether that technique is used or a reference to “named" data is used, both these techniques are available only in FFP and if all the transitions are written in an FFP language then they are no longer provable. (FFP languages are also more difficult conceptually and will either lead to more errors or require programmers with higher conceptual ability). Either provability of FFP languages needs to be attained or FP windows into FFP capabilities need to be created; both may be impossible.
The paper is tantalizing and represents good original thinking and a significant body of research. The concepts are powerful and the premise can have significant impact, however there is more research to be done and perhaps Backus and his team are working it. There are two things BNR could do: the first is pick up where the paper leaves off and mount a small independent research activity and the second is to explore further the state transition nature of call processing via CCITT SDL techniques.
Thank you for bringing this paper to my attention, it is truly thought provoking.
© E. Bierman, May 9, 1983
P.S. There is also a summary of the paper provided by the author in his section 16.
P.P.S. LOGO is available for Apple II computers through Apple dealers.
May 1983
