seq as a class method

Robert Dockins robdockins at fastmail.fm
Wed Mar 29 14:50:49 EST 2006


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



More information about the Haskell-prime mailing list