HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is it that a lambda function requiring multiple input also requires multiple functions?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyrequiresfunctioninputalsothatmultiplefunctionslambdarequiring

Problem

So I recently discovered lambda calculus and for the most part I understand it. However, one specific part of it that I cannot understand is this:

Let's say we define a very simple function

$$ I := \lambda a.a$$

This is simple to understand, nothing confusing. However, if you add another input I will scratch my head furiously:

$$A := \lambda a.\lambda b.a+b$$

This is confusing to me for at least 2 reasons:

-
Why is it that I cannot define a function with multiple parameters like so:

$$A := \lambda a,b. a+b$$

-
How does the second function returned have access to the first parameter if they can only hold one parameter? Is there a prospective for scope? If so, how does it work?

Solution

One view is that there are no functions of multiple parameters. A function which takes "two parameters" is a function taking a single ordered pair. In mathematics, a function $f : A \to B$ has one domain $A$ and codomain $B$. While it is possible to speak of functions with multiple domains, it is more customary to think of a multi-variate function $g$ as an ordinary function whose domain is a cartesian product, $g : A \times B \to C$.

So, if you would like to have functions taking two parameters in $\lambda$-calculus, you should not be changing how $\lambda$-abstraction works, but you should rather extend the calculus with ordered pairs (and people do that).

But we do not have to extend the calculus with ordered pairs, because every function of two arguments $A \times B \to C$ can be converted to a function of a single argument $A$ returning a function $B \to C$. This may take some getting used to, but it works perfectly. That is, there is a bijection between functions $A \times B \to C$ and functions $A \to (B \to C)$, where the latter expression is read as "functions taking an argument from $A$ and returning a function from $B$ to $C$". This is known as currying.

The expression $\lambda a . \lambda b . a + b$ should be read as a function taking an argument $a$ and returning the function $\lambda b . a + b$. It is thus an example of a multi-variate function that has been curried to take one argument at a time.

Context

StackExchange Computer Science Q#98370, answer score: 6

Revisions (0)

No revisions yet.