Python and generic programming

[Oliver Fromme]

Steven Bethard <steven.bethard at gmail.com> wrote:
 > Oliver Fromme <olli <at> haluter.fromme.com> writes:
 > > For example, a function can take an argument that is
 > > either an integer or a string (or a list or whatever)
 > > and it does _not_ have to be known at compile time
 > > which of those is the case.  But the compiler _does_
 > > ensure that the function will work correctly for every
 > > case (by checking that the pattern matching covers
 > > every case, and within each case, the respective type
 > > of the argument _is_ known and is checked at compile
 > > time).
 > > 
 > > I call that dynamic.
 > 
 > I'm not clear from your description (maybe you could show an example or two?)
 > but I gather you could either be talking about union typing, where at compile
 > time a variable is declared as, e.g. (list OR int), or parametric polymorphism,
 > where a variable's type is parameterized by another type, e.g. list<type>.  In
 > either of these cases, I would typically still call it static typing because the
 > possible types are still resolved at compile time.  (The first will be handled
 > much like a C union, and the second will typically be stored as a list of
 > objects, with some run-time checking of type inserted, as in Java 1.5.)

Neither.  Here's an example from the tutorial which
implements a simple insertion sort algorithm.  "#" is
the prompt of the interactive interpreter (so if you
happen to have O'Caml installed, you can just start
the interpreter and type or paste this example in,
just like in Python).  "let rec" defines recursive
functions.  "match <arg> with <pat> -> <result> | ..."
performs pattern matching on types.  "<a> :: <b>" means
element <a> prepended to the front of list <b>.
"[]" is an empty list.  ";;" terminates a statement.
The rest should be obvious.

#let rec sort lst =
     match lst with
         []           -> []
       | head :: tail -> insert head (sort tail)
 and insert elt lst =
     match lst with
         []           -> [elt]
       | head :: tail -> if elt <= head then
                             elt :: lst
                         else
                             head :: insert elt tail
 ;;

This defines a function "sort" and a function "insert"
with the following type signatures:

val sort : 'a list -> 'a list = <fun>
val insert : 'a -> 'a list -> 'a list = <fun>

It can be used like this:

#let l = ["foo"; "bar"; "baz"; "etc"];;
#sort l;;
- : string list = ["bar"; "baz"; "etc"; "foo"]

The type inferred for sort, 'a list -> 'a list, means that
sort can actually apply to lists of any type, and returns a
list of the same type.  The type 'a is a type variable, and
stands for any given type.  The reason why sort can apply
to lists of any type is that the comparisons (=, <=, etc.)
are polymorphic in Caml: they operate between any two values
of the same type.  This makes sort itself polymorphic over
all list types.

The appropriate type checking is done at compile time.  That
is, if your program calls sort with two lists of different
type (e.g. a list of strings and a list of ints), then the
compiler will detect that and report an error.  Type errors
never stay undetected, the compiler will never produce code
that will exhibit a type error at runtime.  This is a key
advantage of Caml (and other languages with pattern matching
and type inference).

Best regards
   Oliver

-- 
Oliver Fromme, Konrad-Celtis-Str. 72, 81369 Munich, Germany

``All that we see or seem is just a dream within a dream.''
(E. A. Poe)