title: How can I avoid using the stack with continuation-passing style?
body: <p>For my diploma thesis I chose to implement the task of the <a href="https://alliance.seas.upenn.edu/~plclub/cgi-bin/contest/ants.html" rel="noreferrer">ICFP 2004 contest</a>. </p>
  
  <p>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.</p>
  
  <p><strong>UPDATE:</strong></p>
  
  <p>The ant-assembly has several restrictions: there are no assembly-instructions for calling functions (that is, I can't write <code>CALL function1, param1</code>), 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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <p>The high-level Clojure DSL:</p>
  
  <pre><code>(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))
  </code></pre>
  
  <p>The ant-assembly I'd like to produce from the <code>go-home</code> function is:</p>
  
  <pre><code>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:
    ...
  </code></pre>
  
  <p>The syntax for the ant-asm instructions above:</p>
  
  <pre><code>turn direction which-line-to-jump
  sense direction what jump-if-true jump-if-false
  move which-line-to-jump
  </code></pre>
  
  <p>My problem is that I fail to find out what to write to the last line in the assembly (<code>JUMP ???</code>). Because--as you can see in the example--<code>go-home</code> can be invoked with two different continuations:</p>
  
  <pre><code>(go-home
    (drop-food))
  </code></pre>
  
  <p>and</p>
  
  <pre><code>(go-home
    (call-help-from-others))
  </code></pre>
  
  <p>After <code>go-home</code> has finished I'd like to call either <code>drop-food</code> or <code>call-help-from-others</code>. In assembly: after I arrived at home (=the <code>WE-ARE-AT-HOME</code> label) I'd like to jump either to the label <code>FUNCTION-DROP-FOOD</code> or to the <code>FUNCTION-CALL-HELP-FROM-OTHERS</code>.</p>
  
  <p>How could I do that without a stack, without PUSHing the address of the next instruction (=<code>FUNCTION-DROP-FOOD</code> / <code>FUNCTION-CALL-HELP-FROM-OTHERS</code>) 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.</p>
  
  <p>(I can try to explain this again if the things above are incomprehensible.)</p>
  
  <p>And huge thanks in advance for your help!  </p>
  
  <p>--<br>
  [1] "interpreting it requires no control stack or other unbounded temporary storage". Steele: Rabbit: a compiler for Scheme.</p>