Emil Axelsson | 24 Aug 08:39 2012
Picon
Picon

Comparing StableNames of different type

Hi!

Are there any dangers in comparing two StableNames of different type?

   stEq :: StableName a -> StableName b -> Bool
   stEq a b = a == (unsafeCoerce b)

I could guard the coercion by first comparing the type representations, 
but that would give me a `Typeable` constraint that would spread 
throughout the code.

--

-- 
/ Emil
Simon Marlow | 24 Aug 11:08 2012
Picon

Re: Comparing StableNames of different type

On 24/08/2012 07:39, Emil Axelsson wrote:
> Hi!
>
> Are there any dangers in comparing two StableNames of different type?
>
>    stEq :: StableName a -> StableName b -> Bool
>    stEq a b = a == (unsafeCoerce b)
>
> I could guard the coercion by first comparing the type representations,
> but that would give me a `Typeable` constraint that would spread
> throughout the code.

I think that's probably OK.  It should be safe even if the types are 
different, but I presume you expect the types to be the same, since 
otherwise the comparison would be guaranteed to return False, right?

Cheers,
	Simon
Emil Axelsson | 24 Aug 11:18 2012
Picon
Picon

Re: Comparing StableNames of different type

2012-08-24 11:08, Simon Marlow skrev:
> On 24/08/2012 07:39, Emil Axelsson wrote:
>> Hi!
>>
>> Are there any dangers in comparing two StableNames of different type?
>>
>>    stEq :: StableName a -> StableName b -> Bool
>>    stEq a b = a == (unsafeCoerce b)
>>
>> I could guard the coercion by first comparing the type representations,
>> but that would give me a `Typeable` constraint that would spread
>> throughout the code.
>
> I think that's probably OK.

OK, good! How about putting this function in the library so that people 
don't have to hack it up themselves?

> It should be safe even if the types are
> different, but I presume you expect the types to be the same, since
> otherwise the comparison would be guaranteed to return False, right?

No, I want to do observable sharing of heterogeneously typed expressions 
which means I will be comparing expressions of different type.

/ Emil
Emil Axelsson | 24 Aug 11:39 2012
Picon
Picon

Re: Comparing StableNames of different type

2012-08-24 11:18, Emil Axelsson skrev:
> 2012-08-24 11:08, Simon Marlow skrev:
>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>> Hi!
>>>
>>> Are there any dangers in comparing two StableNames of different type?
>>>
>>>    stEq :: StableName a -> StableName b -> Bool
>>>    stEq a b = a == (unsafeCoerce b)
>>>
>>> I could guard the coercion by first comparing the type representations,
>>> but that would give me a `Typeable` constraint that would spread
>>> throughout the code.
>>
>> I think that's probably OK.
>
> OK, good! How about putting this function in the library so that people
> don't have to hack it up themselves?

Oops, I did not intend to sound suggestive :) I was more wondering if 
people think it would be a good idea. If so, I can make a proposal.

/ Emil
Simon Marlow | 28 Aug 10:34 2012
Picon

Re: Comparing StableNames of different type

On 24/08/2012 10:39, Emil Axelsson wrote:
> 2012-08-24 11:18, Emil Axelsson skrev:
>> 2012-08-24 11:08, Simon Marlow skrev:
>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>>> Hi!
>>>>
>>>> Are there any dangers in comparing two StableNames of different type?
>>>>
>>>>    stEq :: StableName a -> StableName b -> Bool
>>>>    stEq a b = a == (unsafeCoerce b)
>>>>
>>>> I could guard the coercion by first comparing the type representations,
>>>> but that would give me a `Typeable` constraint that would spread
>>>> throughout the code.
>>>
>>> I think that's probably OK.
>>
>> OK, good! How about putting this function in the library so that people
>> don't have to hack it up themselves?
>
> Oops, I did not intend to sound suggestive :) I was more wondering if
> people think it would be a good idea. If so, I can make a proposal.

Ok, I've added it.  It will be in GHC 7.8.1.

Cheers,
	Simon
Nicolas Frisby | 28 Aug 18:08 2012
Picon

Re: Comparing StableNames of different type

On Tue, Aug 28, 2012 at 3:34 AM, Simon Marlow <marlowsd <at> gmail.com> wrote:
>>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>>>>
>>>>> Are there any dangers in comparing two StableNames of different type?
>>>>>
>>>>>    stEq :: StableName a -> StableName b -> Bool
>>>>>    stEq a b = a == (unsafeCoerce b)
>>>>
> Ok, I've added it.  It will be in GHC 7.8.1.
>
> Cheers,
>         Simon

