Über Duck-Typing und Typvarianz

von Hubert Schmid vom 2012-10-07

Beim Duck-Typing sind die Methoden und Eigenschaften eines Typs entscheidend – nicht die Identität des Typs mit den deklarierten Beziehungen zu anderen Typen. Diese dynamische Typisierung findet sich beispielsweise in Python. Die Funktion im folgenden Beispiel erwartet lediglich, dass sich das übergebene Argument wie ein iterable verhält, und dass die Elemente mit dem Operator < vergleichbar sind.

def is_sorted(iterable):
    iterator = iter(iterable)
    try:
        previous = next(iterator)
        for current in iterator:
            if current < previous:
                return False
            previous = current
        return True
    except StopIteration:
        return True

Die Python-Funktion is_sorted ist generisch und kann mit vielen unterschiedlichen Typen aufgerufen werden. In Java benötigt man dafür hingegen generische Methoden, und die erwarteten Eigenschaften der Argumente werden durch generische Interfaces angegeben. In der folgenden (für Java idiomatischen) Implementierung sind das Iterable<T> und Comparable<T>:

public static <T extends Comparable<T>> boolean isSorted(Iterable<T> iterable) {
    Iterator<T> iterator = iterable.iterator();
    if (iterator.hasNext()) {
        T previous = iterator.next();
        while (iterator.hasNext()) {
            T current = iterator.next();
            if (previous.compareTo(current) > 0) {
                return false;
            }
            previous = current;
        }
    }
    return true;
}

Generische Funktionen mit mehreren Parametern erfordern in der Regel eine Form der Typvarianz, um die für den Funktionsaufruf möglichen Typkombinationen beschreiben zu können. Zur Demonstration überlade ich die obige Methode mit einer Variante, die ein Funtionsobjekt für den Vergleich übergeben bekommt. Typvarianz wird in diesem Fall benötigt, da statt einem Comparator für T auch ein Comparator für eine Basisklasse von T übergeben können werden soll. Denn schließlich können auch die Objekte auch damit verglichen werden. Der Comparator ist also kontravariant. In Java verwendet man in solchen Fällen die sogenannten Wildcards:

public static <T> boolean isSorted(Iterable<T> iterable, Comparator<? super T> comparator) {
    Iterator<T> iterator = iterable.iterator();
    if (iterator.hasNext()) {
        T previous = iterator.next();
        while (iterator.hasNext()) {
            T current = iterator.next();
            if (comparator.compare(previous, current) > 0) {
                return false;
            }
            previous = current;
        }
    }
    return true;
}

Mit Lambda-Funktionen und dem Einzug funktionaler Idiome in objekt-orientierte Programmiersprachen gewinnt das Thema Typvarianz zunehmend an Bedeutung. Diese Entwicklung ist relativ gut an Scala zu beobachten, wo dieses Jahr viel Arbeit sowohl in die Sprache als auch in die Bibliothek investiert wurde, um die Programmierung zu vereinfachen. Java steht dabei noch ganz am Anfang. Erst mit Java 8 und dessen Lambda-Funktionen wird die volle Problematik dort sichtbar werden.

Dass es in statisch typisierten Programmiersprachen auch ganz anders geht, zeigt C++. Generische Funktionen werden dort mit Templates realisiert, die eine Form des Duck-Typings verwenden. Im Gegensatz zu dynamisch typisierten Programmiersprachen wird in C++ aber bereits während der Übersetzung sichergestellt, dass die verwendeten Objekte alle benötigten Eigenschaften besitzen. Die obige Funktion sieht in idiomatischem C++ wie folgt aus:

template <typename Iterator, typename Less>
bool is_sorted(Iterator first, Iterator last, Less&& less)
{
    if (first != last) {
        Iterator previous = first;
        for (++first; first != last; ++first, ++previous) {
            if (less(*first, *previous)) {
                return false;
            }
        }
    }
    return true;
}

Die Implementierung hängt nicht von konkreten Typen ab. Wie im Python-Beispiel erwartet sie lediglich, dass sich die für Iterator und Less eingesetzten Typen entsprechend verhalten. Dadurch erspart man sich komplexe Typdeklarationen. Darüber hinaus wird der Code aber auch flexibler und generischer einsetzbar. Denn erstens funktioniert dieser Mechanismus ohne Erweiterung der eingesetzten Typen um die passenden Interfaces. Und zweitens werden die möglichen Typen nicht darauf beschränkt, was sich deklarativ beschreiben lässt. Beispielsweise funktioniert obige Funktion für einen std::vector<int> auch mit einer Funktion, die zwei long- statt zwei int-Argumenten vergleicht.

std::vector<int> values{2, 3, 5, 7, 11, 13};
bool result = is_sorted(values.begin(), values.end(),
    [](long lhs, long rhs) { return lhs < rhs; });

Man versuche das Gleiche mal in Java zu realisieren: Eine generische Methode, die für ein Iterable<Integer> und einen Comparator<Long> funktioniert.

Übrigens: Die C++-Implementierung lässt sich so erweitern, dass sie mit und ohne Funktionsobjekt für den Vergleich funktioniert. Dafür muss lediglich die Deklaration wie folgt geändert werden:

template <typename Iterator,
          typename Less = std::less<typename std::iterator_traits<Iterator>::value_type>
bool is_sorted(Iterator first, Iterator last, Less&& less = Less());