调用延续与函数调用

Question

让我们考虑一个阶乘函数的简单示例，它以类似 CPS 的伪类风格编写（省略了中间结果的枚举和排序，因为会非常嘈杂）：

(def (fact n k) (if (eq? n 0) (k 1) (fact (- n 1) (\result (k (* n result))))))

调用延续 (k 1)（即 "returning" 一个值）在技术上是否与 "normal" 函数调用不同，如在 else 分支中？我想到的一件事是，在这种情况下，延续是唯一在其论证中没有另一个延续的东西 :)

另外，你能说这个计算类似于动态构造树的 DFS 树遍历，当前计算是当前探索的节点，"other unexplored branches" 是调用 stack/continuation 吗？

Answer 1

好吧，你已经回答了你的第一个问题：技术上的区别是没有更多的传递延续：这是到此为止建立的张力得到释放的点，即实际执行累积计算的地方[通过一系列 beta 还原]。当然从语言的语义来看，这是一个普通的函数应用。

至于第二个问题，我可能理解错了，但我想说的是每次计算都是向叶方向的树行走，但树不是动态构造的，而是静态的（通常是无限的）程序[唯一地]定义的对象。但是，调用堆栈 [即使它是微不足道的，因为尾调用] 是你已经走过的（从根节点到当前节点），而延续是你未来的路径，从将延续应用到某些东西（即当您应用此事实函数时，下一个节点再次成为事实，除非 n 为 0）。

  (fact _ id)
   /      \
(= _ 0)?   otherwise
  |          \
 (id 1)    (fact _ (λ (x) (id (* 2 x))))
  |          /          \
  1       (= _ 0)?      otherwise
            |              \
      (id (* 2 1)))    (fact _ (λ (x) (id (* 2 (* 1 x)))))
            |                    /        \
          (id 2)               (= _ 0)?  otherwise
            |                    |           \ 
            2           (id (* 2 (* 1 1)))    ...
                                 |
                           (id (* 2 1))
                                 |
                              (id 2)
                                 |
                                 2

如果您喜欢从这些方向思考，您可能想阅读有关流程树的内容，例如 Hatcliff 的 "An Introduction to Online and Offline Partial Evaluation" http://repository.readscheme.org/ftp/papers/pe98-school/hatcliff-DIKU-PE-summerschool.pdf -- 顺便说一句，PE 的主题非常有趣），也许您可能喜欢（至少前 20 页左右）Scott 的 "Lattice of flow diagrams"（https://www.cs.ox.ac.uk/files/3223/PRG03.pdf——恕我直言，这篇论文实际上将 "more natural" 翻译成应用函数式语言）。

希望能给你一些见解。

调用延续与函数调用

Invoking a continuation vs a function call

continuations

functional-programming