11 ms·

Type erasure and reification

92 points by matt_d 8y ago

bunderbunder 8y ago
Nice, clear summary. I'd like to throw some more thoughts out there, though. Focusing overmuch on what Java did leaves the picture somewhat incomplete. First off, I've seen some people suggest that type erasure is a problem because it leads to a loss of type safety. This isn't really true. Haskell, for example, also preserves no run-time type information. The difference there is really about strength of typing - Haskell is very strongly typed, whereas C is weakly typed, and Java falls somewhere in the middle. Second, the Java convention of passing Class variables into generic methods in order to give them all the type information they need: <T> T getT(Class[t] clazz) { ... } looks a bit like the C/C++ type erasure pattern that the author mentioned in passing at the start of the article, if you squint at it. My own sense is that the reason why type erasure was a problematic choice in Java is that it places Java in this uncomfortable middle ground where you have neither the robust compile-time type checking of a strong statically typed language like Haskell, nor the robust run-time reflection of a modern dynamic language. The end result, being robust at nothing, did not turn out to be the best of both worlds.
- hota_mazi 8y ago
  > First off, I've seen some people suggest that type erasure is a problem because it leads to a loss of type safety. This isn't really true. I'd argue it's the opposite. Giving your programs the ability to access reified types at runtime weaken the robustness of your code, because you can second guess the compiler and introduce crashing code, such as incorrect type casts. Reification also comes at a cost: performance, more problematic interoperability (Scala could notoriously not be ported to .net because it was not possible to make its type system work properly on a reified platform). Contrary to popular belief, Java's choice of erasure was not dictated by backward compatibility concerns but because erasure is a sound approach for type system representation.
  - seanmcdirmid 8y ago
    Scala could be ported .net easily enough, but it couldn’t interop with reified generic APIs. MS actually doesn’t use generics as aggressively as it could in its API for similar reasons (eg there are two APIs for collections that use genetics and don’t).
    - bunderbunder 8y ago
      My understanding is that the problem was, more specifically, that they couldn't easily get Scala's types mated to .NET, and that was in turn an implication of the decision to use IKVM to run the Java binaries for Scala's standard libraries on the CLR. Which I could see being a problem, because then you need to figure out how to smoothly marshal data back and forth between (type erased) Scala collections and .NET functions, which typically expect reified types these days. If they had gone with producing a .NET native version of Scala's standard libraries, they might have had easier success. But it also would have been a Pyrrhic victory, because you'd have lost the ability to run any existing Scala code, which would have scads of dependencies on other bits of the JDK as well, on Scala for .NET. At which point, what's the point? I expect that porting F# to the JVM would encounter similar problems. And I expect that which platform you want to blame them on depends on which one is your home platform. IMO the real story here is that the two big managed platforms are effectively walled gardens, by virtue of having VMs that implement such very high-level bytecode. Both of them effectively demand that all languages running on them can interact with, in effect, a thoroughly object-oriented ABI. There being approximately as may flavors of OOP as there are OO languages, that creates a situation where, if your language isn't set up to play nice with that platform's particular brand of OOP, you're going to have a bad time.
      - dtech 8y ago
        > But it also would have been a Pyrrhic victory, because you'd have lost the ability to run any existing Scala code, which would have scads of dependencies on other bits of the JDK as well, on Scala for .NET. At which point, what's the point? Ask the parade of JVM languages porting themselves to native and JS runtimes.
- skybrian 8y ago
  Haskell implementations typically pass around dictionaries at runtime when you use type classes. Since there is one per instance, this could be thought of as a form of type reification. https://www.schoolofhaskell.com/user/jfischoff/instances-and-dictionaries https://www.schoolofhaskell.com/user/jfischoff/instances-and...
  - 0db532a0 8y ago
    I don't agree that this is type reification. The dictionaries are resolved at compile time. They may indeed be passed to a function at run-time, but they are not exposed to the user. They are simply a compile-time substitution of abstract function invocations with the implementations according to the chosen type. For actual reification of types in Haskell, you can look at Haskell's Data.Typeable library.
    - skybrian 8y ago
      Well, it's an internal data structure needed at runtime that corresponds to a type, which seems close enough for a rough analogy. But I agree that it's not a language feature.
    - int_19h 8y ago
      It depends on whether you're looking at it from the implementation perspective, or from language user perspective. To the implementation, a dictionary carrying type information (or anything derived from that, such as e.g. method dispatch tables) at runtime is type reification.
      - 0db532a0 8y ago
        The concept of reification exists only in the context of a chosen language and its universe of objects, and it doesn't extend to the language's implementation. Given the language Haskell and its universe of objects, Data.Typeable provides a reification of Haskell's types into physical objects inside that universe. The type class dictionaries are not physical objects inside this universe.
    - 8y ago
