[Haskell-cafe] How unique is Unique

[Heinrich Apfelmus]

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. 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.


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.

You can make the environment explicit as a type parameter and use the 
usual rank-2 polymorphism trick:

    interpret :: (forall env. Expr env a) -> a

The additional type parameter will quickly become unwieldy, though.


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.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com