Числа Черча - реализовать один, два, а дополнение


Даны следующие упражнения:

Упражнение 2.6

В случае, представляющих пары процедур не было умопомрачительной достаточно, считают,что на языке, который могут манипулировать процедуры, мы можем обойтись без номера (по крайней мере, пока соответствующие неотрицательные целые числа) по реализации 0 и работу добавление 1 а

(define zero (lambda (f) (lambda (x)
x)))

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

Это представление известно как Церковь цифры, в честь его изобретателя, Алонсо Церковь, логик, который изобрел исчисление.

Определить одну и две сразу (не в условий ноль и добавить-1). (Подсказка: Используйте замещения для оценки (добавить-1 ноль)). Дать прямое определение добавление процедуры + (не в плане повторного применения добавить-1).

Я написал это решение. Я не 100% уверен, что правильный ответ есть, и я не уверен, что лучший способ проверить мое решение так что вполне возможно, что я допустил ошибку в моем ответе. Пожалуйста, дайте мне знать, что вы думаете.

;given definitions
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))
; exercise 2.6: define one and two directly -
; not in terms of zero or add-1
(define one
  (lambda (f) (lambda (x) (f (f x)))))
(define two
  (lambda (f) (lambda (x) (f ((f (f x)) x)))))

(define (church-plus a b)
  (define (church-num n)
    (cond ((= 0 a) (lambda (x) x))
          ((= 1 a) (lambda (f) (lambda (x) (f ((n f) x)))))
          (else (church-num (- n 1)))))
  (church-num (+ a b)))


1484
2
задан 4 апреля 2011 в 02:04 Источник Поделиться
Комментарии
1 ответ

Церковь определила цифры как повторное применение функции. Первые несколько числительных определяются так:

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

... и так далее.

Чтобы увидеть, как одно проистекает, начнем с определения одного как (добавьте-1 ноль) , а затем выполните приложения, как показано ниже (я уже писал каждая функция должна быть применена и один аргумент на отдельной линии для наглядности):

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

(define one
(add-1 ;; substitute with definition of add-1
zero))

(define one
((lambda (n) ;; apply this function to argument zero
(lambda (f) (lambda (x) (f ((n f) x)))))
zero))

(define one
(lambda (f) (lambda (x) (f ((zero ;; substitute with definition of zero
f) x)))))

(define one
(lambda (f) (lambda (x) (f (((lambda (f) ;; apply this function to argument f
(lambda (x) x))
f)
x)))))

(define one
(lambda (f) (lambda (x) (f ((lambda (x) ;; apply this function to argument x
x)
x)))))

(define one
(lambda (f) (lambda (x) (f x)))) ;; we're done!

Вы можете попробовать свои силы в двух аналогичным образом. =)

По определению, Церковь цифрами повторное применение функции. Если эта функция была целая функция инкремента и первоначальный параметр был 0, то мы могли бы создать все натуральные числа 0, 1, 2, 3, .... Это важный инсайт.

Таким образом, Церковь счисления-это функция, которая принимает один аргумент, приращения функции, и возвращает функцию, которая принимает один аргумент, добавка личность. Таким образом, если применить церкви входит в число приращения функции (лямбда (Н) (+ 1 П)) (или просто добавьте 1 на схеме), которые мы затем применяются к целым добавка тож 0, мы получим целое число, эквивалентное Церкви Матери в результате. В код:

(define (church-numeral->int cn)
((cn add1) 0))

Несколько тестов:

> (church-numeral->int zero)
0
> (church-numeral->int one)
1
> (church-numeral->int two)
2
> (church-numeral->int (add-1 two))
3
> (church-numeral->int (add-1 (add-1 two)))
4

Церковь-числительное дополнение следует взять две церковные цифры в качестве входных данных, а не чисел, как в коде.

Мы используем понимание выше о функции инкремента и аддитивной личности, чтобы заметить, что целочисленное сложение просто многократное увеличение. Если мы хотим добавить целые числа а и б, мы начинаем с числа б и увеличить его в раза, чтобы получить а + б.

То же самое относится к Церкви цифры. Вместо того, чтобы использовать целочисленное приращение функции и число аддитивной личности, мы используем Церкви приращение функции добавить-1 и мы начинаем с церкви входит в качестве добавки личность. Таким образом, мы можем реализовать Церкви-матери, кроме как:

(define (plus cn-a cn-b)
((cn-a add-1) cn-b))

Несколько примеров:

(define three (plus one two))
(define four (plus two two))
(define five (plus two three))
(define eight (plus three five))

... и связанных тестов:

> (church-numeral->int three)
3
> (church-numeral->int four)
4
> (church-numeral->int five)
5
> (church-numeral->int eight)
8

2
ответ дан 5 апреля 2011 в 10:04 Источник Поделиться