延续传递风格程序
Continuation passing style procedures
我很难理解连续传递样式中的过程如何“记住”来自先前函数调用的值。
作为示例，我有以下过程将从列表中过滤偶数值：
(define (get-pairs alist proc)
(if (null? alist)
(proc '())
(get-pairs
(cdr alist)
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l)))))))
然后我调用它：
(get-pairs '(1 2)
(lambda (n) (display n)))
得到预期的结果(2).
get-pairs会递归调用自身，直到它的参数alist为空。那么最后一个函数调用将是：(get-pairs '() proc)。 proc 将是程序：
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l))))
在这个 lambda 主体中，alist 和 proc 是前面函数调用的参数：(get-pairs '(2) proc)。我的问题是，如果 proc 仅在最后评估，每个 lambda 过程如何“记住”过去函数调用的参数？
或者是在每次调用 get-pairs 时，作为参数传递给下一次调用的 lambda 主体被“分析”，对应的值为 alist 和 proc 已经替换到它的正文中了吗？
TL;DR: 闭包 由 tail-call-optimized 函数创建必须捕获一个 copy 的（相关部分）他们的定义环境。或者，忽略 TCO 部分，将其视为常规递归函数，其中在递归函数执行期间创建的任何 lambda 函数都是闭包，捕获它引用的变量的值。
这个可以在Scheme评估的环境模型的框架下理解。
每次调用 (lambda (...) ...) 都会创建一个新的 lambda 函数对象，隐式地与其定义环境配对，一起称为 closure.
get-pairs 的每次调用都会创建自己全新的调用框架，并且从 创建的任何 lambda 表达式 都将保留指向 (的副本) 那个框架。
使用以下变体可以更容易地看到这一点，它们执行与问题中的变体完全相同的功能：
(define (get-pairs1 alist proc)
(if (null? alist)
(proc '())
(get-pairs1
(cdr alist)
(let ((alist alist)) ; creates fresh new environment frame
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l))))))))
(define (get-pairs2 alist proc)
(if (null? alist)
(proc '())
(get-pairs2
(cdr alist)
(let* ((alist alist)
(num (car alist))
(newproc
(if (zero? (remainder num 2))
(lambda (l) (proc (cons num l)))
(lambda (l) (proc l)))))
newproc))))
proc 是 not“在最后评估”，过程 是变量 proc的值在最后被调用，但是变量proc的值在每次调用时都被找到。并且在每次调用时该值都是不同的，即 new lambda 函数对象在每次单独调用 get-pairs 时重新创建。每次调用 get-pairs 时变量 proc 的值都不同。
因此，对于示例调用 (get-pairs2 '(1 2 3 4) display)，最终 proc 的调用与
相同
((lambda (l4) ; |
((lambda (l3) ; | |
((lambda (l2) ; | | |
((lambda (l1) ; | | | |
(display ; 1 2 3 4
l1)) ; | | | |
(cons 2 l2))) ; | | |
l3)) ; | |
(cons 4 l4))) ; |
'())
;; i.e.
;; l1 = cons 2 l2
;; l2 = l3
;; l3 = cons 4 l4
;; l4 = '()
也可以用伪代码写成
(((((display ∘ identity) ∘ {cons 2}) ∘ identity) ∘ {cons 4}) '())
; └───────1──────────┘
; └───────────────2───────────────┘
; └─────────────────────────3──────────────────┘
;└───────────────────────────────────4─────────────────────┘
;; 1: created on 1st invocation of `get-pairs2`
;; 2: created on 2nd invocation of `get-pairs2`
;; 3: created on 3rd invocation of `get-pairs2`
;; 4: created on the final 4th invocation of `get-pairs2`,
;; and then called with `'()` as the argument
其中 {cons n} 表示部分应用 cons，即 (lambda (l) (cons n l))，而 identity 是 (lambda (l) l)。
哦，还有∘代表函数组合，(f ∘ g) = (lambda (x) (f (g x))).
另请参阅我的其他一些可能相关的答案，here and here。
通过调用 (get-pairs2 '(1 2 3 4)) step-by-step，使用基于 let 的 re-writes 模拟函数调用，我们得到（稍微简化）
(get-pairs2 '(1 2 3 4) display)
=
(let ((alist '(1 2 3 4)) ; '(1 2 3 4)
(proc display))
(let* ((num (car alist)) ; 1
(newproc (lambda (l) (proc l))))
(let ((alist (cdr alist)) ; '(2 3 4)
(proc newproc))
(let* ((num (car alist)) ; 2
(newproc (lambda (l) (proc (cons num l)))))
(let ((alist (cdr alist)) ; '(3 4)
(proc newproc))
(let* ((num (car alist)) ; 3
(newproc (lambda (l) (proc l))))
(let ((alist (cdr alist)) ; '(4)
(proc newproc))
(let* ((num (car alist)) ; 4
(newproc (lambda (l) (proc (cons num l)))))
(let ((alist (cdr alist)) ; '()
(proc newproc))
(proc '()))))))))))
在 DrRacket 的代码编辑器中加载它 window 并将鼠标悬停在各种标识符上是一个有趣的游戏，可让您查看每个标识符所指的内容。 运行 带有 Ctrl-R 的代码也产生与原始函数调用相同的结果。
另一个“有趣”的练习是检查上面嵌套的 let 表达式并通过向其添加唯一索引手动重命名每个标识符（将 proc 更改为 proc1，proc2 等等）所以每个名字都变得独一无二。
好的，我会为你做的，尤其是 DrRacket 有一个很好的“重命名标识符”功能，这使得它变得更容易和更少 error-prone。但也请尝试自己做。
(let ((alist '(1 2 3 4)) ; '(1 2 3 4)
(proc display))
(let* ((num (car alist)) ; 1
(newproc (lambda (l) (proc l))))
(let ((alist2 (cdr alist)) ; '(2 3 4)
(proc2 newproc))
(let* ((num2 (car alist2)) ; 2
(newproc2 (lambda (l) (proc2 (cons num2 l)))))
(let ((alist3 (cdr alist2)) ; '(3 4)
(proc3 newproc2))
(let* ((num3 (car alist3)) ; 3
(newproc3 (lambda (l) (proc3 l))))
(let ((alist4 (cdr alist3)) ; '(4)
(proc4 newproc3))
(let* ((num4 (car alist4)) ; 4
(newproc4 (lambda (l) (proc4 (cons num4 l)))))
(let ((alist5 (cdr alist4)) ; '()
(proc5 newproc4))
(proc5 '()))))))))))
所以你看，这不一样proc。其中有五个，每个都可能不同，每个都位于不同的嵌套环境框架中。
您可能会问，为什么要 嵌套 环境？毕竟 get-pairs2 是 tail-recursive，所以它不能那样做，可以 re-use 它的调用框架用于下一次调用。
确实如此，但它仍然是与代码运行效率相关的实现细节，不会改变其含义（语义）。 在语义上 更容易看出代码的含义，嵌套 let re-writes.
尽管如此，这是一个有效的观点，也是您困惑的潜在根源。我也曾被这一点弄糊涂过。
这就是为什么我在 post 的开头写了“（副本） 环境框架”。即使 tail-recursive 调用可以——甚至可能必须，在 Scheme 的 TCO 保证下——re-use 它自己的下一次调用调用框架，新创建的闭包必须保持 它的自己的副本，以免引入语义不同标识符的错误合并。
确实，环境扁平化和帧重用可以通过以下时间计算来描述：
;; re-use the tail-recursive call frame {alist proc}
(let ((alist '(1 2 3 4))
(proc display)
(num #f))
(set! num (car alist)) ; 1
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc l))))
(set! alist (cdr alist)) ; (2 3 4)
(set! num (car alist)) ; 2
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc (cons num l)))))
(set! alist (cdr alist)) ; (3 4)
(set! num (car alist)) ; 3
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc l))))
(set! alist (cdr alist)) ; (4)
(set! num (car alist)) ; 4
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc (cons num l)))))
(set! alist (cdr alist)) ; ()
(proc '()))
或者作为实际编译的定义，
(let ((alist '(1 2 3 4))
(proc display)
(num #f))
(let loop ()
(set! num (car alist))
(set! proc (let ((num num) (proc proc))
(if (zero? (remainder num 2))
(lambda (l) (proc (cons num l)))
(lambda (l) (proc l)))))
(set! alist (cdr alist))
(if (null? alist)
(proc '())
(loop))))
那么现在有多少 proc？ :)
（仍然是五个，否则它不会工作...即有一个 binding 但五个 values 是在循环的 运行 期间创建的，每个都将前一个包含在其中（或者，实际上，持有对它的引用）；当最后一个 proc 值——它是一个函数——最后 运行s，它调用它“内部”的那个，那个调用“内部”的那个 it，依此类推回到第一个 proc，我们已经开始的display。）
我很难理解连续传递样式中的过程如何“记住”来自先前函数调用的值。
作为示例，我有以下过程将从列表中过滤偶数值：
(define (get-pairs alist proc)
(if (null? alist)
(proc '())
(get-pairs
(cdr alist)
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l)))))))
然后我调用它：
(get-pairs '(1 2)
(lambda (n) (display n)))
得到预期的结果(2).
get-pairs会递归调用自身，直到它的参数alist为空。那么最后一个函数调用将是：(get-pairs '() proc)。 proc 将是程序：
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l))))
在这个 lambda 主体中，alist 和 proc 是前面函数调用的参数：(get-pairs '(2) proc)。我的问题是，如果 proc 仅在最后评估，每个 lambda 过程如何“记住”过去函数调用的参数？
或者是在每次调用 get-pairs 时，作为参数传递给下一次调用的 lambda 主体被“分析”，对应的值为 alist 和 proc 已经替换到它的正文中了吗？
TL;DR: 闭包 由 tail-call-optimized 函数创建必须捕获一个 copy 的（相关部分）他们的定义环境。或者，忽略 TCO 部分，将其视为常规递归函数，其中在递归函数执行期间创建的任何 lambda 函数都是闭包，捕获它引用的变量的值。
这个可以在Scheme评估的环境模型的框架下理解。
每次调用 (lambda (...) ...) 都会创建一个新的 lambda 函数对象，隐式地与其定义环境配对，一起称为 closure.
get-pairs 的每次调用都会创建自己全新的调用框架，并且从 创建的任何 lambda 表达式 都将保留指向 (的副本) 那个框架。
使用以下变体可以更容易地看到这一点，它们执行与问题中的变体完全相同的功能：
(define (get-pairs1 alist proc)
(if (null? alist)
(proc '())
(get-pairs1
(cdr alist)
(let ((alist alist)) ; creates fresh new environment frame
(lambda (l)
(let ((num (car alist)))
(if (zero? (remainder num 2))
(proc (cons num l))
(proc l))))))))
(define (get-pairs2 alist proc)
(if (null? alist)
(proc '())
(get-pairs2
(cdr alist)
(let* ((alist alist)
(num (car alist))
(newproc
(if (zero? (remainder num 2))
(lambda (l) (proc (cons num l)))
(lambda (l) (proc l)))))
newproc))))
proc 是 not“在最后评估”，过程 是变量 proc的值在最后被调用，但是变量proc的值在每次调用时都被找到。并且在每次调用时该值都是不同的，即 new lambda 函数对象在每次单独调用 get-pairs 时重新创建。每次调用 get-pairs 时变量 proc 的值都不同。
因此，对于示例调用 (get-pairs2 '(1 2 3 4) display)，最终 proc 的调用与
((lambda (l4) ; |
((lambda (l3) ; | |
((lambda (l2) ; | | |
((lambda (l1) ; | | | |
(display ; 1 2 3 4
l1)) ; | | | |
(cons 2 l2))) ; | | |
l3)) ; | |
(cons 4 l4))) ; |
'())
;; i.e.
;; l1 = cons 2 l2
;; l2 = l3
;; l3 = cons 4 l4
;; l4 = '()
也可以用伪代码写成
(((((display ∘ identity) ∘ {cons 2}) ∘ identity) ∘ {cons 4}) '())
; └───────1──────────┘
; └───────────────2───────────────┘
; └─────────────────────────3──────────────────┘
;└───────────────────────────────────4─────────────────────┘
;; 1: created on 1st invocation of `get-pairs2`
;; 2: created on 2nd invocation of `get-pairs2`
;; 3: created on 3rd invocation of `get-pairs2`
;; 4: created on the final 4th invocation of `get-pairs2`,
;; and then called with `'()` as the argument
其中 {cons n} 表示部分应用 cons，即 (lambda (l) (cons n l))，而 identity 是 (lambda (l) l)。
哦，还有∘代表函数组合，(f ∘ g) = (lambda (x) (f (g x))).
另请参阅我的其他一些可能相关的答案，here and here。
通过调用 (get-pairs2 '(1 2 3 4)) step-by-step，使用基于 let 的 re-writes 模拟函数调用，我们得到（稍微简化）
(get-pairs2 '(1 2 3 4) display)
=
(let ((alist '(1 2 3 4)) ; '(1 2 3 4)
(proc display))
(let* ((num (car alist)) ; 1
(newproc (lambda (l) (proc l))))
(let ((alist (cdr alist)) ; '(2 3 4)
(proc newproc))
(let* ((num (car alist)) ; 2
(newproc (lambda (l) (proc (cons num l)))))
(let ((alist (cdr alist)) ; '(3 4)
(proc newproc))
(let* ((num (car alist)) ; 3
(newproc (lambda (l) (proc l))))
(let ((alist (cdr alist)) ; '(4)
(proc newproc))
(let* ((num (car alist)) ; 4
(newproc (lambda (l) (proc (cons num l)))))
(let ((alist (cdr alist)) ; '()
(proc newproc))
(proc '()))))))))))
在 DrRacket 的代码编辑器中加载它 window 并将鼠标悬停在各种标识符上是一个有趣的游戏，可让您查看每个标识符所指的内容。 运行 带有 Ctrl-R 的代码也产生与原始函数调用相同的结果。
另一个“有趣”的练习是检查上面嵌套的 let 表达式并通过向其添加唯一索引手动重命名每个标识符（将 proc 更改为 proc1，proc2 等等）所以每个名字都变得独一无二。
好的，我会为你做的，尤其是 DrRacket 有一个很好的“重命名标识符”功能，这使得它变得更容易和更少 error-prone。但也请尝试自己做。
(let ((alist '(1 2 3 4)) ; '(1 2 3 4)
(proc display))
(let* ((num (car alist)) ; 1
(newproc (lambda (l) (proc l))))
(let ((alist2 (cdr alist)) ; '(2 3 4)
(proc2 newproc))
(let* ((num2 (car alist2)) ; 2
(newproc2 (lambda (l) (proc2 (cons num2 l)))))
(let ((alist3 (cdr alist2)) ; '(3 4)
(proc3 newproc2))
(let* ((num3 (car alist3)) ; 3
(newproc3 (lambda (l) (proc3 l))))
(let ((alist4 (cdr alist3)) ; '(4)
(proc4 newproc3))
(let* ((num4 (car alist4)) ; 4
(newproc4 (lambda (l) (proc4 (cons num4 l)))))
(let ((alist5 (cdr alist4)) ; '()
(proc5 newproc4))
(proc5 '()))))))))))
所以你看，这不一样proc。其中有五个，每个都可能不同，每个都位于不同的嵌套环境框架中。
您可能会问，为什么要 嵌套 环境？毕竟 get-pairs2 是 tail-recursive，所以它不能那样做，可以 re-use 它的调用框架用于下一次调用。
确实如此，但它仍然是与代码运行效率相关的实现细节，不会改变其含义（语义）。 在语义上 更容易看出代码的含义，嵌套 let re-writes.
尽管如此，这是一个有效的观点，也是您困惑的潜在根源。我也曾被这一点弄糊涂过。
这就是为什么我在 post 的开头写了“（副本） 环境框架”。即使 tail-recursive 调用可以——甚至可能必须，在 Scheme 的 TCO 保证下——re-use 它自己的下一次调用调用框架，新创建的闭包必须保持 它的自己的副本，以免引入语义不同标识符的错误合并。
确实，环境扁平化和帧重用可以通过以下时间计算来描述：
;; re-use the tail-recursive call frame {alist proc}
(let ((alist '(1 2 3 4))
(proc display)
(num #f))
(set! num (car alist)) ; 1
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc l))))
(set! alist (cdr alist)) ; (2 3 4)
(set! num (car alist)) ; 2
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc (cons num l)))))
(set! alist (cdr alist)) ; (3 4)
(set! num (car alist)) ; 3
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc l))))
(set! alist (cdr alist)) ; (4)
(set! num (car alist)) ; 4
(set! proc (let ((num num) (proc proc)) ; closure!
(lambda (l) (proc (cons num l)))))
(set! alist (cdr alist)) ; ()
(proc '()))
或者作为实际编译的定义，
(let ((alist '(1 2 3 4))
(proc display)
(num #f))
(let loop ()
(set! num (car alist))
(set! proc (let ((num num) (proc proc))
(if (zero? (remainder num 2))
(lambda (l) (proc (cons num l)))
(lambda (l) (proc l)))))
(set! alist (cdr alist))
(if (null? alist)
(proc '())
(loop))))
那么现在有多少 proc？ :)
（仍然是五个，否则它不会工作...即有一个 binding 但五个 values 是在循环的 运行 期间创建的，每个都将前一个包含在其中（或者，实际上，持有对它的引用）；当最后一个 proc 值——它是一个函数——最后 运行s，它调用它“内部”的那个，那个调用“内部”的那个 it，依此类推回到第一个 proc，我们已经开始的display。）