clojure - 我怎样才能避免使用连续传递风格的堆栈？

Question

对于我的毕业论文，我选择实现 ICFP 2004 contest 的任务.

任务——正如我自己翻译的那样——是编写一个编译器，将高级 ant 语言翻译成低级 ant 程序集。在我的例子中，这意味着使用用 Clojure(一种 Lisp 方言)编写的 DSL 作为高级 Ant 语言来生成 Ant 汇编。

更新:

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

实际上，ant-assembly 用于描述状态机(= Ant 的“大脑”)的转换。对于“函数调用”(=状态转换)，我只有 JUMP/GOTO。

虽然没有堆栈、堆或适当的 CALL 指令之类的东西，但我仍然希望能够调用 ant-assembly 中的函数(通过跳转到某些标签)。 在几个地方，我读到将我的 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 可以通过两种不同的延续来调用:

(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 变换在那里有很详细的介绍，尽管有很多内容供您先阅读。