seq as a class method

[Andy Gill]

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 at haskell.org
> http://haskell.org/mailman/listinfo/haskell-prime