- pron 8y ago
  Regardless of questions of what should or shouldn't be done, there is a serious issue with reifying generic types with type parameters that support subtyping, as the JVM does. It requires deciding on a variance policy (to determine the subtyping relationships among the generic types), and different languages choose different variance policies to fit with their overall design. Reifying generic types in this case would bake a single variance policy into the runtime, which would hinder the ability of different languages to share data structures. If the type parameters do not support subtyping, this is not a problem, and, indeed, when generic types will be instantiated with parameters of Java's upcoming value types (that cannot be subtyped), they will likely be reified and specialized.
  - int_19h 8y ago
    > It requires deciding on a variance policy (to determine the subtyping relationships among the generic types) Why does it? In C#, for example, variance policy for generic type parameters is expressed explicitly - invariant by default, covariant or contravariant if you ask for it. While C# also has reified generics, I don't see why this couldn't be done with non-reified ones.
    - sreque 8y ago
      C#'s reified generics are actually a problem for other languages that want to run on the CLR, and in fact those languages generally have data structures with no reified generics (the data structures just store type Object and do perform dynamic casting). In order to work with the CLR bytecode generated outside of their compilers, these languages unfortunately also have to provide providence for understanding generic data structures. The JVM has been more successful than the CLR at hosting other languages, and having unreified generics I believe has contributed to that success. For instance, I have seen both the creator of Scala and one of the JRuby contributors both say they prefer JVM generics to CLR generics.
      - int_19h 8y ago
        I still don't see what that has to do with variance policy specifically. You're basically saying that reified generics are bad, because they require all languages on a given runtime to be aware of them to interoperate. Which is a valid point, but if you are aware of generics, then CLR lets you express whatever variance you want - including none. And so long as your language has CLR interface casts at all, you automatically get support for that variance at runtime, even if the type system of the language doesn't reflect such relations statically; so e.g. you might not be able to implicitly convert IEnumerable<Derived> to IEnumerable<Base>, but you should always be able to explicitly cast IEnumerable<Derived> -> Object -> IEnumerable<Base>.
alexhutcheson 8y ago
Does anyone know of a good blog post or article that explains why Java's type erasure approach to generics is considered problematic? I'd be interested to read about the specific problems it causes.
- bunderbunder 8y ago
  It's a bunch of small things, none of which are showstopping, all of which are annoying. You can't have these two functions co-existing in the same class: void Frob(List<String> someList) { ... } void Frob(List<Integer> someList) { ... } because, after erasure, they have identical signatures. You've got to repeat yourself a bunch, because generic methods don't know their own type parameters. So, to take an example using the Jackson JSON-handling library: MyClass foo = objectMapper.readValue(json, MyClass.class); is a bit annoying if you're coming from a language like C#, where you'd expect to be able to write code more like: MyClass foo = objectMapper.readValue(json); Generic type instantiations aren't really types in Java, they're more this sort of type-ish concept. List<String> and List<Integer> exist as distinctions made by Java's type checker, but their actual class is just List - there's no such thing as List<String>.class. That's what's going on with that method overload example above. It's also the reason that this won't even compile, and you've got to resort to hacky workarounds in this sort of situation: Node<MyClass> foo = objectMapper.readValue(json, Node<MyClass>.class); Then there's all the stuff about boxing, and how you can't have generic collections of atomic values, only boxed values. Which is responsible for a lot of excess memory consumption and pointer chasing, and also for things like that whole extra side quest in Java 8 streams where you get classes like IntStream and DoubleStream (but not FloatStream).
  - Matthias247 8y ago
    Besides those you also can't do something like Object xyz = ...; if (xyz instanceof List<String>) { doA(); } else if (xyz instanceof List<Integer> { doB(); } because there is only a single List type at runtime.
    - bunderbunder 8y ago
