[Haskell-cafe] Everything but the lazyness - idea for force/delay lists

[Brian Hulley]

Hi -

I've been thinking about how to get an extremely fast language with all the 
benefits of Haskell ie completely pure with no side effects, but with 
monads, higher order functions, type classes etc, but without the lazyness.

I know this is controversial, but having started to write a serious program 
in Haskell, I find that almost all of it doesn't need any lazyness at all, 
yet I have to constantly mess up my code by using Tuple2 a b instead of 
(a,b), ! in all my data types, and millions of brackets to use $! (which has 
the wrong associativity for passing multiple arguments strictly) etc and I 
can't do anything about the slowness and possible space leaks introduced by 
library functions which are lazy, not to mention the fact that afaiu the 
lifted type system necessary for any language which supports lazyness, and 
general undecidability results means that it will probably be impossible to 
ever compile lazy code to be as fast as OCaml etc.

(This is not to say Haskell is too slow - I find the app I'm writing at the 
moment runs fast enough (given all my strictness annotations) it's just that 
lazyness is making my life more difficult rather than easier and is probably 
also costing something in terms of speed.)

The one place where I'm using lazyness is where I need to glue the output of 
one computation to another by using a lazy list. In effect I'm using a lazy 
list as the equivalent of an iterator in C++ - the elements are only created 
when needed, but once read, I only read them once, so I don't need the 
memoization properties of lazyness.

When I first started to learn Haskell, I thought lazyness was essential for 
monads and hence an acceptable price to pay for using them. However I now 
think that monads would work perfectly without lazyness, since they are 
usually always defined in terms of >>= (not >> as I'd thought when I didn't 
know Haskell).

Other uses of lazyness are of course infinite structures and fixpoints etc.

I think the use of a lazy list as a read-once-on-demand stream could be 
achieved just as easily by a strict language with some syntactic sugar by 
redefining the meaning of []:

    data GlueList a = Empty | Cons a [a]

    type [a] = () -> GlueList a

    force :: (() -> a) -> a
    force f = f ()

Pattern matching could then be changed so that

    p [a] = exp

is short for:

     p x = case force x of
                 Cons a y -> case force y of
                                         Empty -> exp

and

    p [h|t] = exp    -- Prolog style list sugar

    p x = case force x of
                   Cons h t -> exp

and in an expression, [exp1,...] would be expanded into the appropriate 
delayed construction eg:

    x = [a]

    x = \() -> Cons a (\() -> Empty)

(List comprehensions could just be written using do notation).

There could also be extra syntactic support for force/delay eg !exp to mean 
exp () and ~exp to mean \()->exp. With this extra sugar, it might be 
relatively painless to still use infinite data structures.

Lazyness seems to sometimes be used to accomplish things that could easily 
be implemented in other ways, perhaps even better, and with more control 
(and certainly more explicitness) over the exact aspect of lazyness that is 
being used in a certain situation eg memoization, desugared attribute 
grammars, list-as-glue, etc.

The advantages would be that the resulting language would be simpler to 
understand and could execute like lightning so there would be no need to use 
C or ML ever again.

Afaik the full speed advantage can't be achieved just by syntactic sugar for 
regular Haskell since regular Haskell, even with seq etc, still needs to use 
a lifted type system, but syntactic sugar could certainly be used to 
implement such a language on top of Haskell to investigate if the complete 
absence of lazyness would cause any problems in practice. If I get time I 
might try to do this but I've shared the idea here in the vague hope someone 
else might want to do it first :-)

There certainly seems to be a "gap in the market" between the perfection of 
lazy Haskell's monads, typeclasses etc and strict ML's side effects and less 
expressive type system.

Regards, Brian.

-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com