2
$\begingroup$

Found this term for a supposed 'adder' in lambda calculus.

λabcd.ac(bcd)

Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know how to apply it. All the examples I could find always put in real numbers (like "3" and "5") but strictly speaking, if we want to abide by the rules of lambda calculus, numbers should be represented by lambda-terms too, right? Elsewhere I saw them defined recursively like this:

3 = λab.a(a(a(b))),

5 = λab.a(a(a(a(a(b))))).

I have a hard time linking the concept of "repeatedly applying a value to itself" to anything i already know. What does that even mean? Why is it equivalent to adding? Why does the above term add anything?

Looking for a step-by-step explanation that shows the adder "in action" and how it actually works.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

So... I'm not going to completely answer your question by showing the adder to you in action, but here's some intuition as to why it works.

Natural numbers can be defined recursively:

  • $0$ is a natural number.
  • If $n$ is a natural number, then $S(n)$ is a natural number, where $S$ is the successor function.

The lambda expression $\lambda s. \lambda z. s(s(s(z)))$ is an "abstracted" version of $S(S(S(0)))$, using Church encoding. The only difference between this and the recursive definition above is that a caller needs to supply the successor function and the zero.

What does it mean to "supply" a zero? Well, you can put anything you like there, even another number. So if you took, say, $S(S(0))$ and "replaced" the zero with $S(S(S(0)))$, you would be basically adding $2$ and $3$.

Or, to put it another way:

$$\mathit{add}\,m\,n = \lambda s. \lambda z. m\,s\,(n\,s\,z)$$

Do you see what's going on here? You are supplying $m$ with the same successor function, but giving it a different zero, namely, $(n\,s\,z)$.

Finally:

$$\mathit{add} = \lambda m. \lambda n. \lambda s. \lambda z. m\,s\,(n\,s\,z)$$

On a final note, I suspect that using meaningful names for your variables is half the battle here. Understanding what each variable means helps a lot.

As an exercise, now try implementing multiplication. The idea is that to multiply $m$ by $n$, you "supply" $n$ as the successor function rather than the zero.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I kinda get it, but am still somewhat confused about the brackets. Why is it λm.λn.λs.λz.ms(nsz) and not λm.λn.λs.λz.m(s(n(s(z)))? How do i know in what order to apply which variable to what? In the omega combinator it doesn't matter, but how do i know it here, where I have four different variables in the function body? $\endgroup$ Commented Mar 24, 2022 at 15:42
  • $\begingroup$ @SNEED Think of a Church numeral $m$ as a function that takes two arguments. If you wrote $m(s(n(s(z))))$, you are only giving it one argument, namely $s(n(s(z)))$. Writing $m\,s\,(n\,s\,z)$, you are giving it two arguments, $s$ and $n\,s\,z$. $\endgroup$ Commented Mar 25, 2022 at 0:54
  • $\begingroup$ How is (n s z) even a valid expression, if there is no order specified? But I guess λm.λn.λs.λz.ms(nsz) would turn to λm.λn.λs.λz.s(s(s(z)))s(s(s(s(z)))sz). That's it? Still not really getting why stacking a few variables, accounts for numerical values. I get that its derived from the piano axioms but I don't get how they are functionally equivalent. Does it mean that every lambda expression holds a numerical value? The introduction of hierarchies into the system with brackets still confuses me. Do I ignore them in beta reduction? $\endgroup$ Commented Mar 28, 2022 at 0:29
  • $\begingroup$ @SNEED Application customarily associates to the left. $n\,s\,z$ is the same as $(n\,s)\,z$, in the same way that $x-y-z$ means $(x-y)-z$ and not $x-(y-z)$. $\endgroup$ Commented Mar 28, 2022 at 2:54
  • $\begingroup$ As for why "stacking a few variables accounts for numerical values", yes, it's based on the Peano axioms. Every natural number is either zero, or the successor of a natural number. Every natural number can be formed by applying a finite number of "successor" operations to zero. Not every lambda expression is of this form. $\endgroup$ Commented Mar 28, 2022 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.