cryptonector 8y ago
The word 'reification' is a beautiful one that means to make something hidden visible or accessible, or to give concrete form to an abstract thing. The first time I happened on that word was when reading about Scheme continuations. The simplest way to describe continuations is: reification of return addresses. In a language like C every function call has a hidden argument: a return closure that consists of a text address and a value to restore the frame pointer to upon return. Reifying the return address closure requires giving it a name, and that name is simply "continuation" -- it refer to what follows when this function returns by... calling its continuation. Because returns (now: calls to continuation functions) are always done in the tail position by definition, the caller's stack frame can be reused. This is a key point. There's only one other mystery needed to fully explain Scheme continuations. Namely, that function frames have to be allocated on the heap in order to get full Scheme semantics. Add delineated continuations and you can have function frame stacks again at the price of a bit more ceremony so that the run-time can know when to call a function on a new stack.
- _old_dude_ 8y ago
  The name reification comes from the latin res, thing, so it's the processus that transform something into a thing. For a language runtime, it's the way to transform a language artifact to a runtime object. By example, in Java, apart the reification of the type argument, the transformation of a lambda to a proxy that implement the functional interface is also a reification.
  - talaketu 8y ago
    Thanks for the latin! I'd only heard reification in the context of data modelling, where it's often meant to model the meta-model. For example, RDF reification. RFD involves statements in the triple form (subject, predicate, object). The triple (Mary, enrolled, UCSF) corresponds to the statement that "Mary is enrolled at UCSF". A reification might be to turn that statement into a subject, and to make a statement about the statement. Eg. ((Mary, enrolled, USCF), created, 2018-12-06) - the statement that Mary is enrolled at USCF was created on 2018-12-06.
- 8y ago
chenglou 8y ago
There’s actually another category: type reification WITH type erasure! https://github.com/mrakgr/The-Spiral-Language/blob/master/readme.md https://github.com/mrakgr/The-Spiral-Language/blob/master/re... (search for default_of) Well, kinda cheating since the language’s about inlining these away. But technically true...
bokchoi 8y ago
Here is an interesting blog post by Gilad Bracha on reified generics: https://gbracha.blogspot.com/2018/10/reified-generics-search-for-cure.html https://gbracha.blogspot.com/2018/10/reified-generics-search...
emmanueloga_ 8y ago
META I really like this guy's articles. If you look in the archives [1], he's been writing prolifically for at least 15 years. Let's zoom on 2018: [2] * 3 summaries of reading for at least 40 books read in a number of miscellaneous subjects (some of them re-reads) * Articles on type theory * Some articles centered around specific programming languages like python, Haskell, and Go * Articles on concurrency * And much more! :-) I think he has "seasons" of learning particular languages. I think I've read some of his articles on Clojure, but he stopped writing about it eventually. According to StackOverflow [3], he appears to be an expert in Python. In his Github account [4], I see a bunch of repos including one for code on his blog, but I don't think there's any particular repo he focuses on (maybe pycparser?). Apart from making me feel inadequate about my own year accomplishments (how many books have I read this year?), I'm curious what one would do after such sizable knowledge ingestion. I'm surprised this guy doesn't attempt to come up with his own programming language. Maybe he knows is not worth it? Maybe he knows that is better to know the nooks and crannies of existing languages than trying to come up with a new one? Maybe he just reads books instead of going dancing, watching a movie, socializing in a bar, listening music, browsing the web, playing the piano, or what not. Maybe he does all this things and still has time for reading and learning and writing his blog. Sometimes I wish/hope/expect that everything I've learnt will sometime in the future allow me to create something, anything, where I can mix and match pieces of everything I've taken in. For sure this guy already benefits from all his knowledge on his day job, his side projects and maybe on his everyday life and interactions. I don't know, but I'm curious. I mostly punish myself, all the time, for not being more productive, all the time. 1: https://eli.thegreenplace.net/archives/all https://eli.thegreenplace.net/archives/all 2: https://eli.thegreenplace.net/archives/2018 https://eli.thegreenplace.net/archives/2018 3: https://stackoverflow.com/users/8206/eli-bendersky?tab=profile https://stackoverflow.com/users/8206/eli-bendersky?tab=profi... 4: https://github.com/eliben?utf8=%E2%9C%93&tab=repositories&q=&type=source&language= https://github.com/eliben?utf8=%E2%9C%93&tab=repositories&q=...

