如何避免使用连续传递风格的堆栈？

Question

对于我的文凭论文，我选择实现 ICFP 2004 的任务竞赛。

我自己翻译的任务是编写一个编译器，将高级 ant 语言转换为低级 ant 汇编。就我而言，这意味着使用以 Clojure（一种 Lisp 方言）编写的 DSL 作为高级 ant 语言来生成 ant 汇编。

更新：

ant 汇编有几个限制：没有用于调用函数的汇编指令（也就是说，我不能编写 CALL function1, param1），也不能返回来自函数，也不将返回地址压入堆栈。此外，根本没有堆栈（用于传递参数），也没有任何堆或任何类型的内存。我唯一拥有的是 GOTO/JUMP 指令。

实际上，蚂蚁组装是为了描述状态机（=蚂蚁的“大脑”）的转换。对于“函数调用”（=状态转换），我所拥有的只是跳转/转到。

虽然没有堆栈、堆或适当的 CALL 指令之类的东西，但我仍然希望能够调用 ant 程序集中的函数（通过跳转到某些标签）。 我在几个地方读到，将 Clojure DSL 函数调用转换为连续传递样式 (CPS)，我可以避免使用堆栈 [1]，并且可以将我的 ant 汇编函数调用转换为普通的 JUMP（或 GOTO）。这正是我所需要的，因为在 ant 汇编中我根本没有堆栈，只有 GOTO 指令。

我的问题是，在 ant-Assembly 函数完成后，我无法告诉解释器（解释 ant-Assembly 指令）在哪里继续。也许一个例子有帮助：

高级 Clojure DSL：

(defn search-for-food [cont]
  (sense-food-here? ; a conditional w/ 2 branches
    (pickup-food ; true branch, food was found
      (go-home ; ***
        (drop-food
          (search-for-food cont))))
    (move ; false branch, continue searching
      (search-for-food cont))))

(defn run-away-from-enemy [cont]
  (sense-enemy-here? ; a conditional w/ 2 branches
    (go-home ; ***
      (call-help-from-others cont))
    (search-for-food cont)))

(defn go-home [cont]
  (turn-backwards
    ; don't bother that this "while" is not in CPS now
    (while (not (sense-home-here?))
      (move))) 
    (cont))

我想从 go-home 函数生成的 ant-assemble 是：

FUNCTION-GO-HOME:
  turn left nextline
  turn left nextline
  turn left nextline ; now we turned backwards
SENSE-HOME:
  sense here home WE-ARE-AT-HOME CONTINUE-MOVING
CONTINUE-MOVING:
  move SENSE-HOME
WE-ARE-AT-HOME:
  JUMP ???

FUNCTION-DROP-FOOD:
  ...

FUNCTION-CALL-HELP-FROM-OTHERS:
  ...

上面 ant-asm 指令的语法：

turn direction which-line-to-jump
sense direction what jump-if-true jump-if-false
move which-line-to-jump

我的问题是我无法找出要写入程序集中最后一行的内容（JUMP ???）。因为 - 正如您在示例中看到的 - go-home 可以通过两个不同的延续来调用：

(go-home
  (drop-food))

并且

(go-home
  (call-help-from-others))

在 go-home 完成后我想调用drop-food 或 call-help-from-others。在组装中：当我到家后（=WE-ARE-AT-HOME 标签），我想跳到标签 FUNCTION-DROP-FOOD 或到FUNCTION-CALL-HELP-FROM-OTHERS。

我怎样才能在没有堆栈的情况下做到这一点，而不将下一条指令的地址 (=FUNCTION-DROP-FOOD / FUNCTION-CALL-HELP-FROM-OTHERS) 推送到堆栈？我的问题是我不明白连续传递风格（=无堆栈，只有 GOTO/JUMP）如何帮助我解决这个问题。

（如果上面的事情难以理解，我可以尝试再次解释这一点。）

非常感谢您的帮助！

--
[1]“解释它不需要控制堆栈或其他无限的临时存储”。 Steele：Rabbit：Scheme 的编译器。

Answer 1

是的，您已经为连续传递风格提供了精确的动机。

看起来您已将代码部分翻译为连续传递风格，但并未完全翻译。

我建议你看一下 PLAI，但我可以向你展示一些你的函数是如何的转换，假设我可以猜测 clojure 语法，并混合在方案的 lambda 中。

(defn search-for-food [cont]
  (sense-food-here? ; a conditional w/ 2 branches
   (search-for-food
    (lambda (r)
      (drop-food r 
                 (lambda (s)
                   (go-home s cont)))))
   (search-for-food
    (lambda (r)
      (move r cont)))))

无论你是否在这里感觉到食物，你都在寻找食物，这一事实让我有点困惑，我发现自己怀疑这要么是奇怪的半翻译代码，要么只是并不完全符合你的想法方法。

希望这有帮助！

真的：去看看 PLAI。那里详细介绍了 CPS 变换，不过还有很多内容需要您先阅读。

Answer 2

你的蚂蚁汇编语言甚至不是图灵完备的。你说它没有内存，那么你应该如何为你的函数调用分配环境呢？你最多可以让它接受常规语言并模拟有限自动机：任何更复杂的东西都需要内存。为了实现图灵完备，您需要相当于垃圾收集堆的东西。为了完成评估 CPS 术语所需的一切，您还需要一个间接 GOTO 原语。 CPS 中的函数调用基本上（可能是间接的）提供参数传递的 GOTO，而你传递的参数需要内存。

Answer 3

显然，您的两个基本选择是内联所有内容，没有“外部”过程（要获得额外的学分，请在此处查找“内部”和“外部”的原始含义），或者以某种方式“记住”您需要“返回”的位置”来自过程“调用”（其中返回点不一定需要落在紧随“调用”点之后的物理位置）。基本上，返回点标识符可以是代码地址、分支表的索引，甚至是字符符号——它只需要标识相对于被调用过程的返回目标。

这里最明显的是在编译器中跟踪给定调用目标的所有返回目标，然后在被调用过程的末尾构建一个分支表（或分支梯形图）以从多个返回目标之一中进行选择可能的回报目标。 （在大多数情况下，只有少数可能的返回目标，但对于常用的过程，可能有数百或数千个。）然后，在调用点，调用者需要加载一个参数及其返回点的索引 相对于被调用的过程。

显然，如果被调用者依次调用另一个过程，则必须以某种方式保留第一个返回点标识符。

毕竟，连续传递只是返回地址的更通用形式。

Answer 4

您可能对 Andrew Appel 的书Compiling with Continuations感兴趣。