Sat Mar 13 22:35:39 CET 2010
Manipulating binding structure in Haskell
Problem: convert an imperative register transfer language to SSA form
to construct a functional dependency network.
Try to do this without low-level interpretation (tagless).
Register allocation is SSA -> assignments (convert nodes to registers)
We're interested in the reverse operation: assignments -> SSA
So, this needs an environment that has a mapping of symbolic register
names to their current instances. Whenever an assignment happens, the
environment is updated with a new value and the old value becomes
We're only interested in building functional representations.
I.e. using a reader monad with (String -> a) mappings, where the a
parameter is the representation of the emulator (i.e. true logic,
multi-value logic, AST, ...) seems a straightforward excercise:
addlw (k0,k1,...,k7) =
("W0","W1",...,"W7") -> (("W0","W1",...,"W7"),"C","DC","Z")
where the strings are taked from the environment, added to ki, and
placed back into the environment replacing the previous values.
Can it also be encoded in the type system such that there is no
dynamic String mapping? This seems a bit less straightforward.
Yes it does seem possible to make get/set functions for each of the
machine register bits, i.e. define the machine state as a state monad
with accessor functions indexed by bit numbers.
- Instead of manipulating bindings, just manipulate state.
- The state of the machine is a monad.
- The monad is parameterized by the representation type of the
bits to allow analysis based on abstract evaluation.
- The monad can probably be decomposed into a layering of several
monads (try out monad transformers).
- Programs (functional representation of imperative code) can be
constructed in do notation.