[Haskell-cafe] Everything but the lazyness - idea for force/delay
brianh at metamilk.com
Mon Jun 12 19:30:52 EDT 2006
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
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
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.
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.
More information about the Haskell-Cafe