Type and polymorphic basis

Type and polymorphic basis

What is a static type?

According to Pierce: "Type systems are a syntax method that classifys program phrases according to the kind of values calculated by the program and automatically checks for error behavior through classification results." ”

The type allows you to represent the definition and value fields of the function. For example, from a mathematical point of view, this definition:

f: R -> N

It tells us that the function "f" is a mapping from the real to the natural set.

Abstractly, this is the exact definition of a specific type. The type system gives us some more powerful ways to express these collections.

Given these comments, it makes sense for the compiler to validate the program statically (at compile time). That is, if the value (at runtime) does not meet the constraints specified by the program, compilation will fail.

Generally speaking, type check can only guarantee that unreasonable programs can not be compiled through. It does not guarantee that every reasonable program will compile through.

As the type system's ability to express it increases, we can produce more reliable code because it validates the program's in variability before we run the program (of course, the model bug that discovers the type itself!). ） 。 Academia has been working hard to improve the performance of type systems, including value-dependent types!

It is important to note that all type information is deleted at compile time because it is no longer needed. This is called erasing.

The type in Scala

Scala's powerful type system is very expressive. Its main features are:

• Paramethy polymorphism Roughly speaking, it's generic programming
• (Local) type inference Roughly speaking, that's why you don't need to write val i: Int = 12: Int
• Existence Quantification Roughly, define some types without names
• Windows We'll learn this next week; roughly, "cast" one type of value into another

Paramethy polymorphism

Polymorphism is used to write generic code (to different types of values) without compromising the richness of static types.

For example, without paramethy polymorphism, a common list data structure always looks like this (in fact, it looks a lot like Java before generics):

scala> 2 :: 1 :: "bar" :: "foo" :: Nil
res5: List[Any] = List(2, 1, bar, foo)

Now we can't recover any type of information about its members.

scala> res5.head
res6: Any = 2

So our application will degenerate into a series of type transformations ("asInstanceOf") and there will be a lack of type security (because these are dynamic).

Polymorphism is achieved by specifying type variables.

scala> def drop1[A](l: List[A]) = l.tail
drop1: [A](l: List[A])List[A]

scala> drop1(List(1,2,3))
res1: List[Int] = List(2, 3)

Scala has rank 1 polymorphism

Roughly speaking, this means that in Scala, there are some type concepts that you want to express that are "too general" for the compiler to understand. Suppose you have a function

def toList[A](a: A) = List(a)

You want to continue using it generically:

def foo[A, B](f: A => List[A], b: B) = f(b)

This code cannot be compiled because all type variables are pinned only in the call context. Even if you "pin" type B:

def foo[A](f: A => List[A], i: Int) = f(i)

... You will also get a type mismatch error.

Type inference

A traditional objection to static types is that it has a lot of syntax overhead. Scala mitigates this problem by type inference.

In a functional programming language, the classic method of type inference is the Hindley Milner algorithm, which was first implemented in ML.

Scala type inference system implementation is slightly different, but similar in nature: infer constraints, and try to unify types.

For example, you can't do this in Scala:

scala> { x => x }
<console>:7: error: missing parameter type
       { x => x }

In OCaml you can:

# fun x -> x;;
- : 'a -> 'a = <fun>

All types in Scala are inferred to be local. S cala analyzes one expression at a time. For example:

scala> def id[T](x: T) = x
id: [T](x: T)T

scala> val x = id(322)
x: Int = 322

scala> val x = id("hey")
x: java.lang.String = hey

scala> val x = id(Array(1,2,3,4))
x: Array[Int] = Array(1, 2, 3, 4)

The type information is well preserved, and the Scala compiler infers the type for us. Please note that we do not need to explicitly specify the return type.

Transgender Variance

Scala's type system must explain both class hierarchy and polymorphism. C lass hierarchies can express sub-class relationships. W hen mixing OO and polymorphism, a central question is: If T’ is a sub-class of T should Container's be considered a Container[T] Container[T’] Variance annotations allow you to express the relationship between class hierarchies and polymorphic types:

Name	Meaning	Scala tag
Co-change covariant	C'T's is a sub-class of C'T'	[+T]
Inverted contravariant	C is a sub-class of C.T'	[-T]
Unchanged invariant	It has nothing to do with C.T. and C.T.).	[T]

What sub-type relationships really mean: For a given type T T’ is its sub-type, can you replace it?

scala> class Covariant[+A]
defined class Covariant

scala> val cv: Covariant[AnyRef] = new Covariant[String]
cv: Covariant[AnyRef] = Covariant@4035acf6

scala> val cv: Covariant[String] = new Covariant[AnyRef]
<console>:6: error: type mismatch;
 found   : Covariant[AnyRef]
 required: Covariant[String]
       val cv: Covariant[String] = new Covariant[AnyRef]
                                   ^

