对于我的毕业论文，我选择执行ICFP 2004 contest的任务。
正如我自己翻译的那样，任务是编写一个编译器，该编译器将高级 Ant 语言转换为低级 Ant 程序集。在我的情况下，这意味着使用用Clojure(Lisp方言)编写的DSL作为高级 Ant 语言来产生 Ant 组合。
更新:
Ant 汇编有几个限制:没有用于调用函数的汇编指令(也就是说，我不能编写CALL function1, param1)，也没有从函数返回的内容，也没有将返回地址压入堆栈的指令。而且，根本没有堆栈(用于传递参数)，也没有任何堆或任何类型的内存。我唯一拥有的是GOTO/JUMP指令。
实际上， Ant 组装是用来描述状态机的转换的(= Ant 的“大脑”)。对于“函数调用”(状态转换)，我所拥有的只是JUMP/GOTO。
尽管没有堆栈，堆或适当的CALL指令，但我仍然希望能够在ant-assembly中调用函数(通过跳转到某些标签)。
在许多地方，我读到了将Clojure DSL函数调用转换为连续传递样式(CPS)的过程，可以避免使用stack [1]，并且可以将我的ant-assembly函数调用转换为简单的JUMP(或GOTO)。这正是我所需要的，因为在ant-assembly中我根本没有堆栈，只有GOTO指令。
我的问题是， Ant 装配功能完成后，我无法告诉解释器(解释 Ant 装配指令)从何处继续。也许一个例子会有所帮助:
高级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 程序集是: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的编译器。
最佳答案
您的 Ant 汇编语言甚至不是图灵完整的。您说它没有内存，那么应该如何为函数调用分配环境呢？您最多可以接受常规语言并模拟有限自动机:更复杂的事情都需要内存。要完成图灵处理，您需要达到等于垃圾收集堆的水平。要完成评估CPS术语所需执行的所有操作，您还需要一个间接的GOTO原语。 CPS中的函数调用基本上是(可能是间接的)提供参数传递的GOTO，传递的参数需要内存。