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

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