All,
Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.
(λm λn λa λb . m (n a b) b) (λ f x. x) (λ f x. f x)
This is what I tried, but I am stuck:
Considering the above expression as : (λm.E) M equates to
E= (λn λa λb. m (n a b) b)
M = (λf x. x)(λ f x. f x)
=> (λn λa λb. (λ f x. x) (λ f x. f x) (n a b) b)
Considering the above expression as (λn. E)M equates to
E = (λa λb. (λ f x. x) (λ f x. f x) (n a b) b)
M = ??
.. and I am lost!!
Can anyone please help me understand that, for ANY lambda calculus expression, what should be the steps to perform reduction?
You can follow the following steps to reduce lambda expressions:
(λX. e1) e2
whereX
can be any valid identifier ande1
ande2
can be any valid expressions.(λx. e1) e2
withe1'
wheree1'
is the result of replacing each free occurrence ofx
ine1
withe2
.So for your example we start with the expression
Here the subexpression
(λm. (λn. (λa. (λb. (m ((n a) b)) b)))) (λf. (λx. x))
fits our pattern withX = m
,e1 = (λn. (λa. (λb. (m ((n a) b)) b))))
ande2 = (λf. (λx. x))
. So after substitution we get(λn. (λa. (λb. ((λf. (λx. x)) ((n a) b)) b)))
, which makes our whole expression:Now we can apply the pattern to the whole expression with
X = n
,e1 = (λa. (λb. ((λf. (λx. x)) ((n a) b)) b))
ande2 = (λf. (λx. (f x)))
. So after substituting we get:Now
((λf. (λx. (f x))) a)
fits our pattern and becomes(λx. (a x))
, which leads to:This time we can apply the pattern to
((λx. (a x)) b)
, which reduces to(a b)
, leading to:Now apply the pattern to
((λf. (λx. x)) (a b))
, which reduces to(λx. x)
and get:Now we're done.
Where you're going wrong is that in the first step, you can't have
because the original expression doesn't include that application expression. To make this clear, you can put in the implicit parentheses following the rule that application is left-associative (using [ and ] for the new parens and putting in some missing "."s):
From here, find an expression of the form
(λv.E) M
some where inside and reduce it by replacingv
withM
inE
. Be careful that it really is an application of the function to M: it isn't if you have something likeN (λv.E) M
, since then N is applied to the function and M as two arguments.If you're still stuck, try putting in the parens for each lambda also - basically a new "(" after each ".", and a matching ")" that goes as far to the right as possible while still matching the new "(". As an example, I've done one here (using [ and ] to make them stand out):