[Haskell-cafe] How unique is Unique

[Emil Axelsson]

2011-05-28 11:35, Heinrich Apfelmus skrev:
> Emil Axelsson wrote:
>> Hello!
>>
>> Lacking a proper blog, I've written some notes about Data.Unique here:
>>
>>    http://community.haskell.org/~emax/darcs/MoreUnique/
>>
>> This describes a real problem that makes Data.Unique unsuitable for
>> implementing observable sharing.
>>
>> The document also proposes a solution that uses time stamps to generate
>> symbols that are "more unique".
>>
>> Does anyone have any comments on the proposed solution? Are there any
>> alternatives available?
>
> I don't know how Data.Unique is implemented. For observable sharing, I
> usually implement my own variant of Data.Unique with a global
> variable/counter.

This is how Data.Unique is implemented too. Would your implementation 
pass the test I posted at the link above?



> Since every module of my DSL depends on the same
> global variable, only two things should happen:
>
> * Reloading a module does not reload the global counter. Everything is fine.
> * Reloading a module does reload the global counter. This forces *all*
> modules to be reloaded, which removes all expressions that have used the
> old variable from scope.

But Simon Marlow just said that CAFs are reset upon reload. So the first 
situation should never occur(?). And as my example shows, resetting the 
counter does not force all dependent modules to get reloaded.



> However, note that the problem is not so much with Data.Unique; the real
> problem is that you can't say "I want this to be unique", you have to
> say "I want this to be unique within this or that *context*". Imagine
> that I give you two expressions with some  Uniques  inside, some of them
> equal, some of them not. How do you know that two equal Uniques denote
> the same subexpressions? For that, you have to know that I created them
> in the same context, in the same *environment*.
>
> Using Data.Unique assumes that the environment is one program run. It is
> clear that reloading modules in GHCi leads to different environments.

OK, so I guess you could say that my solution makes the context explicit 
by associating it with a time stamp. Of course, this is just an 
approximation, because it's not impossible for two different contexts to 
get the same time stamp, especially in a parallel setting. However, it 
seems that this somewhat ugly trick might actually be what makes this 
approach to observable sharing work in practice.



> Concerning observable sharing, I very much like the approach from
>
>     Andy Gill. Type safe observable sharing.
> http://www.ittc.ku.edu/csdl/fpg/sites/default/files/Gill-09-TypeSafeReification.pdf
>
> which uses  StablePointers . Unfortunately, it forces Typeable
> contraints on polymorphic combinators.

As far as I've heard, the semantics of stable pointers is not always 
well-defined either (but I could be wrong). But I should look into 
whether this technique could be used with the syntactic library. It 
would be nice to be able to gather several techniques under a common 
interface.

/ Emil