In the previous
Scala types (4)
directory
- 21. Structure type
- 22. Path dependency type
- 23. Type projection
- 24. Specialized Types
- 25. Type Lambda
21. Structure type
Strucural Types are often described as “duck typing” and this is a good comparison if you want to get an intuitive understanding.
So far, all we’ve been thinking about on the type side is, “Does it implement interface X?” With “structure types,” we can go a step further and start reasoning about the structure (hence the name) of a given object. When we examine a type matching problem with a structural type, we need to change the question to: “Is there a method with this signature?” .
Let’s take a very common example to see why it’s so powerful. Imagine that you have a lot of closed support. In Java, the java.io.Closeable interface is usually implemented to write common Closeable utility classes (in fact, Google Guava has one). Now imagine someone implementing a MyOwnCloseable class, but not java.io.Closeable. Because of static typing, your Closeables library has a problem and you can’t pass instances of MyOwnCloseable to it. Let’s use structure types to solve this problem:
type JavaCloseable = java.io.Closeable
// reminder, it's body is: { def close(): Unit }
class MyOwnCloseable {
def close() :Unit= ()}// method taking a Structural Type
def closeQuietly(closeable: { def close() :Unit }) =
try {
closeable.close()
} catch {
case ex: Exception= >// ignore...
}
// accepts a java.io.File (implements Closeable):
closeQuietly(new StringReader("example"))
// accepts a MyOwnCloseable
closeQuietly(new MyOwnCloseable)Copy the codeThis structure type is taken as an argument to the method. Basically, the only thing we can expect from this type is that it should have an inner (close) method. It can have more methods, so it’s not a perfect match, but the type must define the smallest set of methods in order to be effective.
It is also important to note that using structure types has a significant negative impact on runtime performance, since it is actually implemented through reflection. Instead of investigating bytecodes here, remember that viewing bytecodes generated by Scala (or Java) classes is an easy thing to do with: Javap in the Scala REPL, so you should try it out for yourself.
Before we move on to the next topic, one more refined usage style. Imagine that your structure type is pretty rich, like a type that represents something that you can open, use, and then have to close. By using “type aliases” (described in detail in another section) and “structural types,” we can separate type definitions from methods as follows:
type OpenerCloser = {
def open() :Unit
def close() :Unit
}
def on(it: OpenerCloser)(fun: OpenerCloser= >Unit) = {
it.open()
fun(it)
it.close()
}Copy the codeBy using such a type alias, the def part becomes clearer. I highly recommend the “type alias for larger structure types” approach, but I also end with a caution to make sure you really don’t have any other options before deciding to use structure types. You need to think about the negative performance impact.
22. Path dependency type
This Path Dependent Type allows us to do “Type checking” on types within a Type. This may seem strange, but the following example is intuitive:
class Outer {
class Inner
}
val out1 = new Outer
val out1in = new out1.Inner // concrete instance, created from inside of Outer
val out2 = new Outer
val out2in = new out2.Inner // another instance of Inner, with the enclosing instance out2
// the path dependent type. The "path" is "inside out1".
type PathDep1 = out1.Inner
// type checks
val typeChecksOk: PathDep1 = out1in
// OK
val typeCheckFails: PathDep1 = out2in
// <console>:27: error: type mismatch;
// found : out2.Inner
// required: PathDep1
// (which expands to) out1.Inner
// val typeCheckFails: PathDep1 = out2inCopy the codeEvery outer class has its own inner class. So they are different types — the difference depends on which path we use to get them.
Using this type is useful because we can force the type from inside a specific parameter. A specific signature that adopts this type is as follows:
class Parent {
class Child
}
class ChildrenContainer(p: Parent) {
type ChildOfThisParent = p.Child
def add(c: ChildOfThisParent) =??? }Copy the codeThe path-dependent types we use now are encoded into the logic of the type system. The container should contain only the Parent’s Child object, not any Parent.
We’ll see how to introduce any of the Parent’s Child objects soon in the type projection section.
23. Type projection
Type Projections are similar to “path dependent types” in that they allow you to refer to the Type of an inner class. Syntactically, you can organize the path structure of the inner class and then separate it with the # symbol. Let’s look at the first and major difference between these path-dependent types (.syntax) and type projections (# syntax) :
// our example class structure
class Outer {
class Inner
}
// Type Projection (and alias) refering to Inner
type OuterInnerProjection = Outer#Inner
val out1 = new Outer
val out1in = new out1.InnerCopy the codeAnother accurate intuition is that rather than path-dependence, type-projection can be used for “type-level programming,” such as (there is type) Existential Types.
Existential types are closely related to type erasure.
val thingy: Any=??? thingymatch {
case l: List[a] =>
// lower case 'a', matches all types... what type is 'a'? !
}Copy the codeWe do not know the type of A because the runtime type has been erased. We know that List is a type constructor * -> *, so there must be some type that can be used to construct a valid List[T]. This “certain type” is the existence type.
Scala provides a shortcut for this:
List[_]
// ^ some type, no idea which one!Copy the codeSuppose you’re using some abstract type members, which in our case will be monads. We want to force our users to use only Cool instances of Monad because, for example, our Monad only makes sense for these types. We can do this by using these type boundaries with type T:
type Monad[T] forSome { type T >: Cool }Copy the codeMikeslinn.blogspot.com/2012/08/sca…
The translator’s note:
It is recommended to read the following articles to deepen your understanding of this section:
- What does the # operator mean in Scala?
- Existential types in Scala
24. Specialized Types
24.1. @ specialized
Type Specialization is more of a performance trick than normal “Type system stuff”. But if you want to write good performance collections, it’s very important, and we need to master it. For example, we’ll implement A very useful collection called Parcel[A], which holds A value of A given type — useful indeed!
case class Parcel[A] (value: A)Copy the codeSo that’s our basic implementation. Is there a problem? That’s right, because A can be anything, it will be represented as A Java object, even if we only box Int values. So the above class causes the original values to be boxed and unboxed because the container is processing objects:
val i: Int = Int.unbox(Parcel.apply(Int.box(1)))Copy the codeAs we all know, boxing is not a good idea when you don’t really need it, because it generates more run-time work by converting back and forth between int and object int. How can this problem be eliminated? One technique is to “professionalize” our Parcel for all primitive types (Long and Int will suffice here) as follows:
If you’ve read the Value class, you’ve probably noticed that Parcel can be a good substitute for implementation! That’s true. However, specialized was already available in Scala 2.8.1, and the Value class was introduced in 2.10.x. And while the former can specialize more than one value (although it generates code at an exponential rate), the Value class is limited to just one.
case class Parcel[A] (value: A) {
def something: A=??? }// specialzation "by hand"
case class IntParcel(intValue: Int) {
override def something: Int = /* works on low-level Int, no wrapping! * /????? }case class LongParcel(intValue: Long) {
override def something: Long = /* works on low-level Long, no wrapping! * /????? }Copy the codeThe implementations of IntParcel and LongParcel will effectively avoid boxing because they process directly on the raw values and do not need to enter object domain. Now we just need to select the *Parcel we want based on our instance.
This looks good, but the code basically becomes harder to maintain. It has N implementations, one for each primitive value type we need to support (e.g., int, long, byte, char, short, float, double, Boolean, void, plus Object)! There are a lot of templates to maintain.
Now that we’re familiar with “type specialization” and know that implementing it manually isn’t very friendly, let’s take a look at how Scala helps us fix this problem by introducing the @specialized annotation:
case class Parcel[@specialized A] (value: A)Copy the codeAs shown above we apply the @specialized annotation to the type parameter A, instructing the compiler to generate all the specialized variables for the class, which are: ByteParcel, IntParcel, LongParcel, FloatParcel, DoubleParcel, BooleanParcel, CharParcel, ShortParcel, CharParcel and even VoidParcel (which isn’t the actual name, but you get the idea). The compiler is also responsible for calling the correct version, so we can just write the code and not worry about whether a class is specialized or not. The compiler will use the appropriate version (if any) whenever possible:
val pi = Parcel(1) // will use `int` specialized methods
val pl = Parcel(1L) // will use `long` specialized methods
val pb = Parcel(false) // will use `boolean` specialized methods
val po = Parcel("pi") // will use `Object` methodsCopy the code“Great, let’s go ahead and use it” – this is the reaction most people get when they discover the benefits of specialization, because it speeds up low-level operations exponentially while reducing memory usage. Unfortunately, it’s also expensive: when multiple parameters are used, the amount of code generated can quickly become huge, like this:
class Thing[A.B] (@specialized a: A, @specialized b: B)Copy the codeIn the example above, we use the second style of applying specialization – on parameters – which has the same effect as if we had professionalized A and B directly. Note that the code above will generate 8 * 8 = 64 implementations, because it has to deal with cases like “A is an int, B is an int” and “A is A Boolean, but B is A long” — you can see where that is. In fact, the number of classes generated is about 2 * 10^(NR_of_type_specializations), which can easily reach thousands of classes if you already have three type arguments.
There are ways to prevent this “exponential explosion”, for example by limiting the types of targets for specialization. Assuming that Parcel mostly deals only with integers and never with floating-point numbers, we could make the compiler specialize only Long and Int, such as:
case class Parcel[@specialized(Int.Long) A] (value: A)Copy the codeThis time let’s explore a bit of bytecode using: Javap Parcel:
// Parcel, specialized for Int and Long
public class Parcel extends java.lang.Object implements scala.Product.scala.Serializable{
public java.lang.Object value(a); // generic version, "catch all"
public int value$mcI$sp(); // int specialized version
public longvalue$mcJ$sp(); }// long specialized version
public boolean specInstance$(); // method to check if we're a specialized class impl.
}Copy the codeAs you can see, the compiler provides additional specialization methods, such as value$MCI $sp(), which will return int, and long has a similar method. It is worth noting that there is another method called specInstance$, which returns true if the implementation used is a specialized class.
In case you’re wondering which classes are currently specialized in Scala, they have (and may not be complete) : Function0, Function1, Function2, Tuple1, Tuple2, Product1, Product2, AbstractFunction0, AbstractFunction1, AbstractFunction2. Because the current cost of specialization for two parameters is already high, one trend is not to specialize for more parameters, although we could.
A classic example of why we avoid boxing is “memory efficiency.” Imagine a Boolean value, which would be great if its storage consumed only 1 bit, but it does not (including all JVMS I know). For example on HotSpot a Boolean is treated as an int, so it takes up 4 bytes of space. Its sibling java.lang.Boolean, like all Java objects, has an 8-byte object header, followed by an additional 4-byte store for Boolean. Due to the arrangement of Java object layouts, the space occupied by this object is redistributed by 16 bytes (8 bytes for the object header, 4 bytes for the value, and 4 bytes for the padding). This is another sad reason why we want to avoid boxing.
24.2. Miniboxing
❌ The author has not completed this chapter
This is not a Scala feature, but can be used as a compiler plug-in with Scalac.
As we explained in the previous section, specialization is powerful, but also a “compiler bomb” with the problem of exponential code growth. There is a proven concept to solve this problem, Miniboxing is a compiler plug-in that does the same thing as @specialized, yet doesn’t generate thousands of classes.
TODO, there’s a project from withing EPFL to make specialization more efficient: Scala Miniboxing
25. Type Lambda
❌ The author has not completed this chapter
We’ll use “path-dependent types” and “structural types” in the section on Type lambda. If you missed these two sections, you can skip back to them.
Before we look at the Type Lambdas, let’s review some details about “functions” and “Curryification” :
class EitherMonad[A] extends Monad[alpha] [({type lambda.= Either[AAlpha] # lambda] {})def point[B](b: B) :Either[A.B]
def bind[B.C](m: Either[A.B])(f: B= >Either[A.C) :Either[A.C]}Copy the code