Saturday, April 30, 2016

Can Wombat do Lazy?

I went to a nice talk by Paul Bone: Haskell Sucks. He pointed out various issues with lazy evaluation. He wants a language to be strict by default, with laziness as an option. So I wondered if Wombat could do laziness just as it currently is.

If we have a type X then we want a type Lazy X. Clearly Lazy X is implementedBy a Unit=>X which gets evaluated if and when we need the value. The archetypal lazy construct [in some unspecified language] is:
lazy allNats = cons(1,  map (1+) allNats)
but we can't do that in Wombat. Instead we need something like
`allNats =  lazy { cons(1, map (1+) allNats) }
And here we see a problem. Any operation which contains a Lazy operand has to not do its normal thing, but instead produce a new Lazy object. Well at least every operation in Wombat is a function call (more or less), and if we assume that then we just need a rule like this:
forall _f:_X=>_Y (  `_f (_lx:Lazy _X) = lazy {_f (unlazy _lx)}  )
For every value of type _X=>_Y it creates a new value of type (Lazy _X)=>(Lazy _Y).

Unfortunately that isn't going to do it. Because when we want to unpack a lazy thing to get some part of it out, we want the rest to be left lazy. You need to keep calling unlazy on the bits you are interested in till you get what you want. There seem to be problematic issues with that. Why do we expect that there will be only one way to unpack a lazy value into some combination of lazy values? In our example it seeems obvious that we want to unpack our Lazy (List Int) into a pair of a Lazy Int and a Lazy (List Int), but do we know that is the only way to unpack it? I conclude that a laziness option has to be built in to the language, and I'm inclined to wonder whether it is actually possible to do that in a way that has perfectly clear semantics.