I just recalled another plus for Scala over C++. Scala has a neat module system. C++ still lacks that.
Parametricity? Parametricity by what? Do you mean type parametricity? If so, then, I’m afraid, no… That’s not the definition. Type parametricity is making the type a parameter of the code.
I’m not sure how C++'s type system is “safer” when your templates can do completely not what you mean as long as the method names match up as used, and you can specify nonsense like myThing<double, Vector<int>> where the former is supposed to be the argument to the latter. (Note: you might say: okay, write myThing such that you call it as myThing<double, Vector>, but that doesn’t work if you want to allow non-parameterized classes as the “container”.)
Since templates are code generation, the type system catches any type errors in the generated code, but it has very little safety in what you can ask for. In Scala you can’t even ask without an error.
Also, when you have a huge number of types in play, the code generation method creates enormous binaries; generics keep the binaries small by handling the abstraction earlier. This is something I think Rust does really well: it will specialize if you parameterize over a trait, but it will compile a generic interface if you just use the trait bare. So you effectively have both type erasure or not, controlled by the declaration site. In Scala, erasure is pervasive and you have to use type witnesses to effectively smuggle the compile-time information in.
I’m not sure why you think the Scala type system is unsafe, though. If you’re casting stuff with asInstanceOf, then you should be thinking of that as equivalent to (MyWhatever*) casting in C++, or at least dynamic_cast. If you avoid that, you’re on pretty solid ground.
The two systems are each quite elaborate and quite capable, and they are both quite different from each other.
@Hossein:
What do you precisely miss because of type erasure? If you want to instantiate an object of generic type then you can always pass some factory function. Eg:
def generateAndDoSomethingWithObjects[T](size: Int, factory: (Int, String) => T, transformer: T => U): Array[U] = {
val input = Array.fill(size)(factory(5, "eh"))
input.map(transformer)
}
For me type erasure is a rather good thing. It prevents some unwanted developments like:
- deep reflection - after type erasure reflection is less useful so there’s less incentive to use it
- heavy methods overloading - for me overloading often makes code less readable and is a problem for IDE that infers wrong overload and points me to wrong method
- imperative style object building - C# supports only parameterless constructors for generic parameters so you then need to invoke some setters, init method and/ or other abominations
Project Valhalla partially undoes type erasure - for value types only. It does that not to enable deep reflection or something like that but for performance reasons. In current Java versions you can only parametrize a generic function with a reference type, so layout always stays the same - every reference has the same size. With Project Valhalla you will be able to parametrize a generic method with value type and value types have different sizes and command different memory layouts - that’s why they need special support.
@Ichoran:
How my comment about GC is wrong? You have discussed a completely different thing than me. I’ve stated that doing multithreaded functional programming in Rust isn’t going to be efficient and you claimed that with Rust you don’t need to do functional programming.
Anyway, you have to put some serious effort to design a memory ownership rules in your application if you choose Rust. With JVM based languages you can skip that and that lowers the cost of developing software - something that corporations really want.
I think it would be hard to compare the performance of tracing garbage collection and reference counting in a multithreaded world. Tracing garbage collection allows a very efficient sharing of immutable data between threads. Reference counting needs ubiquitous and expensive atomic operations for that, so you would avoid that. Therefore you would design a multithreaded system very differently in Scala and Rust.
Tracing GC performance is not bad. In memory allocation benchmark here: https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/binarytrees.html C# and Java scored 8.26s and 8.39s where fastest C version using plain alloc + free took 19.05s, i.e. was over twice slower. Memory pooling and freeing whole memory pools at once changes the comparison dramatically, but how often you have a problem where you can free memory in such large batches? In usual situations memory pooling would lead to a lot of memory space overhead, I think.
The main disadvantage of tracing GC is memory space overhead. It wouldn’t make sense to run GC cycles constantly so tracing GC waits for the garbage to accumulate and then releases it in big amounts. OTOH tracing GC algorithms improve. There are following GCs in development: http://openjdk.java.net/projects/shenandoah/ and http://openjdk.java.net/projects/zgc/ . They both aim for super low GC pauses.
@Ichoran, can you please elaborate more on:
If you want to program in a pure functional style, Scala is also the best, due to the advanced type system.
Please note that this is not a thread on pluses for C++ over Scala. So, I’ll not dive into that. This post tries to correct the pluses I find unjustified to be given to Scala over C++.
Now, type safety is about preventing type mistakes as early as possible. Programmers often champion that by instructing the compiler on type calculation.
In C++ where there truly is a categorical distinction between compile-time and runtime, that “as early as possible” tends to mean at compile-time. It’s under the same understanding that type calculation is exclusive there to compile-time.
In Scala where there is no such distinction, there is no clear point in time to flag as a reference for the “as early as possible”. Early type calculation is instructed using implicits. It turns out, however, that implicits are just like every other object in that the Scala language specification gives no guarantee for the not late-binding of. And, late-binding is a runtime act – opening the door for type-unsafety… (Sorry if that’s too technical. This is a language semantics matter.)
Plain wrong. Please do not bring up trivia in a technical chat. That usage of the term “parametricity” is technically inaccurate.
I have many threads on the Scala list where I cry out for being beaten-up by that.
Always? Common Scala wrong impression. Sometimes the DSL syntax you’re trying to embed does not accommodate that. See my posts on embedding my $\lambda$-calculi in Scala.
Concept-based overloading makes code more readable and helps type inference. With erasure, you have to resort to implicits, which again the EDSL syntax might not be able to accommodate.
I really don’t understand the hostility in your interactions. Please don’t limit what people may or may not bring up, and don’t dismiss contributions as trivial.
Parametricity is used this way in the pretty highly cited (http://citeseer.ist.psu.edu/showciting?doi=10.1.1.38.9875) Therorems for Free, at first in
This theorem about functions of type ∀X. X* => X* is pleasant but not earth-shaking. What is more exciting
is that a similar theorem can be derived for every type. The result that allows theorems to be derived from
types will be referred to as the parametricity result, because it depends in an essential way on parametric polymorphism (types of the form ∀X. T ). Parametricity is just a reformulation of Reynolds’ abstraction theorem: terms evaluated in related environments yield related values [Rey83]. The key idea is that types may be read as relations. This result will be explained in Section 2 and stated more formally in Section 6.
This use of the term has been taken over quite broadly, (just as an example http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.11.1298&rep=rep1&type=pdf)
It seems everything you don’t agree with gets dismissed as very bad, plain wrong, trivia, or technically inaccurate.
4 Likes
I seem to need to apologise for misrepresenting myself. Certainly didn’t mean to be hostile.
Phil Wadler’s theorems for free is a groundbreaking work that was published around three decades ago. Nowadays, I may personally even reject a paper if it’s written under the impression that parametricity is only type polymorphism.
So then we can get back why erasure is a mixed blessing.
The second paper I cited gives a really nice succinct first sentence:
A polymorphic function is parametric if its behavior does not depend on the type at which it is instantiated.
Erasure ensures this. That’s a great boon if you would like all your polymorphic functions to be parametric.
On the other hand, if you would like non-parametric polymorphic functions, it’s a problem that requires hoop jumping and workarounds.
Choosing which one you prefer to facilitate is a language level choice with semantic consequences: One that is good or bad for some particular use, but the reverse for others, not one that is good or bad in general for all purposes.
Why would you want that?
Because it provides you with theorems for free - that is, allows you to know more (sometimes everything there is to know) about a function just from knowing its type.
My question was about practical reasons why you may choose to design your real-world language that way. So, for example, were Java and other JVM languages developed with that in mind? I strongly doubt that for those JVM languages which ever made it outside theory labs. In fact, I recall Phil Wadler himself explaining how, when they wanted to add type polymorphism to Java (later known as Java Generics), they hacked the type system by employing erasure.
And, theorems for free is a brilliant piece of theory work worth a lot of respect.
Type erasure in JVM has some serious benefits for Scala - Scala isn’t limited by JVM generics implementation because it (to wide extent) doesn’t exist after compilation. In paper Generics of a Higher Kind there is following quote:
Since Scala uses type erasure in the back-end, the extent of the changes is limited to the type checker. Clearly, our extension thus does not have any impact on the run-time characteristics of a program. Ironically, as type erasure is at the root of other limitations in Scala, it was an important benefit in implementing type constructor polymorphism.
Similar extensions in languages that target the .NET platform face a tougher challenge, as the virtual machine has a richer notion of types and thus enforces stricter invariants. Unfortunately, the model of types does not include higher-kinded types. Thus, to ensure full interoperability with genericity in other languages on this platform, compilers for languages with type constructor polymorphism must resort to partial erasure, as well as code specialisation in order to construct the necessary representations of types that result from abstract type constructors being applied to arguments.
I prefer richer compile-time type system to richer runtime reflection. IMO runtime reflection is a can of worms, so I’m actually happy that in Scala it’s rarely used.
Haskell also has type erasure, just like Java. If you want to code like in Haskell, then you need to use implicit type classes. They allow for much richer overloading capabilities than direct method overloading.
1 Like
When I started with Scala the .NET backend was already dying, so I wasn’t following it much. But from what I’ve read I have an impression that Scala.NET was never strongly integrated with .NET reified generics. Erasure was too broad to make interoperation with C# as efficient as with Java.
OTOH we have Scala.JVM and Scala.js. Both are going strong. Scala.JVM can use Java libraries and can export functions to use in Java code (look for example at Java API in Akka - it’s written in Scala, but consumable by more or less idiomatic Java code). Similarly, Scala.js can use libraries written in JavaScript (typically you first write a facade using annotations and/ or js.Dynamic type) and it can export functions usable from JavaScript code.
Type erasure probably also helps in case of Scala Native, because in native code you typically don’t do any reflection so you don’t need to e.g. store element class in an empty list of references.
Essentially .NET is the only platform that has reified generics. All other platform don’t have it, so by having erased generics it’s easier to integrate Scala with those other platforms. But as I’ve written before, reified generics in .NET make it hard to integrate with Scala even though there was a separate backend that tried to leverage reified generics.
For Scala.fully-reified you would probably have to either design a completely new VM (incompatible with everything else) or perhaps leverage GraalVM/ Truffle: https://github.com/oracle/graal/tree/master/truffle and have some sort of interoperation with other languages implemented on top of GraalVM/ Truffle.
I wasn’t questioning the possibility of cross-compiling Scala.
In what way is it erasure that has made all that possible? Do I understand it correctly that, in effect, the cross-compilation builds on bidirectional translations between JVM types and JavaScript ones? And, if so, what is the added value of erasure?
Type erasure or type reification doesn’t change anything if you decide not to use generics at all. That’s why neither erasure nor reification is required for cooperation - you can target non-generic classes like C# collections before C# 2.0.
The benefit of erasure it that you can quickly cast between erased generic class and non-parametrized class, like in Java. In C# you cannot do that - generic and non-generic collections are incompatible and you need to rebuild them if you want to convert from one to another.
Neither Java, nor JavaScript or C++ will provide you with reified generics. Therefore for interoperation with them you would need to convert between generic and non-generic classes in environment with reified generics. That would be costly.
Also if you want to interoperate with language with weaker type system, like in case of Scala interoperating with C# then you can’t expect C# to abide all your stronger type constraints (otherwise it wouldn’t be weaker, type system wise). So you’re left with partial erasure anyway.
PS:
Also rebuilding original reified classes from erased ones is in general impossible. If you erase List.empty[Int], then you’re left with List.empty[AnyRef] and you can’t restore information that is lost forever. What you can restore is the information the compiler has at compile time, but then reification doesn’t bring much benefit.