Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've been messing around with functional programming languages for a few years, and I keep encountering this phrase. For example, it is a chapter of "The Little Schemer, which certainly predates the blog by this name. (No, the chapter doesn't help answer my question.)

I understand what lambda means, the idea of an anonymous function is both simple and powerful, but I fail to understand what "the ultimate" means in this context.

Places that I've seen this phrase:

  1. The title of chapter 8 of The Little Schemer
  2. A blog: http://lambda-the-ultimate.org/
  3. A series of "Lambda the ultimate X" papers: http://library.readscheme.org/page1.html

I feel like I'm missing a reference here, can anyone help?

share|improve this question
1  
Looks like it's the name of a popular blog, but if there is another historical source, I'm interested... –  Klaim Sep 12 '11 at 15:25
1  
Can you provide some references to places that you have seen this phrase? That context would be hugely helpful in finding answer. –  Adam Crossland Sep 12 '11 at 15:27
    
@Adam - added some references. –  Eric Wilson Sep 12 '11 at 15:34

3 Answers 3

up vote 29 down vote accepted

Yes, it's simply a recurring phrase in the title of several papers, starting from a couple in the 70s, in which Sussman and Steele demonstrate the use of lambda calculus for programming, by means of a minimalist Lisp dialect named "Scheme" they devised for the purpose. You can find the papers themselves here; they're interesting and surprisingly relevant.

I'm not sure if this is ever explicitly stated, but it's clear (from context, having read the papers, and knowing the general background and research interests of the authors) that the phrase is simply a catchy slogan for their contention that lambda abstractions, as a computational primitive, are not only universal in the formal sense (of being able to encode any program in some fashion, however awkward), but universal in a practical sense that any and every construct present in other languages, even those that are baked-in from the ground up, can be reimplemented in a lambda-based language in a way that is both effective and natural to use.

The repeated phrase leads to the obvious generalized form "for all X, lambda is the ultimate X", which is the sense I've generally taken "Lambda the Ultimate" to mean as the blog name, noting that LtU is concerned with programming language design and theory. Ironically, LtU would probably also be one of the best places to find someone who could tell you about something for which lambda is not the ultimate implementation. :]

Note also that Sussman is one of the authors of SICP, a very influential textbook that also uses the Scheme language and spends a fair amount of time introducing lambda abstractions as a concept.

share|improve this answer
2  
+1 for locating those classic papers. Guy L. Steele, Jr. also pretty much wrote the book on Common LISP. LISP and Scheme were not the end of the road for Guy, who went on to contribute to J, Fortress, and other languages. Guy was also involved in the Jargon File and Hacker's Dictionary. –  John Tobler Sep 12 '11 at 18:43
    
@John Tobler: Quite so! I only focused on Sussman because he seemed to have more involvement with Scheme, which is deeply tied to the Lambda Papers. Didn't mean to give the impression that Steele hadn't done anything else, since that's far from true indeed. :] –  C. A. McCann Sep 12 '11 at 18:49

Lambda The Ultimate refers to the idea that the lambdas of lambda-calculus can effectively implement every builtin concept in every programming language, past, present, and future. Classes, Modules, Packages, Objects, Methods, Control-Flow, Data Structures, Macros, Continuations, Coroutines, Generators, List Comprehensions, Streams, and so on.

As it happens, that ultimate nature includes standing for an Anonymous Function. But lambdas are not, at their core, limited to just anonymous functions. They get taught that way, but the essence of lambda goes far deeper than mathematical functions without names. In other words, I take issue with:

I understand what lambda means, the idea of an anonymous function is both simple and powerful, but I fail to understand what "the ultimate" means in this context.

As a practical matter, the use of lambdas as syntactic abstractions ('macros'), which are not call-by-value/applicative (which mathematical functions are), is absolutely crucial to buying into the idea that lambdas really can serve as the core of every programming language processing system.

For Theory: There is an interesting connection with Bertrand Russell's paradox and the Axioms of Comprehension (and Extension) in naive set theory. A lambda is to functions what set-builder notation is to sets: lambdas are function-builder notation. There is an important difference, usually ignored, between (lambda (x) (* x x)) and what that evaluates to (the function that squares). If one fails to distinguish between the two in general, that is, between the notation and the denotation (a mistake that Church and Frege both made) then one runs afoul of paradoxes. For sets and Frege, it is Bertrand Russell's Barber of Seville that illustrates the error; for functions and Church, it is Alan Turing's Halting Oracle.

Note that the paradoxes are good, practical, things. We want EVAL to be expressible, and we want lambdas to mean more than just functions. That assuming the opposite leads to contradiction is the desirable result; it serves as a nice sanity test: lambdas can hardly be ultimate if they only express mere functions.


Racket (formerly PLT Scheme) continues to prosecute the idea that practical programming languages really can be built, from the ground up, on 'just lambda'.

Kernel, by Shutt, argues that lambda is not really the ultimate abstraction. He argues there is one concept more primitive still (for Greek, dubbed vau) which was known to Sussman as FEXPR.

Felleisin and company (for Racket) get much of the power of Shutt's vau by using the concept of phases, or metalevels, which approximately means running the source code through multiple stages of translation (as with preprocessing C, but using the same language at each 'step', and the 'steps' are not actually entirely distinct in time). (So, they argue that a lambda in a higher phase approximates a vau well enough.) In fact, they argue that phases are better than FEXPRs, precisely for being more limited; in short, "FEXPRs are too powerful" (see Wand's work, which Shutt argues against).

Brian Smith's 3-Lisp, "Procedural reflection in programming languages", attempts a rigorous reformulation of the theory of LISP-like languages along the lines of sharply distinguishing notations (symbols/language/programs) from denotations (things/referrents/values/results). http://dspace.mit.edu/handle/1721.1/15961

Mitchell Wand's "The Theory of FEXPRs is Trivial" sends more nails into the (temporary?) coffin that Kent Pittman wrought for FEXPRs (who, like Felleisen, argues against FEXPRs as making compilation too hard).

Paul Graham argues with strength and at length in "On Lisp" that the real power is lambdas as transformers of syntax (macros), rather than as transformers of values (mathematical functions). Plotkin's development of the applicative lambda-calculus could be taken as somewhat contrasting, because Plotkin limits Church's calculus to its call-by-value/applicative subset. Of course, handling the applicative part efficiently is very important, so it is important to develop theory specialized to that use of lambda. (Plotkin and Graham do not argue against one another.)

In fact, in general, the notion of Lambda as Ultimate is just one such twist on the eternal debate between efficiency and expressiveness; it is the position that lambda is the ultimate tool for expressiveness, and, given enough study, will ultimately prove to be the ultimate tool for efficiency as well. In other words, we can, if we want to, see the future of programming languages as nothing more and nothing less than the study of how to efficiently implement all of the practically relevant fragments of the lambda calculus.

Landin's "The Next 700 Programming Languages", http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf, is an accessible reference that contributes to the development of that concept that Lambda is Ultimate.

share|improve this answer

I guess it's simply a reference to some papers written by Sussman and Steele between 1975 and 1980 called:

  • Lambda: The Ultimate Imperative
  • Lambda: The Ultimate Declarative
  • Lambda: The Ultimate GOTO
  • LAMBDA: The Ultimate Opcode

See Wikipedia article.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.