First-order parametric polymorphism and first-order function

I开发者_运维技巧 am reading the paper Generics of a Higher Kind, the first sentence is

With Java 5 and C# 2.0, first-order parametric polymorphism was introduced in mainstream object-oriented programming languages under the name of generics.

I don't know what's first-order parametric polymorphism, I also do not quite understand what's first-order function, I know high-order function is function that takes a function and return a function, but I don't know what's zeroth-order function, first-order function. I saw an explanation from here, like this:

f -> g is zeroth order

f -> g -> h is first order

f -> g -> h -> i is second order

Etc.

Can anyone explain these two terms for me?

For higher-order (aka higher kinded) parametric polymorphism, so first values have a type, types have a kind now if you think of a parametric type as sort of a type function (function of types) so for example IEnumerable<T> is a type function of kind * -> *, when you apply a type to this type function you get a type of kind *. So with this view of parametric types (type constructors) as type functions we can start to talk about higher-order type functions, a type function which can take/return type functions as arguments. This is known as higher-kinded polymorphism and it is highly expressive type system feature lacking in languages such as Java & C#. If you know about C++ templates then there is a limited but inconsistant and almost useless support for such a thing via template template parameters (yes template template).

You might wonder why would it be useful to have such a feature? well they allow one to express higher level abstractions and more generic code such as Monads & Functors. Standard Haskell98 supports higher-kinded polymorphism.

For your first-order function example, first you must understand that all functions in a lambda calculus only take one argument and the arrows in your example actually associates to the right so this is what you actually have:

f -> g is zeroth order. f -> (g -> h) is first order, function returns a function. f -> (g -> (h -> i)) is second order, function returns a function which returns a function.

The same 'one argument only' applies to type, kind, sorts (kinds having sorts) functions as well.