deeqSeq proposal

[Andy Adams-Moran]

Andy Gill wrote:
> 
> On Apr 4, 2006, at 3:47 AM, Simon Marlow wrote:
> 
>> On 30 March 2006 23:12, Andy Gill wrote:
>>
>>> Implementation:
>>>
>>> deepSeq (RAW_CONS <is_deep_seq'd_bit> ... fields ) =
>>>      if <is_deep_seq'd_bit> == True
>>>          then return  /* hey, we've already deepSeq'd this */
>>>          else set <is_deep_seq'd_bit> to True.
>>>                   deepSeq (field_1)
>>>                   ...
>>>                   deepSeq (field_n)
>>> deepSEQ (REF/MVAR...) = return
>>
>> So deepSeq doesn't return _|_ when passed a cyclic structure?  This is a
>> bad idea, because it lets you distinguish cyclic structures from
>> infinite ones.  deepSeq has to behave like a function, regardless of its
>> implementation.
>>
>> Cheers,
>>     Simon
> 
> Good observation, though pragmatically I'd rather the deepSeq to
> behave well on loops. Its the thunks I'm trying to remove, not
> the loop itself.
> 
> Allowing loops in the returned value gives the the beauty of laziness
> to construct the cycle, but the assurance that the structure does not
> contain
> thunks. A nice property, and a way to interact with laziness.
> 
> let xs' () = 1 : 2 :  xs' ()
> let xs2 = xs'
> 
> let xs = 1 : 2 : xs
> 
> So deepSeq xs2 ==> _|_, but deepSeq xs ==> xs
> 
> I appeal to the "morally correct reasoning"  argument .. If the program
> terminates, then it is still correct. The deepSeq is an assertion about
> the ability to represent the result in finite space.

I'm not convinced Simon's argument holds, as I don't think you can use
deepSeq to write a Haskell function that will distinguish cyclic
structures from infinite ones. If we can't do that, then we haven't
really added any new semantic observational capability to the theory, so
I think the "morally correct reasoning" argument holds.

Simon?

A

-- 
Andy Adams-Moran                             Phone: 503.626.6616, x113
Galois Connections Inc.                              Fax: 503.350.0833
12725 SW Millikan Way, Suite #290                http://www.galois.com
Beaverton, OR 97005                             adams-moran at galois.com