Generics vs Templates

There are two similar features that LM supports that initially may seem very similar to the end user but in implementation they are quite different.

What is an Open Type?

An open type is any type that contains a type variable such as List<a>. This is the type of a generic list that hasn't been given a concrete parameter yet. When processing open types there are two philosophically distinct approaches to semantic code generation.

Generics are Type Erasure

Languages such as Rust or Java take the generic approach to open types. Upon encountering a generic parameter, that type parameter will be weakened down to its minimal parameterized bound. To practically use generic type parameters, each type must be given constraints that specify what behavior will be available.

For example List<a> might not be very useful because it will erase down to the bottom type List<?>. This means that we know precisely nothing about the parameter and probably can't do anything useful with it. We don't even know the size of this type.

However, by adding constraints we can specify how much information that we need about the type to use it. Now if we add more information such as List<PartialOrd> we can create a generic list for things that can be ordered. This list may now allow us to sort the elements.

Templates are Code Generation

The other major option to dealing with parameterized types is called templating and is used by languages such as C++ or Zig. Upon encountering a parameterized type in a function, a new copy of that function will be created with the function body becoming specialized to the new concrete type. Sometimes it is difficult to create a truly generic implementation of a parameterized function, so substitution becomes very handy.

For example, consider the templated == operator in the standard library. The default == operator will recursively compare all fields to see if two structures are equivalent. To accomplish this task the templated == function must in turn call specialized versions of == that correspond to each field's type. This is accomplished by creating, only upon demand, specialized versions of the library template for the == function.