Argument dependent name lookup

Argument dependent name lookup (häufig argument dependent lookup oder kurz ADL, zu deutsch argumentabhängige Namensauflösung; früher Koenig-Lookup nach dem Informatiker Andrew Koenig) ist eine Technik, um in Programmiersprachen mit Unterstützung sowohl von Namensräumen als auch freien Funktionen unter bestimmten Umständen Symbole aus anderen Namensräumen automatisch zu importieren. Ein Beispiel ist die Programmiersprache C++.

Übersicht

Ein einfaches Beispiel für ADL in C++ stellt die Benutzung der Stream-Klassen dar:

#include <iostream>

int main()
{
  std::cout << "Hallo, Welt!" << std::endl;
}

In diesem Beispiel wird die Stream-Operator-Funktion operator<< verwendet, die im Namensraum std definiert ist, genauso wie die restlichen Stream-Klassen. Ohne die Verwendung von ADL würde demnach das obige Beispiel nicht funktionieren. Man müsste entweder den entsprechenden Code in den std-Namensraum verlegen oder den Operator explizit per

using std::operator<<;

importieren. Aber auch dies löst nicht das zugrundeliegende Problem, denn spätestens wenn benutzerdefinierte Datentypen aus mehreren verschiedenen Namensräumen zusammen mit den Stream-Klassen in std verwendet werden sollen, liegen üblicherweise verschiedene Definitionen von operator<< in verschiedenen Namensräumen vor.

Es ist auch möglich, auf die Infix-Schreibweise komplett zu verzichten:

#include <iostream>

int main()
{
  std::operator<<(std::cout, "Hallo, Welt").operator<<(std::endl);
}

Die Funktionsnotation erlaubt die Qualifizierung der Funktionsaufrufe mit den entsprechenden Namensräumen, ist allerdings deutlich mehr Schreibarbeit. Außerdem muss der Aufrufer wissen, ob die Überladungsversion des (im Beispiel zweistelligen) Operators eine freistehende Funktion (im Beispiel: erster Aufruf mit zwei Parametern) oder Komponente einer Klasse ist (im Beispiel: zweiter Aufruf mit Punkt und einem Parameter). Funktionsaufrufe schränken selbst in einfachen Beispielen wie dem obigen die Nützlichkeit insbesondere von Operatorüberladung deutlich ein; daher spezifiziert der C++-Standard (Abschnitt 3.4.2), dass der Compiler die zu den Argument-Typen gehörigen Namensräume (die sogenannten associated namespaces) ebenfalls durchsuchen muss.

Das Schnittstellenprinzip in C++

Der Grund dafür, dass argumentabhängige Namensauflösung in C++ notwendig ist, liegt letztlich in der Interpretation dessen, was man als die Klassen-Schnittstelle einer Klasse ansieht. Im Unterschied zu den meisten anderen Sprachen interpretiert C++ eine Funktion als zu einer Klasse gehörig, wenn diese einerseits Argumente des Klassentyps akzeptiert und andererseits im selben Namensraum liegt wie die Klasse. ADL erlaubt es, derartige freie Funktionen weitgehend so zu benutzen, als wären sie direkter Bestandteil der Klassenschnittstelle.

Ein Anwendungsbeispiel für das Schnittstellenprinzip stellen wiederum die Streamklassen der Standardbibliothek dar. Um eigene Datentypen mit den Standard-Streams verwenden zu können, müsste man anderenfalls für jede neue Klasse die Stream-Klassen erweitern, damit diese damit umgehen können. Dies ist nicht praktikabel. Operator-Definitionen für die Ausgabe auf Streams können daher keine Methoden der Stream-Klassen sein, sondern müssen als freie Funktionen implementiert werden.

Derartige Funktionen sind zudem sehr eng an die Klasse gekoppelt, deren Stream-Ausgabe sie ermöglichen. Aus diesem Grund werden sie üblicherweise in demselben Namensraum definiert wie die zugehörige Klasse. Der ADL-Mechanismus ermöglicht es dann, sie bei der Auflösung der Operator-Überladung berücksichtigen zu können:

#include <iostream>

namespace geometry
{
  struct vector2D
  {
    vector2D() : x(0), y(0) {}
    vector2D(double x_new, double y_new) : x(x_new), y(y_new) {}
    double x;
    double y;
  };

  std::basic_ostream<char>& operator<<(std::basic_ostream<char>& stream, const vector2D& v)
  {
    stream << "(" << v.x << ", " << v.y << ")";
    return stream;
  }
}

int main()
{
  geometry::vector2D v(1, 2);

  std::cout << v << std::endl;
}

Schwierigkeiten

