11
$\begingroup$

I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.

  1. $\lambda xy.xy$
  2. $\lambda x.\lambda y.xy$

Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same thing?

Especially this definition of pair creation made me wonder:

pair = $\lambda xy.\lambda p.pxy$

$\endgroup$
0
15
$\begingroup$

These are just differences of notations. $λxyz.t$ is short for $λx.λy.λz.t$. No magic here.

Indeed, $\mbox{pair}=λxyp.pxy$ but you tend to emphasize that $\mbox{pair}\,t\,u$ is a function $λp.ptu$ by changing the way you write the definition. But it is really the same.

$\endgroup$
0
17
$\begingroup$

The first is an abbreviation for the second. It's a common syntactic convention to shorten expressions.

On the other hand, if you have tuples in the language, then there is a difference between

  1. $\lambda x.\lambda y.xy$ and
  2. $\lambda (x,y).xy$.

In the former case I can provide a single argument to the function, and pass the resulting function around to other functions. In the latter case, both arguments must be supplied at once. There is, of course, a function that can be applied to convert 1 into 2 and vice versa. This process is known as (un)currying.

The definition of $\text{pair}$ you mention is an encoding of the notion of pairs into the $\lambda$-calculus, rather than pairs as a primitive data type (as I hinted at above).

$\endgroup$
0
2
$\begingroup$

Transforming a function that takes multiple arguments to a chain of functions with single arguments is called currying. The two functions are essentially the same.

Wikipedia article about currying

$\endgroup$
1
  • 8
    $\begingroup$ There's no such thing as a function taking multiple arguments in the lambda calculus. $\lambda x y. x y$ is exactly the same as $\lambda x. \lambda y. x y$, not just basically the same. $\endgroup$ – sepp2k Mar 22 '12 at 14:51

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.