it seems that there is not yet a ticket about putting seq into a type class (again).
In my opinion, having seq available for every type is a serious flaw. One problem is that the law f = \x -> f x doesn't hold anymore since the equation is false for f = _|_. There was also a discussion on one of the mailing lists some time ago which revealed that the Monad instance for IO doesn't satisfy the monad laws because of the availability of seq for IO, I think.
In addition, the automatic definition of seq for every type can make implementation details visible which were thought of as completely hidden. For example, it might make a difference whether one uses data or newtype for a one-alternative-one-field datatype, even if the data constructor is hidden.
I therefore propose to declare a class like this:
class Seq a where seq :: a -> b -> b
Oh please, no. This sounds like a good idea in principle, but it was a nightmare in practice. First, the implementation details and the difference between _|_ and const _|_ make a difference to space behaviour, and one needs a way to control that. Hiding the differences can make space leaks *impossible* to fix. Secondly, the need to insert and remove Seq contexts from type signatures during space debugging is a major overhead. In my practical experience such overheads made some desirable refactorings impossible to carry out in the time available for the project. Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases. John
John Hughes:
Wolfgang Jeltsch:
it seems that there is not yet a ticket about putting seq into a type class (again).
And I hope it stays that way.
This sounds like a good idea in principle, but it was a nightmare in practice.
First, the implementation details and the difference between _|_ and const _|_ make a difference to space behaviour, and one needs a way to control that. Hiding the differences can make space leaks *impossible* to fix.
Along similar lines: I like Haskell being lazy, but it has to make it easier for the programmer to enforce eager evaluation where necessary for good resource utilisation. `seq' already is annoying and inconvenient (as it forces you to re-arrange your code), let's not make it worse. I'd like Haskell' to make it easier to force evaluation, which is why I like the bang pattern proposal. Manuel
Am Freitag, 24. März 2006 14:40 schrieb John Hughes:
[...]
Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases.
I will probably have a look at this paper. Nevertheless, I feel uncomfortable with the fact that something that isn't a monad claims to be a monad, etc. Maybe we should rename seq to unsafeSeq or something similar.
John
Best wishes, Wolfgang
On 2006-03-29 at 18:34+0200 Wolfgang Jeltsch wrote:
Am Freitag, 24. März 2006 14:40 schrieb John Hughes:
[...]
Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases.
I will probably have a look at this paper. Nevertheless, I feel uncomfortable with the fact that something that isn't a monad claims to be a monad, etc. Maybe we should rename seq to unsafeSeq or something similar.
Or do what I suggested in http://www.haskell.org//pipermail/haskell-prime/2006-March/001120.html <26869.1143633002@calligramme.charmers> and make seq a pragma. It really doesn't matter that pragmas in C are optional: we don't have to follow that. If we don't like calling these non-optional pragmas by that name, we can think of another, but I'm sure that seq (a) doesn't belong as a function, (b) is essential, and (c) is made too fiddly if it's in a class, so the best way is to use some form of syntax to distinguish them from ordinary functions. It certainly seems to me that we need a method of adding operational annotations while leaving the denotation unchanged (or at least replacing it with something ⊑ it), and that such annotations shouldn't masquerade as functions. I'm also curious to know what people currently involved in implementation think of STEP. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk
On Wed, Mar 29, 2006 at 05:58:24PM +0100, Jon Fairbairn wrote:
Or do what I suggested in http://www.haskell.org//pipermail/haskell-prime/2006-March/001120.html <26869.1143633002@calligramme.charmers> and make seq a pragma. It really doesn't matter that pragmas in C are optional: we don't have to follow that.
Would that really change that much. Anyone who likes the old seq function (less characters to type than with pragma) will be able to define it: seq a b = {-# SEQ a #-} b Perhaps if you allowed syntax for forcing many expressions people would be more willing to use it: {-# SEQ a, b, c, d #-} e Best regards Tomasz
John, et. al., I'd rather just use a polymorphic function, but would having some sort of ... notation in class contexts help? sort (Eq a,_) => [a] -> [a] Which means that we need at least the Eq a, but perhaps more. See #86 http://hackage.haskell.org/trac/haskell-prime/wiki/ PartialTypeAnnotations In terms of seq, and deepSeq, here is a space leak problem I often need to solve. Imagine a function cpuStep :: CPUState -> CPUState where the CPUState is a large structure, for (say) the 68000 register file, a and also contains information about a level-1 cache. I want to run for 100,000 instructions. runCPU :: Int -> CPUState -> CPUState runCPU 0 state = state runCPU n state = runCPU (n-1) (cpuStep state) My job is to make this run in approximately constant space; a reasonable request. Well, we can add a seq to the modified state: runCPU n state = state'` `seq` runCPU (n-1) state' where state' = cpuStep state But the thing still leaks like crazy. *I've seen this again and again.* Some internal piece of data inside CPUState depends on the value of another piece of CPUState from the previous iteration. At Galois, we often fix this with a deepSeq (actually using NFData). runCPU n state = state'` `depSeq` runCPU (n-1) state' where state' = cpuStep state Great, the leak is gone, but now each step takes 100s of times longer! So we descend into the implementation of cpuStep, turning on-and-off deepSeq's until we have constant space version. Ugg. Then someone makes a small change to our implementation of cpuStep, and re-introduces the leak... We have used a version of deepSeq that that looked up a table at runtime, to find what to make strict and what not to make strict. This made for rapid binary searching to find the problem thunk(s), but ugly unsafePerformIOs behind the derivings, and non-standard hacks. But like runtime flags for asserts, we could have runtime arguments for seq/deepSeq pragmas. Questions - Does anyone have any better suggestions of how to fix this real issue? - Could a polymorphic deepSeq allow for a implementation that does not do repeated walked over pre-evaluated data? Andy Gill On Mar 24, 2006, at 5:40 AM, John Hughes wrote:
it seems that there is not yet a ticket about putting seq into a type class (again).
In my opinion, having seq available for every type is a serious flaw. One problem is that the law f = \x -> f x doesn't hold anymore since the equation is false for f = _|_. There was also a discussion on one of the mailing lists some time ago which revealed that the Monad instance for IO doesn't satisfy the monad laws because of the availability of seq for IO, I think.
In addition, the automatic definition of seq for every type can make implementation details visible which were thought of as completely hidden. For example, it might make a difference whether one uses data or newtype for a one-alternative-one-field datatype, even if the data constructor is hidden.
I therefore propose to declare a class like this:
class Seq a where seq :: a -> b -> b
Oh please, no.
This sounds like a good idea in principle, but it was a nightmare in practice.
First, the implementation details and the difference between _|_ and const _|_ make a difference to space behaviour, and one needs a way to control that. Hiding the differences can make space leaks *impossible* to fix.
Secondly, the need to insert and remove Seq contexts from type signatures during space debugging is a major overhead. In my practical experience such overheads made some desirable refactorings impossible to carry out in the time available for the project.
Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases.
John
_______________________________________________ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
On Mar 29, 2006, at 2:23 PM, Andy Gill wrote:
John, et. al.,
I'd rather just use a polymorphic function, but would having some sort of ... notation in class contexts help?
sort (Eq a,_) => [a] -> [a]
Which means that we need at least the Eq a, but perhaps more. See #86 http://hackage.haskell.org/trac/haskell-prime/wiki/ PartialTypeAnnotations
In terms of seq, and deepSeq, here is a space leak problem I often need to solve.
Imagine a function
cpuStep :: CPUState -> CPUState
where the CPUState is a large structure, for (say) the 68000 register file, a and also contains information about a level-1 cache.
I want to run for 100,000 instructions.
runCPU :: Int -> CPUState -> CPUState runCPU 0 state = state runCPU n state = runCPU (n-1) (cpuStep state)
My job is to make this run in approximately constant space; a reasonable request.
Well, we can add a seq to the modified state:
runCPU n state = state'` `seq` runCPU (n-1) state' where state' = cpuStep state
But the thing still leaks like crazy. *I've seen this again and again.* Some internal piece of data inside CPUState depends on the value of another piece of CPUState from the previous iteration.
[snip]
Questions - Does anyone have any better suggestions of how to fix this real issue?
My initial thought is to add strictness flags to the datatype declaration for the bits of state that cause trouble (report, section 4.2.1). For something like this, I'd expect you could safely mark _every_ field strict; in that case you might be able to coerce the compiler to unbox the entire state record and save a few allocations. But it strikes me that you must have thought of this already; is there some reason it won't work? [snip] Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
On Mar 29, 2006, at 11:50 AM, Robert Dockins wrote:
On Mar 29, 2006, at 2:23 PM, Andy Gill wrote:
John, et. al.,
I'd rather just use a polymorphic function, but would having some sort of ... notation in class contexts help?
sort (Eq a,_) => [a] -> [a]
Which means that we need at least the Eq a, but perhaps more. See #86 http://hackage.haskell.org/trac/haskell-prime/wiki/ PartialTypeAnnotations
In terms of seq, and deepSeq, here is a space leak problem I often need to solve.
Imagine a function
cpuStep :: CPUState -> CPUState
where the CPUState is a large structure, for (say) the 68000 register file, a and also contains information about a level-1 cache.
I want to run for 100,000 instructions.
runCPU :: Int -> CPUState -> CPUState runCPU 0 state = state runCPU n state = runCPU (n-1) (cpuStep state)
My job is to make this run in approximately constant space; a reasonable request.
Well, we can add a seq to the modified state:
runCPU n state = state'` `seq` runCPU (n-1) state' where state' = cpuStep state
But the thing still leaks like crazy. *I've seen this again and again.* Some internal piece of data inside CPUState depends on the value of another piece of CPUState from the previous iteration.
[snip]
Questions - Does anyone have any better suggestions of how to fix this real issue?
My initial thought is to add strictness flags to the datatype declaration for the bits of state that cause trouble (report, section 4.2.1). For something like this, I'd expect you could safely mark _every_ field strict; in that case you might be able to coerce the compiler to unbox the entire state record and save a few allocations.
But it strikes me that you must have thought of this already; is there some reason it won't work?
[snip]
The principal concern is the space leak, not the performance. But you ask a good question. Well, first the number of datatypes involved was large, over 100 data's. Put in the 100s of bangs, and the problem was still there. Secondly, we might not have access the the code for cpuStep, it might be in a library. The problem(s) were things like regs :: !Array Int RegVal status :: ![Status] The ! gives you a single level of strictness, so the list above is only strict in its first cons, not its spine or its elements. The Array is not strict in its values. If a RegVal depends on a previous register value, it might keep the *whole* array inside the thunk. Consider this example: copyRegister :: Int -> Int -> Array Int RegVal -> Array Int RegVal copyRegister r1 r2 arr = arr // [(r1,arr ! r2)] a simple fix is: copyRegister :: Int -> Int -> Array Int RegVal -> Array Int RegVal copyRegister r1 r2 arr = deepSeq $ arr // [(r1,arr ! r2)] But what happens if 'copyRegister a b' is itself a thunk? Perhaps something like: regs :: !!Array Int RegVal status :: !![Status] should be considered. (Aside: What would be nice to have is "there should only be one instance of this type, tell me if that is not the case" evaluation mode. I'm not quite sure how to express this, though). Andy Gill
Hello Andy, Thursday, March 30, 2006, 12:06:36 AM, you wrote:
Questions - Does anyone have any better suggestions of how to fix this real issue?
use mutable state, possible in the ST monad?
The problem(s) were things like
regs :: !Array Int RegVal
use parallel or unboxed arrays here
status :: ![Status]
you need a strict list, smth like: type StrictList a = Cons !(StrictList a) !a | Nil it's the exact what i said some time ago, although for me main problem is not space leaks, but the huge time required to work with lazy data structures what are really never contain unevaluated data
(Aside: What would be nice to have is "there should only be one instance of this type, tell me if that is not the case" evaluation mode. I'm not quite sure how to express this, though).
my congratulations, you are discovered the "unique" types from Clean (these types is one of reasons why this lazy language sometimes are faster that haskell/ghc) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Mar 29, 2006, at 1:59 PM, Bulat Ziganshin wrote:
Hello Andy,
Thursday, March 30, 2006, 12:06:36 AM, you wrote:
Questions - Does anyone have any better suggestions of how to fix this real issue?
use mutable state, possible in the ST monad?
Thanks for you comments. This would be fine if I was starting from scratch. For the sake of argument, though, one of our clients gave us the basic code, which, because it is written in a purely functional style, they love its specification feel. We did not write it, so rewriting is not an option (client will not pay for this). My job is to make our wrapper round such that the state to state model works in reasonable space. I can request small changes, a seq here, a prime there, but no restructuring.
The problem(s) were things like
regs :: !Array Int RegVal
use parallel or unboxed arrays here
status :: ![Status]
you need a strict list, smth like:
type StrictList a = Cons !(StrictList a) !a | Nil
it's the exact what i said some time ago, although for me main problem is not space leaks, but the huge time required to work with lazy data structures what are really never contain unevaluated data
Again, this is someone elses code. I've love a way of asking for a strict list, or a strict array. Ideally a hyperstrict one. But using new datatypes in the context of Haskell' is not a realistic option everywhere. I am talking about what Galois is wanting from Haskell' .. a easier way of hammering space leaks. Efficiency is not really a problem for us, thanks to the great work of the Haskell community over the last few years! A deepSeq solution would go a long way to help alleviate space leak, and helping track them down. I've personally spend perhaps 4 weeks thumping space leaks in various projects over the last 12 months (I do tend to get given the space leaks to find) but would rather find better use of galois' time. Once we find the problem, they tend to be a handful of lines, and deepSeq is part of a methodology for systematically finding them. I'm about to mail out a concrete proposal for deepSeq in Haskell'.
(Aside: What would be nice to have is "there should only be one instance of this type, tell me if that is not the case" evaluation mode. I'm not quite sure how to express this, though).
my congratulations, you are discovered the "unique" types from Clean (these types is one of reasons why this lazy language sometimes are faster that haskell/ghc)
I'll look at unique times in Clean, then... thanks for the pointer.
-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (8)
-
Andy Gill -
Bulat Ziganshin -
John Hughes -
Jon Fairbairn -
Manuel M T Chakravarty -
Robert Dockins -
Tomasz Zielonka -
Wolfgang Jeltsch