Die argumentabhängige Auflösung von Symbolen kann zu subtilen Fehlern und unportablem Code zwischen verschiedenen Implementierungen führen. Ein weiteres Problem ist gelegentliches kontra-intuitives Verhalten des Compilers bei der ADL-Auflösung, insbesondere bei Verwendung von using-Anweisungen.

Die durch argumentabhängige Namensauflösung auftretenden Probleme (hauptsächlich unbeabsichtigte Überladung) sind prinzipiell dieselben, die in Programmiersprachen ohne Namensräume auftreten. Daher bedeuten sie eine Einschränkung der Schutzfunktion von Namensräumen.

Wenn der aufzulösende Funktionsname beispielsweise identisch zu einer Funktion aus dem Namensraum std ist, kann es vorkommen, dass der Compiler diese Funktion auswählt anstelle der vom Programmierer vorgesehenen, da zunächst alle zugeordneten Namensräume importiert werden. Danach erst wird anhand der Signaturen die konkrete Funktion ausgewählt (selbst wenn der Programmierer eine bestimmte Version per using-Direktive angefordert hat).

Beispielsweise kann das folgende Programm nicht von jeder C++-Implementierung übersetzt werden:

#include <vector>

namespace N
{
  struct X{};

  template <typename T>
  int* operator+(T, unsigned int i)
  {
    return i + 1;
  }
}

int main()
{
  std::vector<N::X> v(5);
  const N::X& elem = v[0];

  // (...)
}

Ob das obige Programm übersetzt werden kann, liegt letztlich an der Implementierung von vector. In einigen Implementierungen ist der Element-Zugriff v[0] über Iteratoren implementiert, auf die wiederum operator+() angewendet wird. Je nach Implementierungs-Details kann es vorkommen, dass der Namensraum N als zugehöriger Namensraum bei Auflösung des Iterator-Zugriffs berücksichtigt und die obige Implementierung des +-Operators fälschlicherweise benutzt wird. Erschwerend kommt hinzu, dass eventuell auftretende Fehlermeldungen aus der Standardbibliothek kommen, was eine Diagnose stark erschwert. Im schlechtestmöglichen Fall übersetzt der Compiler das Programm ohne Fehlermeldung, erzeugt dabei jedoch falschen Programmcode.

Weitere Probleme werden durch Implementierungsfehler einzelner Compiler bei der ADL-Auflösung verursacht. Die Unterschiede in den Standardbibliotheken und Compilern sind der Grund, weshalb ein Programm sich zum Beispiel bei Übersetzung mit GNU C++ anders verhalten kann als mit Microsoft Visual C++.

Alternativen

Andere Programmiersprachen wie Java oder C# kommen ohne argumentabhängige Namensauflösung aus. Dies liegt vor allem daran, dass diese Programmiersprachen strenger objektorientiert sind. C++ ist im Unterschied dazu eine Multi-Paradigmen-Sprache, die ein objektorientiertes Arbeiten nicht erzwingt, und deren Standard-Bibliothek eher auf Generizität basiert als auf Objektorientierung.

In strenger objektorientierten Sprachen stellen alle benutzerdefinierten Typen normalerweise Klassen dar, die von einer gemeinsamen Basis (üblicherweise Object o. ä.) erben. Die Basis-Klasse definiert eine grundlegende Schnittstelle, die damit von jedem benutzerdefinierten Typen zur Verfügung gestellt wird. Das obige Beispiel der Ein- und Ausgabe mittels Standardfunktionen wird in diesen Sprachen also über Objektorientierung und virtuelle Methoden gelöst.

Aktuelle Entwicklungen

Aufgrund verschiedener Formulierungslücken in der C++-Norm gab es in der Vergangenheit wiederholt Vorschläge, wie der derzeitige ADL-Mechanismus in C++ angepasst werden könnte, um vom Programmierer unerwartete Verhaltensweisen möglichst zu vermeiden und zudem die Kompatibilität verschiedener Implementierungen zu verbessern.

Ein Vorschlag des Informatikers David Abrahams von 2004 bestand in der Einführung von sogenannten expliziten Namensräumen, in denen die ADL-Auflösung de facto ausgeschaltet bzw. deutlich eingeschränkt sein sollte. Ein anderer Vorschlag von Herb Sutter sah bestimmte Einschränkungen der ADL-Auflösung vor, die weitgehende Kompatibilität mit vorhandenem Quelltext wahren und trotzdem gleichzeitig die wichtigsten Schwierigkeiten beheben sollten.

Die Norm C++11 berücksichtigt keinen dieser Vorschläge, definiert jedoch den ADL-Algorithmus detaillierter als in früheren Versionen, insbesondere werden nun mehrere Fälle definiert, in denen ADL keinen Sinn ergibt und vom Compiler nicht durchgeführt werden soll.