Types and Programming Languages

Eric Rollins

I've been reading Pierce's Types and Programming Languages. I've become interested in the interactions between Parametric Polymorphism and runtime efficiency. I do have a interesting (to me :-) point at the end, but it takes a lot of introduction...

Parametric Polymorphism is the ability of a function to accept arguments of different types. An example from the programming language Standard ML is:

- fun palindrome(x, y) = (x, y, x);
val palindrome : 'a * 'b -> 'a * 'b * 'a = _fn
We have defined a function palindrome which accepts two arguments, x and y, and returns a tuple (x, y, x). When we type this definition into the Alice ML interpreter it responds that we have defined a function which takes a tuple with two components of unspecified types a and b (the single quote (') indicates it is a type variable, not a specific type) and returns (->) a three component tuple using the same unspecified types. We can invoke the function with two integer arguments like this:
- palindrome(1, 2);
val it : int * int * int = (1, 2, 1)
Here Alice says the result is a three-integer tuple. We can also invoke it with strings:
- palindrome("a", "b"); 
val it : string * string * string = ("a", "b", "a")
Or tuples of pairs of integers:
- palindrome((1,1), (2,2));
val it : (int * int) * (int * int) * (int * int) = ((1, 1), (2, 2), (1, 1))
With type annotations we can also create an explicitly statically typed (non-polymorphic) version, int_palindrome, which only accepts ints:
- fun int_palindrome(x: int, y: int) = (x, y, x);
val int_palindrome : int * int -> int * int * int = _fn
This version works for ints and produces a compile-time error for all other types:
- int_palindrome(1, 2);
val it : int * int * int = (1, 2, 1)

- int_palindrome("a", "b");
1.0-1.24: mismatch on application: expression type
   string * string
does not match function's argument type
   int * int
because type
   string
does not unify with
   int
Standard ML's type inference system will automatically restrict the arguments of a function to satisfy the operations inside it. We can define add:
- fun add(x, y) = x + y;
val add : int * int -> int = _fn
Here it has determined the arguments to plus (+) must be integers, so x and y and the return type must be integers:
- add(1, 2);
val it : int = 3

- add("a", "b");
1.0-1.13: mismatch on application: expression type
   string * string
does not match function's argument type
   int * int
because type
   string
does not unify with
   int
Here again in Standard ML the type error is found at compile-type, not run-time. Note in this case didn't need to provide type annotations.

With these examples we can categorize functions in programming languages in several different overlapping ways:

1) Dynamically typed: All type errors are found at runtime: Lisp, Perl, Python, Ruby.

2) Statically typed: All type errors are caught at compile time: C, C++, Standard ML, Haskell, Java (with generics).

3) Statically typed with type inference: type annotations can often be omitted, as the compiler can figure out the types based on usage inside the function: Standard ML, Haskell.

4) Parametrically polymorphic: functions can accept a range of types, without having to be redefined [*by the programmer*] each time: Lisp, Perl, Python, Ruby, Standard ML, Haskell, C++ Templates, Java Generics.

*By the Programmer* is key to my point, shortly. And BTW, subtype polymorphism (found in Java and C++ class inheritance) is a related, but different, beast.

In the section What Types are Good For of the Introduction Pierce lists several headline benefits, including Efficiency:

"The first type systems in computer science, beginning in the 1950s in languages such as Fortran, were introduced to improve the efficiency of numerical calculations by distinguishing between integer-valued arithmetic expressions and real-valued ones; this allowed the compiler to use different representations and generate appropriate machine instructions for primitive operations."

In the section Erasure and Typability of the chapter Simply Typed Lambda Calculus he says:

"Most compilers for full-scale programming languages actually avoid carrying annotations at run time: they are used during typechecking (and during code generation, in more sophisticated compilers), but do not appear in the compiled form of the program. In effect, programs are converted back into an untyped form before they are evaluated."

And in the section Erasure and Evaluation Order of the chapter Universal (Parametric Polymorphic) Types he says:

"In a more realistic interpreter or compiler for a programming language based on System F ... type annotations play no significant role at run time, in the sense that no run-time decisions are made on the basis of types ... For these reasons, many polymorphic languages instead adopt a type-erasure semantics, where after the typechecking phase, all the types are erased and the resulting untyped terms are interpreted or compiled to machine code." [followed by a footnote about retaining types to do run-time checks of casts]

Now dynamically typed languages typically don't make direct use of native hardware datatypes. In Java terminology they use Integer objects instead of the int primitive data type. And functions would not even be declared as accepting Integer references, instead they would accept Object references and use instanceof to dynamically determine which form of addition should be used. So at the lowest level the plus (+) method would be defined like:

static Object plus(Object x, Object y) {
  if (x instanceof Integer && y instanceof Integer) {
    Integer lx = (Integer)x;
    Integer ly = (Integer)y;
    return new Integer(lx.intValue() + ly.intValue());
  } else if (x instanceof Float && y instanceof Float) {
    Float lx = (Float)x;
    Float ly = (Float)y;
    return new Float(lx.floatValue() + ly.floatValue());
  } // else if...
}
While this type of dynamic operator choice is to be expected for interpreted languages like Perl, Python, and Ruby, I was initially surprised to find this was also the case for compiled Lisp. The Lisp compilation chapters at the end of Abelson and Sussman's Structure and Interpretation of Computer Programs and Norvig's Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp had felt unrealistic (compared to say the Dragon Book), but I hadn't pinned down why. Re-reading Norvig, in the section The Abstract Machine of the chapter Compiling Lisp I find:

