Implementing forward refs in monadic assembler and interpreter
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
Mike Gunter wrote:
However, forward branches make things harder. I'd like to be able to write something along the lines of:
[snip]
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.
What is the structure of the data which is produced by the assembler? If it roughly corresponds to conventional machine code (e.g. a list of opcodes with parameters), then you can use similar techniques to those used by a "real" assembler. If you are assembling into a list, the simplest approach is to perform the assembly phase twice. The first phase generates the list of label/address pairs. The second phase, which has the complete list of label addresses available, performs the complete assembly process. Both phases could use identical code; you just need to ensure that the first phase can assemble a branch instruction for which the label is unknown. Alternatively, you could perform one pass plus a post-processing phase which "fixes" any forward references. This would require either that you can store a label in an assembled branch instructions in place of an actual address, or that you generate a list incomplete branch instructions so that you can go back and fix them. OTOH, if you're actually interpreting the "assembly language" directly, then a forward branch would have to store the label in a "variable" to indicates that instructions are just to be skipped until that label is reached. -- Glynn Clements <glynn.clements@virgin.net>
Glynn Clements comments the request for the implementation of forward references in an assembly code simulated in Haskell.
If you are assembling into a list, the simplest approach is to perform the assembly phase twice. The first phase generates the list of label/address pairs. The second phase, which has the complete list of label addresses available, performs the complete assembly process.
Both phases could use identical code; you just need to ensure that the first phase can assemble a branch instruction for which the label is unknown.
Alternatively, you could perform one pass plus a post-processing phase which "fixes" any forward references. This would require either that you can store a label in an assembled branch instructions in place of an actual address, or that you generate a list incomplete branch instructions so that you can go back and fix them.
OTOH, if you're actually interpreting the "assembly language" directly, then a forward branch would have to store the label in a "variable" to indicates that instructions are just to be skipped until that label is reached.
This is squeezing the power of a modern lazy language into a soap box... What are the labels good for, hm? Just to identify your chunks of code which are targets of some jumps? Well, use these chunks themselves, their references as your targets; the branching instruction picks up this chunk as the next segment of code to execute. Connect your chunks lazily. Then no forward reference can hurt you. If I may, a shameless personal plug. Look at my paper presented at the last FDPE, a construction of a CPS "assembly-style" interpreter, with lazy code deployment tricks. Jerzy Karczmarczuk
On Fri, Nov 15, 2002 at 01:38:03AM -0800, Mike Gunter wrote:
\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 would suggest a forward declaration like in Pascal. At least it would fit the monadic style: out <- forwardLabel brPositive r3 out add r1 100 fLabelSet out I admit it doesn't look that nice, but it's easy to implement. Axel.
On Fri, Nov 15, 2002 at 01:38:03AM -0800, Mike Gunter wrote:
I need to implement an assembler and interpreter for a simple instruction set.
[...] 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.
This is a job for recursive monadic bindings, an extension currently in Hugs and GHC: http://www.cse.ogi.edu/PacSoft/projects/rmb This can be used if your monads belong to the MonadFix class, and the monads you need for the assembler do. The continuation monad doesn't, however. See Levent Erkok's papers and thesis on that page for more.
participants (5)
-
Axel Simon -
Glynn Clements -
Jerzy Karczmarczuk -
Mike Gunter -
Ross Paterson