92 points by matt_d 8y ago

Nice, clear summary. I'd like to throw some more thoughts out there, though. Focusing overmuch on what Java did leaves the picture somewhat incomplete. First off, I've seen some people suggest that type erasure is a problem because it leads to a loss of type safety. This isn't really true. Haskell, for example, also preserves no run-time type information. The difference there is really about strength of typing - Haskell is very strongly typed, whereas C is weakly typed, and Java falls somewhere in the middle. Second, the Java convention of passing Class variables into generic methods in order to give them all the type information they need: <T> T getT(Class[t] clazz) { ... } looks a bit like the C/C++ type erasure pattern that the author mentioned in passing at the start of the article, if you squint at it. My own sense is that the reason why type erasure was a problematic choice in Java is that it places Java in this uncomfortable middle ground where you have neither the robust compile-time type checking of a strong statically typed language like Haskell, nor the robust run-time reflection of a modern dynamic language. The end result, being robust at nothing, did not turn out to be the best of both worlds.

hota_mazi 8y ago
> First off, I've seen some people suggest that type erasure is a problem because it leads to a loss of type safety. This isn't really true. I'd argue it's the opposite. Giving your programs the ability to access reified types at runtime weaken the robustness of your code, because you can second guess the compiler and introduce crashing code, such as incorrect type casts. Reification also comes at a cost: performance, more problematic interoperability (Scala could notoriously not be ported to .net because it was not possible to make its type system work properly on a reified platform). Contrary to popular belief, Java's choice of erasure was not dictated by backward compatibility concerns but because erasure is a sound approach for type system representation.
- seanmcdirmid 8y ago
  Scala could be ported .net easily enough, but it couldn’t interop with reified generic APIs. MS actually doesn’t use generics as aggressively as it could in its API for similar reasons (eg there are two APIs for collections that use genetics and don’t).
  - bunderbunder 8y ago
    My understanding is that the problem was, more specifically, that they couldn't easily get Scala's types mated to .NET, and that was in turn an implication of the decision to use IKVM to run the Java binaries for Scala's standard libraries on the CLR. Which I could see being a problem, because then you need to figure out how to smoothly marshal data back and forth between (type erased) Scala collections and .NET functions, which typically expect reified types these days. If they had gone with producing a .NET native version of Scala's standard libraries, they might have had easier success. But it also would have been a Pyrrhic victory, because you'd have lost the ability to run any existing Scala code, which would have scads of dependencies on other bits of the JDK as well, on Scala for .NET. At which point, what's the point? I expect that porting F# to the JVM would encounter similar problems. And I expect that which platform you want to blame them on depends on which one is your home platform. IMO the real story here is that the two big managed platforms are effectively walled gardens, by virtue of having VMs that implement such very high-level bytecode. Both of them effectively demand that all languages running on them can interact with, in effect, a thoroughly object-oriented ABI. There being approximately as may flavors of OOP as there are OO languages, that creates a situation where, if your language isn't set up to play nice with that platform's particular brand of OOP, you're going to have a bad time.
    - dtech 8y ago
      > But it also would have been a Pyrrhic victory, because you'd have lost the ability to run any existing Scala code, which would have scads of dependencies on other bits of the JDK as well, on Scala for .NET. At which point, what's the point? Ask the parade of JVM languages porting themselves to native and JS runtimes.
skybrian 8y ago
Haskell implementations typically pass around dictionaries at runtime when you use type classes. Since there is one per instance, this could be thought of as a form of type reification. https://www.schoolofhaskell.com/user/jfischoff/instances-and-dictionaries https://www.schoolofhaskell.com/user/jfischoff/instances-and...
- 0db532a0 8y ago
  I don't agree that this is type reification. The dictionaries are resolved at compile time. They may indeed be passed to a function at run-time, but they are not exposed to the user. They are simply a compile-time substitution of abstract function invocations with the implementations according to the chosen type. For actual reification of types in Haskell, you can look at Haskell's Data.Typeable library.
  - skybrian 8y ago
    Well, it's an internal data structure needed at runtime that corresponds to a type, which seems close enough for a rough analogy. But I agree that it's not a language feature.
  - int_19h 8y ago
    It depends on whether you're looking at it from the implementation perspective, or from language user perspective. To the implementation, a dictionary carrying type information (or anything derived from that, such as e.g. method dispatch tables) at runtime is type reification.
    - 0db532a0 8y ago
      The concept of reification exists only in the context of a chosen language and its universe of objects, and it doesn't extend to the language's implementation. Given the language Haskell and its universe of objects, Data.Typeable provides a reification of Haskell's types into physical objects inside that universe. The type class dictionaries are not physical objects inside this universe.
  - 8y ago
