сокращение лямбда - исчисления:(((лямбда f (лямбда x (f x))) (лямбда y (* y y))) 12)

Question

учитывая входные данные

(((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

what does this step evaluate to: lambda x (f x)

Я пытаюсь оценить это, и пока у меня есть следующее дерево:

как я могу это оценить ?ищу рекомендации относительно того, что я, возможно, делаю неправильно или как с этим поступить.

Answer 1

Лямбда-выражения вычисляются путем уменьшения крайнего левого значения redex в первую очередь.Повторный показ - это что-то вроде формы $(\лямбда a.b)c$ .Твое выражение лица такое $(\лямбда f.\лямбда x.fx)(\лямбда y .*гг)~12$.Итак, ваш первый повторный запрос - это

$$(\лямбда f.\лямбда x.fx)(\лямбда y .*гг)$$

Таким образом, вы заменяете $(\лямбда у .*гг)$ для $y$ в $\лямбда x.fx$ чтобы получить $$\лямбда x.(\лямбда y .*гг)х~ 12$$

Тогда ваше следующее повторное выражение - это полное выражение, ($(\лямбда у .*гг)х$ также является redex, но это не крайний левый), заменяющий $12$ в течение $x$.Таким образом, вы получаете $$(\лямбда у .*гг)~12$$

Затем ваше последнее повторное выражение снова является полным выражением, так что вы получаете

$$*~12~12$$