对此过程的行为感到困惑

Question

（语境）

我定义了一个过程，它两次将另一个单参数过程对象应用于它的参数。以过程 inc 为例，它的参数加 1，(double inc) 将加 2。因此 ((double inc) 5) returns 7.

（问题）

我预计 (((double (double double)) inc) 5) 到 return 13。由于 double double 将应用程序 4 次，因此最左边的 double 将导致应用单参数程序 8 次。线性增长。

我错了。查看下面的程序实际上 returns.

显然我遗漏了一些东西并且我的理解存在缺陷。

(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 扩展的解释。

只需将 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

Answer 2

这应该很容易使用原因或替代模型推导出来。

原因：

(double double)

这就像双倍但两倍，四倍。当应用一个函数时，它将应用该函数 4 次。

(double (double double))

这是双倍的四倍。 quadrouple 的结果将翻四倍，成为 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。

这与 lambda 演算有关，其中幂定义为 λ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

最后一个留作练习。

对此过程的行为感到困惑

Confused with behavior of this procedure

lambda

scheme

prediction

racket

r5rs

原因：

换人