My students are pretty confused by lambda calculus. I'm looking for a way to start them off. Is there some image or analogy for lambda calculus that I can use to help them understand in the beginning?
My kids are college sophomores, and I would just like to give them a clear way to start thinking about it.
One totally intuitive way to introduce the concept is with Excel formulas. So, imagine in A1, we have the value 10. In B1, we have the formula =power(A1,2), and in B2, we have the formula =(A1+A1)/A1. So, at this point, our sheet looks like this:
A B C
1 10 100
2 2
In actuality, we have now created a literal, and two lambda expressions: $10$, $(\lambda x.(power\, x\, 2))$ and $(\lambda x.(/\, (+\, x\, x)\, x))$.
Now, let's add a formula into C1. That formula will be: =B1+1. This is a third $\lambda$ expression: $(\lambda x.(+\, x\, 1))$. Our sheet now looks like this:
A B C
1 10 100 101
2 2
Since we are pointing C1 to B1, which itself points to A1, we have now created $(\lambda x.(+\, x\, 1))\, (\lambda x.(power\, x\, 2))\, 10$, which resolves now in exactly the way you would expect from the Excel formulas:
$(\lambda x.(+\, x\, 1))\, (\lambda x.(power\, x\, 2))\, 10$
$(\lambda x.(+\, x\, 1))\, (power\, 10\, 2)$
$(+\, (power\, 10\, 2)\, 1))$
$(+\, 100\, 1))$
$101$
Simply re-pointing C1 to B2 gives us a new lambda expression:
$(\lambda x.(+\, x\, 1))\, (\lambda x.(/\, (+\, x\, x)\, x))\, 10$
Which again, resolves to 3 as you would expect.
What's nice here is that if you get rid of the 10 in A1 (you must replace it with a non-number so that Excel does not convert it to 0), you will get #VALUE, because you have created a $lambda$ expression, but not fed in the rightmost value.
