Efficient Constraint Solving in Dynamic Languages [Elektronische Ressource] / Stephan Frank. Betreuer: Peter Pepper

Stephan Frank

Sujets

• Informatik

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2011
• Nombre de lectures: 17
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Efficient Constraint Solving in Dynamic Languages
vorgelegt von
Diplom-Informatiker
Stephan Frank
aus Berlin
Von der Fakultät IV – Elektrotechnik und Informatik
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
Dr.-Ing.
genehmigte Dissertation
Promotionsausschuss:
Prof. Dr.-Ing. Stefan Jähnichen (Vorsitzender)
Prof. Dr. rer. nat. Peter Pepper (Berichter)
Prof. Dr. rer. nat. Ute Schmid (Berichter)
Tag der wissenschaftlichen Aussprache: 05. April 2011
Berlin 2011
D 83Zusammenfassung
Die Integration von Constraints in eine Programmiersprache ermöglicht die elegante
deklarative Beschreibung von Problemen mit unvollständiger Information, z.B. von
Such- und Optimierungsproblemen, sowie Aufgaben in den Bereichen Planung,
Analyse, Simulation, Diagnose und Testen.
Das Problemlösen durch die Beschreibung mit Hilfe von Constraints, d.h. For-
meln, die entsprechende Einschränkungen für Variablen darstellen, hat in den
letzten Jahren durch die Entwicklung von mächtigeren und schnelleren Algorith-
men an Bedeutung gewonnen. Oft werden zum Experimentieren mit neuartigen
Datenrepräsentationen und Algorithmen kommerzielle Implementierungen benutzt,
deren Flexibilität in diesen Bereichen jedoch stark eingeschränkt ist.
Ziel dieser Arbeit wardaherzumeinendieSchaffungeinesConstraint-Programmier-
und -Experimentier-Systems mit hoher Modularisierung und Flexibilität aber auch
einer angemessenen Performanz. Dabei spielt vor allem auch die Realisierung in
Hinblick auf die zugrunde liegende dynamische Host-Sprache eine Rolle, die zwar
einen komfortablen, experimentierlastigen Entwicklungsansatz erlaubt und begün-
stigt, was aber zu Lasten der Performanz geht. Die Arbeit behandelt zwei große
Aspekte: Zum einen beschreiben wir ausführlich theoretische Grundlagen, Design
und Implementierung unseres Solver-Systems CLFD. Zum anderen untersuchen
wir die Integration der Constraint-Programmierung als domainspezifische Sprache
DSL.
Im Solver-Framework CLFD wird die Flexibilität in allen Solverbereichen als
Basiselement zugrunde gelegt. Der Benutzer soll jederzeit die Möglichkeit haben
aus einem Spektrum verschiedener Basisstrukturen und -funktionen zu wählen
und zu experimentieren. Gleichzeitig erlaubt der streng modularisierte Aufbau die
einfache Ergänzung durch eigene Implementierungen nahezu aller Solverbereiche.
Definierte Protokolle für die Interaktion zwischen den einzelnen Solverelementen
sind die Schlüsselelemente für die erzielte Flexibilität und ermöglichen auch die
(eingeschränkte) Kontrolle der Einhaltung theoretischer Grundannahmen.
Beispielhaft stellt CLFD bereits eine Anzahl verschiedener Implementierungen
z.B. für Integer-basierte Finite Domains zur Verfügung. Außerdem wurden eine
Vielzahl von Constraintimplementierungen für diesen Domain-Bereich integriert, bis
hin zum automatischen Handling nicht-linearer Ausdrücke und mehrerer globaler
Constraints.
Neben den eigentlichen Constraint-Löser-Konzepten diskutiert die Arbeit die
Anwendung von Heuristiken zur Lösungsfindung. Auch hier wurde ein möglichst
flexibler und durch den Nutzer erweiterbarer Ansatz gewählt. Wir betrachten
hierbei zum einen den Schedulerprozess, der die bei der Constraintpropagierung
1verwendete Reihenfolge auf Basis verschiedenster Datenpunkte dynamisch steuert.
Zum anderen entwickeln wir ein differenziertes und durchdachtes Suchframework
zur Realisierung und zum Tuning verschiedenster Suchmethoden und -heuristiken.
Da sehr flexible Methoden und Konzepte zur Modularisierung und Dynamisierung
fastzwangsläufigzueinervermindertenPerformanceführen,stellenwirverschiedene
Ansätze zu einer weitgehenden Vermeidung bzw. Verminderung dieser Probleme
vor und diskutieren diese im Detail. Dabei gehen wir insbesondere auch auf Aspekte
in Design und Implementierung hinsichtlich der dynamischen Hostsprache ein.
Unser Solver-System CLFD ermöglicht die (dynamische) Definition verschie-
dener Constraintprobleme und erlaubt die einfache Evaluierung verschiedenster
Lösungsmethoden und Datenstrukturen.
Ein zweiter Aspekt der Arbeit beschäftigt sich mit der Sprachintegration von
CLFD. Das Framework in der obigen Form stellt eher einen Constraint-Bibliotheks-
ansatz dar. Constraint-Probleme werden mit Standardsprachmethoden (Instantiie-
rung, Funktionsaufrufe etc.) definiert und evaluiert. Die Benutzung von Constraint-
Programmierung wirkt deshalb oft aufgesetzt und sprachfremd. Eine weitere Ziel-
setzung war daher die Entwicklung einer Domain-spezifischen Sprache (DSL) zur
stufenlosen Integration in die zugrunde liegende dynamische Host-Umgebung. Hier-
bei betrachten wir vor allem zwei Ebenen: Zum einen muss es möglich sein, in
möglichst formeller Art und Weise Constraintprobleme zu definieren; zum anderen
sollte auch die Erweiterung des Solvers, insbesondere die Ergänzung zusätzlicher
Einschränkungsalgorithmen, weitgehend (und soweit möglich) deklarativ erfolgen
können.
2Abstract
The integration of constraints into a programming language enables the elegant
declarative description of problems with incomplete information, e.g. search and
optimization problems or task descriptions in the areas of planning, analysis,
simulation, diagnosis and testing.
The inference of solutions through problem descriptions with constraints, i.e.
formulas which represent respective restrictions for variables, has been on the rise
in recent years. This has been driven by the development of powerful and fast
algorithms. New data representations and experimentation with newly developed
algorithms need a flexible framework to allow the simple integration and adaption.
Current systems, especially from commercial vendors, often lack the openness to
allow such research comfortably.
The goal of this thesis is the development of a constraint programming and
experimentation framework which is highly modularized and flexible but which at
the same time still provides acceptable performance.
The work is divided in two aspects of work: a first part develops and describes
comprehensively the theoretical aspects, design and implementation decisions of our
solver framework CLFD. The dynamic nature of the host programming language
has been influencing many design aspects and implementation decisions. A second
part reflects on the transparent integration of the constraint description into the
underlying dynamic host language.
The basic element of all parts of the solver framework CLFD is the flexibility in
all areas. A user shall have the possibility to select from a range of base structures
and base functions and modularly enhance and experiment with these elements.
The modular design allows for an exchange of different implementations in all
areas. Defined protocols at the module borders and interactions points are the key
element for this flexibility. They also ensure the compliance with the presented
module properties (if computationally feasible). Another aspect is the design in
relation to the dynamic host language. It allows for a dynamic reorganization
and optimization, yet at the same time requires a different design with respect to
statically compiled languages to ensure a well performing solver engine.
Exemplarily, CLFD provides a number of different domain and management
data structures. Furthermore, several constraint pruning algorithms from simple
domain restriction, automatic handling of non-linear constraints to complex global
constraints are made available.
Additionally to the actual constraint pruning several concepts for the heuristic
extension for solution finding are discussed. We focus on the scheduler process
which selects the different constraints in a certain order during the propagation
3phase. This selection order greatly influences the overall performance. Furthermore
we define a sophisticated search framework which realizes and tunes many aspects
of heuristic search in a highly flexible way.
Such a flexible, modularized concept in addition to the dynamic aspects of the
host language comes with a performance penalty, though at the same time greatly
enhance on-the-fly optimization and experimentation. Therefore we present and
detail several approaches to redeem or at least cushion such performance problems.
Our solver framework enables the dynamic definition of different constraint
problems and solver modules and thus allows for a comfortable evaluation of
different solving methods and data structure aspects.
A second aspect of this thesis is the transparent language integration of the
constraint system definition and solving properties of CLFD. The solver framework
as described above represents an approach quite similar to a programming library.
Constraint problems are defined and evaluated by calling a number of respective
interface methods (object instantiation and function calls).The employment of
constraint programming thus feels quite foreign and superimposed compared to
the underlying host paradigm.
A further goal of this thesis is thus to define and evaluate a domain specific
language (DSL) approach to enable a transparent integrat