Сокращение исчисления Лямбды

Ответ 1

Для уменьшения лямбда-выражений вы можете выполнить следующие шаги:

• Полностью заключить в скобки выражение, чтобы избежать ошибок и сделать его более очевидным, когда происходит приложение функции.
• Найти приложение-функцию, то есть найти вхождение шаблона (λX. e1) e2, где X может быть любым допустимым идентификатором, а e1 и e2 могут быть любыми допустимыми выражениями.
• Примените эту функцию, заменив (λX. e1) e2 на e1', где e1' является результатом замены каждого свободного вхождения X в e1 на e2.
• Повторяйте 2 и 3 до тех пор, пока шаблон больше не появится. Обратите внимание, что это может привести к бесконечному циклу для ненормирующих выражений, поэтому вы должны остановиться после 1000 итераций или около того; -)

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

((λm. (λn. (λa. (λb. (m ((n a) b)) b)))) (λf. (λx. x))) (λf. (λx. (f x)))

Здесь подвыражение (λm. (λn. (λa. (λb. (m ((n a) b)) b)))) (λf. (λx. x)) соответствует нашей схеме с X = m, e1 = (λn. (λa. (λb. (m ((n a) b)) b)))) и e2 = (λf. (λx. x)). Итак, после подстановки получим (λn. (λa. (λb. ((λf. (λx. x)) ((n a) b)) b))), что делает все наше выражение:

(λn. (λa. (λb. ((λf. (λx. x)) ((n a) b)) b))) (λf. (λx. (f x)))

Теперь мы можем применить шаблон ко всему выражению с помощью X = n, e1 = (λa. (λb. ((λf. (λx. x)) ((n a) b)) b)) и e2 = (λf. (λx. (f x))). Поэтому после подстановки получаем:

(λa. (λb. ((λf. (λx. x)) (((λf. (λx. (f x))) a) b)) b))

Теперь ((λf. (λx. (f x))) a) соответствует нашей схеме и становится (λx. (a x)), что приводит к:

(λa. (λb. ((λf. (λx. x)) ((λx. (a x)) b)) b))

На этот раз мы можем применить шаблон к ((λx. (a x)) b), который сводится к (a b), что приводит к:

(λa. (λb. ((λf. (λx. x)) (a b)) b))

Теперь примените шаблон к ((λf. (λx. x)) (a b)), который сводится к (λx. x) и получит:

(λa. (λb. b))

Теперь все готово.

Ответ 2

Если вы ошибаетесь, так это то, что на первом этапе вы не можете

M = (λf x. x)(λ f x. f x)   

потому что исходное выражение не включает это выражение приложения. Чтобы это было ясно, вы можете поместить в неявные круглые скобки после правила, что приложение лево-ассоциативное (используя [и] для новых паренов и вставляя некоторые отсутствующие "." S):

[ (λm . λn . λa . λb . m (n a b) b) (λ f x. x) ] (λ f x. f x)

Отсюда найдите выражение вида (λv.E) M где-то внутри и уменьшите его, заменив v на M в E. Будьте осторожны, что это действительно приложение функции для M: это не так, если у вас есть что-то вроде N (λv.E) M, так как тогда N применяется к функции, а M - как два аргумента.

Если вы все еще застряли, попробуйте поместить в parens для каждой лямбды также - в основном новую "(" после каждого "." и соответствующий ")", который идет как можно дальше вправо, новый "(" Например, я сделал это здесь (используя [и], чтобы они выделялись):

( (λm . λn . λa . [λb . m (n a b) b]) (λ f x. x) ) (λ f x. f x)