19
$\begingroup$

I was watching the lecture by Jim Weirich, titled 'Adventures in Functional Programming'. In this lecture, he introduces the concept of Y-combinators, which essentially finds the fixed point for higher order functions.

One of the motivations, as he mentions it, is to be able to express recursive functions using lambda calculus so that the theory by Church (anything that is effectively computable can be computed using lambda calculus) stays.

The problem is that a function cannot call itself simply so, because lambda calculus does not allow named functions, i.e.,

$$n(x, y) = x + y$$

cannot bear the name '$n$', it must be defined anonymously:

$$(x, y) \rightarrow x + y $$

Why is it important for lambda calculus to have functions that are not named? What principle is violated if there are named functions? Or is it that I just misunderstood jim's video?

$\endgroup$
  • 4
    $\begingroup$ This doesn't sound important at all. You can assign $(x,t) \mapsto x+y$ to a variable $n$ and then you have given a name to the function. $\endgroup$ – Yuval Filmus Mar 11 '14 at 11:49
  • $\begingroup$ @YuvalFilmus yes, you can bind a name to a function. I think the real question here, the puzzlement, is why (in lambda calculus) can't a function call itself by such a name? Why do we need a technique like the Y operator in order to do recursive functions? I hope my answer below helps. $\endgroup$ – Jerry101 Mar 12 '14 at 6:48
  • 1
    $\begingroup$ @Jerry101 The historical reason for the absence of self-application is that $\lambda$-calculus was intended to be a foundation of mathematics, and the ability to self-apply makes such a foundation immediately inconsistent. So this apparent inability (which we know now can be circumvented) is a design feature of $\lambda$-calculus. $\endgroup$ – Martin Berger Mar 12 '14 at 8:12
  • $\begingroup$ @MartinBerger please say more. Inconsistent for the reason in my answer? Or for another reason? $\endgroup$ – Jerry101 Mar 12 '14 at 8:40
  • 1
    $\begingroup$ @Jerry101 Inconsistent in the sense that you can prove 0 = 1 in such a foundation of mathematics. After Kleene and Rosser showed the inconsistency of the pure, untyped $\lambda$-calculus, the simply-typed $\lambda$-calculus was developed as an alternative that does not allow us to define fix-point combintors such as $Y$. But if you add recursion to the simply-typed $\lambda$-calculus it again becomes inconsistent, because every type is inhabited by a non-terminating program. $\endgroup$ – Martin Berger Mar 12 '14 at 9:04
24
$\begingroup$

The main theorem regarding this issue is due to a British mathematician from the end of the 16th century, called William Shakespeare. His best known paper on the subject is entitled "Romeo and Juliet" was published in 1597, though the research work was conducted a few years earlier, inspired but such precursors as Arthur Brooke and William Painter.

His main result, stated in Act II. Scene II, is the famous theorem:

What's in a name? that which we call a rose
By any other name would smell as sweet;

This theorem can be intuively understood as "names do not contribute to meaning".

The greater part of the paper is devoted to an example complementing the theorem and showing that, even though names contribute no meaning, they are the source of endless problems.

As pointed out by Shakespeare, names can be changed without changing meaning, an operation that was later called $\alpha$-conversion by Alonzo Church and his followers. As a consequence, it is not necessarily simple to determine what is denoted by a name. This raises a variety of issues such as developing a concept of environment where the name-meaning association are specified, and rules to know what is the current environment when you try to determine the meaning associated with a name. This baffled computer scientists for a while, giving rise to technical difficulties such as the infamous Funarg problem. Environments remain an issue in some popular programming languages, but it is generally considered physically unsafe to be more specific, almost as lethal as the example worked out by Shakespeare in his paper.

This issue is also close to the problems raised in formal language theory, when alphabets and formal systems have to be defined up to an isomorphism, so as to underscore that the symbols of the alphabets are abstract entities, independent of how they "materialize" as elements from some set.

This major result by Shakespeare shows also that science was then diverging from magic and religion, where a being or a meaning may have a true name.

The conclusion of all this is that for theoretical work, it is often more convenient not to be encumbered by names, even though it may feel simpler for practical work and everyday life. But recall that not everyone called Mom is your mother.

Note:
The issue was addressed more recently by the 20th century American logician Gertrude Stein. However, her mathematician colleagues are still pondering the precise technical implications of her main theorem:

Rose is a rose is a rose is a rose.

published in 1913 in a short communication entitled "Sacred Emily".

$\endgroup$
  • 3
    $\begingroup$ Additional note: In recent decades "rose" has (in computer science) been mostly replaced by "foobar" (and parts thereof) as the canonical example for a name that is as good as any other. This preference has apparently been introduced by American railroad engineers. $\endgroup$ – FrankW Mar 11 '14 at 20:01
  • $\begingroup$ That said, canonical names for often used concepts are important for efficient communication. $\endgroup$ – Raphael Mar 11 '14 at 20:55
  • 1
    $\begingroup$ @Raphael Agreed, but I would put that in the everyday life category. And how do we know the boundaries of what is really canonical? Still, I often feel concern when I see students taking all terminology, notation and definitions (or even the way some theorems are stated) for a God-given immutable truth. Even here, on SE, students ask questions, not realizing that we may not know their notations, or the definitions they use in class. The magic of true names does not die easily. $\endgroup$ – babou Mar 11 '14 at 21:54
