Lambda the Ultimate

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.

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).

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.

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

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.

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.)

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.

I found at http://clisp.cons.org/propaganda.html the following:

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

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)"?).

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.

Papers to look at:

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

Textbook:

"Algebra of Programming" (Bird, de Moor)

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.

The famous (but dated) "Psuedo Knot" benchmark paper and other papers are available from http://openmap.bbn.com/~kanderso/performance/.

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