1

I'm working on some problems where I'm supposed to reduce lamda terms to normal form. I'm not sure if I'm doing it right so if someone could let me know, that would be awesome.

$$(\lambda x.\lambda y.x*2+y*3)\; 5 \;4 $$

$$\rightarrow(\lambda y.5*2+y*3) \; 4 $$

$$\rightarrow(5*2+4*3) $$

$$\rightarrow 22$$

And secondly, how does that equation differ from $\lambda x.(\lambda y.x*2+y*3) \; 5$? They just moved the parenthesis over $1\ldots$ does that mean the $λx$ would just stay in the answer? as in:

$$\lambda x.(\lambda y.x*2+y*3) 5$$

$$\rightarrow\lambda x.(x*2+5*3)$$

And would I solve it to be:

$$\rightarrow \lambda x.(x*2+15)$$

Thanks in advance,

Sean

user2869231
  • 135

1 Answers1

1

Yes, you are right.

Let $$f = \lambda x.\ \lambda y.\ x\cdot 2 + y \cdot 3,$$ that is, (using different notation) we have $f(x)(y) = 2x+3y$, and so $(f\ 5\ 4) = f(5)(4) = 10+12 = 22$. On the other hand, if you won't take whole $f$ into parentheses, then we arrive at $$\Big(\lambda x.\ (\lambda y. x \cdot 2 + y \cdot 3)\ 5 \Big)= (\lambda x.\ x \cdot 2+15),$$ if we were to pass $4$ later, then we get $(\lambda x.\ x \cdot 2 + 15)\ 4 = 8+15 = 23$.

The difference is that the scope of $\lambda$ extends to as far right as possible, so the additional $5$ is under the scope of $\lambda x$. Hence, $5$ would be substituted into $y$. However, in the former example, the number $5$ was separated from both lambdas by parentheses, and so it would be substituted into $x$.

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • Awesome! Thank you :). And I'm so glad you wrote it in f(x) terminology - makes so much more sense than lambdas everywhere lol – user2869231 Oct 14 '13 at 18:36
  • @user2869231 It might make sense now, but really it is not much useful when dealing with more than three parameters. There is another notation which I really like that uses symbol $\mapsto$, and is commonly recognized in math. You may be forced to use the $\lambda$-notation in class, but in your own notes you can write things like $f = x\mapsto y \mapsto 2x+3y$, and when not using any variables, using additional parentheses is a good idea like $(x \mapsto y \mapsto 2x+3y)$. Naturally, you can also mix $f(x) = y \mapsto 2x+3y$, but be aware that it usually is less readable. – dtldarek Oct 14 '13 at 18:41
  • so pretty much arrows instead of parenthesis? – user2869231 Oct 14 '13 at 18:44
  • @user2869231 Parentheses are good if you are defining $f$ like $f(x) = x+1$, however, when there is no $f$, then what would you write, $(x) = x+1$?! Hence, the lambda: $(\lambda x.\ x+1)$ or an arrow $(x \mapsto x+1)$. Please be aware, that some people write lambdas differently, like $\lambda x(x+1)$, and then the scoping rules are different (e.g. see the answer of @bluesh34). It's simmilar to regular quantifiers, e.g. $\forall x.\ P(x)$ versus $\forall x(P(x))$. – dtldarek Oct 14 '13 at 18:53
  • @user2869231 Also, if you would like to check something, you can try haskell and type in (\x y -> x*2 + y*3) 5 4 or try ruby by typing in lambda{|x|­ lambda{|y| x*2 + y*3}}­[5][4]. – dtldarek Oct 14 '13 at 18:59