10
$\begingroup$

I would like to venture an opinion that is different from those of @babou and @YuvalFilmus: It is vital for pure $\lambda$-calculus to have anonymous functions. The problem with having only named functions is that you need to know in advance how many names you will need. But in the pure $\lambda$-calculus you have no a priori bound on the number of functions used (think about recursion), so you either use (1) anonymous functions, or (2) you go the $\pi$-calculus route and provide a fresh name combinator ($\nu x.P$ in $\pi$-calculus) that gives an inexhaustible supply of fresh names at run-time.

The reason pure $\lambda$-calculus does not have an explicit mechanism for recursion is that pure $\lambda$-calculus was originally intended to be a foundation of mathematics by A. Church, and recursion makes such a foundation trivially unsound. So it came as a shock when Stephen Kleene and J. B. Rosser discovered that pure $\lambda$-calculus is unsuitable as a foundation of mathematics (Kleene–Rosser paradox). Haskell Curry analysed the Kleene-Rosser paradox and realised that its essence is what we now know as Y-Combinator.

Added after @babou's comment: there is nothing wrong with having named functions. You can do this as follows: $\mathsf{let} f = M \mathsf{in} N$ is a shorthand for $ (\lambda f.N)M $ in the call-by-value $\lambda$-calculus.

$\endgroup$
  • 1
    $\begingroup$ I think the OP wanted the ability to name functions, not to forbid anonymous ones. This said, I would think that any requirement of λ-calculus regarding the need for anonymous functions would show as well in languages like Lisp/Scheme or ML. In the case of Lisp/Scheme, the meta-circularity of evaluators should make it possible to create new names as needed, though I am not sure I would want it that way in a formal system. The use of unbounded number of functions is not necessarily a problem when recursion allows local reuse of already used names. $\endgroup$ – babou Mar 11 '14 at 22:49
  • $\begingroup$ @babou Scheme and ML have letrec, so they can easily live with a finite number of named functions. I'd be interested to see a presentation of the pure $\lambda$-calculus with an explicit scheme for reusing names. And yes, the ability to name functions (and other terms) is perfectly compatible with the pure $\lambda$-calculus. $\endgroup$ – Martin Berger Mar 12 '14 at 0:23
  • $\begingroup$ Should the last line read (lambda f. N) M? $\endgroup$ – Joe the Person Jun 8 at 3:09
  • $\begingroup$ @JoethePerson Yes, well spotted. Fixed. Thanks. $\endgroup$ – Martin Berger Jun 8 at 13:31
4
$\begingroup$

I believe the idea is that names are not necessary. Anything that appears to require names can be written as anonymous functions.

You can think of the lambda calculus like assembly language. Someone in a lecture on assembly might say "There are no object oriented inheritance trees in assembly language." You might then think up a clever way to implement inheritance trees, but thats not the point. The point is that inheritance trees are not required at the most basic level of how a physical computer is programed.

In the lambda calculus the point is that names are not required to describe an algorithm at the most basic level.

$\endgroup$
4
$\begingroup$

I'm enjoying the 3 answers here so far -- most especially @babou's Shakespearen analysis -- but they don't shed light on what I think is the essence of the question.

λ-calculus does bind names to functions whenever you apply a function to a function. The issue is not the lack of names.

"The problem is that a function cannot call itself simply" by referring to its name.

(In pure Lisp, the name --> function binding is not in scope within the function's body. For a function to call itself by its name, the function would have to refer to an environment that refers to the function. Pure Lisp has no cyclic data structures. Impure Lisp does it by mutating the environment that the function refers to.)

As @MartinBerger pointed out, the historical reason that λ-calculus doesn't let a function call itself by name was an attempt to rule out Curry's paradox when trying to use λ-calculus as a foundation of mathematics, including deductive logic. This didn't work since techniques like the Y combinator allow recursion even without self-reference.

From Wikipedia:

If we can define function r = (λ.x x x ⇒ y) then r r = (r r ⇒ y).

If r r is true then y is true. If r r is false then r r ⇒ y is true, which is a contradiction. So y is true and as y can be any statement, any statement may be proved true.

r r is a non-terminating computation. Considered as logic r r is an expression for a value that does not exist.

$\endgroup$
  • $\begingroup$ I am pretty new to lambda calculus, so I had a question, which I have had for pretty much forever by now. What does $\lambda.x \space x x$ mean? I'm pretty sure it doesn't mean multiply $x$ by $x$. Does it mean apply the expression $x$ to itself? Also, what does the part => y signify? $\endgroup$ – Rohan Prabhu Mar 14 '14 at 7:34
  • $\begingroup$ @RohanPrabhu λ.x x x translates to Lisp as (lambda (x) (x x)) and to JavaScript as function (x) {return x(x);}. x⇒y means x implies y, about the same as (NOT x) OR y. See en.wikipedia.org/wiki/Lambda_calculus $\endgroup$ – Jerry101 Mar 14 '14 at 18:26
  • $\begingroup$ Thank you for answering that embarrassing rookie question! $\endgroup$ – Rohan Prabhu Mar 18 '14 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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