Why does (( (λf.λx.f(f(f(x)))) (λg.λy.g(g(y))) ) (λz.z + 1)) (0) evaluate to 8?

user_4220743 0
Viewed 153

So I have this lambda expression: (λf.λx.f(f(f(x)))) (λg.λy.g(g(y)))(λz.z + 1)(0) and I'm trying to evaluate it by hand. They way I'm thinking about this is that (λf.λx.f(f(f(x)))) basically represents the expression f(f(f(x))). Then likewise (λg.λy.g(g(y))) represents the expression g(g(y)). Then g(g(y)) is passed in to replace f. So we get g(g(g(g(g(g(y)))))). Or g composed with itself 6 times. Then we pass in z+1 for g and then plug in 0 into that final expression and we wind up with 6.

>>>(((lambda f: lambda x: f(f(f(x))))(lambda g: lambda y: g(g(y))))(lambda z: z+1))(0)
8

The problem is that when I go to verify this answer using python's built in lambda calculus tools I get 8 as the answer.

So clearly I'm doing my evaluation wrong. I'm thinking of 2 g compositions being multiplied by 3 f compositions to get 6. But clearly I'm supposed to be thinking of it as 2^3 compositions but I don't understand why.

lambda-calculus lambda python
2 Answers

Your intuition is failing you somewhat. It's tempting to try to compose those two expressions the "intuitive" way, but doing so oversimplifies the problem. Let's take a look at the first couple of steps.

Here's your lambda expression with some of the extraneous parentheses removed for readability purposes

(λf.λx.f(f(fx))) (λg.λy.g(gy)) (λz.z+1) 0

Now, your intuition tells you that we "compose" the first two functions by letting f be λy.g(gy). But that's not really the case. See, we're not letting f be λy.g(gy); we're letting f be λg.λy.g(gy) (the g is still an argument at this time). So the first simplification applies as

(λx.(λg.λy.g(gy))((λg.λy.g(gy))((λg.λy.g(gy))x))) (λz.z+1) 0

It's a confusing mess, but the point is the bit that's being repeated still has a g argument. Then we plug in λz.z+1 for x, which is admittedly fairly simple

(λg.λy.g(gy)) ((λg.λy.g(gy))((λg.λy.g(gy))(λz.z+1))) 0

Alright. Now in the innermost redex we're going to let g be (λz.z+1). So, glossing over a few steps of the process, we're going to get a function on y which says "add one to this thing twice". i.e.

(λg.λy.g(gy)) ((λg.λy.g(gy))(λy.y+2)) 0

Okay, now let's do it again. The left-hand side of the redex is the same as before, so we're going to do the thing on the right-hand side twice. The thing on the right-hand side is "add one to this number", so we get

(λg.λy.g(gy)) (λy.y+4) 0

Finally, do it one last time. We're adding four to a number twice.

(λy.y+8) 0

And for the grand prize, zero plus eight is...

8
user_22886590

It's definitely a good exercise to walk it through step by step like Silvio, but more simply:

You apply f->f^3 to g->g^2, isn't that g->(((g^2)^2)^2) = g^8? and so (+1)^8 (0) = 8

user_45659470
Related