Путать с поведением этой процедуры

Question

(Context)

Я определил процедуру, которая применяет другой объект процедуры с одним аргументом к своему параметру дважды. Возьмем, к примеру, процедуру inc, которая добавляет 1 к своему аргументу, (double inc) добавит два. следовательно ((double inc) 5) возвращает 7.

(ПРОБЛЕМА)

Я ожидал, что (((double (double double)) inc) 5) вернется 13. Так как double double будет применять процедуру 4 раза и, следовательно, самый левый double будет приводить к применению однопараметрического параметра. процедура 8 раз. Линейный рост.

Я не прав. Посмотрите ниже, что на самом деле возвращает процедура.

Очевидно, что я что-то упускаю, и в моем понимании есть изъян.

(define (double proc)
(lambda (y) (proc (proc y))))

(define (inc x) (+ x 1))

> ((double inc) 5)
7
> (((double double) inc) 5)
9
> (((double (double double)) inc) 5)
21
> (((double (double (double double))) inc) 5)
261    
> 

Answer 1

Это должно быть довольно легко вычесть, используя как причину, так и модель замещения.

Причина:

(double double)

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

(double (double double))

Это двойная четверка. Результат четырехугольника будет четырехугольным, делая его 4 * 4. При применении с функцией это будет применяться 16 раз.

(double (double (double double)))

Это удваивает предыдущий. Затем снова то же самое. 16 * 16 позволяет применить результат 256 раз.

Таким образом, (double double) - это 2^2, (double (double double)) - это (2^2)^2, а (double (double (double double))) - это ((2^2)^2)^2 или 2^8 для краткости.

Это относится к лямбда-исчислению, где мощность определяется как λb.λe.e b или (lambda (b) (lambda (e) (e b)). Теперь double является церковной цифрой для 2. Вы видите, что вы делаете ((2^2)^2)^2?

Замена

Вот сокращенные выражения. Я иногда прыгаю шаги позже, потому что это почти то же самое, что происходит несколько раз.

((double inc) 5)               ; ==>
((lambda (y) (inc (inc y))) 5) ; ==>
(inc (inc 5))                  ; ==> 7


(((double double) inc) 5)                   ; ==>
(((lambda (y) (double (double y))) inc) 5)  ; ==>
(((lambda (y) (double (double y))) inc) 5)  ; ==>
((double (double inc)) 5)                   ; ==>
((double (lambda (y) (inc (inc y)))) 5)     ; ==>
((lambda (y) ((lambda (y) (inc (inc y))) ((lambda (y) (inc (inc y))) y))) 5) ; ==>
((lambda (y) (inc (inc (inc (inc y))))) 5) ; ==>
(inc (inc (inc (inc 5)))) ; ==> 9


(((double (double double)) inc) 5)                                                                ; ==>
(((double (lambda (y) (double (double y)))) inc) 5)                                               ; ==>
(((lambda (y) ((lambda (y) (double (double y))) ((lambda (y) (double (double y))) y))) inc) 5)    ; ==>
(((lambda (y) (double (double (double (double y))))) inc) 5)                                      ; ==>
((double (double (double (lambda (y) (inc (inc y)))))) 5)                                         ; ==>
((double (double (lambda (y) (inc (inc (inc (inc y))))))) 5)                                      ; ==>
(inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))))))))) ; ==> 21

Я оставлю последнее как упражнение.

Answer 2

Проблема заключается в вашей интерпретации того, что расширяется double при вложении.

Просто примените замену y на inc, один уровень за раз, и вы увидите, что происходит:

(double inc) расширение с использованием let, чтобы прояснить ситуацию:

(lambda (y)
        (let ([proc inc])
             ((proc (proc y))))

Пока все хорошо.

((double double) inc) расширение:

     (lambda (y)
        (let ([proc (lambda (y_0) (double (double y_0)))])
             (proc (proc y))))

Первое приложение работает по назначению, но второе удваивает не применение функции inc, а самой функции double, поскольку вы применяете double к функции double в (double double).

Если вы сделаете это снова, то есть ((double (double double) inc), вы можете увидеть, что это становится грязным ...

То, что вы, вероятно, ищете, это применить результат одного приложенияdouble до результата другого отдельного приложения ...

Как в:

> ((double (double (double inc))) 5)
13
> ((double (double (double (double inc)))) 5)
21