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

Question

我正在逐步完成另一个答案(https://stackoverflow.com/a/68013528/651174)中提供的过程，我正在努力完成这个过程中的替换。这就是我现在的处境：

; 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 (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。取而代之的是，在身体中用100代替x。这将使事情更加具体，并且恰好与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都解决了，只剩下apply的调用在lambda上。如前所述，让我们用args2作为列表'(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 2

严格地说，您不应该在lambda下减少一个术语，因为语言有逐值递减策略。您也会发现这样做不那么令人困惑(有一些简化策略允许您在lambda下减少一个术语，但您需要小心使用避免无意中的变量捕获)。

假设您正确地遵循按值调用策略：

(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 3

通常，使用定义的已知子句来扩展定义，为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)