How can I avoid using the stack with continuation-passing style?

Question

For my diploma thesis I chose to implement the task of the ICFP 2004 contest.

The task--as I translated it to myself--is to write a compiler which translates a high-level ant-language into a low-level ant-assembly. In my case this means using a DSL written in Clojure (a Lisp dialect) as the high-level ant-language to produce ant-assembly.

UPDATE:

The ant-assembly has several restrictions: there are no assembly-instructions for calling functions (that is, I can't write CALL function1, param1), nor returning from functions, nor pushing return addresses onto a stack. Also, there is no stack at all (for passing parameters), nor any heap, or any kind of memory. The only thing I have is a GOTO/JUMP instruction.

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

While not having anything like a stack, heap or a proper CALL instruction, I still would like to be able to call functions in the ant-assembly (by JUMPing to certain labels). At several places I read that transforming my Clojure DSL function calls into continuation-passing style (CPS) I can avoid using the stack[1], and I can translate my ant-assembly function calls into plain JUMPs (or GOTOs). Which is exactly what I need, because in the ant-assembly I have no stack at all, only a GOTO instruction.

My problem is that after an ant-assembly function has finished, I have no way to tell the interpreter (which interprets the ant-assembly instructions) where to continue. Maybe an example helps:

The 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-assembly I'd like to produce from the go-home function is:

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 instructions above:

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 fail to find out what to write to the last line in the assembly (JUMP ???). Because--as you can see in the example--go-home can be invoked with two different continuations:

(go-home
  (drop-food))

and

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

After go-home has finished I'd like to call either drop-food or call-help-from-others. In assembly: after I arrived at home (=the WE-ARE-AT-HOME label) I'd like to jump either to the label FUNCTION-DROP-FOOD or to the FUNCTION-CALL-HELP-FROM-OTHERS.

How could I do that without a stack, without PUSHing the address of the next instruction (=FUNCTION-DROP-FOOD / FUNCTION-CALL-HELP-FROM-OTHERS) to the stack? My problem is that I don't understand how continuation-passing style (=no stack, only a GOTO/JUMP) could help me solving this problem.

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

And huge thanks in advance for your help!

--
[1] "interpreting it requires no control stack or other unbounded temporary storage". Steele: Rabbit: a compiler for Scheme.

Answer 1

Your ant assembly language is not even Turing-complete. You said it has no memory, so how are you supposed to allocate the environments for your function calls? You can at most get it to accept regular languages and simulate finite automata: anything more complex requires memory. To be Turing-complete you'll need what amounts to a garbage-collected heap. To do everything you need to do to evaluate CPS terms you'll also need an indirect GOTO primitive. Function calls in CPS are basically (possibly indirect) GOTOs that provide parameter passing, and the parameters you pass require memory.

Answer 2

Yes, you've provided the precise motivation for continuation-passing style.

It looks like you've partially translated your code into continuation-passing-style, but not completely.

I would advise you to take a look at PLAI, but I can show you a bit of how your function would be transformed, assuming I can guess at clojure syntax, and mix in scheme's 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)))))

I'm a bit confused by the fact that you're searching for food whether or not you sense food here, and I find myself suspicious that either this is weird half-translated code, or just doesn't mean exactly what you think it means.

Hope this helps!

And really: go take a look at PLAI. The CPS transform is covered in good detail there, though there's a bunch of stuff for you to read first.

Answer 3

Clearly, your two basic options are to inline everything, with no "external" procedures (for extra credit look up the original meaning of "internal" and "external" here), or somehow "remember" where you need to go on "return" from a procedure "call" (where the return point does not necessarily need to fall in the physical locations immediately following the "calling" point). Basically, the return point identifier can be a code address, an index into a branch table, or even a character symbol -- it just needs to identify the return target relative to the called procedure.

The most obvious here would be to track, in your compiler, all of the return targets for a given call target, then, at the end of the called procedure, build a branch table (or branch ladder) to select from one of the several possible return targets. (In most cases there are only a handful of possible return targets, though for commonly used procedures there could be hundreds or thousands.) Then, at the call point, the caller needs to load a parameter with the index of its return point relative to the called procedure.

Obviously, if the callee in turn calls another procedure, the first return point identifier must be preserved somehow.

Continuation passing is, after all, just a more generalized form of a return address.

Answer 4

You might be interested in Andrew Appel's book Compiling with Continuations.