RE: seq as a class method
Hi Andy, This is a good question, and something we hit in GHC quite often too. Our solution is to use a mixture of strictness annotations, deepSeq, smart constructors, and hand-waving optimism that things will be evaluated soon enough anyway. Having to occasionally deepSeq the structore to force the thunks has quite a few problems, as you say. A better approach might be to establish a guarantee that the data type isn't leaky; that is, every field is either strict, or guaranteed to be deepSeq'd at construction by a smart constructor. To enforce the smart constructor, you might want ReadOnlyConstructors (see the Haskell' proposal). So for things like this: regs :: !Array Int RegVal You either use a strict Array type, or deepSeq the Array when constructing the record. To support record update without having to re-deepSeq everything in the record you would want to provide record updaters as part of the abstract datatype. Hope this helps... Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: seq as a class method
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 [EMAIL PROTECTED] 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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: seq as a class method
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: seq as a class method
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: seq as a class method
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: seq as a class method
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
seq as a class method
Hello, 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 (Perhaps the class name should be chosen better.) Generation of standard instances should be supported via deriving clauses or Template Haskell. For an algebraic datatype declared via data T a1 ... an = C1 t11 ... t1m1 | ... | Ck tk1 ... tkmk the implementation of seq should be something like this: seq (C1 _ ... _) = id seq _ = id What do others think? Best wishes, Wolfgang ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime