An Overview of Generic Programming: Writing Code With Arbitrary Types

Generic Programming is a specialized form of programming in some languages (primarily statically typed languages) where code is written to process objects of any arbitrary type. The distinction between generic programming and normal programming is when writing generic code the “type” (often denoted T) of the data is not explicitly stated. The generic programming paradigm is challenging to master because it requires a high level of abstraction (ignoring the type of data in its entirety).

Languages, like C++ (templates), Java, C#, and soon Golang, have built-in support for generic programming and include a large standard library of generic collections and data structures.

Table Of Contents

What Does Generic Programming Look Like?

Here’s an example of a generic list in C#¹:

 1// Define a List of ANY type where the type is denoted as T
 2public class MyList<T>
 3{
 4    // Store a list of items of type T
 5    private T[] items;
 6
 7    // Add an item to the list
 8    public void Add(T item)
 9    {
10        // Add item to the list
11    }
12}

Here’s an example of the same generic list in Typescript²:

 1// Define a List of ANY type where the type is denoted as T
 2class MyList<T> {
 3    // Store a list of items of type T
 4    items: T[];
 5
 6    // Add an item to the list
 7    add(item: T) {
 8        this.items.push(item);
 9    }
10}

In the above examples, the logic is the same and is type agnostic. These examples both define generics, which manage an internal array of elements (non-type specific), and have cooresponding add methods for new array elements. The genericization of these list objects allows for both implementations to work within their ecosystem and reduce duplicated code for a List of any type of data.

Back To Top

Benefits of Generic Programming

• Less boilerplate code; More business logic
• Generic code can work for any data type
• Code Duplication can be significantly reduced
• Bug fixes only have to happen in one place
• Code Reusability can be greatly increased
• Code Stability can be greatly increased
• Generics should theoretically be able to reach 100% test coverage, minimizing the chance of regressions

Back To Top

Generic Programming and Type Assumptions

With Generic types (often denoted as T but not always), no assumptions can be made about the instance type being processed. Since no assumptions of type can be made in generic code it becomes possible for the same logic to work for many types in a consistent and repeatable way. The type agnostic nature makes generics a powerful language feature, but it also makes generic code difficult to read or to understand for unaccustomed engineers.

NOTE: Strictly speaking, some languages like C# and Java have a base Object class ALL classes inherit from. In those situations, you can make assumptions about the type as long as you treat it as the base Object.

Generic programming requires a different mindset from object oriented programming because the type of the data is not explicitly stated. Instead, the focus is on how an “unknown” type is able to be manipulated without the need to know the type. A great use case, and the most common use case for generics, is data structures.

Back To Top

Other Types of Generic Programming

Generic programming is really about abstracting the type away from the code. Separating a type from code logic can be done through the use of a type parameter, but it can also be done through the use of other abstraction mechanisms in a programming language (such as interfaces or reflection).

Generics vs Interfaces

While in most languages interfaces are defined and implemented by classes explicitly this is not always the case. For example, both Go and TypeScript use implicit interfaces, not pre-declared directly on a type, and are later inferred through a type contract negotiation process. Implicit interface typing is a powerful tool.

Back To Top

Example: Explicit Interfaces

 1// Example of an interface in C#
 2public interface IStructure {
 3    // Return the structure's name
 4    string Name { get; }
 5}
 6
 7// Structure implements the IStructure interface
 8public class Structure : IStructure {
 9    public string Name { get; set; }
10}

Example: Implicit Interfaces

 1// Example of an interface in Go
 2type Reader interface {
 3    Read(p []byte) (n int, err error)
 4}
 5
 6type myReader struct {}
 7
 8// Implement the Reader interface
 9func (r *myReader) Read(p []byte) (n int, err error) {
10    return 0, nil
11}

Back To Top

Interfaces as Contracts

Interfaces define a contract a type must adhere to. The interface contract can then be used as the type in code, rather than the original type. This contract allows for many different types to be used, essentially genericizing the code substantially.³

If using an interface type is possible for your purposes, then it is generally the recommended method for generic programming. There are several reasons for this best practice: 1) Interfaces allow for code to use specific knowledge about a type (i.e. parameters or methods), and 2) The interface contract is type checked by the compiler at compile time.

Back To Top

Generics vs Reflection

Reflection libraries are used to inspect the type of a variable or object and perform operations on it. Generally, reflection is able to access the metadata of any object and access properties, execute methods, and manipulate values. Reflection is, however, a double edged sword.

So, why not use reflection instead of supporting generics in the language?

Reflection libraries are just that – libraries. They are limited to accessing and manipulating metadata about a type. Reflection libraries suffer from serious performance implications and are NOT statically type checked by the compiler. Due to the lack of complier support, using reflection can lead to difficult bugs, performance issues, and a large amount of code where there is no type safety.

It is also easy to misuse reflection. Reflection does not benefit from IDE support (because it only functions at runtime) or complier support. The lack of immediate feedback causes developers to use reflection in the dark until the code executes. The accessing of metadata, or the manipulation of values, is generally done using string values passed into a method. The propagation of string literals in the usage of reflection quickly becomes a technical debt issue.

Back To Top

Object Oriented Programming and Type Assumptions

In object oriented programming, the type of an object is known as the object’s class. What makes these abstract types different from generic types is the instantiated type is known at compile time. In other words, the type is explicitly defined, either by class definition or interface implementation, and methods are designed to function with a specified type.

Data Structures & Generic Programming

Data structures are patterns of data organization and manipulation used in many programming languages. The most common data structure is a list of items. Because a list is simply a collection of items, it is easy to create a generic list. The first data structure most computer science students learn is a linked list. The linked list data structure is a list of items, but each item contains a reference (or pointer) to the next item in the list.

Back To Top

Example of a Doubly Linked List

Below is an example in C# of a doubly linked list. A doubly linked list is useful for forward and backward traversal because each node contains a reference to the node before and after.

 1// Create a generic node to hold the data
 2// and its next and previous node references
 3internal class Node<T> {
 4  internal Data T;
 5  internal Node<T> Next;
 6  internal Node<T> Prev;
 7}
 8
 9// Generic Linked List
10public class List<T>
11{
12    // Store a reference to the first node in the list
13    private Node<T> Head;
14
15    // Store a reference to the last node in the list
16    private Node<T> Tail;
17
18    // Add an item to the list
19    public void Add(T item)
20    {
21        // Add item to the list
22    }
23
24    // Delete an item from the list
25    public void Delete(T item)
26    {
27        // Find item in list and delete
28    }
29}

Back To Top

Blockchain Data Structures

The most notable use of a linked list (more appropriately a stack if we want to be uppity about it) is probably the implementation of a blockchain. A blockchain is a list of blocks, each containing 1) a hash of the previous block (i.e. a pointer), 2) a timestamp, and 3) a transaction. The hash of the previous block is used to verify the block is valid.

Conclusion

Writing generic code is a lot of fun and is a great way to learn about pure algorithmic design without the hassle of typing.

The next post is going to give an introduction to the newly added generics support for Go, starting in version 1.18 (February 2022 Release Date).

Back To Top