Argument dependent name lookup

Argument dependent name lookup (häufig kurz Argument dependent lookup oder ADL, zu deutsch argumentabhängige Namensauflösung) 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 prominentes Beispiel ist die Programmiersprache C++. ADL wird gelegentlich auch als Koenig-Lookup bezeichnet (nach dem Informatiker Andrew Koenig).

Ü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;
 
  return 0;
}

In diesem Beispiel wird die Stream-Operator-Funktion operator<< verwendet. Diese ist im Namensraum std definiert, 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);
 
  return 0;
}

Die Postfix-Notation erlaubt die Qualifizierung der Funktionsaufrufe mit den entsprechenden Namensräumen, ist allerdings deutlich mehr Schreibarbeit. Zudem würde die Notwendigkeit eines Postfix-Aufrufes selbst in einfachen Beispielen wie dem obigen die Nützlichkeit insbesondere von Operator-Überladung deutlich einschränken. 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 semantisch 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 seien sie direkter Bestandteil der Klassenschnittstelle^[1].

Ein Anwendungsbeispiel für das Schnittstellenprinzip stellen wiederum die Streamklassen der Standardbibliothek dar. Um eigene Datentypen mit den STL-Streams verwenden zu können, müsste man anderenfalls für jede neue Klasse die Stream-Klassen erweitern, damit diese damit umgehen können. 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.

Semantisch sind derartige Funktionen 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 std-Namensraum 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 auf 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];
 
  // (...)
  return 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 welche 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 schlechtest mö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 ein strenger objektorientiertes Paradigma zugrundelegen. C++ ist im Unterschied dazu eine Mehr-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 im C++-Standard 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 von David Abrahams von 2004 schlug die Einführung von sogenannten "expliziten" Namensräumen vor, in welchen die ADL-Auflösung de facto ausgeschaltet bzw. deutlich eingeschränkt sein sollte^[2]. 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^[3].

Der aktuelle Entwurf des nächsten C++-Standards ("C++ 0x") beinhaltet diese Vorschläge bislang nicht^[4], 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).

Einzelnachweise

1. ↑ What's In a Class? - The Interface Principle von Herb Sutter; abgerufen am 18. November 2009
2. ↑ "Explicit Namespaces" von David Abrahams; abgerufen am 15. November 2009
3. ↑ "A Modest Proposal: Fixing ADL (revision 2)" von Herb Sutter; abgerufen am 15. November 2009
4. ↑ Aktueller Entwurf des neuen ISO-C++-Standards ("C++ 0x"); abgerufen am 15. November 2009