Might we benefit from having a variant that returns Maybe (a :=: b)?
Is that safe? I have limited experience with StableNames, but that
intuitively seems safe. But polymorphism and references deserve more
thought than I've given this yet.

I'm referring to "data (:=:) :: * -> * -> * where Refl :: (a :=: a)",
just to be clear.
Edward Kmett | 28 Aug 20:07 2012
Picon

Re: Comparing StableNames of different type


On Tue, Aug 28, 2012 at 12:08 PM, Nicolas Frisby <nicolas.frisby <at> gmail.com> wrote:
On Tue, Aug 28, 2012 at 3:34 AM, Simon Marlow <marlowsd <at> gmail.com> wrote:
>>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>>>>
>>>>> Are there any dangers in comparing two StableNames of different type?
>>>>>
>>>>>    stEq :: StableName a -> StableName b -> Bool
>>>>>    stEq a b = a == (unsafeCoerce b)
>>>>
> Ok, I've added it.  It will be in GHC 7.8.1.
>
> Cheers,
>         Simon

Might we benefit from having a variant that returns Maybe (a :=: b)?
Is that safe? I have limited experience with StableNames, but that
intuitively seems safe. But polymorphism and references deserve more
thought than I've given this yet.

I'm referring to "data (:=:) :: * -> * -> * where Refl :: (a :=: a)",
just to be clear.


No.

You can't safely determine that  a ~ b given that two stablenames are equal.

If you give Nothing a stableName, it'll have one stable name, regardless of if you use it as a Maybe Int or a Maybe Bool. Maybe Int and Maybe Bool are clearly not equal. This is admittedly an implementation detail. GHC would be perfectly within its rights (if somewhat silly) to construct a fresh Nothing every time, but it doesn't.

The reasoning you applied only works for fully monomorphic types.

 -Edward
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Nicolas Frisby | 28 Aug 23:06 2012
Picon

Re: Comparing StableNames of different type

Great. It was the sharing of polymorphic values like [] I was worried
about. Thanks for confirming.

On Tue, Aug 28, 2012 at 1:07 PM, Edward Kmett <ekmett <at> gmail.com> wrote:
>
> On Tue, Aug 28, 2012 at 12:08 PM, Nicolas Frisby <nicolas.frisby <at> gmail.com>
> wrote:
>>
>> On Tue, Aug 28, 2012 at 3:34 AM, Simon Marlow <marlowsd <at> gmail.com> wrote:
>> >>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>> >>>>>
>> >>>>> Are there any dangers in comparing two StableNames of different
>> >>>>> type?
>> >>>>>
>> >>>>>    stEq :: StableName a -> StableName b -> Bool
>> >>>>>    stEq a b = a == (unsafeCoerce b)
>> >>>>
>> > Ok, I've added it.  It will be in GHC 7.8.1.
>> >
>> > Cheers,
>> >         Simon
>>
>> Might we benefit from having a variant that returns Maybe (a :=: b)?
>> Is that safe? I have limited experience with StableNames, but that
>> intuitively seems safe. But polymorphism and references deserve more
>> thought than I've given this yet.
>>
>> I'm referring to "data (:=:) :: * -> * -> * where Refl :: (a :=: a)",
>> just to be clear.
>>
>
> No.
>
> You can't safely determine that  a ~ b given that two stablenames are equal.
>
> If you give Nothing a stableName, it'll have one stable name, regardless of
> if you use it as a Maybe Int or a Maybe Bool. Maybe Int and Maybe Bool are
> clearly not equal. This is admittedly an implementation detail. GHC would be
> perfectly within its rights (if somewhat silly) to construct a fresh Nothing
> every time, but it doesn't.
>
> The reasoning you applied only works for fully monomorphic types.
>
>  -Edward
Manuel M T Chakravarty | 26 Aug 08:03 2012
Picon
Picon

Re: Comparing StableNames of different type

Emil Axelsson <emax <at> chalmers.se>:
> 2012-08-24 11:08, Simon Marlow skrev:
>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>> Hi!
>>> 
>>> Are there any dangers in comparing two StableNames of different type?
>>> 
>>>   stEq :: StableName a -> StableName b -> Bool
>>>   stEq a b = a == (unsafeCoerce b)
>>> 
>>> I could guard the coercion by first comparing the type representations,
>>> but that would give me a `Typeable` constraint that would spread
>>> throughout the code.
>> It should be safe even if the types are
>> different, but I presume you expect the types to be the same, since
>> otherwise the comparison would be guaranteed to return False, right?
> 
> No, I want to do observable sharing of heterogeneously typed expressions which means I will be comparing
expressions of different type.