pron 8y ago
Regardless of questions of what should or shouldn't be done, there is a serious issue with reifying generic types with type parameters that support subtyping, as the JVM does. It requires deciding on a variance policy (to determine the subtyping relationships among the generic types), and different languages choose different variance policies to fit with their overall design. Reifying generic types in this case would bake a single variance policy into the runtime, which would hinder the ability of different languages to share data structures. If the type parameters do not support subtyping, this is not a problem, and, indeed, when generic types will be instantiated with parameters of Java's upcoming value types (that cannot be subtyped), they will likely be reified and specialized.
- int_19h 8y ago
  > It requires deciding on a variance policy (to determine the subtyping relationships among the generic types) Why does it? In C#, for example, variance policy for generic type parameters is expressed explicitly - invariant by default, covariant or contravariant if you ask for it. While C# also has reified generics, I don't see why this couldn't be done with non-reified ones.
  - sreque 8y ago
    C#'s reified generics are actually a problem for other languages that want to run on the CLR, and in fact those languages generally have data structures with no reified generics (the data structures just store type Object and do perform dynamic casting). In order to work with the CLR bytecode generated outside of their compilers, these languages unfortunately also have to provide providence for understanding generic data structures. The JVM has been more successful than the CLR at hosting other languages, and having unreified generics I believe has contributed to that success. For instance, I have seen both the creator of Scala and one of the JRuby contributors both say they prefer JVM generics to CLR generics.
    - int_19h 8y ago
      I still don't see what that has to do with variance policy specifically. You're basically saying that reified generics are bad, because they require all languages on a given runtime to be aware of them to interoperate. Which is a valid point, but if you are aware of generics, then CLR lets you express whatever variance you want - including none. And so long as your language has CLR interface casts at all, you automatically get support for that variance at runtime, even if the type system of the language doesn't reflect such relations statically; so e.g. you might not be able to implicitly convert IEnumerable<Derived> to IEnumerable<Base>, but you should always be able to explicitly cast IEnumerable<Derived> -> Object -> IEnumerable<Base>.

alexhutcheson 8y ago

Does anyone know of a good blog post or article that explains why Java's type erasure approach to generics is considered problematic? I'd be interested to read about the specific problems it causes.

bunderbunder 8y ago
It's a bunch of small things, none of which are showstopping, all of which are annoying. You can't have these two functions co-existing in the same class: void Frob(List<String> someList) { ... } void Frob(List<Integer> someList) { ... } because, after erasure, they have identical signatures. You've got to repeat yourself a bunch, because generic methods don't know their own type parameters. So, to take an example using the Jackson JSON-handling library: MyClass foo = objectMapper.readValue(json, MyClass.class); is a bit annoying if you're coming from a language like C#, where you'd expect to be able to write code more like: MyClass foo = objectMapper.readValue(json); Generic type instantiations aren't really types in Java, they're more this sort of type-ish concept. List<String> and List<Integer> exist as distinctions made by Java's type checker, but their actual class is just List - there's no such thing as List<String>.class. That's what's going on with that method overload example above. It's also the reason that this won't even compile, and you've got to resort to hacky workarounds in this sort of situation: Node<MyClass> foo = objectMapper.readValue(json, Node<MyClass>.class); Then there's all the stuff about boxing, and how you can't have generic collections of atomic values, only boxed values. Which is responsible for a lot of excess memory consumption and pointer chasing, and also for things like that whole extra side quest in Java 8 streams where you get classes like IntStream and DoubleStream (but not FloatStream).
- Matthias247 8y ago
  Besides those you also can't do something like Object xyz = ...; if (xyz instanceof List<String>) { doA(); } else if (xyz instanceof List<Integer> { doB(); } because there is only a single List type at runtime.
  - bunderbunder 8y ago

cryptonector 8y ago

