Question

I am having a difficulty in deciding the scope of the left-most lambda in the following expression.

λx.x(λuv.v)(λab.a)(λcd.c)

I have learnt that we should put brackets in such a way that the scope of lambda will be maximum. So arrived at candidate- answer 1, below.

On the other hand, since the expression (λuv.v)(λab.a)(λcd.c) does not contain any x, if we put brackets as in answer 2, still we are not changing the scope, right?

But I know that these two answers are not equivalent. So which one is the correct one?

The two candidate answers are:

  1. λx.(x(λuv.v)(λab.a)(λcd.c))
  2. (λx.x)(λuv.v)(λab.a)(λcd.c)

I came up with this confusion through the tutorial: A Tutorial Introduction to the Lambda Calculus by Raul Rojas. There, in page 6, ~T is given as λx.x(λuv.v)(λab.a)(λcd.c). If we apply brackets as in my answer-1, we will not be able to evaluate ~T to F.

Was it helpful?

Solution

The correct answer is:

(λx.x (λuv.v) (λab.a) (λcd.c))

If I add in parethenese to disambiguate application, it becomes.

(λx.((x (λuv.v)) (λab.a)) (λcd.c))

OTHER TIPS

Sorry reviving this question, but I think there are parenthesis missing on the tutorial. It should be

$$\neg T = (\lambda x. x (\lambda uv. v)(\lambda ab. a))(\lambda cd. c)$$

On the book we have $$\neg T = \lambda x. x (\lambda uv. v)(\lambda ab. a)(\lambda cd. c)$$ but that will evaluate to $T$ as the first redex to be processed will be $(\lambda uv. v)(\lambda ab. a)$

I'm a newbie here, so veterans, please check if I'm not mistaken!

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top