Арифметика с церковными цифрами

https://stackoverflow.com/questions/3912341

29-09-2019
|

Вопрос

Я работаю через SICP и Задача 2.6 поместил меня в что -то вроде затруднения. При работе с церковными цифрами, концепция кодирования ноль и 1 является произвольными функциями, которые удовлетворяют определенным аксиомам, кажется, имеет смысл. Кроме того, получение прямой формулировки отдельных чисел с использованием определения нуля, и функция ADD-1 имеет смысл. Я не понимаю, как можно сформировать оператор плюс.

До сих пор у меня есть это.

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

Просматривая запись в Википедии Lambda Calculus, Я обнаружил, что определение плюса было плюс: = λmnfx.mf (NFX). Используя это определение, я смог сформулировать следующую процедуру.

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

Чего я не понимаю, так это то, как эта процедура может быть получена непосредственно, используя только информацию, данную ранее полученными процедурами. Может ли кто-нибудь ответить на это в какой-то строгой форме, похожей на доказательство? Интуитивно, я думаю, я понимаю, что происходит, но, как однажды сказал Ричард Фейнман: «Если я не могу его построить, я не могу этого понять ...»

Решение

Это на самом деле довольно просто. Это, вероятно, будет рассматриваться как Flamebait, но парины затрудняют его-лучший способ увидеть, что происходит, это либо представить, что вы находитесь на карри-языке, либо просто используйте тот факт, что схема имеет функции с несколькими аргументами и Примите это ... вот объяснение, которое использует лямбдас и множество аргументов, где удобно:

Каждый номер N закодирован как

(lambda (f x) ...apply (f (f (f ... (f x)))) N times...)

Это означает, что кодирование n на самом деле
```
(lambda (f x) (f^N x))
```
куда f^N является функциональным экспонентом.
Более простой способ сказать это (при условии, что карри): число n закодируется как
```
(lambda (f) f^N)
```
Так что на самом деле "поднять на силу n" функция
Теперь возьмите свое выражение (заглядывая внутрь lambdaS здесь):
```
((m f) ((n f) x))
```
поскольку n является кодированием числа, это то, что экспонентация, так что это на самом деле:
```
((m f) (f^n x))
```
И то же самое для m:
```
(f^m (f^n x))
```
а остальное должно быть очевидным ... у тебя m приложения f применяется n приложения f применяется x.
Наконец, чтобы уйти некоторый Веселье - вот еще один способ определить plus:
```
(define plus (lambda (m) (lambda (n) ((m add1) n))))
```
(Ну, не слишком весело, так как этот, вероятно, более очевиден.)

Другие советы

^{(Убедитесь, что вы понимаете функции высшего порядка).} В Алонзо церковьS. Нетипное исчисление лямбды Функция является единственным примитивным типом данных. Там нет чисел, логических, списков или чего -либо еще, только функции. Функции могут иметь только 1 аргумент, но функции могут принимать и/или возвращать функции, а не значения этих функций, но сами функции. Поэтому, чтобы представлять цифры, логические, списки и другие типы данных, вы должны придумать умный способ, чтобы анонимные функции поддерживали их. Церковные цифры это способ представить натуральные числа. Отказ Три наиболее примитивных конструкция в нетипедном исчислении Lambda - это:

λx.x, ан идентификационная функция, принимает некоторую функцию и немедленно возвращает ее.
λx.x x, самостоятельное применение.
λf.λx.f x, Функциональное приложение, принимает функцию и аргумент и применяет функцию к аргументу.

Как вы кодируете 0, 1, 2 как не что иное, как функции? Нам как -то нужно построить понятие количество в систему. У нас есть только функции, каждая функция может быть применена только к 1 аргументу. Где мы можем увидеть что -то напоминающее количество? Эй, мы можем применить функцию к параметру несколько раз! Очевидно, что в 3 повторных вызове функции есть чувство: f (f (f x)). Отказ Итак, давайте кодируем это в исчислении Lambda:

0 = λf.λx.x
1 = λf.λx.f x
2 = λf.λx.f (f x)
3 = λf.λx.f (f (f x))

И так далее. Но как перейти от 0 до 1 или от 1 до 2? Как бы вы написали функцию, которая, учитывая число, вернет число, увеличенное на 1? Мы видим шаблон в церковных цифрах, с которыми всегда начинается термин λf.λx. и после того, как у вас есть конечное повторное применение фланг, поэтому нам нужно как -то войти в тело λf.λx. и обернуть его в другой f. Отказ Как изменить тело абстракции без уменьшения? Что ж, вы можете применить функцию, обернуть тело в функцию, а затем обернуть новое тело в старую абстракцию Lambda. Но вы не хотите, чтобы аргументы изменились, поэтому вы применяете абстракции к значениям одного имени: ((λf.λx.f x) f) x → f x, но ((λf.λx.f x) a) b) → a b, что не то, что нам нужно.

Поэтому add1 является λn.λf.λx.f ((n f) x): вы подаете заявку n к f а потом x Чтобы уменьшить выражение тела, затем примените f к этому телу, затем снова абстрагирует это с λf.λx.. Упражнение: тоже видите, что это правда, быстро учится β-восстановление и уменьшить (λn.λf.λx.f ((n f) x)) (λf.λx.f (f x)) увеличить 2 на 1.

Теперь понимая интуицию, стоящую за обертыванием тела в другой вызов функции, как мы реализуем добавление 2 чисел? Нам нужна функция, которая дана λf.λx.f (f x) (2) и λf.λx.f (f (f x)) (3), вернется λf.λx.f (f (f (f (f x)))) (5). Посмотрите на 2. Что если бы вы могли заменять это x с телом 3, то есть f (f (f x))? Чтобы получить тело 3, это очевидно, просто примените его к f а потом x. Отказ Теперь примените 2 к f, но затем нанесите его на тело 3, не чтобы x. Отказ Затем оберните его λf.λx. очередной раз: λa.λb.λf.λx.a f (b f x).

Вывод: Чтобы добавить 2 числа a и b вместе, оба из которых представлены как церковные цифры, вы хотите заменять x в a с телом b, так что f (f x) + f (f (f x)) = f (f (f (f (f x)))). Отказ Чтобы это произошло, применить a к f, тогда к b f x.

Ответ Эли технически правильный, но в тот момент, когда этот вопрос задается #apply Процедура не была введена, я не думаю, что авторы намеревались узнать, что студенты знали об этом или о таких понятиях, как карри, чтобы иметь возможность ответить на этот вопрос.

Они в значительной степени направляют один на ответ, предполагая, что один применил метод замены, а затем оттуда следует заметить, что эффект добавления является составом одного числа на другое. Композиция является концепцией была введена в упражнении 1.42; И это все, что требуется, чтобы понять, как аддитивная процедура может работать в этой системе.

; The effect of procedure #add-1 on `one`, and `two` was the composition of `f` 
; onto `one` and `f` onto `two`.
;
; one   : (λ (f) (λ (x) (f x)))
; two   : (λ (f) (λ (x) (f (f x))))
; three : (λ (f) (λ (x) (f (f (f x)))))
;
; Thus one may surmise from this that an additive procedure in this system would
; work by composing one number onto the other.
;
; From exercise 1.42 you should already have a procedure called #compose.
;
; With a little trial and error (or just plain be able to see it) you get the
; following solution.

(define (adder n m)
  (λ (f)
    (let ((nf (n f))
          (mf (m f)))
      (compose nf mf))))

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow