Церковный цифр для дополнения

Question

Я застрял на следующем шаге. Будет здорово, если кто-то может помочь мне:

2 = λfx.f(f x)
3 = λfx.f(f(f x))
ADD = λm n f x. m f (n f x)

Мои шаги:

   (λm n f x. m f (n f x)) (λf x.f(f(f x))) (λf x.f(f x))
-> ((λn f x. (λf x.f(f(f x))) f (n f x))) (λf x.f(f x))
-> ((λf x. (λf' x'.f'(f'(f' x'))) f ((λf" x".f"(f" x")) f x)

Является ли скобками в скобках? Я действительно путаю себя на замене и скобках. Есть ли формальный, более простые методики для решения таких проблем?

Answer 1

Пытаться Яйца аллигатора!

Вот мои шаги, которые я полученных с помощью яиц аллигатора:

ADD 2 3
-> (λm n f x. m f (n f x)) (λf x.f(f(f x))) (λf x.f(f x))
->   (λn f x. (λf x.f(f(f x))) f (n f x))   (λf x.f(f x))
->     (λf x. (λf x.f(f(f x))) f ((λf x.f(f x)) f x)) 
->     (λf x.   (λx.f(f(f x)))   ((λf x.f(f x)) f x)) 
->     (λf x.       f(f(f(λf x.f(f x)) f x)))))
->     (λf x.       f(f(f  (λx.f(f x)) x)))))
->     (λf x.       f(f(f     (f(f x))  )))))

Answer 2

Мой совет, от моего собственного ограниченного, но недавнего опыта:

1. Делать один вещь за раз: выполнить преобразование альфа, бета-восстановление или преобразование ETA. Примечание. В марне страницы вы работаете над тем, на каком шаге вы предприняли, чтобы добраться до следующей строки. Если эти слова не знакомы вам, что они делают - просто посмотрите на Википедия.

Краткое резюме этих этапов сокращения:

Альфа просто означает изменение названий переменных в контексте последовательно:

λfx. f (f x) => λgx. g (g x)

Бета просто означает применить лямбда в один аргумент

(λf x. f x) b => λx. b x

ETA - это просто «развернутая» излишне обернутая функция, которая не меняет его значение.

λx.f x => f

Затем

2. Использовать много Alpha Conversion, чтобы изменить имена переменных, чтобы сделать вещи более понятными. Всех тех fS, всегда будет запутано. Вы сделали что-то подобное с " На ваш второй ряд

3. Притворись, что ты компьютер! Не прыгайте вперед или не пропустите шаг, когда вы оцениваете выражение. Просто сделайте следующую вещь (и только одну вещь). Переместите только быстрее, как только вы уверены, двигаетесь медленно.

4. Подумайте о том, чтобы назвать некоторые выражения и заменять их только для своих лямбдских выражений, когда вам нужно их оценить. Я обычно отмечаю замену на марже страницы как by def Как это не очень эффектно снижение. Что-то вроде:

   add two three 
   (λm n f x. m f (n f x)) two three | by def
   

Так что следуйте приведенным выше правилам, вот мой рабочий пример:

two   = λfx. f (f x)
three = λfx. f (f (f x))
add   = λmnfx. m f (n f x)

0  | add two three 
1  | (λm n f x. m f (n f x)) two three           | by def
2  | (λn f x. two f (n f x)) three               | beta
3  | (λf x. two f (three f x))                   | beta
4  | (λf x. two f ((λfx. f (f (f x))) f x))      | by def
5  | (λf x. two f ((λgy. g (g (g y))) f x))      | alpha
6  | (λf x. two f ((λy. f (f (f y))) x))         | beta
7  | (λf x. two f (f (f (f x))))                 | beta
8  | (λf x. (λfx. f (f x)) f (f (f (f x))))      | by def
9  | (λf x. (λgy. g (g y)) f (f (f (f x))))      | alpha
10 | (λf x. (λy. f (f y)) (f (f (f x))))         | beta
11 | (λf x. (λy. f (f (f (f (f x))))))           | beta

Answer 3

Есть ли формальный, более простые методики для решения таких проблем?

это много Проще написать редуктор и PrettyPrinter для слайных терминов, чем делать сокращения вручную. Но PLT Redex. может дать вам ногу на сокращении; попробуйте определить правила для сокращения нормального заказа, а затем все, что вам нужно сделать, это беспокоиться о Призрачные результаты без избыточных скобок.

Вы, вероятно, тоже узнаете намного больше.