Lambda the Ultimate

inactiveTopic Can Programming Be Liberated from the von Neumann Style?
started 8/27/2002; 8:54:54 AM - last post 8/29/2002; 11:32:48 PM
Ehud Lamm - Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/27/2002; 8:54:54 AM (reads: 3615, responses: 15)
Can Programming Be Liberated from the von Neumann Style?
John Backus's classic manifesto arguing for functional (aka applicative) programming languages.

I'vee been looking for an online copy for a long time. Thanks!

Read all about the von Neumann bottleneck and why side effects are bad for you.

Alas, the paper shows its age. The applicative language Backus had in mind seems to be APL, not Haskell

It would be great if someone would produce an updated version, translating the examples into one of the more modern formalisms.

Posted to history by Ehud Lamm on 8/27/02; 9:01:02 AM

Paul McJones - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/27/2002; 11:28:16 AM (reads: 2463, responses: 2)
Re the APL vs Haskell question, Paul Hudak's comments on Backus's work (in "Conception, evolution, and application of functional programming languages", ACM Computing Surveys, September 1989 are perhaps appropriate. He begins the section on FP with:

Backus’ FP was one of the earliest functional languages to receive widespread attention. Although most of the features in FP are not found in today’s modern functional languages, Backus’ [1978] Turing Award lecture was one of the most influential and now most-often cited papers extolling the functional programming paradigm. It not only stated quite eloquently why functional programming was “good” but also quite vehemently why traditional imperative programming was "bad,".* Backus coined the term “word-at-a-time programming” to capture the essence of imperative languages, showed how such languages were inextricably tied to the von Neumann machine, and gave a convincing argument why such languages were not going to meet the demands of modern software development. That this argument was being made by the person who is given the most credit for designing FORTRAN and who also had significant influence on the development of ALGOL led substantial weight to the functional thesis. The exposure given to Backus’ paper was one of the best things that could have happened to the field of functional programming, which at the time was certainly not considered mainstream.

* Ironically, the Turing Award was given to Backus in a large part because of his work on FORTRAN.

I worked with Backus at IBM Research during 1974-1975, and I found his dedication to exploring a "variable-free" approach to programming both inspiring and frustrating. To me, the ability of the lambda calculus to define new "combining forms" was a feature; to him it was a bug. I think I may have influenced him to start thinking about the issue of state, which was missing from his earliest formulations. I imagine he might appreciate monads.

Ehud Lamm - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/27/2002; 12:15:54 PM (reads: 2461, responses: 0)
There are two themes in the paper. One is lack of side effects as opposed to manipulating state. There other is the idea of loop less code. Indeed, Backus writes: Functional programs deal with structured data, are often nonrepetitive and nonrecursive... (from the abstract). Most modern descriptions of functional programming, on the other hand, emphasize that functional languages rely on recursion. How come?

Iverson's languages champion the notion of many-at-a-time execution and loopless code.

Much as I admire Iverson's work, I find that the approach taken by most functional languages today is cleaner. Many-at-a-time exection (e.g., maps and folds) are not built in operators, but rather user programmable high order functions (often defined recursively).

By the way, J does allow you to create operators of this type (which are called adverbs).

Michael Vanier - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/27/2002; 5:06:05 PM (reads: 2361, responses: 1)
I think J is really the language that is currently closest in spirit to what Backus was advocating. Even so, J does permit explicit definitions (equivalent to lambda expressions) although good J style is to use implicit ("tacit" in J terminology) definitions.

The real issue is to get away from named function arguments. This is a combinator-based paradigm, unlike most functional languages, which are basically variants of lambda calculus. The advantage is that in the absence of named arguments, it becomes possible to treat functions algebraically and thus to do a lot of transformations on code that wouldn't be possible otherwise.

I think that the idea of using only a fixed set of combinators is somewhat misguided, although it does work. In principle, you just need two (S and K are the canonical examples, but there are other possibilities). However, to make programming user-friendly you need many more. You can either define the other combinators in terms of the primitive ones (which was Backus' idea, I think) or you can let users specify their own through some kind of lambda abstraction (which I would prefer). The problem with allowing lambdas is that people then start to write "regular" functional code. I'd be interested to see a language that only allowed users to define lambdas only if they were combinators (i.e. had no free variables at all).

Anyone who is interested in this sort of approach should try to get a hold of Haskell Curry's two-volume magnus opus "Combinatory Logic", which can be found in many university libraries.

Paul Snively - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/27/2002; 6:41:41 PM (reads: 2352, responses: 0)
For a look at what happens if you only have S and K and no lambda, see Unlambda. If nothing else, it clarifies a level beyond which you desperately want some syntactic sugar!

Ehud Lamm - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/28/2002; 12:47:20 AM (reads: 2385, responses: 0)
I agree that tacit definition in J seem to come closest to waht Backus had in mind.

Still, it is worth mentioning that both APL and J allow explicit definitions (i.e, referencing the function arguments by name) and side effects.

James Hague - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/28/2002; 9:35:40 AM (reads: 2272, responses: 0)
This thread wouldn't be complete without a pointer to FL, Backus's lesser known successor to FP. A few years ago, I tried to dig up as much info on FL as I could find, including contacting anyone involved in the project. Sadly, FL is just a footnote to programming language history, but wow does it smack of J.

It's interesting that the FL group explicitly avoided a static type system, because it was something else to get in the way of learning the language.

Alex Sauer-Budge - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/28/2002; 11:19:02 AM (reads: 2231, responses: 0)
In the article, Backus writes "our fixation on von Neumann languages has continued the primacy of the von Neumann computer, and our dependency on it has made non-von Neumann languages uneconomical and has limited their development."

On the surface, it seems that functional programs are capable of being executed faster than their low-level state-driven counterparts (e.g. by taking advantage of parallelism made clear by reduced state-dependency), but in practice they appear to be much slower.

Are the obstacles to reducing a functional program to efficient machine code for current computer architectures fundamentally (i.e. theoretically) insurmountable? Has there been any work to design computer architectures which execute functional programs efficiently?

(A note on my perspective: I am merely a programming language user whose applications put abstraction at very great odds with efficiency of performance. In my field of numerical methods for engineering design/analysis, FORTRAN is still the reigning champion for efficiency-- even other low-level languages like C are somewhat snubbed for their inefficiency. Unfortunately, our performance needs and available languages cause us to spend too much time hassling with the details of loops, etc., and not enough time with the essential concepts of our methods.)

Luke Gorrie - Connection Machine Lisp  blueArrow
8/28/2002; 11:37:56 AM (reads: 2310, responses: 0)
I recently read a great paper called "Connection Machine Lisp" by Guy Steele and Danny Hillis. It's a wonderfully fun Lisp extended with parallel data structures, and was designed for the Connection Machine (a massively parallel non-von Neumann computer from the 80s). It's based an array-like data structure that you can operate on in parallel, and the programming style is inspired by FP and APL.

I've only managed to find it in ACM's digital library, so I've mailed them and asked for permission to post a copy.

Alex Peake - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/28/2002; 7:16:08 PM (reads: 2161, responses: 0)

I found at the following:

" the area of floating point arithmetics...CMU CL, which outperforms C and FORTRAN. If your code is heavily numeric, you might prefer CMUCL, ..."

Ehud Lamm - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/29/2002; 10:32:15 AM (reads: 2149, responses: 0)
Thanks for the link. This is an excellent paper, I highly recommend it. If anyone finds it outside the ACM DL, let us know.

Alex Sauer-Budge - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/29/2002; 11:22:18 AM (reads: 2084, responses: 2)
Thank you for the references. The Connection Machine was a bit before my time, so I don't know much about it. It seems from what I have read and understand from the paper that xapping and friends are language features which provide _explicit_ access to the underlying parallel hardware, which is interesting and useful for explicitly parallel algorithms, but what I am curious about is the possibility of an architecure on which average functional programs (constructed with core langauge features) can easily be compiled to run very efficiently. Can a functional program compiled with the right compiler implicitly take advantage of non-monolithic architecture like multiple local processors or highspeed network clusters?

On the subject of numerical processing with Lisp: I was quite excited about it for a bit, but after reading "Fast Floating-Point Processing in Commmon Lisp," by Richard Fateman, I lost interest when it seemed to me that the style of fast numerical code was essentially imperative and in addition to being 2-3 times slower, it provided no discernable syntax advantages over the traditional imperative languages in use. Additionally, I was a bit intimidated by the dynamic nature of the language as I would hate to discover a type-related bug 20 hours into the computation. I have to admit that I really just skimmed the surface, but decided not to jump in (yet).

More on the topic of functional lnaguage advocacy, does anyone know of any recent work on implementing numerical algorithms in functional languages? How about research into solving problems with large chunks of data, like trees with hundreds of thousands of nodes, or hashes with a million entries? Does the functional paradigm scale to these situations, or do you need to treat large chunks of data in a special way? An example from Backus's paper, the Trans function should not return a copy of the data with reordered values when computing an inner product, which modern functional languages may or may not do in a similar situation (does Haskell create a temporary list for the elemental products during "foldl (+) 0 (map2 (*) l1 l2)"?).

Alex Peake - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/29/2002; 5:02:09 PM (reads: 2082, responses: 0)
In SML foldl is defined:

fun foldl e [] = e | foldl e (x::xs) = foldl f (f(x,e)) xs;

recursion, but no intermediate lists.

I also saw a quote (though I do not remember the source) that 90% of the Fortran library is map, filter and accumulate operations, so there is hope for functional expression.

You might take a look at Partial Evaluation (recent posts) as a means of extracting better performance.

David Bakin - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/29/2002; 11:32:48 PM (reads: 2081, responses: 0)
Another descendant of this line of thought is the Bird-Meertens Formulism - aka Squiggol.

Papers to look at:

"An Introduction to the Bird-Meertens Formalism" (Gibbons) "A Pointless Derivation of Radix Sort" (Gibbons)


"Algebra of Programming" (Bird, de Moor)

Jay Han - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/30/2002; 10:58:10 AM (reads: 2058, responses: 0)
I don't know if any FPL is suitable for "grande"* problems like you describe. Possibly Sisal? (which has come back to life at

Another related question may be: can FPLs provide efficient I/O? After all, large data needs fast I/O.

*= yes I was thinking of Java Grande.

Jay Han - Re: Can Programming Be Liberated from the von Neumann Style?  blueArrow
8/30/2002; 10:58:53 AM (reads: 2072, responses: 0)
A bit off tangent...

The famous (but dated) "Psuedo Knot" benchmark paper and other papers are available from

There are a handful of tech reports on numerical computation using Concurrent Clean that may be of interest.