[Solved]: Why is it important for functions to be anonymous in lambda calculus?

ignougroup
Problem Detail: 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?

Asked By : Rohan Prabhu

Answered By : babou

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22497