Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2848
Main Title: Efficient Constraint Solving in Dynamic Languages
Translated Title: Effizientes Constraintlösen in dynamischen Sprachen
Author(s): Frank, Stephan
Advisor(s): Pepper, Peter
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: 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.
URI: urn:nbn:de:kobv:83-opus-30685
http://depositonce.tu-berlin.de/handle/11303/3145
http://dx.doi.org/10.14279/depositonce-2848
Exam Date: 5-Apr-2011
Issue Date: 31-May-2011
Date Available: 31-May-2011
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Constraintlösen
Constraints
Deklarative Sprachen
DSLs
Dynamische Sprachen
Constraint solving
Constraints
Declarative languages
DSLs
Dynamic languages
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_10.pdf1.9 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.