§ Self modifying code for function calls: Look ma, I don't need a stack!

If one does not have recursive calls, one can eliminate the need to push return addresses on a call stack by writing self-modifying code --- I leant of this from TAOCP, volume 1. Knuth shows this off once he introduces MIXAL, his fantasy aseembly language in which TAOCP programs are written. I'll explain the usual way one performs call-return, then explain the nifty self-modifying-code way. I think this is the cleanest, most accessible example of self-modifying-code that I know.

§ The traditional solution for call/ret

We wish to have function f call function g. For g to be able to return control to f, f pushes a return address into the call stack, that g pops and jmps to fs body. In code: 
START_F:
      ...
L0    push addr(L0); location of instr to be run after call.
      jmp START_G
L1:   

=========

g's body
START_G:
      ...
      retloc = pop ; pop location to jump to
RETG: jmp retloc
Rather than push ing and pop ing, we can rewrite the code of g, to change retloc before a call to g. In made-up-pseudocode, here's what that would look like:

§ The jump based solution 

* f's body
START_F:
      ...
L0    store loc(RETG) assemble(jmp addr(L1))
      jmp START_G
L1:   

=========

* g's body
START_G:
      ...
RETG: <###-to-be-filled-dummy-###>
instead of having a call stack, before f calls g, f modify g's code at location RETG into a jmp instruction by store ing the instruction jmp addr(L1). This effectively creates a 'custom' g that knows how to return control flow into f. 
* g's body (after execution of L0)
START_G:
      ...
RETG: jump addr(L1)
This way, we have obviated the need for a push/pop sequence, by directly modifying g's code. This is really neat --- we replace the overhead of a push/pop with a single store.

§ Why recursion breaks.

We don't actually need a call stack, as long as we don't want to write recursive functions. We can't have recursion, or more generally "re-entrance": consider a call chain of the form:
  • A -> B -> C -> B.
  • during A -> B, A will scribble a into B.
  • during B -> C, B will scribble a into C.
  • during C -> B, C will scribble into B, destroying the previous .
  • This creates a cycle, where C will attempt to return to Band vice versa.