How can I avoid using a stack with style continuation?

Question

For my thesis, I decided to complete the task of the ICFP 2004 contest .

The task - as I translated it for myself - is to write a compiler that translates a high-level ant language into a low-level ant assembly. In my case, this means using the DSL recorded in the Clojure (a Lisp) dialog box as a high-level ant language to create an ant association.

UPDATE:

The ant assembler has several limitations: there are no build commands for function calls (that is, I cannot write CALL function1, param1 ), and also do not return from functions and do not push return addresses onto the stack. In addition, there is no stack at all (for passing parameters), no heap, no memory. The only thing I have is the GOTO / JUMP instruction.

Actually, the ant assembly is intended to describe the transitions of a finite state machine (= brain of ants). For "function calls" (= state transitions) I have JUMP / GOTO.

Having nothing like a stack, heap, or the correct CALL instruction, I still want to be able to call functions in ant -assembly (using JUMPing for specific labels). In several places, I read that converting Clojure DSL function function calls to Continued Transfer (CPS) style, I can avoid using the stack [1], and I can translate my ant function calls to plain JUMP (or GOTO). This is exactly what I need, because in the ant assembler I don’t have a stack at all, only a GOTO instruction.

My problem is that after completing the ant build function, I cannot tell the interpreter (which interprets the instructions of the ant assembler) where to continue. Maybe an example helps:

High Level 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)) 

The ant element that I would like to create from the go-home function:

 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: ... 

The syntax for the ant -asm statements above is:

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

My problem is that I cannot find out what to write to the last line of the assembly ( JUMP ??? ). Because - as you can see in the example - go-home can be called with two different extensions:

 (go-home (drop-food)) 

and

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

After go-home I would like to call either drop-food or call-help-from-others . In the assembly: after I got home (= label WE-ARE-AT-HOME ), I would like to go either to the label FUNCTION-DROP-FOOD , or to FUNCTION-CALL-HELP-FROM-OTHERS .

How could I do this without a stack without pushing the address of the next command (= FUNCTION-DROP-FOOD / FUNCTION-CALL-HELP-FROM-OTHERS ) FUNCTION-CALL-HELP-FROM-OTHERS stack? My problem is that I do not understand how the continuation-transfer style (= no stack, only GOTO / JUMP) can help me solve this problem.

(I can try to explain this again if the above things are not clear.)

And many thanks for your help!

- Page [1] "To interpret it, no management stack or other unlimited temporary storage is required." Steele: Rabbit: compiler for the circuit.

Answer 1

Your ant assembler language is not even complete. You said that it has no memory, since you have to allocate environments for calls to your functions? You can at best make it accept ordinary languages ​​and simulate state machines: for something more complex, memory is required. To be ready for Turing, you need what is a bunch of garbage. To do everything you need to do to evaluate the conditions of the CPS, you will also need the indirect GOTO primitive. Function calls in CPS are mainly (possibly indirect) GOTOs that provide parameter passing, and the required parameters require memory.

Answer 2

Yes, you indicated the exact motivation to continue the style.

It looks like you partially translated your code into continuation-walk-through-style, but not completely.

I would advise you to take a look at PLAI , but I can show you a little about how your function will be transformed, assuming that I can guess at clojure syntax and mix in the lambda scheme.

 (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))))) 

I am a little confused by the fact that you are looking for food, whether you feel food here or not, and I am suspicious of the fact that this is a strange semi-translated code or just does not mean exactly what you think it means.

Hope this helps!

And really: take a look at the PLAI . The CPS transformation is well lit there, although there are tons of things for you to read first.

Answer 3

Obviously, your two main options are to embed everything without any "external" procedures (for additional credit, see the initial value "internal" and "external" here) or somehow "remember" where you need to go to " return “from the call” procedure (where the return point does not have to fall into physical locations immediately after the “calling” point). In principle, the return point identifier can be a code address, an index in a branch table, or even a symbolic character — it just needs to identify the purpose of the return with respect to the called procedure.

The most obvious here is to track in your compiler all return goals for a given call target, and then at the end of the called procedure create a branch table (or branch branch) to select from one of several possible return goals. (In most cases, there are only a few possible return targets, although there can be hundreds or thousands for commonly used procedures.) Then, the caller needs to load a parameter with the index of his return point relative to the called procedure at the call point.

Obviously, if the called call, in turn, calls another procedure, the first identifier of the return point must be somehow saved.

Passing on a continuation is, after all, just a more generalized form of the return address.

Answer 4

You might be interested in Andrew Appel Compiling with Continuations.