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.

(λx.λy.yx)z (λw.w) I am lost with this.

if anyone could lead me in the right direction that would be much appreciated

  • $\begingroup$ Did you try to find a partition of the problem where you'd been able to solve at least one part? $\endgroup$ – greybeard Sep 14 at 6:42
  • $\begingroup$ It may help to note that lambda calculus is confluent (Church-Rosser) under the full $\beta$-reduction strategy. $\endgroup$ – ShyPerson Sep 19 at 19:28

It is better to remind ourselves the Lambda calculus precedence rules first. See https://stackoverflow.com/q/4794330/9939883 for better details about precedence.

Application has higher precedence than Abstraction. Application is left associateive and Abstraction is right associative.

(λx.λy.y x) z (λw.w)

Since application has higher precedence,

(λx.λy.(y x)) z (λw.w)

Since application is left associative

= ((λx.λy.(y x)) z) (λw.w)

Applying repeated abstractions

= (λy.(y z)) (λw.w) 

= (λw.w) z

= z
| cite | improve this answer | |
  • $\begingroup$ Thank you, I have made some edits. $\endgroup$ – silversilva Sep 15 at 2:55
  • 1
    $\begingroup$ Thank you! Nice explanation! $\endgroup$ – D.W. Sep 15 at 5:15

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.