seq as a class method

[Andy Gill]

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