Introduction to Programming Languages/Template Oriented Programming

Template Oriented Programming

High-order functions foster a programming style that we call template oriented. A template is an algorithm with "holes". These holes must be filled with operations of the correct type. The skeleton of the algorithm is fixed; however, by using different operations, we can obtain very different behaviors. Let's consider, for instance, the SML implementation of filter:

fun filter _ nil = nil
  | filter p (h::t) = if p h then h :: (filter p t) else filter p t

An algorithm that implements filter must apply a given unary operator p on each element of a list. Nevertheless, independent on the operation, the procedure that must be followed is always the same: traverse the list applying p on each of its elements. This procedure is a template, a skeleton that must be filled with actual operations to work. This skeleton can be used with a vast suite of different operators; thus, it is very reusable.

This programming style adheres to the open-closed principle that is typically mentioned in the context of object oriented programming. The implementation of filter is closed for use. In other words, it can be linked with other modules and used without any modification. However, this implementation is also open for extension. New operations can be passed to this algorithm as long as these operations obey the typing discipline enforced by filter. Filter can be used without modification, even if we assume that new operations may be implemented in the future, as long as these operations fit into the typing contract imposed by filter.

The combination of templates and partial application gives the programmer the means to create some very elegant code. As an example, below we see an implementation of the quicksort algorithm in SML. In this example, the function grt is used as a function factory. Each time a new pivot must be handled, i.e., the first element of the list, we create a new comparison function via the call grt h. We could make this function even more general, had we let the comparison operation, in this case greater than, open. By passing a different operator, say, less than, we would have an algorithm that sorts integers in a descending order, instead of in the ascending order.

fun grt a b = a > b
 
fun qsort nil = nil
  | qsort (h::t) = (qsort (filter (grt h) t)) @ [h] @ (qsort (filter (leq h) t))

Templates without High-Order Functions

Some programming languages do not provide high-order functions. The most illustrious member of this family is Java. Nevertheless, templates can also be implemented in this language. Java compensates for the lack of high-order functions with the powerful combination of inheritance and subtype polymorphism. As an example, we will show how to implement the map skeleton in Java. The code below is an abstract class. Mapper defines a method apply that must be implemented by the classes that extend it. Mapper also defines a concrete method map. This method fully implements the mapping algorithm, and calls apply inside its body. However, the implementation of apply is left open.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public abstract class Mapper<A, B> {

  public abstract B apply(A e);

  public final List<B> map(final List<A> l) {
    List<B> retList = new LinkedList<B>();
    Iterator<A> it = l.iterator();
    while (it.hasNext()) {
      retList.add(apply(it.next()));
    }
    return retList;
  }
}

In order to use this skeleton, the developer must extend it through a mechanism known as Inheritance. If a class A extends another class B, then we call A a subclass of B. As an example, the class below, a subclass of Mapper, implements a function that increments the elements of a list:

public class Incrementer extends Mapper<Integer, Integer> {
  @Override
  public Integer apply(Integer e) { return e + 1; }
}

The class Incrementer maps a list of integers into a new list of integers. The code snippet below demonstrates how we can use instances of this class to increment every element of a list of integers. As we can see, the overall process of emulating templates in a language without high-order functions is rather lengthy.

    List<Integer> l0 = new LinkedList<Integer>();
    for (int i = 0; i < 16384; i++) {
      l0.add(i);
    }
    Mapper<Integer, Integer> m = new Incrementer();
    List<Integer> l1 = m.map(l0);