Understanding polymorphism
I have been working on a programming language for quite some time now and I realized I didn't understand well polymorphism. In order to learn more about it I decided to wrote this post. This post is a summary of the things I learned.
Generic
It's useful when you don't want to repeat yourself.
Generic functions
Suppose you have the following code in C:
int square_int(int n) {
return n * n;
}
float square_float(float n) {
return n * n;
}
double square_double(double n) {
return n * n;
}
The behavior of each function conceptually is the same, but they accept different types. Wouldn't be better if you could just write a function that squares int's, floats and double's?
Generic functions exists for this. The idea is that sometimes, the same behavior can work over different types.
Templates
One way to have generic functions is by using templates. They allow to specify types parameters a function can take. Then, when calling it, you specify it's type parameters in addition to the arguments.
In C++, a language with templates, the square function could look like this:
template <class T> // Create a template parameter named T
T square(T n) { // Defines a function named square that receives T and returns T
return n * n;
}
int main() {
int a = square<int>(4);
float b = square<float>(4);
double c = square<double>(4);
return 0;
}
You define square just one time, and then you can use it with any type that supports multiplication.
Duck typing
Another way to achieve generic code is using duck typing. When you use a dynamic programming language you are using duck typing. You don't specify type parameters. And at runtime, if objects support or not operations.
In Python, a language with duck typing, our square function would look like this:
def square(n): # Defines a function named square that takes one parameter
return n * n
print(square(4)) # 16
print(square(4.0)) # 16.0
Similar to in C++ you can use the square function with different types as long they support multiplication. But this is checked at runtime instead of compile time.
You can have duck typing at compile time, a lot of programming languages use this approach, as is really simple. For example, C++ templates are essentially this. But I don't know what is the technical term.
Parametric polymorphism + Type classes
Another way to have generic functions is to have a Hindley-Milner type system. If we want to keep using our example we also need type classes.
I really like this this approach because it feels like duck typing, but it works at compile time. At the same time that providing a lot more guarantees and being less work for the compiler that instantiating templates.
Our previous example on Haskell would look like this:
square n = n * n
main = do
print(square(4)) -- 16
print(square(4.0)) -- 16.0
You can even annotate the type if of square if you want:
square :: Num a => a -> a
square n = n * n
main = do
print(square(4)) -- 16
print(square(4.0)) -- 16.0
You can use the square function with different types as longs they implement the Num type class.
For me, the big win of this approach over templates, is that is not necessary to analyze multiple times generic functions. If you want to know if a function works with a certain type just check that the type satisfy the constraints of the function.
Other interesting thing about parametric polymorphism is that it gives you theorems for free:
- Parametricity: Money for Nothing and Theorems for Free by Bartosz Milewski
- Parametricity, Functional Programming, Types by Tony Morris at #FnConf18
Generic types
When you are defining a collection, usually you want it to work with multiple types. Imagine you are implementing a linked list in C.
If you are not familiar with linked lists they are a way to represent list of things. Without generics you have to define the linked list for every type you want to make lists off. For example:
struct LinkedListInt {
int current;
LinkedListInt* next;
};
LinkedListInt list;
struct LinkedListFloat {
float current;
LinkedListFloat* next;
};
LinkedListFloat list;
If we had generic types we could define the linked list once. Lucky for us, there are languages that support things like this. A linked list In C++ would look something like this:
template <typename T>
struct LinkedList {
T current;
LinkedList* next;
};
LinkedList<int> list1; // Linked list of ints
LinkedList<float> list2; // Linked list of floats
Essentially, generic types are templates applied to types. A lot of times when you are working with collections you want them to be generic.
Ad hoc
Ad hoc polymorphism is the other side of generics. Instead of defining one behavior for multiples types you define what the behaviour should be for each type.
Operator Overloading
There are different ways to represent numbers on computers. For example, integers and floats are represented differently at the hardware level. So, integers can't be added the same way floating numbers are added (at the hardware level). However, most languages use + to represent addition both for integers and floats. In a lot of languages this is a builtin operator overloaded.
a = 3 + 2
b = 3.0 + 2.0
c = "Hello, " + "World!" // Concatenate
Operator overloading consists in allowing multiple definitions of an operator. Each definition should be for a type in specific. What definition is actually called would depends on the types of the arguments.
Function Overloading
Function overloading works in a similar way to operator overloading. It consists of allowing multiple definitions for the same function. Let's look at a C++ example.
#include <iostream>
struct Point2 {
float x;
float y;
};
struct Point3 {
float x;
float y;
float z;
};
void print_point(Point2 p) {
std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}
void print_point(Point3 p) {
std::cout << "(" << p.x << ", " << p.y << ", " << p.z << ")" << std::endl;
}
int main() {
Point2 p1 = Point2{.x = 2.0, .y = 3.5};
Point2 p2 = Point2{.x = 0.5, .y = 4.1, .z = 1.0};
print_point(p1);
print_point(p2);
return 0;
}
Then when running the program the output is:
(2.0, 3.5)
(0.5, 4.1, 1.0)
We can call print_point with p1 and p2. What functions end up being called depends on the type of the value passed.
Multiple Dispatch
If we take function overloading one step further, we get multiple dispatch. It's almost the same as before, with one key difference: which function is called is decided at runtime.
Our example of function overloading would look like this in Julia, a language with multiple dispatch.
struct Point2
x::Float32
y::Float32
end
struct Point3
x::Float32
y::Float32
z::Float32
end
function print_point(p::Point2)
println("($(p.x), $(p.y))")
end
function print_point(p::Point3)
println("($(p.x), $(p.y), $(p.z))")
end
point = if rand() > 0.5 # The rand() function return a random
Point2(2.0, 3.5) # number between 0 and 1
else
Point3(0.5, 4.1, 1.0)
end
print_point(point) # Can print (2.0, 3.5) or (0.5, 4.1, 1.0) depending on
# the result of rand()
As you can see, the value of rand() is not known at compile time, therefore the type of point also can't be known at compile time. Then, what version of print_point to call must be decided at runtime.
Other stuff
Type Classes
A type class consists of a set of functions that should be implemented for a type. Is not that different to the concept of interfaces in object-oriented languages. Or the concept of traits in Rust programming language.
Let's see an example in Haskell, the language where they were first added.
-- Define the Shape class
class Shape a where
surface :: a -> Float
perimeter :: a -> Float
-- Define two records (or structs)
data Circle = Circle Float
data Rectangle = Rectangle Float Float
-- Implements Shape class for Circle
instance Shape Circle where
surface (Circle r) = pi * r^2
perimeter (Circle r) = 2 * pi * r
-- Implements Shape class for Rectangle
instance Shape Rectangle where
surface (Rectangle w h) = w * h
perimeter (Rectangle w h) = 2 * (w + h)
-- Implements a generic function for Shape
print_surface :: (Shape a) => a -> IO()
print_surface a = print (surface a)
main = do
print_surface (Circle 15)
print_surface (Rectangle 20 40)
The output of the program is:
706.85834
800
In the example first, we define a type class named Shape with two functions. Then, define two records Circle and Rectangle. After, implement Shape for both Circle and Rectangle. Finally, we define a generic function that prints the surface of any type a that implements Shape. Here, a is a type variable.
There where two types of polymorphism involved here. First, we use ad hoc polymorphism when defining the surface and perimeter for different types. Then, parametric bounded polymorphism when we define print_surface for a type that implements Shape.
One important thing to know is that type classes define constraints, not types. So you can't have a variable of type Shape, nor have collections that contains Shape. In contrast with subtyping...
Subtyping
For a language to allow subtyping there should be a hierarchical relation between its types. It should also, allow using a subtype from a type anywhere that type is expected.
This can be achieved in multiple ways. With inheritance, interfaces, traits and/or abstract types. This are the ones I know off, but probably there are more.
Let's see an example in Julia, a language that uses abstract types for this.
abstract type Shape end
print_surface(s::Shape) = println(surface(s))
struct Circle <: Shape
radius
end
surface(c::Circle) = pi * c.radius^2
struct Rectangle <: Shape
width
height
end
surface(r::Rectangle) = r.width * r.height
print_surface(Circle(15))
print_surface(Rectangle(20, 40))
In Julia subtyping is achieved through abstract types. As you can see, they can be used in a similar-ish to type classes. Although, in the case of abstract types it doesn't force a set of functions to be implemented for the types.
Also, specifically with respect to Julia vs. Haskell, types in Julia are dynamic, so you could have for example a list of Shape, and each concrete item could have a different type.