Tuesday, May 6, 2014

Simulating template specialization with value-level polymorphism

When I showed my last post about translating a generic algorithm from C++ to Java to my friend who's an expert in C++, his main question was, what about template specialization? The simplest example of specialization is std::advance, which advances an iterator by n steps. It works in O(n) time for iterators that only support "it++", and in O(1) time for iterators that support "it+=n".

In value-level programming, that can be simulated by having a method in the ForwardIteratorOperations interface that returns Maybe<RandomAccessIteratorOperations>. For iterators that don't support fast random access, that method would return Maybe.Nothing, and for those that do, it would return a Maybe.Something containing a valid RandomAccessIteratorOperations. Since Java doesn't have sum types like Maybe, we can simulate it with a nullable return value instead. I've written a translation of std::advance into Java using that approach, you can find the code at the end of this post.

The problem is that the above approach doesn't scale to all uses of template specialization in C++, because if there are multiple interrelated concepts that you can specialize on, the number of possible conversions grows quadratically or worse. Another complication is that some concepts can have several type parameters, like multi-parameter type classes in Haskell. I'm still trying to figure out if that's an important use case.

In fact, I'm still trying to figure out if template specialization is worth the trouble at all. The C++ STL seems to have few uses of specialization. The examples I've found are std::advance, std::distance, vector<bool> which is known to be broken, and some specializations on trivially destructible types like pointers that allow you to skip calling destructors. The Boost libraries use specialization more, but it's often to compensate for the drawbacks of C++, like the lack of lambdas or garbage collection. I haven't found a really convincing use case for specialization yet, but I'll change my view if I find one.

Why am I so against specialization? Well, part of the reason is that I'm trying to explore "value-level programming", which means having no type-directed overloading or dispatch anywhere. But the bigger problem is that specialization in C++ seems to be incompatible with modularity and separate compilation, and would stay incompatible even if templates supported separate compilation. If you specialize someone else's templates, and their headers don't include yours, then everything will compile without errors, but the runtime behavior is undefined. That violates the principle that "well-typed programs don't have type errors", which feels very important to me. With the approach I outlined above, such errors are provably impossible, but at the cost of spelling out many things explicitly.

APPENDIX: the translation of std::advance into Java.

public class Main {

    static interface Forward<Iterator> {
        Iterator increment(Iterator iterator);
        boolean equal(Iterator first, Iterator second);
        /* Nullable */ RandomAccess<Iterator> getFastRandomAccess();
    }
   
    static interface RandomAccess<Iterator> {
        Iterator add(Iterator iterator, Integer delta);
        Integer subtract(Iterator first, Iterator second);
    }

    static interface Input<Iterator, Value> {
        Value get(Iterator iterator);
    }
       
    static <Iterator> Iterator advance(
        Iterator iterator,
        Integer delta,
        Forward<Iterator> forward
    ) {
        if (forward.getFastRandomAccess() != null) {
            return forward.getFastRandomAccess().add(iterator, delta);
        } else {
            while (delta > 0) {
                iterator = forward.increment(iterator);
                delta = delta - 1;
            }
            return iterator;
        }
    }
   
    static class List<Value> {
        public final Value value;
        /* Nullable */ public final List<Value> next;
        public List(
            Value value,
            List<Value> next
        ) {
            this.value = value;
            this.next = next;
        }
    }
   
    static class ArrayRandomAccess implements RandomAccess<Integer> {
        public Integer add(Integer iterator, Integer delta) {
            System.out.println("Using integer add");
            return iterator + delta;
        }
        public Integer subtract(Integer first, Integer second) {
            return first - second;
        }
    }
   
    static class ArrayForward implements Forward<Integer> {
        public Integer increment(Integer iterator) {
            System.out.println("Using integer increment");
            return iterator + 1;
        }
        public boolean equal(Integer first, Integer second) {
            return first == second;
        }
        public RandomAccess<Integer> getFastRandomAccess() {
            return new ArrayRandomAccess();
        }
    }
   
    static class ArrayInput<Value> implements Input<Integer, Value> {
        private final Value [] array;
        public ArrayInput(Value [] array) {
            this.array = array;
        }
        public Value get(Integer index) {
            return array[index];
        }
    }

    static class ListForward<Value> implements Forward<List<Value>> {
        public List<Value> increment(List<Value> iterator) {
            System.out.println("Using list increment");
            return iterator.next;
        }
        public boolean equal(List<Value> first, List<Value> second) {
            return first == second;
        }
        public RandomAccess<List<Value>> getFastRandomAccess() {
            return null;
        }               
    }
   
    static class ListInput<Value> implements Input<List<Value>,Value> {
        public Value get(List<Value> list) {
            return list.value;
        }
    }
   
    static <Iterator, Value> Value peekAhead(
        Iterator iterator,
        Integer delta,
        Forward<Iterator> forward,
        Input<Iterator, Value> input
    ) {
        return input.get(advance(iterator, delta, forward));
    }

    public static void main(String [] args) {
        Double [] array = new Double [] { 1.0, 2.0, 3.0 };
        List<Double> list =

            new List<Double>(1.0,
                new List<Double>(2.0,
                    new List<Double>(3.0, null)));
        System.out.println("" + peekAhead(

            0, 2, new ArrayForward(), new ArrayInput(array)));
        System.out.println("" + peekAhead(

            list, 2, new ListForward(), new ListInput()));
    }
}


And the output is this:

Using integer add
3.0
Using list increment
Using list increment
3.0

No comments:

Post a Comment