Everything but the lazyness - idea for force/delay lists

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

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 

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Everything but the lazyness - idea for force/delay lists

Vo Minh Thu
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 <[hidden email]>:

> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Everything but the lazyness - idea for force/delay lists

Brian Hulley
minh thu wrote:
> 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).

Hi Thu -

Someone pointed out (offlist) a useful paper by Phil Wadler "How to add
laziness to a strict language without even being odd" which shows how
laziness can be used without needing a lifted type system.

Once you've understood the subtleties of the FFI, it's relatively easy to
use it link to C libs.

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

Well I'd tell you if I knew myself! :-)

Seriously though, at the moment my aim is to develop an integrated
programming environment for a language similar to Haskell, either Haskell
itself or a non-lazy version of it, also with some syntactic modifications
to make it easier to use. It's in very early stages though. I'm trying as
much as possible to write everything from scratch (including the GUI) in
Haskell so I can see what the advantages/disadvantages of Haskell are and
where improvements in the syntax would be useful.

My experience so far is that the typeclasses and existentials that Haskell
supports are an advantage over OCaml or SML, but that the lazyness is a real
nusiance but with some extra effort it's possible to mostly get rid of it.

Regards, Brian.

>
> mt
>
> 2006/6/13, Brian Hulley <[hidden email]>:
>> 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.


--
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: Everything but the lazyness - idea for force/delay lists

Bulat Ziganshin-2
Hello Brian,

Friday, June 16, 2006, 12:13:27 AM, you wrote:

> Seriously though, at the moment my aim is to develop an integrated
> programming environment for a language similar to Haskell, either Haskell
> itself or a non-lazy version of it, also with some syntactic modifications
> to make it easier to use. It's in very early stages though. I'm trying as
> much as possible to write everything from scratch (including the GUI) in
> Haskell so I can see what the advantages/disadvantages of Haskell are and
> where improvements in the syntax would be useful.

i hope you are know about Clean


--
Best regards,
 Bulat                            mailto:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe