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


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.


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))

| cite | improve this answer | |

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!

| cite | improve this answer | |

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.