1

如何进行替换？我试图追踪，但我真的不明白发生了什么......代码：

(define (repeated f n)
  (if (zero? n)
    identity
    (lambda (x) ((repeated f (- n 1)) (f x)))))

f 是一个函数，n 是一个整数，它给出了我们应该应用 f 的次数。....谁能帮我解释一下。我知道它会返回几个程序，我想相信它会成功f(f(f(x)))

好的，我会以不同的方式重新问这个问题，因为我上次并没有真正得到答案。考虑这段代码

(define (repeated f n)
  (if (zero? n)
    identity
    (lambda (x) ((repeated f (- n 1)) (f x)))))

其中 n 是一个正整数， f 是一个任意函数：方案如何在此代码上运行假设我们给出(repeated f 2). 会发生什么？这是这样想的：

(f 2)

(lambda (x) ((repeated f (- 2 1)) (f x))))


(f 1)

(lambda (x) ((lambda (x) ((repeated f (- 1 1)) (f x)))) (f x))))


(f 0)

(lambda (x) ((lambda (x) (identity (fx)))) (fx))))

> (lambda (x) ((lambda (x) (identity (f x)))) (f x))))

>  (lambda (x) ((lambda (x) ((f x)))) (f x))))

这是我首先被卡住了，我希望它去 (f(f(x)) 但现在我会得到 (lambda x ((fx) (fx)) ，括号肯定是错误的，但我想你明白我的意思意思是。我关于解释器如何工作的论点有什么问题

4

4 回答 4

2

您的实现实际上延迟了进一步的递归并返回一个过程，该过程的主体将创建自身的副本以在运行时完成任务。

例如。(repeated double 4)==>(lambda (x) ((repeated double (- 4 1)) (double x))) 因此，当调用它时，它((repeated double 4) 2)会((repeated double (- 4 1)) (double 2))) 在操作数部分的计算(lambda (x) ((repeated double (- 3 1)) (double x)))结果处运行，依此类推，在运行时进行闭包，因此计算结果与此相等，但在运行时分阶段进行。

((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) (identity x)) (double x))) (double x))) (double x))) (double x))) 2)

编写相同功能的另一种方式如下：

(define (repeat fun n)
  (lambda (x)
    (let repeat-loop ((n n)
                      (x x))
      (if (<= n 0) 
          x
          (repeat-loop (- n 1) (fun x))))))

(define (double x) (+ x x))
((repeat double 4) 2) ; ==> 32
于 2013-10-08T21:56:11.440 回答
2

你有一个函数，它接受一个函数f和一个非负整数n并返回函数f n，即f(f(f(...f(n)...)。根据你对递归的看法，这可以可以通过两种方式中的任何一种直接实现。在这两种情况下，如果n为 0，那么您只需要一个返回其参数的函数，并且该函数就是identity函数。（这是约定俗成的，与 x 0 = 1。更深入地考虑它确实有意义，但这可能超出了这个问题的范围。）

您如何处理递归案例是您有一些选择的地方。第一个选项是将f n (x)视为f(f n-1 (x))，其中您调用f 的结果是使用x调用f n-1：

(define (repeated f n)
  (if (zero? n)
      identity
      (lambda (x)
        (f ((repeated f (- n 1)) x)))))

另一种选择是将f n (x)视为f n-1 (f(x))，其中 _f n-1以f(x)的结果被调用。

(define (repeated f n)
  (if (zero? n)
      identity
      (lambda (x)
        ((repeated f (- n 1)) (f x)))))

无论哪种情况，这里要注意的重要一点是，在 Scheme 中，像

(function-form arg-form-1 arg-form-2 ...)

通过评估function-form产生一个值function-value（应该是一个函数）并评估每个arg-form-i产生值arg-value-i，然后使用arg-values调用_function-value_ 来评估。由于产生一个函数，它适合作为：(repeated ...)function-form

 (f ((repeated f (- n 1)) x))
;    |--- f^{n-1} ------| 
;   |---- f^{n-1}(x) ------|
;|------f(f^{n-1}(x)) ------|

 ((repeated f (- n 1)) (f x))
; |--- f^{n-1} ------|
;|---- f^{n-1}(f(x))--------|

根据 Will Ness 的评论，值得指出的是，虽然这些是分解这个问题的自然方法（即，基于等式 f n (x) = f n-1 (f(x)) = f(f n- 1（x））），它不一定是最有效的。这些解决方案都需要计算一些中间函数对象来表示需要大量存储的f n-1 ，然后在此基础上进行一些计算。直接计算 f n (x) 非常简单有效，例如repeat：

(define (repeat f n x)
  (let rep ((n n) (x x))
    (if (<= n 0)
        x
        (rep (- n 1) (f x)))))

那么，一个更有效的版本repeated只是简单地将 的x论点柯里化repeat：

(define (repeated f n)
  (lambda (x) 
    (repeat f n x)))

这应该比其他任何一个实现具有更好的运行时性能。

于 2013-10-08T21:29:53.183 回答
0

等式推理在这里会很有帮助。想象一下具有类似 Haskell 语法的基于lambda 演算的语言，实际上是一种组合演算。

这里，括号仅用于表达式的分组（不适用于函数调用，它根本没有语法——只是并列）：f a b c与 相同((f a) b) c，与 Scheme 相同(((f a) b) c)。like f a b = ...的定义等价于 (以及is 的(define f (lambda (a) (lambda (b) ...)))快捷方式。(lambda (a) ...)(\a-> ...)

Scheme 的语法只是模糊了这里的画面。我的意思不是括号，而是被迫显式地使用 lambdas 而不仅仅是方程式，并自由地改变参数：

f a b = \c -> ....   ===   f a b c = ....      ; `\ ->` is for 'lambda'

您的代码几乎等同于

repeated f n x                          ; (define (repeated f n)
  | n <= 0    = x                       ;  (if (zero? n)  identity
  | otherwise = repeated f (n-1) (f x)  ;    (lambda (x)
                                        ;      ((repeated f (- n 1)) (f x)))))

（读|作“何时”）。所以

  repeated f 2 x =     ; ((repeated f 2) x) = ((\x-> ((repeated f 1) (f x))) x)
= repeated f 1 (f x)       ;      = ((repeated f 1) (f x))
= repeated f 0 (f (f x))   ;      = ((\y->((repeated f 0) (f y))) (f x))
= f (f x)                  ;      = ((\z-> z) (f (f x)))
                           ;      = (f (f x))

上面的缩减序列省略了 Scheme 中环境框架创建和链接的细节，但一切都非常直观。f是一样的，f不管我们什么时候执行减法等等。n-1 where n=21

于 2013-10-15T09:36:38.140 回答
0

丹尼。我认为，如果我们repeated使用较小的 n（0、1 和 2）值，将能够看到函数如何转换为 f(f(f(...(x)))。我假设identity' 的实现是(define (identity x) x)（即按原样返回其唯一参数），并且“then”部分if应该是(identity f).

(repeated f 0) ;should apply f only once, no repetition
-> (identity f)
-> f

(repeated f 1) ;expected result is f(f(x))
-> (lambda (x) ((repeated f 0) (f x)))
-> (lambda (x) (f (f x))) ;we already know that (repeated f 0) is f

(repeated f 2) ;expected result is f(f(f(x)))
-> (lambda (x) ((repeated f 1) (f x)))
-> (lambda (x) (f (f (f x)))) ; we already know that (repeated f 1) if f(f(x))

... 等等。

于 2013-10-08T21:34:43.213 回答