CODEWITHSUNDEEP
lambdalambda-calculuschomsky-normal-form
jrz
jrz

Reputation: 1387

Lambda Expression reduction to NF

I need to reduce the following Lambda expressions into Normal Form, using Normal Order. These are my reductions but they don't make sense to me:

//First expression
(λf.λx.f(fx))(λy.+y1)(+ 2 3)
(λx.fx)(λy.+y1)(+ 2 3)
f(λy.+y1)(+ 2 3)
f(+(+ 2 3) 1)
f(+ 5 1)
f 6

//Second expression
λx. + ((λy.((λx.∗ xy) 2)) x) y)
+((λy.((λw.* wy) 2) w)
+((λw.* ww) 2)
+(* 2 2)
+ 4

Both NF that I got make no sense. The second one is a + function which requires 2 variables but ends up with only one.

I would appreciate any suggestions and corrections.

Upvotes: 0

Views: 84

Answers (1)

pteranobyte
pteranobyte

Reputation: 594

1.

//First expression
(λf.λx.f(fx))(λy.+y1)(+ 2 3)

I think your mistake here is thinking that the first term can be reduced. I don't think it can, so start applying it to the other terms right away.

2.

//Second expression
λx. (+ ((λy.((λx.∗ xy) 2)) x) y)

To reduce this start by applying the innermost term and renaming the last y so you get:

λx. (+ ((λy.(∗ 2y)) x) w)

Then continue :)

Upvotes: 0

Related Questions