scala> class Contravariant[-A]
defined class Contravariant

scala> val cv: Contravariant[String] = new Contravariant[AnyRef]
cv: Contravariant[AnyRef] = Contravariant@49fa7ba

scala> val fail: Contravariant[AnyRef] = new Contravariant[String]
<console>:6: error: type mismatch;
 found   : Contravariant[String]
 required: Contravariant[AnyRef]
       val fail: Contravariant[AnyRef] = new Contravariant[String]
                                     ^

Inverting seems strange. W hen will it be used? Surprisingly, the definition of functional traits uses it!

trait Function1 [-T1, +R] extends AnyRef

If you think about it from a replacement perspective, it makes a lot of sense. Let's first define a simple class hierarchy:

scala> class Animal { val sound = "rustle" }
defined class Animal

scala> class Bird extends Animal { override val sound = "call" }
defined class Bird

scala> class Chicken extends Bird { override val sound = "cluck" }
defined class Chicken

Suppose you need a function with Bird as the argument:

scala> val getTweet: (Bird => String) = // TODO

The standard animal library has a function that meets your needs, but its parameters are Animal. I n most cases, if you say, "I need a sub-class, I have a 我需要一个___，我有一个___的子类 that's all right. H owever, in the function argument here is inverted. I f you need a function variable that accepts the argument type Bird, but points it to a function that accepts the argument type Chicken, you get an error when you pass it in a Duck. However, this is not the problem if you point the variable to a function that accepts the argument type Animal:

scala> val getTweet: (Bird => String) = ((a: Animal) => a.sound )
getTweet: Bird => String = <function1>

The return value type of the function is co-variable. If you need a function that returns Bird, but points to a function that returns a type of Chicken, that's certainly necessary.

scala> val hatch: (() => Bird) = (() => new Chicken )
hatch: () => Bird = <function0>

Boundary

Scala allows you to limit polymorphic variables through boundaries. These boundaries express sub-type relationships.

scala> def cacophony[T](things: Seq[T]) = things map (_.sound)
<console>:7: error: value sound is not a member of type parameter T
       def cacophony[T](things: Seq[T]) = things map (_.sound)
                                                        ^

scala> def biophony[T <: Animal](things: Seq[T]) = things map (_.sound)
biophony: [T <: Animal](things: Seq[T])Seq[java.lang.String]

scala> biophony(Seq(new Chicken, new Bird))
res5: Seq[java.lang.String] = List(cluck, call)

The type of underlying is also supported, which makes the introduction of inverter and clever co-change handy. List[+T] co-variable; a list of Bird is also Animal of Animals. List defines an ::(elem T) a new elem List The new List has the same type as the original list:

scala> val flock = List(new Bird, new Bird)
flock: List[Bird] = List(Bird@7e1ec70e, Bird@169ea8d2)

scala> new Chicken :: flock
res53: List[Bird] = List(Chicken@56fbda05, Bird@7e1ec70e, Bird@169ea8d2)

List also ::[B >: T](x: B) List[B] N ote B >: T that type B is a super-class of type T. This approach allows us to do the correct thing by List[Bird] Animal in front of a List.

scala> new Animal :: flock
res59: List[Animal] = List(Animal@11f8d3a8, Bird@7e1ec70e, Bird@169ea8d2)

Note that the return type is Animal.

Quantization

Sometimes, you don't care if you can name a type variable, such as:

scala> def count[A](l: List[A]) = l.size
count: [A](List[A])Int

You can then replace it with a wildcard:

scala> def count(l: List[_]) = l.size
count: (List[_])Int

This is equivalent to a short case of the following code:

scala> def count(l: List[T forSome { type T }]) = l.size
count: (List[T forSome { type T }])Int

Note that quantifying the results can become very difficult to understand:

scala> def drop1(l: List[_]) = l.tail
drop1: (List[_])List[Any]

Suddenly, we lost the type of information! Let's fine-check the code to see what happens:

scala> def drop1(l: List[T forSome { type T }]) = l.tail
drop1: (List[T forSome { type T }])List[T forSome { type T }]

We cannot use T because type does not allow this.

You can also apply boundaries to wildcard type variables:

scala> def hashcodes(l: Seq[_ <: AnyRef]) = l map (_.hashCode)
hashcodes: (Seq[_ <: AnyRef])Seq[Int]

scala> hashcodes(Seq(1,2,3))
<console>:7: error: type mismatch;
 found   : Int(1)
 required: AnyRef
Note: primitive types are not implicitly converted to AnyRef.
You can safely force boxing by casting x.asInstanceOf[AnyRef].
       hashcodes(Seq(1,2,3))
                     ^

scala> hashcodes(Seq("one", "two", "three"))
res1: Seq[Int] = List(110182, 115276, 110339486)

Refer to the existence type in Scala written by D. R. MacIver