如何避免使用延续传递样式的堆栈？

Question

对于我的毕业论文,我选择执行ICFP 2004竞赛的任务.

任务 - 我将其翻译成自己 - 是编写一个编译器,将高级蚂蚁语言翻译成低级蚂蚁组件.在我的例子中,这意味着使用用Clojure(一种Lisp方言)编写的DSL作为产生蚂蚁组装的高级蚂蚁语言.

更新:

ant-assembly有几个限制:没有用于调用函数的汇编指令(也就是说,我无法写入CALL function1, param1),也没有从函数返回,也没有将返回地址压入堆栈.此外,根本没有堆栈(用于传递参数),也没有任何堆或任何类型的内存.我唯一拥有的是GOTO/JUMP指令.

实际上,ant-assembly用于描述状态机的转换(=蚂蚁的"大脑").对于"函数调用"(=状态转换),我所有的都是JUMP/GOTO.

虽然没有像堆栈,堆或适当的CALL指令那样的东西,但我仍然希望能够在ant-assembly中调用函数(通过JUMPing到某些标签).在几个地方,我读到将Clojure DSL函数调用转换为延续传递样式(CPS)我可以避免使用堆栈[1],并且我可以将我的ant-assembly函数调用转换为普通JUMP(或GOTO).这正是我需要的,因为在ant-assembly中我根本没有堆栈,只有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-assembly 是:

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中所看到的 - 可以使用两个不同的continuation调用:

(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语法,并混合使用scheme的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，而你传递的参数需要内存。