Как вызвать функции номера схемы из SICP

В SICP (например, 2.6) следующие функции описываются как способы «обойтись без цифр». Я чешу, пытаясь понять это. Для начала, как эти функции вызываются? Могу ли я на самом деле применить их каким-то образом, где вывод будет 1? (Или любое другое число?)

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

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

Мои первые попытки не увенчались успехом:

Welcome to DrScheme, version 4.1.5 [3m].
Language: Simply Scheme; memory limit: 128 megabytes.
> (add-1 (zero))
. . procedure zero: expects 1 argument, given 0
> (add-1 zero)
#<procedure>
> (add-1 1)
#<procedure>
> ((add-1 1))
. . #<procedure>: expects 1 argument, given 0
>

scheme sicp
person Leonard    schedule 05.05.2009    source источник
comment
Вы можете не смотреть на en.wikipedia.org/wiki/   -  person Sebastian Krog    schedule 06.05.2009

Ответы (3)


arrow_upward
9
arrow_downward

Эти функции, представляющие числа, называются Церковными числами (как указано в SICP). Их существование означает, что вы можете определить систему вычислений (такую ​​как лямбда-исчисление), не имея чисел в качестве объектов первого класса — вместо этого вы можете использовать функции в качестве примитивных объектов. Этот факт представляет в основном теоретический интерес; Числа Черча не подходят для практических вычислений.

Вы можете убедиться в правильности своих определений числительных Черча, применяя их с другими объектами в качестве аргументов. Когда вы применяете число Черча, представляющее n, к функции f, вы получаете другую функцию, которая применяет f к своему аргументу n раз, например, f(f(f(x))) для n=3.

> (define (double x) (* 2 x))
> (zero double)
#<procedure>
> ((zero double) 1)
1
> ((zero double) 100)
100
> (define one (add-1 zero))
> ((one double) 1)
2
> ((one double) 100)
200
> (define (cons-a x) (cons 'a x))
> ((zero cons-a) '())
()
> (((add-1 one) cons-a) '(1 2 3))
(a a 1 2 3)
person Nathan Kitchen    schedule 05.05.2009
comment
Пенроуз включает это в «Новый разум императора», я думаю, это просто предлог для использования другого шрифта. (в книге он представляет ноль и единицу как числа контурным шрифтом) - person Jason S; 06.05.2009

arrow_upward
3
arrow_downward

это оригинальное лямбда-исчисление, оно не производит числа, оно полностью заменяет числовой тип функциями.

Итак, у вас есть «нулевая» функция, и если вы вызовете для нее add-1, вы не получите 1, вы получите другую функцию, которая представляет 1. Дело в том, что созданные функции соответствуют основным арифметическим аксиомам, поэтому они эквивалентны натуральным числам

person Javier    schedule 05.05.2009

arrow_upward
0
arrow_downward 

(define (as-primitive-num church-num)
    (define (inc a) (+ a 1))
    ((church-num inc) 0))

;testing:
(define one (add-1 zero))
(define two (add-1 one))

(display (as-primitive-num one)) (newline)
(display (as-primitive-num two)) (newline)

и вывод:

    1
    2
person user1651640    schedule 06.09.2012