I'm trying to beta-reduce the following: $$\lambda xy.y((\lambda xyz.xyz)(\lambda u.u)(\lambda u.uu))$$ Anyway I think that I didn't understand terms' scope.

Considering the application in the shape of $ (\lambda x.y)M $ and evaluating by leftmost outermost, at the first step, I have that my $ (\lambda x.y)M $ is:

  1. $ (\lambda xyz.xyz)(\lambda u.u), $ or
  2. $ (\lambda xyz.xyz)(\lambda u.u)(\lambda u.uu)$?

How should I choose M?

Thank you.

  • $\begingroup$ Are there no parentheses around the $\lambda xy.y$ part? Otherwise it's rather hard to be sure what is meant here. $\endgroup$ – MJD Oct 10 '14 at 17:20
  • $\begingroup$ No, I suppose they are hidden: before the first lambda and after the last parenthesis in the equation. $\endgroup$ – MoreOver Oct 10 '14 at 17:40

Since the expression overall has the form $\def\L{\lambda}\L xy.yB$, any $\beta$-reduction will have to be inside the subexpression $B$, which is $(\L xyz.xyz)(\L u.u)(\L u.uu))$. There is a standard convention in $\L$-calculus in which $(a\,b\, c)$ is an abbreviation for $((a\,b)\, c)$, so the expression above should be considered short for $$(\color{darkblue}{((\L xyz.xyz)(\L u.u))}\;(\L u.uu)).$$

The only reducible subexpression is colored in dark blue. It has the form $(\L x.B)M$ where $M=\L u.u$, so you should have no trouble reducing it. (If you do, ask a question in the comments.)

After reducing the blue expression to a result $\color{darkblue}{R}$ you can further reduce $(\color{darkblue}{R} (\L u.uu))$.

  • $\begingroup$ Sorry, I've edited my question, I meant (\lambda x.y)M. Anyway to me it's still not clear why you chose answer 1. and not 2 (from my question). To be more precise, what I don't understand is why that one is "The only reducible expression". Are you saying that I should consider (λxyz.xyz)(λu.u)(λu.uu) like (a)(b)(c) and so it becomes ((a)(b))(c)? Thank you. $\endgroup$ – MoreOver Oct 10 '14 at 21:55
  • $\begingroup$ Are you aware that $\lambda xyz.B$ is a shorthand for $\lambda x.(\lambda y.(\lambda z.B))$? Or should I explain that in more detail? $\endgroup$ – MJD Oct 10 '14 at 21:58
  • $\begingroup$ Yes, I'm aware of this. My problem was with B, in the sense that I couldn't understand where to stop selecting it. Anyway if all come from (a)(b)(c) -> ((a)(b))(c), I've understand the reason. Thank you. $\endgroup$ – MoreOver Oct 10 '14 at 22:01
  • $\begingroup$ If you can expand it entirely, I'd appreciate it, anyway, thank you. $\endgroup$ – MoreOver Oct 11 '14 at 1:28
  • $\begingroup$ I'm concerned that by doing so we might be violating your school's academic honesty rules. $\endgroup$ – MJD Oct 11 '14 at 15:02

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.