Map with types as keys, respecting type equivalence

[Ryan Hendrickson]

Is it possible to create a map with types as keys that respects type equivalence and doesn't have linear lookup cost?

To get a hash map, I'd need a hash function on types that respects type equivalence. The built-in hashCode on types doesn't:

typeOf[String].## != typeOf[java.lang.String].##

This isn't terribly surprising; those values do seem like different data structures even if they represent equivalent types. What is kind of driving me up the wall is that I don't see a way to normalize typeOf[String] into typeOf[java.lang.String], even though something in =:= must be doing that or something equivalent to that. I tried the suggestively-named 'normalize', but

typeOf[String].normalize.## != typeOf[java.lang.String].normalize.##

I tried poking around in the internal API and found dealias, but that also doesn't cut it. Is there any way, public or private, to go from typeOf[String] to typeOf[java.lang.String]? (Besides erasure, which is entirely too liberal.)

(Type equivalence in Scala is undecidable in general, right? I'm not sure what compromises =:= makes in the face of that fact, but I'm sure I'd be fine with similar compromises.)

Or, I could shoot for a tree map, which would require me to give some total ordering to types that also respects type equivalence. I have no idea how I'd begin to do that without solving the above problem, but maybe someone has thought of something clever?






(please forgive me my corporate legal disclaimer)

----------------------------------------

This message is intended exclusively for the individual(s) or entity to
which it is addressed. It may contain information that is proprietary,
privileged or confidential or otherwise legally exempt from disclosure.
If you are not the named addressee, you are not authorized to read,
print, retain, copy or disseminate this message or any part of it.
If you have received this message in error, please notify the sender
immediately by e-mail and delete all copies of the message.

[Paul Phillips]

On Tue, Apr 30, 2013 at 12:05 PM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

I tried poking around in the internal API and found dealias, but that also doesn't cut it.

dealias is how it's done. If the types don't compare == or have different hashCodes, then I assume it's something to do with mirrors and classloaders. The whole situation is a debacle. But it works for me (with the compiler, maybe it doesn't work in reflection.)

scala> typeOf[String]

res0: $r.intp.global.Type = String

scala> typeOf[java.lang.String]

res1: $r.intp.global.Type = String

scala> res0 =:= res1

res2: Boolean = true

scala> res0.##

res3: Int = -2122405762

scala> res1.##

res4: Int = -1083850960

scala> res0.dealias

res5: $r.intp.global.Type = String

scala> res5.##

res6: Int = -1083850960

scala> res5 =:= res1

res7: Boolean = true

[Jason Zaugg]

Works fine for me with runtime reflection.

Welcome to Scala version 2.10.1-20130302-092018-33e32179fd (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_37).

Type in expressions to have them evaluated.

Type :help for more information.

scala> import reflect.runtime.universe._

import reflect.runtime.universe._

