Implementing forward refs in monadic assembler and interpreter

15 Nov 2002

      I need to implement an assembler and interpreter for a simple
instruction set.  For example, this code

  \begin{code}
  compute112	= do 
    { 		zero r1 
    ;		zero r2
    ; 		addi r2 3	-- loop three times
    ;topLoop <-	label
    ;		addi r1 4
    ;		addi r2 (-1)	-- decrement loop counter
    ;		brPositive r2 topLoop
    ;		add r1 100
    }
  \end{code}

would result in register r1 having a value 112.  Without forward
branches, the implementation is reasonably straightforward.  The
assembler can use a Monad with state and writer capabilities.  The
interpreter can use a continuation monad to implement branches and a
state monad for the machine state.

However, forward branches make things harder.  I'd like to be able to
write something along the lines of:

  \begin{code}
  compute12	= mdo 
    { 		zero r1 
    ;		zero r2
    ; 		addi r2 3	-- loop three times
    ;topLoop <-	label
    ;		addi r1 4
    ;		addi r2 (-1)	-- decrement loop counter
    ;		brPositive r2 topLoop
    ;		mov r3 r1
    ;		addi r3 (-10)	
-- !!! Forward branch:
    ;		brPositive r3 out -- if r1 > 10 don't add 100
    ;		add r1 100
    ;out <-	label
    }
  \end{code}

but it's not clear to me how to implement it.  I'd be willing to
accept a somewhat less clean version (for instance, with more
cumbersome forward references.)

Any help would be greatly appreciated.

        thanks,
        mike

Implementing forward refs in monadic assembler and interpreter

Mike Gunter