Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Static types, polymorphism and specialization

Tags:

types

haskell

When I first learned Haskell, I very quickly came to love parametric polymorphism. It's a delightfully simple idea that works astonishingly well. The whole "if it compiles it usually works right" thing is mostly due to parametric polymorphism, IMHO.

But the other day, something occurred to me. I can write foo as a polymorphic function. But when bar calls foo, it will do so with a specific set of argument types. Or, if bar itself is polymorphic, then its caller will assign definite types. By induction, it seems that if you were to take any valid Haskell program and analyse the entire codebase, you can statically determine the type of every single thing in the entire program.

This, in a sense, is a bit like C++ templates. There is no run-time polymorphism, only compile-time polymorphism. A Haskell compiler could choose to generate separate machine code for every type at which each polymorphic function is called. Most Haskell compilers don't, but you could implement one if you wanted to.

Only if you start adding Haskell extensions (ExistentialQuantification is the obvious one) do you start to get real run-time polymorphism, where you have values who's type cannot be statically computed.

Oh, yeah, my question?

  1. Are the statements above actually correct?

  2. Is there a widely-used name for this property?

like image 960
MathematicalOrchid Avatar asked May 10 '12 13:05

MathematicalOrchid


People also ask

What are the types of static polymorphism?

There are two types of polymorphism which are the compile-time polymorphism (overload) and run-time polymorphism (overriding).

Is static typing related to polymorphism?

The essence of object-oriented static typing is subtyping, or subtype polymorphism.

What are the two types of polymorphs?

In Object-Oriented Programming (OOPS) language, there are two types of polymorphism as below: Static Binding (or Compile time) Polymorphism, e.g., Method Overloading. Dynamic Binding (or Runtime) Polymorphism, e.g., Method overriding.

What is the difference between static polymorphism and dynamic polymorphism?

Static polymorphism is polymorphism that occurs at compile time, and dynamic polymorphism is polymorphism that occurs at runtime (during application execution). An aspect of static polymorphism is early binding. In early binding, the specific method to call is resolved at compile time.


1 Answers

Haskell (with no extensions) permits polymorphic recursion, and this feature alone makes it impossible to statically specialize a program to a completely monomorphic one. Here is a program that will print an N-deep nested list, where N is a command-line parameter:

import System  foo :: Show a => Int -> a -> IO () foo 0 x = print x foo n x = foo (n-1) [x]  main = do [num_lists] <- getArgs           foo (read num_lists) 0 

In the first call to foo, a has type Int. In the next recursive call, it has type [Int], then [[Int]], and so forth.

If polymorphic recursion is prohibited, then I believe it's possible to statically specialize a program.

like image 130
Heatsink Avatar answered Oct 09 '22 11:10

Heatsink