Sorting Polymorphically in Many Languages
Polymorphism is a powerful programming language feature. In polymorphism, we have generic functions that don’t know exactly what type of data they will be operating on. Often, the data types won’t even all have been designed yet when the generic function is written. The generic function provides the general outline of the work, but the details of some parts of the work, some specific operations, must be tailored to the specific types being used. The generic code needs some way of accessing these specific operations, and the users of the generic code need some way of specifying them.
There are many use cases for polymorphism. When sorting an array, the algorithm will need to be adapted to the specific element type, so it knows how to compare elements. When drawing virtual objects on a screen, an algorithm might choose where to put each object and which objects to draw, whereas each type of object might have its own specialized implementation of how to draw it.
These are just two examples among many. Most complicated projects have many polymorphic functions. Even in languages that don’t support polymorphism directly, there are usually ways of building it out of existing primitives.
The example I’ve chosen is sorting, specifically sorting an array or vector. It’s just an example; a lot of what I say applies generally to how polymorphism works in that programming language.
This is a good example, as sorting is a function where it’s really obvious where polymorphism is required to get a properly generalizable algorithm. A lot of discussions of polymorphism invent contrived situations where polymorphism seems overkill, and I think that’s fundamentally confusing.
On the other hand, it’s a bad example in some ways, because it only makes sense in the context of a homogeneous array or list, where every element is the same type. This is a bad example because heterogeneous containers, where every element has a different type and the polymorphic function has to look up as many function implementations as there are elements, provides a very different set of problems to solve.
This is especially important as Rust and C++ both provide two types of polymorphism, compile-time and run-time, also known as static and dynamic. The question of which to use is complicated, but for sorting, compile-time or static polymorphism is clearly the appropriate choice, with run-time or dynamic polymorphism feeling very awkward and forced. Heterogeneous containers generally must use some form of dynamic polymorphism (whether through virtual functions in C++ or through type erasure).
So, while I think this example will be illustrative, it won’t allow us to explore run-time, dynamic polymorphism on its home turf, if you will. Hopefully, I can make up this deficit in future blog posts.
Sorting: A Polymorphic Function#
Sorting algorithms are a true use case for polymorphism: rather than distinguishing between a small set of options, many types support the operations necessary for sorting. The algorithm is agnostic to the implementation of those operations. Quick sort, insertion sort, and merge sort apply equally well to sorting integers, floating point values, or alphabetizing strings – any algorithm can be combined freely with any type, or at least any type for which a concept of “ordering” exists.
Here are the operations or properties (or dare I say, traits) that a type needs to be sortable, and that a generic sorting algorithm might need to find out about. The first one is obvious to OOP programmers, but the other two more subtle, and implied in many OOP programming languages:
- Ordering or comparison: Given two values a and b, this operation answers which is greater, or determines that they are equal. Some types have the additional possibility that they are incomparable – arrays of those types cannot be sorted by most algorithms.
- Swapping or moving: The data has to be able to be moved around to turn the unsorted array into a sorted one. This is automatic in many OOP languages for object types due to ubiquitous use of indirection. It is also automatic in Rust, where every type can be moved by just copying all the bytes.
- Striding the array or size: Given a pointer to one element, how do you get to the next one? By how many bytes must you increment the pointer? Most sorting algorithms require this to be constant. If you use indirection for the values, this is also trivial. If you do not, it is key information.
These operations – or more generally, traits of a type – can then be combined with a sorting algorithm to create a concrete procedure to sort an array for a given concrete type.
So let’s see how various programming languages handle this.
Programming Language #0: Sorting in C#
I will start our tour of programming languages with C. C – the non-OOP,
non-C++ programming language; the classic “portable assembly language”
from 1972 – doesn’t have many polymorphic algorithms, algorithms that
accept any type, because you have to implement polymorphism by hand. But
sorting is an important enough one that standard C does have a generic
sorting function: qsort
for quicksort (and on many systems, heapsort
and mergesort` are also avaialble). Because polymorphism is implemented
by hand, we can look at this function to see how one might specifically
tailor polymorphism to the problem of sorting.
Here is the function signature for qsort
:
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
It can be used to sort blocks of memory containing a sequence of integers, foating point values, or (pointers to) strings – any comparable and (trivially) movable fixed-size type.
C function signatures can be hard to read, so I’ll break it down argument by argument:
void *base
: This is an untyped pointer (void *
) to the beginning of the block of memory to be sorted.size_t nmemb
: This is a bound, how much memory is contained in the block of memory. C often represents aggregates by two values, base and a count of the members.size_t size
: How big is each member? On a typical 64-bit system, anint
is 4 bytes, adouble
is 8, andchar *
for strings are 8 bytes. Custom types might be any size.qsort
should work for all of these types, without indirection.int (*compar)(const void *, const void *)
: This is the interesting part. This is a function pointer for the comparison operation as discussed above. You write a function that takes two pointers to two elements, and returns a value that encodes their relationship.
Swapping is assumed to be byte-by-byte, and so size
covers the
last two attributes of the type listed above. The key one here
is compar
, a bit of code that qsort
has to call to do an
operation specific to your type, a small policy injection that
adapts a generic algorithm to your particular type.
The return value of compar
is an int
, but it is interpreted according
to a C convention, shared with (for example) the string comparison
function strcmp
. For a ? b
, a return value r
is interpreted thus:
- if
r < 0
,a < b
- if
r > 0
,a > b
- if
r == 0
,a == b
So, here’s a complete C program that sorts its command line arguments – including the program name:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare_strings(const void *a, const void *b) {
// `a` and `b` are pointers to the element type, which in
// this case is `char *`. Thus they are `char **`.
//
// Nothing is stopping you from getting this wrong and putting
// `char *` instead -- it will just silently not work. The
// compiler can and will make you write `const` in the right
// place, though.
char * const* a_str_ptr = a;
char * const* b_str_ptr = b;
// `strcmp` uses the same convention as `qsort` for comparison.
return strcmp(*a_str_ptr, *b_str_ptr);
}
int main(int argc, char **argv) {
qsort(argv, argc, sizeof(char *), &compare_strings);
for (int i = 0; i < argc; i++) {
printf("%s\n", argv[i]);
}
return 0;
}
But the same qsort
function can also be used to sort integers, if given
different parameters and a different comparison function:
#include <stdlib.h>
#include <stdio.h>
int compare_ints(const void *a_vp, const void *b_vp) {
const int *a_ip = a_vp;
const int *b_ip = b_vp;
int a = *a_ip;
int b = *b_ip;
if (a < b) {
return -1;
} else if (a == b) {
return 0;
} else { // a > b
return 1;
}
}
int main(int argc, char **argv) {
int intary[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
qsort(intary, 10, sizeof(int), &compare_ints);
for (int i = 0; i < 10; i++) {
printf("%d\n", intary[i]);
}
return 0;
}
qsort
implements a form of manual run-time polymorphism, in a
programming language with no built-in support for polymorphism.
It behaves differently based on the element type, as passed to it via a
variety of arguments. One of the traits – the comparison operator –
differs between types in a way that requires custom code, and this is
passed in via pointer. qsort
then invokes the operation via indirect
function call, the same mechanism that is used for polymorphism
in OOP. But unlike OOP-style runtime polymorphism, there is just one
function pointer for all the items, rather than each item coming with
its own “vtable.”
Note that the optimizer is not able to eliminate this indirect call,
especially in the qsort
example, where the sorting function is in the
standard library, whereas the function calling it and the comparison
function are both in application code. This comes at a performance cost,
which means that if you’re programming C and the performance of this
particular sort is essential to your program, it might easily make sense
to write custom sorting code that is not polymorphic.
Programming Language #1: Sorting in Java#
Java is about as far from C as you can get in this matter. C provides no
abstraction or language features specifically for polymorphism, and in
qsort
we use a low-level tool it does provide – function pointers –
to build it ourselves. In Java, however, the programming language is
explicitly object-oriented, and so the whole programming language is
designed to encourage you to leverage polymorphism, as that is one of
the pillars of object-oriented programming.
The version of polymorphism available in Java is dynamic, run-time, “late binding” polymorphism, the type of polymorphism that OOP favors. It is based off of the idea of overriding methods, either from base classes, or interfaces that a custom type (a “class”) can implement.
As I mentioned before, this is not the best match for the problem of sorting, at least not the type of sorting we’re talking about. Run-time polymorphism means that every individual element could potentially have a different comparison procedure, which is unlikely. The possibility of such a thing happen increases the cognitive load.
Nevertheless, Java does support polymorphic sorting, and it’s useful to discuss specifically because it does show how OOP-style polymorphism works when applied to such a problem.
There are many methods that do sorting in Java. Some of
them
take an explicit argument to convey how to do comparisons, just like the
qsort
example. But more commonly, we sort according to what Java refers
to as the “natural order” of the elements, as (for example) in
this overload
of Collections.sort
, with the following signature:
public static <T extends Comparable<? super T>>
void sort(List<T> list)
This sorts a list of elements of type T
, where “list” in Java can refer
to any of a number of collections that store data in order, such as in
a single allocated array (ArrayList
) or a linked list (LinkedList
).
Therefore, it is not only polymorphic in how to compare the elements,
but also in how to navigate through the list.
It needs to know about the same traits of type T
that qsort
does.
Some are not polymorphic: for this method to make sense, we know that
T
must be a reference type, that it must be boxed (that is, it must
use indirection), and that therefore the size of an element is always
the natural pointer size of the platform, and swapping the element only
involves swapping the pointers.
But there’s no getting around the polymorphism of comparisons, and so
we see this strange annotation on the function signature: <T extends Comparable<? super T>>
. This indicates that T
must implement
the interface Comparable
– implement in this context is called
extends
. Specifically, it must implement that interface in such a way
that it can be applied to other elements of type T
(which means that
it uses T
or some “supertype” of T
).
The notation is complicated, because the semantics are complicated.
Technically, T
could be comparable to a parent type of T
, and that
would still work. In fact, T
could refer to an entire class hierarchy
of types derived from some base class, all of them comparable in different
ways to objects elsewhere in the hierarchy and to objects derived from
a yet further base class. Objects of type T
could even be comparable
to any arbitrary object – and all of this is covered in
<T extends Comparable<? superT>>
, trying to express at compile-time
what will cause the type T
to be a reasonable type to use for sorting.
But this is all just an extra check that the compiler can do at compile-time to prevent run-time errors, because all of the information on how to do the comparisons is available at run-time. In fact, other methods don’t use such formal prerequisites at all, preferring to query at run-time for appropriate interfaces, throwing an exception if they are not present.
In all of these cases, the comparison is the “natural
ordering,” which is defined to mean that comparison is
done through a Java interface. Specifically, these methods use the
Comparable
interface, which specifies a method, compareTo
, which must take an
implicit this
parameter and an explicit parameter of the type being
compared to, and, like the comparison functions in qsort
, must then
return an integer whose sign indicates whether the first value was
greater or the second (with zero indicating equality).
This natural ordering is defined on a per-type basis. Each type can
only implement Comparable
once. Fortunately, the regular built-in
types, all the ones we are likely to use, all come with good natural
orderings. For example, this code all works:
import java.util.*;
public class Sort {
public static void main(String[] args) {
List<String> argList = Arrays.asList(args);
Collections.sort(argList);
for (String arg : argList) {
System.out.println(arg);
}
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(3);
list.add(2);
list.add(4);
Collections.sort(list);
for (int i : list) {
System.out.println(i);
}
}
}
See it in use:
$ java Sort b c a
a
b
c
1
2
3
4
$
It gets a little less coherent when we mix different types of object
in the same list, which Java lets us represent in the type system
by using Object
, which is a type that can store a reference to any
non-primitive (including boxed primitives):
import java.util.*;
public class Sort {
public static void main(String[] args) {
List<Object> list = new ArrayList<Object>();
list.add(1);
list.add("Hi");
Collections.sort(list);
for (Object i : list) {
System.out.println(i);
}
}
}
While the Java runtime allows us to create such a collection, the
type system does not allow us to use Collections.sort
to sort it,
as Object
does not provide us enough information to make sure these
elements properly can be compared to each other (which in fact, they
cannot, as comparing strings to integers is not defined in Java’s
“natural ordering”):
$ javac Sort.java
Sort.java:9: error: no suitable method found for sort(List<Object>)
Collections.sort(list);
^
method Collections.<T#1>sort(List<T#1>) is not applicable
(inference variable T#1 has incompatible bounds
equality constraints: Object
lower bounds: Comparable<? super T#1>)
method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
(cannot infer type-variable(s) T#2
(actual and formal argument lists differ in length))
where T#1,T#2 are type-variables:
T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error
$
So how does this work? What is a Java interface? What are its advantages or disadvantages?
Well, Java has two types of values: primitives on the one hand, and
object references on the other. In order to use interfaces, or polymorphism
at all, we must be dealing with objects. For primitives, there are separate
methods for sorting various types of arrays in the Arrays
class. As
primitives cannot be stored directly in collections, Collections
doesn’t have to deal with them.
So, to use this polymorphism through interfaces, we must be dealing with
objects. Objects in Java are a rich, standardized data structure, which
is why it’s possible to query at run-time which interfaces an object
supports. Objects contain not just the fields that the Java programmer
specifies, but additional metadata that includes implementations of
any supported interfaces, including Comparable
. That metadata can be
used to find the right version of the compareTo
method to use to sort
objects of type T
. Once we have a T
, we can query it at run-time
to find the compareTo
method. Theoretically, Java might query every
object separately as it sorts, with a separate query for each comparison,
although I trust that modern Java will in many cases realize that the
method will be the same for each object, and figure out a way to optimize
it out.
As a programmer of a type, we simply declare at the top of the class that
our type Foo
, for example, implements Comparable<Foo>
, and then lower
down include our implementation of compareTo
among our methods with the
override
keyword. Based on that, Foo
objects will be created with
the correct metadata such that Java will know to use that method for
comparison when sorting, whether the type is known at compile-time
or at run-time. We can implement our own version of compareTo
that has a different type than the typical “natural ordering” one
would expect from the state that is contained in a Foo
:
import java.util.*;
public class Sort {
private static class Foo implements Comparable<Foo> {
int inner;
public Foo(int inner) {
this.inner = inner;
}
@Override public int compareTo(Foo foo) {
// Less and greater are swapped by this compared to int
// comparison
if (foo.inner > this.inner) {
return 1;
} else if (foo.inner < this.inner) {
return -1;
} else {
return 0;
}
}
public String toString() {
return "" + inner;
}
}
public static void main(String[] args) {
List<Foo> list = new ArrayList<Foo>();
list.add(new Foo(3));
list.add(new Foo(4));
list.add(new Foo(1));
list.add(new Foo(2));
Collections.sort(list);
for (Object i : list) {
System.out.println(i);
}
}
}
Here is the output:
$ java Sort
4
3
2
1
$
Built-in types such as String
and Integer
already provide
their own compareTo
override methods, corresponding to more
typical implementations of comparisons. Only the author of each
type can provide information on how the types are to be compared
in this way. To get around this, you can use a wrapper type for
each element (like Foo
), or you have to fall back on passing in
the comparison function the old-fashioned way, like in qsort
–
though in Java passing in a function is accomplished here through
yet another interface, Comparator
, as in this alternative
function:
public static <T> void sort(List<T> list,
Comparator<? super T> c)
Here, Comparator
is effectively a function pointer with context, but
it’s expressed as an interface so that you can write a concrete class
that implements the desired function. Fundamentally, Rust and C++
do something similar.
So, how are we to evaluate this system? It’s not particularly designed for situations like sorting. The run-time system is built for the heterogeneous containers, where each individual element of a collection might have a different opinion on how to compare itself to the others. The amount of run-time flexibility is overkill to the situation.
Rather than providing one sorting function pointer, as in the C example, each object comes with its own infrastructure for finding out how to not only sort, but do every other thing that Java might want to do polymorphically with that object, such as convert it to a string, or hash. While the infrastructure is well-optimized and performant for the assumption of heavy use of OOP-style polymorphism, it clearly doesn’t hold to the C++ or Rust performance ideals of not paying for what you don’t use, instead opting to pay an up-front cost under the assumption that any and all objects will regularly be used polymorphically, in OOP style.
The type system in Java is conceptualized as a way of preventing
errors, a layer of safety on top of a more Smalltalk-like natural
OOP state. In Smalltalk any method can be invoked on any object,
and it’s simply a run-time error if that method isn’t available. In
Java, the types form a more rigorous layer to check to make
sure our method calls have correct semantics, allowing errors
to be caught earlier, at compile-time (although Java type errors
are also sometimes caught at run-time). The power of the more ideologically
pure form of OOP is still available in Java, as evidenced by the
signature on the Arrays.sort
method alluded to above (and documented
here.
It is deprecated, but still possible:
public static void sort(Object[] a)
Here is a use case that succeeds:
import java.util.*;
public class Sort {
public static void main(String[] args) {
Arrays.sort(args);
for (String arg : args) {
System.out.println(arg);
}
}
}
Here is the output:
$ java Sort a c b
a
b
c
$
Here is a use that fails:
import java.util.*;
public class Sort {
public static void main(String[] args) {
Object [] array = new Object[2];
array[0] = new Integer(0);
array[1] = "Hi";
Arrays.sort(array);
for (Object obj : array) {
System.out.println(obj);
}
}
}
It outputs:
Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
at java.base/java.lang.String.compareTo(String.java:125)
at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
at java.base/java.util.Arrays.sort(Arrays.java:1249)
at Sort.main(Sort.java:8)
The cost of this is acceptable in Java but not in Rust or C++, or C for that matter. Every object must contain individual metadata if it is to be sortable through a polymorphic function, and it must be boxed. In C++ or Rust, we must be able to sort arbitrary unboxed data, without extra metadata included directly within it. But in Java, all types except for primitives are boxed, only boxed types support polymorphism, and they do so at the cost of additional data in each heap allocation to do so. And it works, for Java’s goals, of being a garbage-collected OOP language with a layer of types to expose errors at compile-time.
As the C example shows, this cost isn’t intrinsic to run-time polymorphism in general, but it is intrinsic to OOP-style polymorphism. OOP uses run-time polymorphism at an individual object level as one of its core features, even when the function does not need to be conveyed on a per-element basis, but only once.
Programming Language #2: Sorting in C++#
C++, of course, supports this type of run-time polymorphism. We could,
if we wanted, build a system like Java’s, where we had an abstract class
Comparable
that we could use to add run-time data to show every object
of a type how to be compared with every other object. We could require
that collections to be sorted contain classes that inherit from – in C++,
inheritance and interface implementation are the same – Comparable
.
C++’s run-time polymorphism could be used to implement sorting in the
exact same way as Java.
But that’s not how sorting is implemented in C++. Sorting, in C++, uses a completely unrelated mechanism of templates. Templates are C++’s mechanism for static, compile-time polymorphism, just as virtual functions and inheritance are C++’s mechanism for dynamic, run-time polymorphism (of a classical OOP variety that closely resembles Java). In spite of them both being forms of polymorphism, and having many overlapping use cases, templates and virtual functions are completely unrelated features.
I have seen people argue that templates and virtual functions are justified in being completely unrelated, because every situation clearly calls for one or the other. But if it’s possible to do sorting with run-time polymorphism, as we see from Java, then clearly the distinction is not clear-cut as all that. What’s to stop a former Java programmer from using C++’s run-time polymorphism to implement their own sorting function a la Java, even though that’s not idiomatic C++? There’s clearly some level of overlap in use cases, even if not in semantics!
So, how do templates actually work?
Caveat for modern C++ fans: I’m going to save concepts for the end. They don’t actually substantially affect my point (as I will explain). I think it’s simpler to talk about pre-concepts C++ at first, and then discuss how concepts impact (or rather, don’t really impact) the equation.
Templates are a form of macro system. A template (class template, function template, type alias template, etc.) is given parameters at compile-time. Once the template is given parameters, it is instantiated and stamps out a concrete component of the program (a class, function, type alias, etc.).
So, that’s quite abstract. This is a situation where an example can help a lot. In line with our theme, we’re going to write a template that involves comparisons: given two values of any type that you can compare (and we’ll have to decide what that means), which is bigger?
template <typename T>
T max_value(T a, T b) {
if (a < b) {
return b;
} else {
return a;
}
}
When we actually invoke it, we provide a type for T
, giving us
a specialized function where T
is replaced by that type.
std::cout << max_value<int>(3, 4) << std::endl;
std::cout << max_value<std::string>("hi"s, "hello"s) << std::endl;
The mere mention of max_value<int>
creates a function max_value<int>
,
and likewise for max_value<std::string>
. This function is the template,
with the template parameter in brackets standing in for T
.
Of course, for function templates, specifying the T
is optional,
as C++ can infer it, so this code works equally well:
std::cout << max_value(3, 4) << std::endl;
std::cout << max_value("hi"s, "hello"s) << std::endl;
So, what are the resulting functions? It’s very similar to as if we had written:
int max_value(int a, int b) {
if (a < b) {
return b;
} else {
return a;
}
}
std::string max_value(std::string a, std::string b) {
if (a < b) {
return b;
} else {
return a;
}
}
These are separate functions. The compiler will simply generate as many
separate versions of max_value
as it needs to. It outputs separate
assembly language for each of them, and treats them as function overloads,
meaning that it uses the static (compile-time) type of the parameters
to figure out which function to call.
So, from the perspective of someone reading the code, we call
max_value
twice, and it figures out how to do its thing on an int
or a std::string
. It’s polymorphic, as it does the same algorithm
(finding max) with an operation that changes based on type (<
). But
from the perspective of someone reading the outputted assembly, it’s
not polymorphic – we’ve simply got two different functions that do
max_value
in two different ways.
In other words, we’ve gone from polymorphic code (compile time) to monomorphic code (run time). This is why Rust calls its equivalent to template instantiation “monomorphization.” This is also why it’s called “compile time polymorphism” – it is no longer polymorphic at run-time.
The advantage: This is a zero-overhead abstraction. We’re having the
compiler write, on our behalf, specialized code for each type. We
do not need each element to have virtual function metadata to
indicate how to do comparisons, nor do we even need a function
pointer like with qsort
. It’s as optimal as specialized hand-written
code, but we didn’t have to do the specialization.
The disadvantage: We have to know the type at compile-time. This prevents heterogeneous containers from being possible with this style of polymorphism. This type of polymorphism can only be based off of the compile-time type, not based off of changing run-time types. It is the exact opposite of “late binding” – the binding is done at compile-time. So, this could not be used for polymorphism over different types of widgets in a list of widgets.
The other disadvantage: Compile times take longer and the resultant binary is larger. (Eh, shrug.)
So what operations are needed to support this template? What definition
are we using for “comparable type” for T
? We’re not explicitly using
any at all, but note that if the type T
doesn’t support the <
operator,
this code will simply fail to compile:
class Foo {
};
max_value(Foo{}, Foo{});
Giving the error:
test.cpp: In instantiation of ‘T max_value(T, T) [with T = main()::Foo]’:
test.cpp:22:14: required from here
test.cpp:8:11: error: no match for ‘operator<’ (operand types are ‘main()::Foo’ and ‘main()::Foo’)
8 | if (a < b) {
| ~~^~~
This goes away if we give it the <
operator.
class Foo {
public:
bool operator <(const Foo &other) const {
return false; // All Foos are created equal!
}
}
max_value(Foo{}, Foo{}); // Now compiles
If we’d written max_value
differently, however, using >
instead,
this might not have made the error message go away. It turns out that <
is the conventional operator to use for comparisons, however, the C++
equivalent to Java’s Comparable
, the defining function for “natural
order” by convention.
Is that all that’s required to make max_value
work? It turns out no,
as many an astute C++ programmer has probably already noticed. There is
another operation besides operator<
required to make max_value
work,
and this is because I intentionally made a mistake (so I could reveal
it later to show how subtle templates can be).
Let’s take a look at the instantiation for std::string
again,
just the signature:
std::string max_value(std::string a, std::string b);
Is that how we’d write max_value
by hand for std::string
? No, we
wouldn’t. We’d write const std::string &a
, and take it by reference,
so that no new objects are initialized in the comparison and return.
If you’re not a C++ programmer, this might seem shocking, but max_value
as we wrote it requires the type to be passable by value, which is a
capability that a type might not have:
class Foo {
public:
Foo() = default;
Foo(const Foo&) = delete;
bool operator <(const Foo& other) const {
return false; // All Foos are created equal
}
};
max_value(Foo{}, Foo{}); // Error! Error!
So, we missed the mark, quite by accident! We had an
extra requirement besides comparison, and we can fix that
by taking the value by (const
) reference (which is what
std::max
does
anyway), which also implies returning by reference:
template <typename T>
const T &max_value(const T &a, const T &b) {
if (a < b) {
return b;
} else {
return a;
}
}
So what was required from T
for us to call max_value
?
In one sense, nothing besides that it should be a type! We could pass any
type in for T
, and the compiler will plug in the type and chug away,
running into errors only once it has attempted to do so! This might
actually happen several template instantiations deep, and the resulting
error shows up in the template where the operation is attempted, not
in where you use the template with an inappropriate type, which can
be confusing.
In another sense, what is required is that we pass types that make
max_value
compile, so in this case, ones that support operator <
.
However, there is no guarantee or check that the type is making the
semantic promises that correspond to that type. Sorting, for example,
requires that that operator work in such a way as to define a strict
equivalence class. If that operator doesn’t in fact do that, std::sort
will compile but won’t work properly.
It seems reasonable in this case to expect people to use operator <
for less-than as it’s such a well-established and fundamental operator.
But templates can also invoke named methods. What if somebody writes
a template that calls some_t.foo()
expecting it to do one thing,
and someone calls that template with an unrelated class that has a
type-compatible foo
method, but with different semantics? There is no
indication to the compiler, when you write the class, that you intend
for foo
to be appropriate for use in the template. We didn’t have to
say, when we wrote Foo
here, that our operator <
was valid for
std::sort
.
Concepts do help with that. You can statically assert that a class supports a concept’s requirements, and that documents your intention to support it semantically as well. Concepts can also cover stricter requirements than a template incidentally imposes, and help document the semantics of templates.
But everything about concepts is opt-in; you can always write a template that will sometimes fail on instantiation. And that makes them much less useful in my book. Don’t get me wrong: I’m glad they exist. I think C++ with concepts is better than C++ without concepts. But it only goes so far, especially when compared with Rust traits, which are mandatory for Rust’s form of compile-time polymorphism.
More relevant than all of this, to me, is that templates and OOP work so differently than each other. Run-time polymorphism and compile-time polymorphism are just completely different beasts. Students are taught the OOP style run-time polymorphism, and that doesn’t really help them understand templates, or even get started doing so. Again, I feel C++ is too big.
But, at least it has this zero-overhead abstraction, without requiring a method look-up and an indirection for every item to be sorted.
std::sort
, by the way, takes iterators. These iterators must be
value swappable legacy random access iterators, and that’s just a
subset of the requirements, as seen in std::sort
’s CPPReference
page. The way to
get from one element to another (and therefore implicitly the size),
the way to swap elements, and the way to compare them are all implicitly
derived from RandomIt
, the type parameter specifying the type of the
iterator (at least in the overloads of std::sort
that do not take an
explicit comparator).
Programming Language #3: Sorting in Haskell#
Now for Haskell!
We’re mostly talking about Haskell to move on to talking about Rust, as this is a Rust-focused blog. There’s a lot going on with Haskell typeclasses that I won’t have time to get into here.
Haskell is where Rust got traits from, although Haskell calls them typeclasses. Incidentally, Haskell uses run-time polymorphism where Rust uses compile-time polymorphism, but the semantics are more similar than you might expect from that statement.
In Haskell, like Java, all types that sort
accepts are boxed, covering
size and swapping among the traits that might need to be customized.
Unlike Java, the operations we need to perform on values of this type
are passed to sort
once, rather than looked up on a per-element basis.
Here is the type for sort
:
sort :: Ord a => [a] -> [a]
a
here is like T
in C++: a type variable that can be replaced
with any type. As in Java, this is subject to type erasure: sort
just operates on generic boxed values. Any comparison-specific operations
it needs come from the Ord a =>
, which constrains a
to types that
have instances of the Ord
typeclass.
Here is the definition of Ord
:
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
(<), (<=), (>), (>=) :: a -> a -> Bool
max, min :: a -> a -> a
compare x y = if x == y then EQ
-- NB: must be '<=' not '<' to validate the
-- above claim about the minimal things that
-- can be defined for an instance of Ord:
else if x <= y then LT
else GT
x < y = case compare x y of { LT -> True; _ -> False }
x <= y = case compare x y of { GT -> False; _ -> True }
x > y = case compare x y of { GT -> True; _ -> False }
x >= y = case compare x y of { LT -> False; _ -> True }
-- These two default methods use '<=' rather than 'compare'
-- because the latter is often more expensive
max x y = if x <= y then y else x
min x y = if x <= y then x else y
It defines many methods that an instance of Ord
can support.
These methods are functions defined in terms of each other; you
must specifically implement at least one of them for your type to prevent
infinite regress. Minimally, either compare
or <=
is sufficient,
with compare
recommended for more complex types.
Unlike in C++, when you define these methods, it is not enough to simply
define a function called <=
or compare
. Haskell won’t even let you
define functions with the same fully qualified name as the methods,
which exist in the same namespace as any other functions. Unlike
C++, Haskell does not have function overloading, and any time the
same fully qualified name has different semantics for different types,
it is through this mechanism of typeclass
es. Like in Java,
you have to explicitly declare your intention to implement the methods
as found in Ord
, by writing an instance
explicitly, like so:
import Data.Ord
import Data.List
data Foo = Foo Integer
deriving Show
instance Eq Foo where
(Foo a) == (Foo b) = a == b
instance Ord Foo where
(Foo a) <= (Foo b) = b <= a
main = do
let list = [Foo 3, Foo 4, Foo 2]
print $ sort list -- outputs [Foo 4,Foo 3,Foo 2]
Note that the instance
declarations are separate from the definition
of the type! The module where the type is declared can define them, but
so can the module where the typeclass
is declared. Other modules
are not allowed to by default to make sure there is only one canonical
definition of an instance for a given type and typeclass.
How does this actually work then? Well, Ord a
is a secret parameter
to sort
. Haskell will create a bundle of function pointers for us
that represent the specific Ord
instance for whatever type we pass to
sort
, either from knowing the type statically at that point, or passing
along a bundle passed into whatever called sort
. So this compiles to
something quite similar to the C qsort
(at least as far as polymorphism
is concerned), taking in a comparison function. The big difference is,
Haskell will choose the comparison function for us – but it is one
comparison function, not one comparison function per item as in Java.
Programming Language #4: Sorting in Rust#
So, how does Rust do all of this?
As I said, a Rust trait
is very much
like a Haskell typeclass. Rust’s main sort
method,
like Haskell, requires the Ord
typeclass
trait. Like Haskell,
it even has provided (but overrideable) methods as well as required
methods:
pub trait Ord: Eq + PartialOrd {
// Required method
fn cmp(&self, other: &Self) -> Ordering;
// Provided methods
fn max(self, other: Self) -> Self
where Self: Sized { ... }
fn min(self, other: Self) -> Self
where Self: Sized { ... }
fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized + PartialOrd { ... }
}
Like typeclasses, to indicate that a type has a trait requires a specific block that says what trait we’re trying to implement, and lists the implementation of the required methods. Like in Haskell, that block may reside in the crate where the trait is defined, or the trait where the type is defined. Like in Haskell, this allows us to add polymorphism to previously unpolymorphic operations without having to create wrapper types.
Here is an example of implementing this trait (unfortunately, we
have to implement both Ord
and PartialOrd
):
use std::cmp::Ordering;
#[derive(PartialEq, Eq, Clone, Copy, Debug)]
struct Foo(u32);
impl PartialOrd for Foo {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl Ord for Foo {
fn cmp(&self, other: &Self) -> Ordering {
other.0.cmp(&self.0)
}
}
fn main() {
let mut foos = vec![Foo(3), Foo(4), Foo(1), Foo(2)];
foos.sort();
println!("{:?}", foos); // Displays [Foo(4), Foo(3), Foo(2), Foo(1)]
}
It’s very similar to Haskell, but with “C-like” syntax and aesthetic. The syntax for the functions using the trait looks like C++ templates:
fn max<T: Ord>(a: T, b: T) -> T {
if b > a { b } else { a }
}
What’s different from Haskell is how it’s implemented. The semantics
are quite similar, and the Rust implementation can be thought of
as an optimization of the Haskell semantics. Instead of passing in
to sort()
a secret run-time parameter with Foo
’s implementation
of Ord
, the function is monomorphized. We can think of it as
inlining just that one parameter at compile-time, and generating
a specialized function.
Yes, this implementation is fundamentally very similar to C++’s implementation of templates. It’s basically the same in terms of machine code and resulting optimizations. But the semantics are more Haskell-like. Polymorphic functions are type-checked once. They may only use functionality incorporated in the traits at hand. We don’t postpone the type-checking for the template instantiation.
What’s more, the same mechanism is also used for Rust’s run-time
polymorphism, where we can have a type like dyn MyTrait
for
some specific traits that are object-safe. These trait object
types are like OOP polymorphic types, in that each value has its
own copy of the table of polymorphic functions with it, but the
copy is outside the original object. It is a property of the
pointer, not of the object, and implemented with fat pointers.
Like with any other trait, the trait implementation is separate from the type definition or the trait definition (though it must live in the same crate as one of them). Unlike C++, there is one system for polymorphism that can be used in both run-time and compile-time ways, with overlap where possible.
Conclusion#
I hope this shows, if nothing else, that polymorphism itself can take many forms in many programming languages beyond the OOP variety of it. The OOP variety is in some senses self-propagating – if you optimize your language for it as in Java, then it makes sense to use for everything, even if it’s not what you would choose in a language that has other options.
For many forms of polymorphism, in C++ (for templates), Haskell, and Rust, no inheritance is necessary. It is simply not built according to the OOP frame of mind. I personally think Haskell and Rust are doing it right here, as is perhaps obvious from how I’ve written about it.
I hope to write more about run-time polymorphism in Rust, and how it differs from the C++ variety, and how you can manually implement other types of run-time polymorphism if you want. This would be a future post. But, this is a hobby blog, so no promises on timeline!
Subscribe
Find out via e-mail when I make new posts! You can also use RSS (RSS for technical posts only) to subscribe!
Comments
If you want to send me something privately and anonymously, you can use my admonymous to admonish (or praise) me anonymously.
comments powered by Disqus