Re: do notation and
I wrote: | So, changing the translation in GHC might actually introduce | a very nasty space leak in existing programs! Simon Peyton-Jones answered: | It might, conceivably. But the H98 report doesn't | seem the right place to try to tweak full laziness. | So I'm going to leave the report as it is. Hugs and | GHC have changed to match. I do not understand what full laziness has to do with all this! The big question is, in the following: f = do expr1 expr2 Should expr2 be shared among different calls to f? It is clear that expr1 will, but expr2 will not be shared, using the current translation used by GHC and Hugs. Maybe I should be a bit more concrete; Here is a little example program: main = do print start writeFile apa (show [1..]) When translating the do-notation using , we blow out of heap space (in both Hugs and GHC (*)). The code then looks as follows: main1 = print start writeFile apa (show [1..]) When translating the do-notation using =, we do not blow out of heap. The code then looks as follows: main2 = print start = \_ - writeFile apa (show [1..]) The reason for this difference is that the computation writeFile apa (show [1..]) is kept in memory in main1 and not in main2. So, concretely, the fix in Hugs and GHC will possibly break a number of programs. Specifically programs that for example produce a lot of output which does not depend on any run-time information. Regards, /Koen. (*) Since GHC garbage collects CAFs, we have to add an extra reference to main, for example: main = do print start writeFile apa (show [1..]) main -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: do notation and
I do not understand what full laziness has to do with all this! The big question is, in the following: f = do expr1 expr2 Should expr2 be shared among different calls to f? It is clear that expr1 will, but expr2 will not be shared, using the current translation used by GHC and Hugs. Well, if a compiler implemented full lazyiness, then both translations (with = and with ) would share expr2... I think that it is worth warning Haskell users about the potential space leak you noticed, but I don't think that it should influence the decision on do and . I don't believe that it will break many programs. How many programs produce large *input independent* output, that is not already literally in the source, in a caf with a long life-time? Unfortunately I'm not even sure that your warning should be added to the Haskell report, because the report says hardly anything about sharing and space usage. I believe even a call-by-name implementation or a full laziness implementation would be fully Haskell 98 compliant. (I'm not happy about that either). Ciao, Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: do notation and
I don't believe that it will break many programs. How many programs produce large *input independent* output, that is not already literally in the source, in a caf with a long life-time? That sounds like a description of all the animation programs in Paul Hudak's School of Expression book and there's plenty more examples like that. [I haven't tested whether these programs do leak space with the modified compiler - my point is that there is a large class of programs with exactly the characteristics you describe.] -- Alastair Reid ps I think your CAF restriction is a bit of a red herring - Koen's modification to make his example leak in GHC (which GCs CAFs) shows that the leak happens as long as the relevant thunk isn't collected. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: do notation and
I don't believe that it will break many programs. How many programs produce large *input independent* output, that is not already literally in the source, in a caf with a long life-time? That sounds like a description of all the animation programs in Paul Hudak's School of Expression book and there's plenty more examples like that. [I haven't tested whether these programs do leak space with the modified compiler - my point is that there is a large class of programs with exactly the characteristics you describe.] -- Alastair Reid ps I think your CAF restriction is a bit of a red herring - Koen's modification to make his example leak in GHC (which GCs CAFs) shows that the leak happens as long as the relevant thunk isn't collected. This whole discussion is a red herring. The Haskell report doesn't say anything about sharing - it doesn't even mandate laziness (look in the index - you won't find the term lazy :-). Different compilers will behave differently, GHC in particular will probably share expr2 in Koen's example f = do expr1 expr2 regardless of whether the translation uses or =, because GHC implements full laziness (when -O is turned on). So you might reasonably argue that Haskell should provide more control over such things, and I might well agree. But there's no point in discussing whether using = or in the translation of do-notation is better: they're both equivalent as far as the current language specification is concerned. Cheers, Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: do notation and
Simon Marlow wrote: | This whole discussion is a red herring. The Haskell | report doesn't say anything about sharing - it doesn't | even mandate laziness (look in the index - you won't | find the term lazy :-). I was not suggesting that the Haskell'98 report should change or even give a warning -- I was giving a warning to compiler implementors, that this simple change might have disastrous effects. BTW, I remember a similar discussion along these lines on the Haskell mailing list that happened in 1997 I think, but I cannot find the archives. Another comment one can make here is the following: if Haskell does not care about sharing, why is the monomorphism restriction there? Regards, /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: do notation and
I was not suggesting that the Haskell'98 report should change or even give a warning -- I was giving a warning to compiler implementors, that this simple change might have disastrous effects. BTW, I remember a similar discussion along these lines on the Haskell mailing list that happened in 1997 I think, but I cannot find the archives. Another comment one can make here is the following: if Haskell does not care about sharing, why is the monomorphism restriction there? One difference is that when the compiler gives you *less* sharing than you were expecting, then it is in some sense worse than getting more sharing. More sharing might result in space leaks, but in practice (in my experience anyway) this isn't as noticeable as the time leaks you get when sharing is lost. GHC has implemented almost-full-laziness for a long time, and I don't recall anyone ever complaining about space leaks introduced as a result. The monomorphism restriction, on the other hand, is concerned with the user getting no less than the amount of sharing he/she was expecting (personally I think this should be a compiler warning rather than a language restriction, but I'm aware there are other reasons for wanting the MR too). Cheers, Simon ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: do notation and
| So, changing the translation in GHC might actually introduce | a very nasty space leak in existing programs! It might, conceivably. But the H98 report doesn't seem the right place to try to tweak full laziness. So I'm going to leave the report as it is. Hugs and GHC have changed to match. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: do notation and
| do {e ; stmts} = e do {stmts}
With the risk of being late at this, and with the risk of
repeating something that has already been said (because I
have been away), I will give my two euro-cents.
I remember a discussion at the Haskell mailing list about
the possibility of creating a nasty space leak with this
translation. After all, there is a difference between:
e1 e2
which, for the default definition of expands to an
expression which is operationally equivalent to:
e1 = let x = e2 in \_ - x,
and:
e1 = \_ - e2.
In the first case, x is shared between successive
invocations, but in the second case, e2 is recomputed.
I remember that the example involved a definition like:
f = do ...; print [1..]
In the translation in the report, the list [1..] is shared
between all invocations of f, whereas the current GHC
translation does not.
So, changing the translation in GHC might actually introduce
a very nasty space leak in existing programs!
/Koen.
--
Koen Claessen
http://www.cs.chalmers.se/~koen
Chalmers University, Gothenburg, Sweden.
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
Simon Peyton-Jones wrote: However, James implies that in his monad () has a different meaning than its usual one, and Haskell 98 allows that because () is one of the class operations (not a good design choice I think). I'm quite reluctant to make the meaning of do-notation dependent on such differences. James, can you convince us that doing so would be a good idea? I didn't see this before sending off my previous rant. My apologies. Having separate definitions for = and is more flexible. With the definition of a default for in the Monad class, having them separate is no less convenient. More flexible, no less convenient---where is the design flaw? I thought it was a design triumph, fully in the spirit of elegance I associate with Haskell. Are there Monad laws that this breaks? If not, why impose an unnecessary constraint? Let me describe my practical motivation for a separate definition for . I am experimenting with using Haskell to build program generators for embedded domain-specific languages. The goal is to generate high-performance Fortran codes from high-level specifications. I am using a Monad to hold the state of the generation. One thing maintained in the state is a list of declared variables and a list of busy, or in-scope, variables. The generator automatically adds variable declarations as needed. By differentiating between monadic statements that return an argument (=) and those that don't (), the generator can easily determine when variables go out of scope. Within the definition of , it can free these variables (in a logical, not physical, sense) to be reused. This is critical because it allows me to generate code using large temporary arrays efficiently. As far as I can tell, this use of breaks no monad laws. In Hugs, it works fine if I use directly instead of do. For the aesthetic acceptance of my user base, I need it to work with do notation. -- James B. White III (Trey) Center for Computational Sciences Oak Ridge National Laboratory [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
I am certain that was not the intention of the authors. So one
possibility is to change the second line to read
do {e;stmts} = e = (\ _ - do {stmts})
and that is what I *propose* to do.
However, James implies that in his monad () has a different meaning
than its usual one, and Haskell 98 allows that because () is one of
the class operations (not a good design choice I think). I'm quite
reluctant to make the meaning of do-notation dependent on such
differences.
I disagree. Hugs should be changed, not the report. In my opinion ()
is a class operation, because there may be more efficient
implementations of () than the default one (\x y - x = \_ - y).
The do notation should profit from a more efficient implementation.
I do think that James steps on very dangerous ground if his
implementation of () is semantically different from (\x y - x = \_
- y). This semantic equality is a law of the monad class, that users
expect to hold. However, the language (implementation) cannot enforce
it; in particular, compilers cannot use such laws for optimisations. The
programmer has the freedom to break such laws.
The situation is similar with classes such as Eq and Ord. You expect x
/= y == not (x == y), but it is not enforced.
Actually, the report currently doesn't say that the given default
definitions are laws which are expected to hold (except where a comment
says otherwise, see class Enum). I think such a statement should be
added to the report.
Happy Easter,
Olaf
--
OLAF CHITIL,
Dept. of Computer Science, The University of York, York YO10 5DD, UK.
URL: http://www.cs.york.ac.uk/~olaf/
Tel: +44 1904 434756; Fax: +44 1904 432767
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
Olaf Chitil wrote:
I am certain that was not the intention of the authors. So one
possibility is to change the second line to read
do {e;stmts} = e = (\ _ - do {stmts})
and that is what I *propose* to do.
However, James implies that in his monad () has a different meaning
than its usual one, and Haskell 98 allows that because () is one of
the class operations (not a good design choice I think). I'm quite
reluctant to make the meaning of do-notation dependent on such
differences.
I disagree. Hugs should be changed, not the report. In my opinion ()
is a class operation, because there may be more efficient
implementations of () than the default one (\x y - x = \_ - y).
The do notation should profit from a more efficient implementation.
I agree with Olaf (and James).
Incidentally, similar concerns occur in the context of the arrows framework.
Ross Paterson, in response to a request from us at Yale, recently changed
some derived arrow combinators into default methods of the arrow classes in
his implementation of the framework to allow more efficient, instance
specific, implementations of these combinators. Our request was prompted
by our work of (A)FRP, an embedded language.
/Henrik
--
Henrik Nilsson
Yale University
Department of Computer Science
[EMAIL PROTECTED]
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
On Thu, Mar 28, 2002 at 11:48:25AM -0500, [EMAIL PROTECTED] wrote: Incidentally, similar concerns occur in the context of the arrows framework. Ross Paterson, in response to a request from us at Yale, recently changed some derived arrow combinators into default methods of the arrow classes in his implementation of the framework to allow more efficient, instance specific, implementations of these combinators. Our request was prompted by our work of (A)FRP, an embedded language. Yes, but in that case the specific implementations are required to be denotationally equal to the default versions. And surely that was the original intention here. Section 6.3.6 of the Report needs an additional equation: m k = m = \_ - k Then Hugs and GHC would be correct but suboptimal. There's a similar glitch in the claim in section 3.5 of the Report that (+ (- exp)) is a substitute for (\x - x - exp), which is true only if x - y = x + negate y In that case the claim could be simply dropped. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
Ross Paterson wrote: Yes, but in that case the specific implementations are required to be denotationally equal to the default versions. And surely that was the original intention here. Section 6.3.6 of the Report needs an additional equation: m k = m = \_ - k Then Hugs and GHC would be correct but suboptimal. I agree that this equation should be in the report, but note that there is no *requirement* that the monad laws hold for user defined instances. The report merely states that they *should* hold. Maybe we should be more clear what this word *should* means. I understand it as meaning that the term monad suggests that these laws hold, that a programmer should have very good reasons for breaking any of them and if a law is broken a big warning should be attached to the code, because any user of a monad expects it to fulfill the laws. However, because the laws cannot be checked by an implementation, no implementation is allowed to make use of them. In particular, the laws may accidentally have been broken and if an implementation makes use of the laws, then the behaviour of the resulting computation may be completely incomprehensible. (Just to make clear that I don't advocate breaking these laws; but then I'm not a fan of monads anyway...) Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Do-notation
Yes, but in that case the specific implementations are required to be denotationally equal to the default versions. Yes, obviously. My only point was that I believe () should remain a class operation. /Henrik -- Henrik Nilsson Yale University Department of Computer Science [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