"Macro-Assembler. In the translation or macro-assembler approach, each instruction in the abstract machine language is translated into one or more instructions in the computer's instruction set ... In general this will lead to code expansion, because the host computer will probably not provide direct support for Scheme's data types. Thus, whereas in our abstract machine we could write a single instruction for addition, with native code we might have to execute a series of instructions to check the type of the arguments, do an integer add if they are both integers, a floating point add if they are both floating point numbers, and so on... Microcode ... The most important architectural feature of the Lisp Machine was the inclusion of tag bits on each word to specify data types. Also important was microcode to implement certain frequently used generic operations. For example, in the Symbolics 3600 Lisp Machine, the microcode for addition simultaneously did an integer add, a floating point add, and a check of the tag bits. If both arguments turned out to be either integers or floating point numbers, then the appropriate result was taken. Otherwise, a trap was signaled, and a conversion routine was entered."

In retrospect of course they have to do this lowest level dynamic operator choice based on argument types, since they have no static type information at compile time. But the interesting part is that this is nearly inherent in parametric polymorphism. Like Lisp functions, Perl, Python, and Ruby functions don't have argument types. Perl, Python, and Ruby also have functions like Lisp's map and reduce designed to operate polymorphically on lists of items. In all these languages functions are parametrically polymorphic by default, unlike the special-case treatment in C++ and Java.

The alternative to low-level dynamic operator choice is seen in C++ templates. C++ templates allow *the programmer* to specify the function definition once, and the compiler instantiates the definition as many times as necessary. This is typically once per distinct type for which the template is used. Stroustrup does discuss the care needed to avoid code bloat with this implementation.

Java Generics implement the type erasure discussed by Pierce, above. Unlike C++, Java has a single class hierarchy rooted at Object. Unlike C++ templates, Java Generics can only be instantiated with subclasses of Object and not with primitive types like int. Type erasure was chosen so that generic code could be run on an unmodified (non-generic-aware) Java Virtual Machine. Given these restrictions there is no reason for the compiler to create multiple copies of the code, and no additional loss of potential efficiency occurs from erasing types after type-checking. Only type parameters to generics are erased, other types are still retained on objects in the JVM bytecodes for security, reflection, etc.

The interesting case (and the point) is Standard ML (and probably similar languages like Haskell). The Definition of Standard ML (Revised) spells out in excruciating detail the syntax and semantics of the language, but actually leaves open to the implementor basic decisions about low-level type representations and parametric polymorphism implementation. An initial read of the specification, and of Pierce, makes one expect that parametrically polymorphic functions would only be instantiated once. Per the discussion above this necessitates some amount of low-level dynamic operator choice, and corresponding loss of performance. This matches Appel's discussion of the SML/NJ implementation in Compiling with Continuations in 4.1 Data Representation:

"But there is a problem with many of these representations in Standard ML: Types can be abstract, so the details of their representation are not known at compile time... " [This is partly due to separate compilation, discussed below; functors are parameterized modules] "Since modules F and A can be compiled separately, there is no perfect solution to this problem. If functors in ML behaved like the "generic" modules of Ada, this problem would not exist: It is expected of an Ada implementation that each application of a "generic" will generate new code specialized to the particular argument. But in ML the intent of the designers was that machine-code generation (and type checking, etc.) needs to be done only once for each functor, and is independent of the actual parameter to the functor. In the implementation of Standard ML of New Jersey, we wished to avoid the functor problem, and we wanted to avoid too many constraints on the runtime system."

The MLton Standard ML compiler gets around these limitations by using whole-program compilation: all the source files are read at once, so all definitions are available. Separate compilation is not supported. Unlike SML/NJ, MLton in its Compiler Passes uses an Elaborate pass which duplicates a functor body wherever it is applied, and a Monomorphise pass which duplicates each function with each type usage. A later RemoveUnused optimization pass removes all unused functions, so code bloat is avoided. This implementation makes it possible for MLton to achieve high performance with the use of native machine datatypes (integers, reals, unboxed arrays, etc.) and presumed avoidance of low-level dynamic operator choice.

SML/NJ was partly limited by the goal of maintaining an interactive interpretive environment. As the ML specification states: "ML is an interactive language". As shown with Alice ML above, in an interactive language new function definitions and uses (and even new types) can be entered on the fly, so of course the system doesn't know all the types ahead of time. MLton is only a standalone compiler, so it doesn't have this limitation.

C++ and Ada compilers do support separate compilation, so it should be possible to implement ML-style parametrically polymorphic languages efficiently with separate compilation. Alternately byte-code-interpreter based implementations (like Alice ML) or even dynamically typed languages (like Lisp or Python) can use a just-in-time compiler which uses runtime-acquired type information to instantiate optimized monomorphized implementations of polymorphic functions (see Psyco Python for a working example). The downside of JIT is the initial overhead of the complete interpreter plus optimizing compiler bundled with your executable. This doesn't help if our goal is a fast-as-but-higher-level-than-C language on the IBM Cell processor, which limits you to 256K code plus data per core...