Evaluating lambda expression call by value Beta reduction

159 Views Asked by At

$ + = λmnab.m a((n a) b)$
I have to show that $2 + 3 \triangleright_\beta $ 5
what I understand from the lambda expression of + is that it takes
4 arguments m, n , a , b But when I have to evaluate $2 + 3$, I only have $2$ arguments
How do I go about evaluating it.

1

There are 1 best solutions below

6
On BEST ANSWER

I guess, the numbers here are Church numerals: \begin{align} 2 &= \lambda f.\lambda x. f (f x) \\ 3 &= \lambda f.\lambda x. f (f (f x)) \end{align} Applying the first argument (numeral 2) to addition, we get: $$\begin{split} & (\lambda m n a b.ma ((na)b))(\lambda fx. f (f x))&~~~~~~~~~\text{($\beta$-reduction)}\\ \to~ & \lambda n a b.((\lambda fx. f (f x))a) ((na)b) \end{split}$$ Applying the second argument (numeral 3) to the above result, we get: $$\begin{split} & \big(\lambda n a b.((\lambda fx. f (f x))a) ((na)b)\big)\bigl(\lambda fx. f(f (f x))\bigr)&~~~~~~~~~\text{($\beta$-reduction)}\\ \to~ & \lambda a b.((\lambda fx. f (f x))a) (((\lambda fx. f(f (f x)))a)b) \end{split}$$