Transcript Presentation

Heath Carroll
Bill Hanczaryk
Rich Porter

A Theory of Type Polymorphism in
Programming
◦ Robin Milner (1977)

Milner credited with introducing the idea of
type polymorphism
◦ The programming language he developed, ML, was the first
language to use polymorphic type inference and type-safe
exception handling.


Introduce the design of polymorphic type
inference
Present three programming languages that
utilize different degrees of typing
◦ ML – Bill Hanczaryk
◦ C# – Heath Carroll
◦ Python – Rich Porter

Type Polymorphism – A feature of a program that allows
different data types to be handled essentially the same way.
◦ Polymorphic Function – A function that can evaluate values of
different data types.
◦ Polymorphic Data – A data type with only a generalized type.

Static Typing - type checking at compile-time.

Dynamic Typing – type checking at run-time.

Strong Typing - In order to mix types, you must use an
explicit conversion.

Weak Typing - mixing types without an explicit conversion
is okay.

ML Typing
◦ static – type checking at compile time
◦ strong –type mixing must be done explicitly
◦ inferred -> Next Slide

Even though type inferred, basic types still exist
◦ int, real, string, bool, and char.

ML created (by Milner) to specifically utilize the
Hindley-Milner type inference algorithm to
automatically infer the types of expressions

Type Inference - The ability of a programming
language to automatically detect the data type of a
variable.

A compiler is often able to infer the type of a variable
without explicit type annotations having been given.

Why is it useful?
◦ A programmer does not have to explicitly define type
annotations while still maintaining about the same level of
type safety.
◦ Types often clutter programs and slow down programmer
efficiency.

Example
-fun f(x) = 2+x;
>val it = fn : int -> int

How does it work?
◦
◦
◦
◦
◦
+ has two types: int*int -> int, real*real -> real
2 : int has only one type
This implies + : int*int -> int
From context, need x: int
Therefore f(x:int) = 2+x has type int -> int

Standard type checking
◦ int f(int x) { return x+1; };
◦ int g(int y) { return f(y+1)*2;};

Type inference
◦ f(x) { return x+1; };
◦ g(y) { return f(y+1)*2;};

Look at code without type information and
figure out what types could have been
declared.

According to the Wikipedia C# is :
static – compile time type checking
dynamic – runtime type checking
strong – any type mixing must be done explicitly
safe – type mismatches throw errors, find a way to
work (ie adding an int to a string in javascript)
◦ nominative - two variables are type-compatible if
and only if their declarations name the same type
◦
◦
◦
◦
Basically Java using C syntax, boxing, and garbage
collection, but without global variables.

How on earth can a language be both at the
same time? Don’t they contradict each other?
◦ Sort of. It’s just redundant to type check at both
compile time and runtime.
◦ But C# isn’t fully dynamic, it’s dynamic only when
you’d want it to be, literally.
C# has a new static type:
Namely the dynamic type.



dynamic d1 = new Foo();
dynamic d2 = new Bar();
string s;
d1.M(s, d2, 3, null);
Q: What does the compiler do when it comes
across this function M()?



A: Nothing! It allows the program to figure it
out at runtime. (ok, so maybe it does
something…)
The compiler sorts the function call to M(), so
that at runtime M() can be invoked with the
arguments passed in.
Which it does as follows:
1. Reflection is used to obtain the actual
runtime types of the two objects, d1 and d2,
that did not have a static type (or rather had
the static type dynamic). The result is Foo for
d1 and Bar for d2.
Reflection - provides objects (of type Type) that
encapsulate assemblies, modules and types. You can use
reflection to dynamically create an instance of a type, bind
the type to an existing object, or get the type from an
existing object and invoke its methods or access its fields
and properties. If you are using attributes in your code,
Reflection enables you to access them.


2. Method lookup and overload resolution is
performed on the type Foo with the call
M(string,Bar,3,null) using ordinary C#
semantics.
Overload resolution – The Dynamic Runtime
Library is responsible for figuring out which
method to actually use if more than one is
found.
◦ Betterness rules apply.

3. If the method is found it is invoked;
otherwise a runtime exception is thrown

M(string s, int i = 1);
M(object o);
M(int i, string s = “Hello”);
M(int i);
Given the functions above are all applicable,
which one or ones are most suitable and
which one gets the call?



Given these overloads, we can see the working of the rules
above. M(string,int) is not applicable because 5 doesn’t
convert to string. M(int,string) is applicable because its
second parameter is optional, and so, obviously are M(object)
and M(int).
M(int,string) and M(int) are both better than M(object)
because the conversion from 5 to int is better than the
conversion from 5 to object.
Finally M(int) is better than M(int,string) because no optional
arguments are omitted.

Strong
◦ No implicit type conversions

Duck
◦ “When I see a bird that walks like a duck and swims
like a duck and quacks like a duck, I call that bird a
duck”

Dynamic
◦ No initialization/declaration
◦ Type “determined” at run time

Cannot add int to string
◦ ‘a’ + 3 → error
◦ ‘a’ + ‘3’ → ‘a3’

Cannot add string to list
◦ ‘at’ + [‘bad’,‘cat’] → error
◦ [‘at’] + [‘bad’, ‘cat’] → [‘at’,‘bad’,‘cat’]

Interesting
◦ 3*3 → 9
◦ ‘3’*3 → ‘333’
◦ ‘3’*’3’ → error


Not concerned
with type
inference
Only interested
in the aspects
that are used
rather than the
object itself.

Values carry type not variables

Type is determined at run time


Normal type inference is not necessary with
duck typing
Python Type Inference Applications:
◦ Optimized Interpreter
◦ Compile Python → Another Language (Perl, C, …)

Further Reading
◦ “Psyco”
◦ “Type Inference for Python”
◦ “Aggressive Type Inference”