THE BLOG
08/13/2013 12:00 pm ET Updated Oct 12, 2013

What Is the Worst Mistake Ever Made in Computer Programming?

This question originally appeared on Quora.
2013-08-13-cperepelitsa.jpeg
Answer by Costya Perepelitsa, Software Developer

Over-reliance on the von Neumann model in our design of computers and programming languages.

(This may be better recognizable today as the "imperative vs functional programming" debate.)

This was argued by John Backus (inventor of FORTRAN and Backus-Naur Form) when he received the ACM Turing Award in 1977 for "profound, influential, and lasting contributions to the design of practical high-level programming systems".

This answer will simply be highlights of his 29-page Turing Award lecture (2.9 MB PDF) titled: "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs".

First, the beginning of the abstract:

Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of program- ming inherited from their common ancestor--the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.

An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high level programs to build still higher level ones in a style not possible in conventional languages.

Some choice quotes from the paper follow. Backus refers to (what we would now call) imperative languages as "conventional" languages and "von Neumann" languages/models interchangably, so I'll make that substitution where appropriate. All emphasis (bold text) has been added by me:

  • "there is a desperate need for a powerful methodology to help us think about programs, and no [imperative] language even begins to meet that need. In fact, [imperative] languages create unnecessary confusion in the way we think about programs."
  • "Surely there must be a less primitive way of making changes in the store than by pushing vast numbers of words back and forth through the von Neumann bottleneck... it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking... programming [in imperative languages] is basically planning and detailing the enormous traffic of words through the von Neumann bottleneck... Combining single words is not what we really should be thinking about, but it is a large part of programming any task in von Neumann languages."
  • "The assignment statement is the von Neumann bottleneck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer's bottleneck does"
  • "the assignment statement splits programming into two worlds. The first world comprises the right sides of assignment statements. This is an orderly world of expressions, a world that has useful algebraic properties (except that those properties are often destroyed by side-effects). It is the world in which most useful computation takes place. The second... is the world of statements... This world of statements is a disorderly one, with few useful mathematical properties. Structured programming can be seen as a modest effort to introduce some order into this chaotic world, but it accomplishes little in attacking the fundamental problems created by the word-at-a-time von Neumann style of programming, with its primitive use of loops, subscripts, and branching flow of control... the split between the two worlds prevents the combining forms in either world from attaining the full power they can achieve in an undivided world."
  • "[an imperative] language must have a semantics closely coupled to the state... Thus every feature of [an imperative] language must be spelled out in stupefying detail in its framework. Furthermore, many complex features are needed to prop up the basically weak word-at-a-time style. The result is the inevitable rigid and enormous framework of [an imperative] language."
  • "Perhaps the most important element in providing powerful changeable parts in a language is the availability of combining forms that can be generally used to build new procedures from old ones. [Imperative] languages provide only primitive combining forms, and the von Neumann framework presents obstacles to their full use."
  • "Denotational semantics and its foundations provide an extremely helpful mathematical understanding of the domain and function spaces implicit in programs. When applied to [a functional] language, its foundations provide powerful tools for describing the language and for proving properties of programs. When applied to [an imperative] language, on the other hand, it provides a precise semantic description and is helpful in identifying trouble spots in the language... a bewildering collection of productions, domains, functions, and equations that is only slightly more helpful in proving facts about programs than the reference manual of the language"
  • "denotational and axiomatic semantics are descriptive formalisms whose foundations embody elegant and powerful concepts; but using them to describe [an imperative] language can not produce an elegant and powerful language... proofs about programs use the language of logic, not the language of programming. Proofs talk about programs but cannot involve them directly since the axioms of von Neumann languages are so unusable. In contrast, many ordinary proofs are derived by algebraic methods. These methods require a language that has certain algebraic properties. Algebraic laws can then be used in a rather mechanical way to transform a problem into its solution."
  • "[Functional programming] systems offer an escape from conventional word-at-a-time programming... because they provide a more powerful set of functional forms within a unified world of expressions. They offer the opportunity to develop higher level techniques for thinking about, manipulating, and writing programs... the programmer can use his programming language as the language for deriving proofs, rather than having to state proofs in a separate logical system that merely talks about programs."
  • "There are numerous indications that the applicative style of programming can become more powerful than the von Neumann style... when these models and their applicative languages have proved their superiority over conventional languages will we have the economic basis to develop the new kind of computer that can best implement them. Only then, perhaps, will we be able to fully utilize large-scale integrated circuits in a computer design not limited by the von Neumann bottleneck."

Early in the paper, Backus illustrates the inferiority of the imperative style by comparing (pseudo-code) implementations of an inner product.

The Imperative Implementation:

2013-08-13-cp1.png

Backus points out that this implementation has the following properties:

  • "Its statements operate on an invisible 'state' according to complex rules" (those "complex rules" are described in the enormity of the highly complex language reference)
  • "It is not hierarchical. Except for the right side of the assignment statement, it does not construct complex entities from simpler ones."
  • "It is dynamic and repetitive. One must mentally execute it to understand it."
  • "It computes word-at-a-time by repetition (of the assignment) and by modification (of variable i)."
  • "Part of the data, n, is in the program; thus it lacks generality and works only for vectors of length n."
  • "It names its arguments; it can only be used for vectors a and b. To become general, it requires a procedure declaration. These involve complex issues (e.g. call-by-name versus call-by-value)."
  • "Its 'housekeeping' operations are represented by symbols in scattered places (in the 'for' statement and the subscripts in the assignment). This makes it impossible to consolidate housekeeping operations, the most common of all, into single, powerful, widely used operators. Thus in programming those operations one must always start again at square one, writing ['for i in ...'] and ['for j in ...'] followed by assignment statements sprinkled with i's and j's."

The Functional Implementation:

2013-08-13-cp2.png

This implementation has the following properties:

  • "It operates only on its arguments. There are no hidden states or complex transition rules."
  • "It is hierarchical, being built from three simpler functions and three functional forms."
  • "It is static and nonrepetitive, in the sense that its structure is helpful in understanding it without mentally executing it."
  • "It operates on whole conceptual units, not words; it has three steps; no step is repeated."
  • "It incorporates no data; it is completely general; it works for any pair of conformable vectors."
  • "It does not name its arguments; it can be applied to any vectors without any procedure declaration or complex substitution rules."
  • "It employs housekeeping forms and functions that are generally useful in many other programs; in fact, only + and x are not concerned with housekeeping. These forms and functions can combine with others to create higher level housekeeping operators."

Particularly because of Backus' appreciation for a minimalist language with highly expressive and powerful primitives (which the assignment statement usually prevents utterly) that can compose mare powerful extensions to the language than would be possible for imperative languages without updating the specification itself, I have a feeling that Backus would like the Scala programming language (when its few concessions to the imperative style are avoided, anyway).

More questions on Computer Programming: