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

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.