[Haskell] Mixing monadic and non-monadic functions

[Ben Lippmeier]

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.