手动执行函数体替换以查看过程如何工作

Question

我正在逐步执行另一个答案 () 中提供的过程，并且我正在努力尝试完成该过程中的替换。这是我现在所在的位置：

; main function
(define (curry num func)
  (cond ((= num 1) func)
        (else (lambda (x) (curry (- num 1)
                                 (lambda args (apply func (cons x args))))))))

这是我正在打的电话：

(define (add-3 x y z) (+ x y z))
(add-3 100 200 300)
; 600
((((curry 3 add-3) 100) 200) 300)
; 600

以下是我尝试通过代入代码来跟踪函数工作原理的尝试：

; Sub 1/3 (curry 3 add-3)
(lambda (x) (curry (- 3 1)
                   (lambda args (apply add-3 (cons x args)))))
; verify it works
((((lambda (x) (curry (- 3 1)
                   (lambda args (apply add-3 (cons x args))))) 100) 200) 300)
; 600 -- OK

; Sub 2/3 (curry 2 <func>)
; <func> = (lambda args (apply add-3 (cons x args)))
(lambda (x)
     (lambda (x) (curry (- 2 1)
                   (lambda args (apply (lambda args (apply add-3 (cons x args))) (cons x args))))))
; verify it works
((((lambda (x)
     (lambda (x) (curry (- 2 1)
                   (lambda args (apply (lambda args (apply add-3 (cons x args))) (cons x args)))))) 100) 200) 300)
; 700 -- Wrong output

我猜 700 值与我有两个 lambda (x) 并且没有正确封闭它们或其他东西有关。进行上述替换的正确方法是什么？

Answer 1

严格来说，你不应该减少 lambda 下的术语，因为该语言有 call-by-value reduction strategy. You will also find it less confusing that way (there are reduction strategies that allow you to reduce a term under a lambda, but you need to be careful to avoid unintentional variable capture).

假设您正确遵循按价值调用减少策略：

(lambda (x) 
  (curry (- 3 1)
         (lambda args (apply add-3 (cons x args)))))

是最终答案。您不需要进一步减少任何东西。

另一方面，您可以进一步减少以下项：

((lambda (x) 
   (curry (- 3 1)
          (lambda args (apply add-3 (cons x args))))) 100)
=>
(curry (- 3 1) (lambda args (apply add-3 (cons 100 args))))
=>
(curry 2 (lambda args (apply add-3 (cons 100 args))))
=>
(cond ((= 2 1) (lambda args (apply add-3 (cons 100 args))))
      (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(cond (#f (lambda args (apply add-3 (cons 100 args))))
      (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(cond (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(lambda (x) 
  (curry (- 2 1)
         (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))

如果您愿意，可以检查它是否正确：

(((lambda (x) 
    (curry (- 2 1)
           (lambda args
             (apply (lambda args (apply add-3 (cons 100 args)))
                    (cons x args)))))
  200)
 300)

;=> evaluates to 600

Answer 2

一旦你到达

((((lambda (x) (curry 2
                 (lambda args 
                   (apply add-3 (cons x args))))) 
   100) 200) 300)

对于如何继续，您有两种选择。您可以尝试替换内部 curry，就像您在问题中所做的那样，但您必须小心避免引入另一个同名变量，方法是重命名否则会发生冲突的新变量。因此，让我们使用 x1 和 arg1 稍微更改一下，为添加不同的数字做准备：

((((lambda (x1) (curry 2
                  (lambda args1 
                    (apply add-3 (cons x1 args1))))) 
   100) 200) 300)

现在展开里面的curry，就没有冲突了：

((((lambda (x1) 
     (lambda (x2)
       (curry 1 (lambda args2
                  (apply (lambda args1 
                           (apply add-3 (cons x1 args1)))
                         (cons x2 args2)))))) 
100) 200) 300)

观察结果仍然是 600。当然，您可以简单地删除 (curry 1)。从这里开始，您可以开始将这些 lambda 的应用程序替换为参数 100、200 和 300。

但我认为走另一条路更简单。一旦您尝试评估的表达式是 ((lambda (x) ...) 100)，就不要深入研究 ... 来制作更复杂的 lambda。相反，将正文中的 x 替换为 100。这将使事情更具体一些，并且恰好与 Scheme 解释器实际计算表达式的方式一致。

所以从

((((lambda (x) (curry 2
                 (lambda args 
                   (apply add-3 (cons x args))))) 
   100) 200) 300)

我更愿意升入

(((curry 2
         (lambda args 
           (apply add-3 (cons 100 args))))
    200) 300)

现在当我们扩展内部 curry 时没有冲突。（为清楚起见，我使用名称 args1 和 args2，但实际上它们在范围上并不冲突——您可以将它们都称为 args）：

(((lambda (x)
    (curry 1
           (lambda args2
             (apply (lambda args1 
                      (apply add-3 (cons 100 args1)))
                    (cons x args2)))))
    200) 300)

将(curry 1 f)替换为f，将200替换为x，留下

((lambda args2
   (apply (lambda args1 
            (apply add-3 (cons 100 args1)))
          (cons 200 args2)))
   300)

现在所有 currying 都已解决，只剩下对 lambda 的 apply 调用。和以前一样，让我们解决最外层的问题，将 args2 作为 list '(300):

(apply (lambda args1 
         (apply add-3 (cons 100 args1)))
       (cons 200 '(300)))
   
(apply (lambda args1 
         (apply add-3 (cons 100 args1)))
       '(200 300))

接下来计算此 lambda 上的 apply，将 '(200 300) 替换为 args1：

(apply add-3 (cons 100 '(200 300)))

简化 cons 和最后一个 apply，我们得到了我们希望找到的结果：

(add-3 100 200 300)

Answer 3

通常，使用定义的已知子句通过添加新的 explicit 子句来扩展定义，对于 n = 2,3,...，并相应地代入，我们得到 （振作起来）：

(define (curry n f)
  (cond 
    ((= n 1) f)
    (else   (lambda (x)
              (curry (- n 1)
                (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
               (curry 1
                 (lambda xs (apply f (cons x2 xs))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (curry 2
                 (lambda xs3 (apply f (cons x3 xs3))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply (lambda xs3 (apply f (cons x3 xs3))) 
                                   (cons x2 xs))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))

-------- (apply (lambda args B) L)  ==  (let ((args L)) B) -------------

==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (let ((xs3 (cons x2 xs)))
                               (apply f (cons x3 xs3)))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                       (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (curry 3
                 (lambda xs4 (apply f (cons x4 xs4))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                       (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (lambda (x3)
                 (lambda (x2)
                   (lambda xs (apply (lambda xs4 (apply f (cons x4 xs4)))
                                     (cons x3 
                                       (cons x2 xs))))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                        (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (lambda (x3)
                 (lambda (x2)
                   (lambda xs (apply f (cons x4 
                                         (cons x3 
                                           (cons x2 xs))))))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))

等等

因此，在伪代码中，

((curry 1 f) a ...) == (f a ...)
(((curry 2 f) a) b ...) == (f a b ...)
((((curry 3 f) a) b) c ...) == (f a b c ...)
....

等（其中符号 c ... 表示“零个或多个参数”）。

为什么是(apply (lambda args B) L) == (let ((args L)) B)？考虑

(apply (lambda args B) (list x y z))
=
((lambda args B)   x y z)
=
(let ((args (list x y z)))  B)

手动执行函数体替换以查看过程如何工作

Manually doing function body-substitution to see how a procedure works

scheme

lisp

racket

currying

sicp