CHR-Forschungsgruppe der Universität Ulm

Constraint-Programmierung

Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. (E. Freuder)

Die Constraint-basierte Programmierung begann vor etwa 10 Jahren als natürliche Fusion zweier deklarativen Paradigmen: Lösen von Constraints und Logikprogrammierung. Dadurch lassen sich schnell und elegant komplexe kombinatorische Probleme durch eine Verbindung aus Constraintlösen und Suche behandeln. Unter Constraintlösen versteht man das Lösen von Problemen, indem man Constraints (Bedingungen, Einschränkungen) angibt, die von einer Lösung erfüllt werden müssen, und diese Constraints kombiniert, um die Lösung weiter einzuschränken. Haupteinsatzbereiche sind Produktions- und Personalplanung, Transportoptimierung sowie Layoutgenerierung. Der weltweite Umsatz durch Anwendung dieser Technologie wurde für 1996 auf 100 Mill. Dollar geschätzt.

Betrachten Sie zum Beispiel ein Fahrradschloß mit Zahlen. Wir haben die erste Ziffer vergessen, erinnern uns aber an einige ihrer Eigenschaften: Sie war ungerade, größer als 1 und keine Primzahl. Indem wir diese Teilinformationen kombinieren (Constraints: Zahl, größer als 1, ungerade, nicht prim) können wir herleiten, daß die gesuchte Zahl 9 ist.

Während es läuft erzeugt ein Constraint-Programm sukzessive neue Constraints. Der Constraintlöser speichert, kombiniert und vereinfacht die Constraints bis eine Lösung gefunden ist. Die Teillösungen beeinflussen den Lauf des Programms.

Constraint Handling Rules (CHR)

CHR was designed as a language for defining constraint solvers, but at the same time it is one of the most powerful multiset rewriting languages. (Kazunori Ueda and Norio Kato. Programming Logical Links)

Die 1991 von Thom Frühwirth erstellte Sprache CHR ist mittlerweile eine wichtige Spezifikations- und Implementierungssprache für Constraint-basierte Algorithmen und Anwendungen. Algorithmen werden oft durch Inferenzregeln, Transformationsregeln, Sequenzen, Beweisregeln oder logische Axiome spezifiziert, die unmittelbar in CHR geschrieben werden können. Die auf der Prädikatlogik erster ordnung basierende klare Semantik von CHR erleichtert nichttriviale Programmanalyse und -transformation. Es gibt etwa ein Dutzend CHR-Implementierungen in Prolog, Haskell und Java. CHR kann mit mehr als 40 Constraintlösern auch als WebCHR online ausprobiert werden. Weltweit verwenden mehr als 100 Projekte CHR.