[Haskell-cafe] How unique is Unique

[Heinrich Apfelmus]

Emil Axelsson wrote:
> Heinrich Apfelmus wrote:
> 
>> 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.

Something is really weird here. In your example, reloading M2 should not 
reset the counter, but it does. However, it's not true that all CAFs are 
reset. After all, this would mean that  a  would have been reset as well!

(Of course, if the two requirements above were met, then it would work.)

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

Well, what I actually wanted to say is that your values are 
"free-floating", they contain a lot of "dangling pointers". There is a 
fundamental problem here which I think you're trying to paste over with 
judicious use of side effects.

Observable sharing is just a funny way of augmenting your DSL with  let 
  bindings, the funny thing being that you can use the host-language 
let  instead of an separate  Let  constructor. I recommend to think it 
terms of an explicit  Let  constructor, this will clear up a lot of 
confusion.

For instance, your example can be written as

     a = Let (1 := "a") `In` Var 1
     b = Let (2 := "b") `In` Var 2

(Now, the purpose of Data.Unique is just to supply fresh variable 
names.) What happens if  b  is defined as

     b = Let (1 := "b") `In` Var 1

? The expressions  a  and  b  are both  Var 1 , but the variables refer 
to different environments (1 := "a") and (1 := "b"). If you want to make 
a large expression from  a  and  b , you have to unify the two 
environments. For instance, you can use scoping rules (= associated each 
variable with the height in the expression tree) or you can rename 
variables. Or you can use  unsafePerformIO , which provides one single 
global environment, eliminating the need to unify environments in the 
first place. Unfortunately, global environments are unsafe.


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

Err, I meant Stable *Names*, not Stable Pointers, sorry. The worst thing 
that can happen is that you lose some sharing, but you can never 
accidentally introduce sharing.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com