Generics, Interfaces, and Polymorphism

How to do more work while writing less code

Created by Joshua Nelson with reveal.js

What are generics?

Parametric Polymorphism, known in Java as Generics, is re-using the same code for multiple types.

Before

public static String pop(ArrayList<String> list) {
  if (list.size() == 0) {
    return null;
  } else {
    return list.remove(list.size() - 1);
  }
}

After

public static <T> T pop_generic(ArrayList<T> list) {
  if (list.size() == 0) {
    return null;
  } else {
    return list.remove(list.size() - 1);
  }
}

Why is this better?

Exactly the same code, but now it works for all types.

How do they work?

  • Java: Type Erasure
  • C++ and Rust: Monomorphization
  • Python: Duck Typing

Type Erasure

  • Mainly used by Java (not sure if there are any other languages?)
  • Only works on pointers
import java.util.ArrayList;

class Main {
  public static void main(String[] args) {
    ArrayList<int> list = new ArrayList<>();
  }
}
non-pointer-generics.java:5: error: unexpected type
    ArrayList<int> list = new ArrayList<>();
              ^
  required: reference
  found:    int
1 error

Type Erasure

  • Works at runtime: everything is boxed, so it's all the same size (Why is this important?)
  • Workaround for primitives: box them!
  • Can be compiled ahead of time

You can write and compile a .class file that works for types you don't know about yet.

Monomorphization

  • Used by C++, D, Rust
  • Works on any type, not just pointer types
  • Cannot be compiled ahead of time
    • 'Template hell' - this is why C++ is slow to compile
    • Pre-compiled headers (misnomer) - compare .rlibs in Rust

Monomorphization

  • Results in more efficient code at run time, but also more code.
  • In particular, there's a separate copy of the function for each type.

Duck typing

  • Used by Python, JavaScript
  • If there's no types, no need to say which types the function works for!
  • Works similarly to type erasure, but not checked at compile time
def pop(list):
  list.pop()
  • You can replicate duck typing in Java with reflection.
  • This is not recommended, though.
  • See example with add if you really want to know (it's ugly).
public double add(Object t) throws ReflectiveOperationException {
    return new 1.0 + (double) t.getClass().getMethod("doubleValue").invoke(t));
}

Restricting types

  • Everything so far works on arbitrary types
  • Most flexible for the user; very limited for the implementor
  • How do you add two numbers generically?

(playground)

pub fn add<T>(a: T, b: T) -> T {
    a + b
}
  • Need to declare 'properties' of the type

Interfaces

  • Similar to type erasure: variables are boxed
  • 'This function takes this interface'

More info

public static int length(CharSequence seq) {
  return seq.length();
}
  • Go calls them interfaces, so it's getting lumped in with Java
  • Not entirely sure if this is boxed or not.
func MyAbs(a Abser) float64 {
  return a.Abs()
}

Traits and Type-classes

  • 'This function takes a specific type that implements an interface'

    • Rust interfaces are called 'traits'.
    • Haskell interfaces are called 'type classes'.

Rust example (More info) 

pub fn add<T: std::ops::Add<Output = T>>(a: T, b: T) -> T {
    a + b
}

Haskell example (More info) 

add :: (Num a) => a -> a -> a
add a b = a + b

C++ Templates

  • C++ has these, but ... weird

This works exactly when T has operator +

template<typename T> auto add(T a, T b) -> decltype(a + b) {
    return a + b;
}
  • But if there's no operator, there's not necessarily an error! 
    // This version works only with strings
void add(const char *a, const char *b) {
  return;
}
  • Duck typing, but at compile time!
  • This is called 'SFINAE': Substitution Failure Is Not An Error.