Frederik Eaton wrote:
I want the type system to be able to do "automatic lifting" of monads,
i.e., since [] is a monad, I should be able to write the following:
[1,2]+[3,4]
and have it interpreted as "do {a<-[1,2]; b<-[3,4]; return (a+b)}".
print ("a: " ++ readLn ++ "\nb: " ++ readLn)
two lines are read and then printed. Does anybody for a moment
question what order the lines should be read in?
Frederik,
To do "automatic lifting" you need to do a (higher-order) effect
analysis, then make sure the compiler doesn't rearrange applications
which have conflicting effects.
One way of preventing the compiler from rearranging effects is to thread
though a dummy variable - like a "World token", ala the IO monad - which
makes the order of operations explicit as an extra data dependency, then
compile the resulting code.
Another way is to use the effect information to lift the applications
into a hierarchy of monads which represent how effectful the application
is, then compile the monadic code directly. There's a paper by Andrew
Tolmach called "Optimizing ML using a hierarchy of monadic types", which
does exactly this.
Tolmach's approach worked ok, but there were some problems with higher
order functions.. ie with map :: (a -E> b) -> [a] -E> [b] where E is
some effect, you have to assume a worst case effect for the first
argument - so any expression using map can't be moved around by the
compiler - eg for the full laziniess transform.
Another way would be just to annotate every application with the effects
it has, then have the compiler check these before it tries to rearrange
anything - and have an extra rule that you can't suspend an application
which has visible effects.
I am working on a compiler for my PhD project which takes this third
option. I've got the effect analysis working, but I had to resort to a
graph based type inference method - which is something that wouldn't be
easilly added to something like GHC.
Onward!
Ben.
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