The word 'reification' is a beautiful one that means to make something hidden visible or accessible, or to give concrete form to an abstract thing. The first time I happened on that word was when reading about Scheme continuations. The simplest way to describe continuations is: reification of return addresses. In a language like C every function call has a hidden argument: a return closure that consists of a text address and a value to restore the frame pointer to upon return. Reifying the return address closure requires giving it a name, and that name is simply "continuation" -- it refer to what follows when this function returns by... calling its continuation. Because returns (now: calls to continuation functions) are always done in the tail position by definition, the caller's stack frame can be reused. This is a key point. There's only one other mystery needed to fully explain Scheme continuations. Namely, that function frames have to be allocated on the heap in order to get full Scheme semantics. Add delineated continuations and you can have function frame stacks again at the price of a bit more ceremony so that the run-time can know when to call a function on a new stack.

_old_dude_ 8y ago
The name reification comes from the latin res, thing, so it's the processus that transform something into a thing. For a language runtime, it's the way to transform a language artifact to a runtime object. By example, in Java, apart the reification of the type argument, the transformation of a lambda to a proxy that implement the functional interface is also a reification.
- talaketu 8y ago
  Thanks for the latin! I'd only heard reification in the context of data modelling, where it's often meant to model the meta-model. For example, RDF reification. RFD involves statements in the triple form (subject, predicate, object). The triple (Mary, enrolled, UCSF) corresponds to the statement that "Mary is enrolled at UCSF". A reification might be to turn that statement into a subject, and to make a statement about the statement. Eg. ((Mary, enrolled, USCF), created, 2018-12-06) - the statement that Mary is enrolled at USCF was created on 2018-12-06.
8y ago

chenglou 8y ago

There’s actually another category: type reification WITH type erasure! https://github.com/mrakgr/The-Spiral-Language/blob/master/readme.md https://github.com/mrakgr/The-Spiral-Language/blob/master/re... (search for default_of) Well, kinda cheating since the language’s about inlining these away. But technically true...

bokchoi 8y ago

Here is an interesting blog post by Gilad Bracha on reified generics: https://gbracha.blogspot.com/2018/10/reified-generics-search-for-cure.html https://gbracha.blogspot.com/2018/10/reified-generics-search...

emmanueloga_ 8y ago

META I really like this guy's articles. If you look in the archives [1], he's been writing prolifically for at least 15 years. Let's zoom on 2018: [2] * 3 summaries of reading for at least 40 books read in a number of miscellaneous subjects (some of them re-reads) * Articles on type theory * Some articles centered around specific programming languages like python, Haskell, and Go * Articles on concurrency * And much more! :-) I think he has "seasons" of learning particular languages. I think I've read some of his articles on Clojure, but he stopped writing about it eventually. According to StackOverflow [3], he appears to be an expert in Python. In his Github account [4], I see a bunch of repos including one for code on his blog, but I don't think there's any particular repo he focuses on (maybe pycparser?). Apart from making me feel inadequate about my own year accomplishments (how many books have I read this year?), I'm curious what one would do after such sizable knowledge ingestion. I'm surprised this guy doesn't attempt to come up with his own programming language. Maybe he knows is not worth it? Maybe he knows that is better to know the nooks and crannies of existing languages than trying to come up with a new one? Maybe he just reads books instead of going dancing, watching a movie, socializing in a bar, listening music, browsing the web, playing the piano, or what not. Maybe he does all this things and still has time for reading and learning and writing his blog. Sometimes I wish/hope/expect that everything I've learnt will sometime in the future allow me to create something, anything, where I can mix and match pieces of everything I've taken in. For sure this guy already benefits from all his knowledge on his day job, his side projects and maybe on his everyday life and interactions. I don't know, but I'm curious. I mostly punish myself, all the time, for not being more productive, all the time. 1: https://eli.thegreenplace.net/archives/all https://eli.thegreenplace.net/archives/all 2: https://eli.thegreenplace.net/archives/2018 https://eli.thegreenplace.net/archives/2018 3: https://stackoverflow.com/users/8206/eli-bendersky?tab=profile https://stackoverflow.com/users/8206/eli-bendersky?tab=profi... 4: https://github.com/eliben?utf8=%E2%9C%93&tab=repositories&q=&type=source&language= https://github.com/eliben?utf8=%E2%9C%93&tab=repositories&q=...