You may like to have a look at how we have done this in the Accelerate EDSL:

  https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs

In particular, the Eq instance for stable names of AST nodes is at

  https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs#L763

You may be able to use our entire scheme. (We have started to write it up as a paper, but the write up isn't in a
coherent state yet.)

Manuel
Emil Axelsson | 27 Aug 06:11 2012
Picon
Picon

Re: Comparing StableNames of different type

2012-08-26 08:03, Manuel M T Chakravarty skrev:
> Emil Axelsson <emax <at> chalmers.se>:
>> 2012-08-24 11:08, Simon Marlow skrev:
>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>>> Hi!
>>>>
>>>> Are there any dangers in comparing two StableNames of different type?
>>>>
>>>>    stEq :: StableName a -> StableName b -> Bool
>>>>    stEq a b = a == (unsafeCoerce b)
>>>>
>>>> I could guard the coercion by first comparing the type representations,
>>>> but that would give me a `Typeable` constraint that would spread
>>>> throughout the code.
>>> It should be safe even if the types are
>>> different, but I presume you expect the types to be the same, since
>>> otherwise the comparison would be guaranteed to return False, right?
>>
>> No, I want to do observable sharing of heterogeneously typed expressions which means I will be comparing
expressions of different type.
>
> You may like to have a look at how we have done this in the Accelerate EDSL:
>
>    https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs
>
> In particular, the Eq instance for stable names of AST nodes is at
>
>    https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs#L763

Hm, doesn't this impose a `Typeable` constraint on all AST nodes (which 
is what I'm trying to avoid)?

/ Emil
Manuel M T Chakravarty | 28 Aug 09:08 2012
Picon
Picon

Re: Comparing StableNames of different type

Emil Axelsson <emax <at> chalmers.se>:
> 2012-08-26 08:03, Manuel M T Chakravarty skrev:
>> Emil Axelsson <emax <at> chalmers.se>:
>>> 2012-08-24 11:08, Simon Marlow skrev:
>>>> On 24/08/2012 07:39, Emil Axelsson wrote:
>>>>> Hi!
>>>>> 
>>>>> Are there any dangers in comparing two StableNames of different type?
>>>>> 
>>>>>   stEq :: StableName a -> StableName b -> Bool
>>>>>   stEq a b = a == (unsafeCoerce b)
>>>>> 
>>>>> I could guard the coercion by first comparing the type representations,
>>>>> but that would give me a `Typeable` constraint that would spread
>>>>> throughout the code.
>>>> It should be safe even if the types are
>>>> different, but I presume you expect the types to be the same, since
>>>> otherwise the comparison would be guaranteed to return False, right?
>>> 
>>> No, I want to do observable sharing of heterogeneously typed expressions which means I will be
comparing expressions of different type.
>> 
>> You may like to have a look at how we have done this in the Accelerate EDSL:
>> 
>>   https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs
>> 
>> In particular, the Eq instance for stable names of AST nodes is at
>> 
>>   https://github.com/AccelerateHS/accelerate/blob/master/Data/Array/Accelerate/Smart.hs#L763
> 
> Hm, doesn't this impose a `Typeable` constraint on all AST nodes (which is what I'm trying to avoid)?

Yes, you need Typeable, but arguably that is cleaner than unsafeCoerce.

In any case, as I am not aware of any other system than Accelerate that implements observable sharing on
typed ASTs, you may find the Accelerate code to be a helpful source of inspiration.

Manuel
Edward Kmett | 24 Aug 16:10 2012
Picon

Re: Comparing StableNames of different type

You can wind up with StableNames matching even when the types differ. Consider naming [] :: [Int] and [] ::
[()]. This is harmless for most usecases.

I've used unsafeCoerce to compare StableNames on different types for years without problems.

Admittedly, I do find it a bit of an oddity that the type shows up in their signature at all. :)

Sent from my iPhone

On Aug 24, 2012, at 5:08 AM, Simon Marlow <marlowsd <at> gmail.com> wrote:

> On 24/08/2012 07:39, Emil Axelsson wrote:
>> Hi!
>> 
>> Are there any dangers in comparing two StableNames of different type?
>> 
>>   stEq :: StableName a -> StableName b -> Bool
>>   stEq a b = a == (unsafeCoerce b)
>> 
>> I could guard the coercion by first comparing the type representations,
>> but that would give me a `Typeable` constraint that would spread
>> throughout the code.
> 
> I think that's probably OK.  It should be safe even if the types are different, but I presume you expect the
types to be the same, since otherwise the comparison would be guaranteed to return False, right?
> 
> Cheers,
>    Simon
> 
> 
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users <at> haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Gmane