scala> (typeOf[String].normalize.##, typeOf[java.lang.String].normalize.##)

res0: (Int, Int) = (-487473644,-487473644)

But bear in mind that this is only a shallow solution.

scala> (typeOf[Option[String]].normalize.##, typeOf[Option[java.lang.String]].normalize.##)

res13: (Int, Int) = (1261405965,810776374)

This gets closer:

scala> def deepNormalize(t: Type): Type = t.map(_.normalize) match { case `t` => t; case x => deepNormalize(x) }

deepNormalize: (t: reflect.runtime.universe.Type)reflect.runtime.universe.Type

scala> (deepNormalize(typeOf[Option[String]]).##, deepNormalize(typeOf[Option[java.lang.String]]).##)

res14: (Int, Int) = (810776374,810776374)

But even that isn't enough. 

scala> type O[A] = Option[A]; type P[A] = O[A]; trait M[_[_]]

warning: there were 1 feature warning(s); re-run with -feature for details

defined type alias O

defined type alias P

defined trait M

scala> (typeOf[M[Option]].normalize.##, typeOf[M[P]].normalize.##)

res1: (Int, Int) = (241692784,1191703537)

scala> (deepNormalize(typeOf[M[Option]]), deepNormalize(typeOf[M[P]]))

res2: (reflect.runtime.universe.Type, reflect.runtime.universe.Type) = (M[[+A]Option[A]],M[[A]scala.Option[A]])

The eta-expanded type constructors end up as PolyTypes with distinct type parameter symbols, and different hashes. If you just did a deep dealias, rather the a deep normalize, you would have the same problem with the original HK aliases.

Annotations also spoilt the party:

scala> (deepNormalize(typeOf[Option[String @unchecked]]).##, deepNormalize(typeOf[Option[String]]).##)

res0: (Int, Int) = (-809551394,810776374)

scala> deepNormalize(typeOf[Option[String @unchecked]]) =:= deepNormalize(typeOf[Option[String]])

res1: Boolean = true

(The types might even be considered non-equivalent in the presence of a compiler plugin with an AnnotationChecker (e.g. the continuations plugin)

-jason

[Paul Phillips]

On Tue, Apr 30, 2013 at 3:01 PM, Jason Zaugg <jza...@gmail.com> wrote:

But bear in mind that this is only a shallow solution.

I know people are always a threat to pull out the "oh, but  my REAL code does this..." but I could swear he had to be talking about java.lang.String and Predef.String, literally. Weren't he/you? And none of these complications apply to that to my knowledge. So I'm kind of curious what you meant.

But the above examples should help you give up on the idea of hashing all equivalent types to the same hashcode. Jason didn't even list everything you're up against. Have a google for dealiasWiden sometime.

[Jason Zaugg]

On Wed, May 1, 2013 at 1:34 AM, Paul Phillips <pa...@improving.org> wrote:

On Tue, Apr 30, 2013 at 3:01 PM, Jason Zaugg <jza...@gmail.com> wrote:

But bear in mind that this is only a shallow solution.

I know people are always a threat to pull out the "oh, but  my REAL code does this..." but I could swear he had to be talking about java.lang.String and Predef.String, literally. Weren't he/you? And none of these complications apply to that to my knowledge. So I'm kind of curious what you meant.

I just meant that this doesn't get to the originally stated goal of creating "a map with types as keys that respects type equivalence and doesn't have linear lookup cost".

I don't think widening is relevant for this particular quest, just dealiasing and eta-expansion. Forgetting about annotations for now, I think the closest thing you have would be a structural hash, along the lines of `global.typeDeconstruct.show(deepNormalize(t)).##`. But going through strings to get a hash is incredibly fragile (and slow), and I'm not recommending it.

scala> deepNormalize(typeOf[M[Option]]).collect { case PolyType(args, _) => (args zip args.map(_.id)) }

res15: List[List[($r.intp.global.Symbol, Int)]] = List(List((type A,40098)))

scala> deepNormalize(typeOf[M[P]]).collect { case PolyType(args, _) => (args zip args.map(_.id)) }

res16: List[List[($r.intp.global.Symbol, Int)]] = List(List((type A,88967)))

scala> typeDeconstruct.show(deepNormalize(typeOf[M[P]])).##

res17: Int = 1628707614

scala> typeDeconstruct.show(deepNormalize(typeOf[M[Option]])).##

res18: Int = 1628707614

-jason

[Ryan Hendrickson]

> I know people are always a threat to pull out the "oh, but my
> REAL code does this..." but I could swear he had to be talking about
> java.lang.String and Predef.String, literally. Weren't he/you? And none
> of these complications apply to that to my knowledge. So I'm kind of
> curious what you meant.

I'd be content with something that works most of the time. The difference between Predef.String and java.lang.String is something that comes up often enough to be included in 'most of the time'; higher-kinded type aliases and annotated types, at least for my particular use case, are sufficiently esoteric that I don't care if they end up with multiple entries. If normalize/deepNormalize worked as advertised, I'd walk away happy.

Unfortunately, I can't reproduce Jason's success with normalize:


Welcome to Scala version 2.10.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_30).

Type in expressions to have them evaluated.
Type :help for more information.

scala> import reflect.runtime.universe._
import reflect.runtime.universe._

scala> (typeOf[String].normalize.##, typeOf[java.lang.String].normalize.##)

res0: (Int, Int) = (-1483520547,-590014646)


Any ideas as to why?

[Paul Phillips]

On Wed, May 1, 2013 at 7:59 AM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

Any ideas as to why?

Classloaders, somehow. I get the same ## result with "scala" but different results with "scala -nobootcp".

% scala210_1 -nobootcp

Welcome to Scala version 2.10.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_45).

Type in expressions to have them evaluated.

Type :help for more information.

scala> import reflect.runtime.universe._

import reflect.runtime.universe._

scala>  (typeOf[String].normalize.##, typeOf[java.lang.String].normalize.##)

res0: (Int, Int) = (1712057924,559543568)