Haskell erase type?

Question

I was giving a lecture about Haskell when I came across this paragraph ( http://www.seas.upenn.edu/~cis194/lectures/02-lists.html ):

This “not care” is what “parametric” means in parametric polymorphism. All Haskell functions must be parametric in their parameters; functions should not care or make decisions based on the choice of these parameters. The can not function does one thing when Int is another thing when a Bool. Haskell simply does not provide the ability to write such an operation. This langauge property is called parametricity.

There are many deep and deep consequences of parametricity. One of the consequences is what is called type erasure. Since a running Haskell program can never make decisions based on type information, all type information can be deleted at compile time. Although how important types are when writing Haskell code, they are completely irrelevant when running Haskell code. This property gives Haskell a huge speedup over other languages ​​such as Python, which must support types at runtime. (Erasing styles is not the only thing that makes Haskell faster, but Haskell sometimes synchronizes 20 times faster than Python.)

What I don't understand is how is “all Haskell functions” parametric? Are types explicit / static in Haskell? Also I don't understand how erasing styles improves compile- time runtime?

Sorry if these questions are really basic, I'm new to Haskell.

EDIT:

Another question: why does the author say that "Despite how important types are when writing Haskell code, they are completely irrelevant when running Haskell code"?

Answer 1

What I don't understand is how is “all Haskell functions” parametric?

He does not say that all Haskell functions are parametric, he says:

All Haskell functions must be parametric in the parameters of their type .

The Haskell function must not have any type parameters.

Another question: why does the author say that "Despite how important types are when writing Haskell code, they are completely irrelevant when running Haskell code"?

Unlike a dynamically typed language, where you need to check at runtime, if (for example) two things are numbers, before you try to add them together, your running Haskell program knows that if you try to add them together, then they must be numbers, because the compiler was convinced of this beforehand.

Are types explicit / static in Haskell?

Haskell types can often be inferred, in which case they should not be explicit. But you are right in that they are static, and in fact they do not matter at runtime, because static means that the compiler guarantees that everything will be of the type that should be before your program ever done.

Answer 2

Types can be erased in Haskell because the type of an expression is either known at compile time (for example, True ), or its type does not matter at run time (for example, [] ).

There is a warning there, although it is assumed that all meanings have some kind of uniform idea. Most Haskell implementations use pointers for everything, so the actual type of the pointer indicates that it does not matter (except for the garbage collector), but you could imagine a Haskell implementation that uses an uneven representation, and then the type information needs to be saved.

Answer 3

Others have already answered, but perhaps some examples may help.

Python, for example, stores type information until runtime:

 >>> def f(x): ... if type(x)==type(0): ... return (x+1,x) ... else: ... return (x,x) ... >>> f("hello") ('hello', 'hello') >>> f(10) (11, 10) 

The function above, taking any argument x into account, returns a pair (x,x) , unless x is of type int . The function checks this type at runtime, and if x turns out to be int , it behaves in a special way, returning instead (x+1, x) .

To implement the above, the Python runtime must track types. That is, when we do

 >>> x = 5 

Python cannot just store a representation of byte 5 in memory. It is also necessary to mark this view with an int tag, so that when we make type(x) , the tag can be restored.

Next, before performing any operation such as x+1 , Python must check the type tag to make sure that we are actually working on int s. If x is, for example, str ing, Python will throw an exception.

Statically verified languages, such as Java, do not need such checks at runtime. For example, when we run

 SomeClass x = new SomeClass(42); x.foo(); 

the compiler already checked there really the foo method for x at compile time, so there is no need to repeat this again. This can, in principle, increase productivity. (In fact, the JVM does some runtime checks during class loading, but let it just ignore them)

Notwithstanding the above, Java should store type tags such as Python, since it has type(-) similar:

 if (x instanceof SomeClass) { ... 

Therefore, Java allows you to write functions that can behave "specifically" for certain types.

 // this is a "generic" function, using a type parameter A <A> A foo(A x) { if (x instanceof B) { // B is some arbitrary class B b = (B) x; return (A) new B(b.get()+1); } else { return x; } } 

The above foo() function simply returns its argument, unless it is of type B , for which a new object is created instead. This is a consequence of using instanceof , which requires each object to carry a tag at runtime.

Honestly, such a tag is already present in order to be able to implement virtual methods, so it costs nothing more. However, the presence of instanceof allows you to call the above uneven behavior on types - some types can be handled differently.

Haskell instead does not have such a type/instanceof operator. Haskell parametric function of type

 foo :: a -> (a,a) 

should behave the same on all types. There is no way to cause any kind of "special" behavior. Specifically, foo x should return (x,x) , and we can see that just by looking at the annotation like above. To emphasize, there is no need to look at the code (!!) to prove such a property. This is what provides parametricity from the type indicated above.

Answer 4

Implementations of dynamically typed languages ​​usually need to store type information with each value in memory. This is not so bad for Lisp-like languages ​​that have only a few types and can reasonably identify them with a few bits of the tag (although such limited types lead to other performance problems). This is much worse for a language with many types. Haskell allows you to transfer type information at runtime, but it makes you explicit, so you can pay attention to the cost. For example, adding a Typeable a context Typeable a type offers a value with this type of access at runtime to a view of type a . More subtly, typeclass instance dictionaries usually specialize at compile time, but in fairly polymorphic or complex cases, they can persist at runtime. In a compiler similar to an explicitly abandoned JHC, and one likely possibility for a THC compiler that has just been launched, this can lead to leakage of certain types of information to the runtime in the form of pointer tags. But these situations are fairly easy to identify and only rarely cause serious performance problems.