Generics implementation approaches

I want to introduce you to generics implementation approaches with some simple examples everyone can understand. The description of each approach includes key features without details. Basic examples are written in PHP because I'm a PHP developer, but there are also Hack/Java/C++ examples.

Type erasure

This approach means generics arguments are dropped after compilation.

Before type erasure:

<?php

class Container<T> {

    private T $data; 

    public function __construct(T $data) {
        $this->data = $data;
    }  
}

$intContainer = new Container<int>(1);

After type erasure:

<?php

class Container {

    private $data; 

    public function __construct($data) {
        $this->data = $data;
    }  
}

$intContainer = new Container(1);

You can't do that because it doesn't make sense after type erasure:

<?php

class Container<T> {       

    public function foo($data) {
        $className = T::class;

        T::staticFunction();

        $newObject = new T();

        if($data instanceof T) {

        }
    }  
}

During static analysis and compile time generics types can be reflected and checked, but after type erasure at run time, this is not possible. This approach has a small performance/memory effect and some generics types restrictions (see example above).

Type erasure generics visibility table for better understanding:

	static analysis time	compile time	runtime
type reflection	yes	yes	no*
type checking	yes	yes	no

no* - generics types of some languages like Java/Hack may be reflected and not used by VM at runtime.

I can assume the PHP Psalm annotations are a kind of type erasure generics, but there is no such thing in PHP as generic types at compile/run time. PHP Psalm annotations visibility table:

	static analysis time	compile time	runtime
type reflection	yes	no	no
type checking	yes	no	no

Let's look at a real example of type erasure generics in Java:

test.java

class Container<T> {

  private T data;

  public void set(T data) {
      this.data = data;
  }
}

class Programm {
    public static void main(String[] args) {
        Container<Integer> intContainer = new Container<Integer>();
        intContainer.set(1);

        Container<String> stringContainer = new Container<String>();
        stringContainer.set("hello");
    }
}

Use these commands to compile and run the script above:

docker run -it --rm -v $PWD:/app -w /app openjdk:latest javac test.java
docker run -it --rm -v $PWD:/app -w /app openjdk:latest java Programm

If you try to pass string "hello" to intContainer.set() you will get a compile time error:

test.java:13: error: incompatible types: String cannot be converted to Integer
        intContainer.set("hello");
                         ^

Reification

Generic arguments are retained at compile/run time and can be reflected.

There is a real example of reified generics in Hack. The keyword reify is very important to mark a generics as reified.

test.hack

class MyContainer<reify T> {
    private T $var;

    public function set(T $var): void {
        $this->var = $var;
    }
}

<<__EntryPoint>>
function main(): void {
  $intContainer = new MyContainer<int>();
  $intContainer->set(1);

  $stringContainer = new MyContainer<string>();
  $stringContainer->set("hello");
}

You can run the script above with command:

docker run -it --rm -v $PWD:/app -w /app hhvm/hhvm:latest hhvm test.hack

If you try to pass string "hello" to $intContainer->set() you will get a compile time error:

Fatal error: Uncaught TypeError: Argument 1 passed to MyContainer::set() must be an instance of int, string given in /app/test.hack:6

At runtime, there is only one class MyContainer with many generic types. Let's look inside the $stringContainer variable by var_dump():

object(MyContainer) (2) {
  ["86reified_prop"]=>
  vec(1) {
    dict(1) {
      ["kind"]=>
      int(4)
    }
  }
  ["var":"MyContainer":private]=>
  string(5) "hello"
}

The example above describes the MyContainer class and the kind property. I think kind => 4 is a constant for type string. It means you can get the generics type at runtime.

This approach has a small performance/memory effect. Nikita Popov already had an attempt to implement this type of generics in PHP.

Reified generics visibility table:

	static analysis time	compile time	runtime
type reflection	yes	yes	yes
type checking	yes	yes	yes

Monomorphization

A new class is generated for each generic argument combination.

Before monomorphization:

<?php

class Container<T> {

    private T $data; 

    public function __construct(T $data) {
        $this->data = $data;
    }  
}

$intContainer = new Container<int>(1);

After monomorphization:

<?php

class ContainerForInt {

    private int $data; 

    public function __construct(int $data) {
        $this->data = $data;
    }  
}

$intContainer = new ContainerForInt(1);

This approach has a big memory effect. PHP doesn't support native generics, but you can test monomorphic generics with my library.

Monomorphic generics visibility table:

	static analysis time	compilation time	run time
type reflection	yes	yes	no
type checking	yes	yes	yes

C++ templates are a real example of monomorphization:

test.cpp

template <class T> class MyContainer
{
    private:
     T data;

    public:
     void set(T _data)  {
        data = _data;
     }
};

int main () {
  MyContainer<int> intContainer;
  intContainer.set(1);

  MyContainer<const char*> stringContainer;
  stringContainer.set("hello");

  return 0;
}

You can compile and run the script above with commands:

docker run -it --rm -v $PWD:/app -w /app gcc:latest g++ test.cpp -o test
docker run -it --rm -v $PWD:/app -w /app gcc:latest ./test

If you try to pass string "hello" to intContainer.set() you will get a compile time error:

test.cpp: In function 'int main()':
test.cpp:15:20: error: invalid conversion from 'const char*' to 'int' [-fpermissive]
   15 |   intContainer.set("hello");
      |                    ^~~~~~~
      |                    |
      |                    const char*
test.cpp:8:17: note:   initializing argument 1 of 'void MyContainer<T>::set(T) [with T = int]'
    8 |      void set(T _data) {
      |               ~~^~~~~

This approach increases compile time, but improves performance runtime.

I hope it was helpful to you. Play around with the examples above - it's a really interesting process! If you want to go further, read this great article about generics.

Have a nice day!