Implementing forward refs in monadic assembler and interprete r
Erkok, Levent
levent.erkok@intel.com
Thu, 28 Nov 2002 16:31:41 -0800
This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.
------_=_NextPart_000_01C2973E.AFC62480
Content-Type: text/plain
Hi,
As Ross pointed out, forward labels can easily be implemented using
recursive monadic bindings. There're a number of alternatives as to which
underlying monad you want to use. Continuations are problematic, but this
problem can be solved by using a simple state monad: please see the attached
file for one possible implementation. The variables test1-test4 (see the end
of the file) are bound to the compiled and interpreted versions of your
examples compute112 and compute12.
Note: I had to add a "return ()" to the end of your compute12 example, since
mdo-notation requires the last generator to be an expression, just like an
ordinary do-expression. You need a fairly recent version of Hugs to run this
example, November 2002 release would do (try with -98). For ghc, you need
the CVS version, or wait till the next release. As far as I know, no other
implementation supports mdo, nor there are any plans for it.
-Levent.
> -----Original Message-----
> From: Mike Gunter [mailto:m@ryangunter.com]
> Sent: Friday, November 15, 2002 1:38 AM
> To: haskell@haskell.org
> Subject: 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
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
------_=_NextPart_000_01C2973E.AFC62480
Content-Type: application/octet-stream;
name="lang.hs"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="lang.hs"
import Control.Monad.Fix
type Register =3D Int
type RegFile =3D [Register]
type Label =3D String
data Instruction =3D ZERO Register=20
| ADD Register Int
| MOV Register Register
| LABEL Label
| JIP Register Label
deriving Show
type Program =3D [Instruction]
class MonadFix m =3D> Processor m where
zero :: Register -> m ()
mov :: Register -> Register -> m ()
addi :: Register -> Int -> m ()
label :: m Label
brPositive :: Register -> Label -> m ()
-----------------------------------------------------------------------
data Interpreter a =3D Interp ((Int, Program) -> (a, (Int, Program)))
instance Monad Interpreter where
return x =3D Interp (\s -> (x, s))
Interp f >>=3D g =3D Interp (\s -> let (a, s') =3D f s
Interp h =3D g a
in h s')
instance MonadFix Interpreter where
mfix f =3D Interp (\s -> let Interp h =3D f a=20
(a, s') =3D h s
in (a, s'))
mkLabel :: Int -> Label
mkLabel i =3D 'L' : show i=20
newLabel :: Interpreter Label
newLabel =3D Interp (\(i, p) -> (mkLabel i, (i+1, p)))
-- note: we build programs backwards! (for efficiency)
emit :: Instruction -> Interpreter ()
emit ins =3D Interp (\(i, p) -> ((), (i, ins : p)))
instance Processor Interpreter where
zero r =3D emit (ZERO r)
addi r i =3D emit (ADD r i)
mov r1 r2 =3D emit (MOV r1 r2)
label =3D do l <- newLabel
emit (LABEL l)
return l
brPositive r l =3D emit (JIP r l)
------------------------------------------------------------------------=
updateRF :: RegFile -> Register -> (Int -> Int) -> RegFile
updateRF rf r f =3D p ++ f v : s
where (p, v : s) =3D splitAt r (rf ++ pad)
pad =3D take (r - length rf + 1) (repeat 0)
lookUpRegFile :: RegFile -> Register -> Int
lookUpRegFile rf r =3D (rf ++ repeat 0) !! r
execute :: Program -> RegFile
execute pgm =3D step 0 []
where endOfProg =3D length pgm
step ic rf | ic =3D=3D endOfProg =3D rf
step ic rf =3D let inst =3D pgm !! ic
in step (next inst rf ic) (doInst inst rf)
next (JIP r i) rf ic=20
| lookUpRegFile rf r > 0 =3D find i pgm 0
| True =3D ic + 1
next _ _ ic =3D ic + 1
doInst (ZERO r) rf =3D updateRF rf r (const 0)
doInst (ADD r i) rf =3D updateRF rf r (+i)
doInst (MOV r1 r2) rf =3D updateRF rf r1 (const (lookUpRegFile =
rf r2))
doInst _ rf =3D rf
find i [] _ =3D error ("jump to unknown label: " ++ =
show i)
find i (LABEL j:is) k=20
| i =3D=3D j =3D k
| True =3D find i is (k+1)
find i (_:is) k =3D find i is (k+1)
------------------------------------------------------------------------=
compile :: Interpreter () -> Program
compile (Interp f) =3D let (_, (_, pgm)) =3D f (0, []) in reverse pgm
run :: Interpreter () -> RegFile
run =3D execute . compile=20
------------------------------------------------------------------------=
-- examples:
r0, r1, r2, r3 :: Register
(r0 : r1 : r2 : r3 : _) =3D [0 .. ]
compute112 :: Processor m =3D> m ()
compute112 =3D do
zero r1
zero r2
addi r2 3
topLoop <- label
addi r1 4
addi r2 (-1)
brPositive r2 topLoop
addi r1 100
compute12 :: Processor m =3D> m ()
compute12 =3D mdo=20
zero r1=20
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) =20
brPositive r3 out -- if r1 > 10 don't add 100
addi r1 100
out <- label
return ()
------------------------------------------------------------------------=
test1 =3D compile compute112
test2 =3D run compute112 -- yields [0, 112, 0], i.e. r0 =3D 0, r1 =
=3D 112
test3 =3D compile compute12=20
test4 =3D run compute12 -- yields [0, 12, 0, 2], i.e. r0 =3D 0, r1 =
=3D 12
------_=_NextPart_000_01C2973E.AFC62480--