Effizientes Constraintlösen in dynamischen Sprachen

Die Verwendung von Constraints ermöglicht die deklarative Beschreibung von Problemen mit unvollständiger Information. Üblicherweise wird das Lösen von Constraints in Form von Bibliotheken realisiert. Solche Constraint-Bibliotheken haben in der Regel eine eingeschränkte Flexibilität beim Experimentieren und Erweitern mit unterschiedlichen Basis-Datenstrukturen und Algorithmen. Als zusätzlicher Aspekt erfolgt die Definition von Constraint-Systemen wenig deklarativ oder in sprachfremder Form. Wir beschreiben ein flexibles, modularisiertes Solver-Framework, das eine einfache Erweiterung und experimentellen Austausch aller Solverelemente ermöglicht. Ein weiteres Ziel des Designs war das effiziente Lösen von Constraintproblemen in einer dynamischen Implementierungssprache, welche insbesondere durch die Adaption von Datenstrukturen und Algorithmen, sowie die dynamische Erzeugung spezialisierter Funktionen erreicht wurde. Ein generisches Suchprotokoll ermöglicht die einfache Definition neuer Suchansätze auf Basis bereits existierender Algorithmen. Anforderungen zur Korrektheit und Terminierung der einzelnen Komponenten werden analysiert und bewiesen. Außerdem wird die Gesamtperformance des beschriebenen Systems mit einem hochoptimierten Solversystem verglichen. Weiterhin werden Aspekte der Solverintegration und der damit verbundenen deklarativen Definition von Constraint-Problemen und Solvererweiterungen mit Hilfe einer transparenten Sprachintegration in die Host-Sprache dargestellt.The application of constraints enables the declarative description of problems with incomplete information. Typically, constraint solving is realized by an external library. Such a programming library restricts the flexibility with respect to simple exchanges with different foundational data structures and algorithms. It follows as an additional aspect, that the definition of constraint systems is not declarative or in an external, additional language form. We describe a flexible, modular solver framework which allows for the simple extension and the experimental exchange of all solver parts. A further goal of the design was an efficient architecture for constraint solving in a dynamic language environment. This has been realized by an adaption of data structures algorithms as well as the dynamic creation of specialized, problem specific functions. A generic search protocol enables the simple definition of new search approaches by basing on (and modularly expanding) existing algorithm implementations. The requirements for correctness and termination of the individual components are analyzed and proven. Furthermore, the achieved performance is compared to a highly optimized constraint solver. Furthermore, aspects of the integration of constraints and the resulting declarative definition of constraint problems and solver expansions by an transparent language embedding into the host language are portrayed