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

minh thu noteed at gmail.com
Thu Jun 15 13:34:38 EDT 2006


hi
in fact, i think that for a while ...
moreover, i thought to translate to some kind of readable c (because
there s so much c libs all around).
i think it's even possible to retain laziness where it's ok ( for data
structure essentially).

is-it possible to know what you're doing at metamilk ?

mt

2006/6/13, Brian Hulley <brianh at metamilk.com>:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list