Ghent University Academic Bibliography

Advanced

Functional programming abstractions for CP modeling

Pieter Wuille UGent (2011)
abstract
The field of Constraint Programming (CP) provides problem-independent technology for solving combinatorial problems. The programmer describes his problem in a model, which is processed by a problem-independent solver to produce a so- lution. Solver implementations are an active topic of research, and many efficient solvers exist. Specific languages were created that provide CP modeling facilities, but these domain-specific languages (DSL) run behind on features and abstractions, compared to modern general purpose languages. On the other hand, using CP libraries in such a language requires boilerplate code, and is often far less declarative in nature. Functional Programming (FP) is a programming paradigm that is based on the concept of functions as they are defined in mathematics, i.e., without side effects beyond their return value. Functional languages are declarative, offer very high level abstractions, and are easy to analyze. Furthermore, they can be used for general purposes. The existing Monadic Constraint Programming (MCP) framework offers interesting high-level abstractions for CP in the state-of-the-art functional programming language Haskell. In the first part of this thesis, we study how to build upon it to create a practical, concise, and declarative modeling DSL for constraint problems. Our language allows Finite Domain (FD) problems to be written using high-level expressions, while the underlying framework performs optimized translation to specific solver back-ends. Implemented back-ends include a proof-of-concept solver in Haskell, and bindings to the constraint solving library Gecode. For solving with low overhead, an extra mode is provided that generates C++ code for performing the solving at a later stage. In the second part, we provide declarative modeling of search. Controlling the search heuristic employed by a constraint solver is often essential for good performance, but existing systems are either limited in possibilities or imperative in nature. Again, we choose to provide a DSL to do better. The Search Combinators language is declarative, concise and captures many advanced search heuristics. We implement an efficient code generator for these search heuristics, avoiding the pitfalls encountered.
Please use this url to cite or link to this publication:
author
promoter
UGent
organization
alternative title
CP modellering met functionele abstracties
year
type
dissertation (monograph)
subject
keyword
Search, Constraint Programming, Haskell, Programming Languages
pages
IX, 159 pages
publisher
Katholieke Universiteit Leuven. Faculty of Engineering
place of publication
Heverlee, Belgium
defense location
Heverlee : Kasteelpark Arenberg (Auditorium De Molen)
defense date
2011-12-06 17:00
ISBN
9789460184406
language
English
UGent publication?
no
classification
D1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1971634
handle
http://hdl.handle.net/1854/LU-1971634
alternative location
http://people.cs.kuleuven.be/~pieter.wuille
date created
2011-12-21 14:07:19
date last changed
2011-12-22 10:03:51
@phdthesis{1971634,
  abstract     = {The field of Constraint Programming (CP) provides problem-independent technology for solving combinatorial problems. The programmer describes his problem in a model, which is processed by a problem-independent solver to produce a so-
lution. Solver implementations are an active topic of research, and many efficient solvers exist. Specific languages were created that provide CP modeling facilities, but these domain-specific languages (DSL) run behind on features and abstractions, compared to modern general purpose languages. On the other hand, using CP libraries in such a language requires boilerplate code, and is often far less declarative in nature.
Functional Programming (FP) is a programming paradigm that is based on the concept of functions as they are defined in mathematics, i.e., without side effects beyond their return value. Functional languages are declarative, offer very high level abstractions, and are easy to analyze. Furthermore, they can be used for general purposes.
The existing Monadic Constraint Programming (MCP) framework offers interesting high-level abstractions for CP in the state-of-the-art functional programming language Haskell. In the first part of this thesis, we study how to build upon it to create a practical, concise, and declarative modeling DSL for constraint problems. Our language allows Finite Domain (FD) problems to be written using high-level expressions, while the underlying framework performs optimized translation to specific solver back-ends. Implemented back-ends include a proof-of-concept solver in Haskell, and bindings to the constraint solving library Gecode. For solving with low overhead, an extra mode is provided that generates C++ code for performing the solving at a later stage.
In the second part, we provide declarative modeling of search. Controlling the search heuristic employed by a constraint solver is often essential for good performance, but existing systems are either limited in possibilities or imperative in nature. Again, we choose to provide a DSL to do better. The Search Combinators language is declarative, concise and captures many advanced search heuristics. We implement an efficient code generator for these search heuristics, avoiding the pitfalls encountered.},
  author       = {Wuille, Pieter},
  isbn         = {9789460184406},
  keyword      = {Search,Constraint Programming,Haskell,Programming Languages},
  language     = {eng},
  pages        = {IX, 159},
  publisher    = {Katholieke Universiteit Leuven. Faculty of Engineering},
  title        = {Functional programming abstractions for CP modeling},
  url          = {http://people.cs.kuleuven.be/{\texttildelow}pieter.wuille},
  year         = {2011},
}

Chicago
Wuille, Pieter. 2011. “Functional Programming Abstractions for CP Modeling”. Heverlee, Belgium: Katholieke Universiteit Leuven. Faculty of Engineering.
APA
Wuille, P. (2011). Functional programming abstractions for CP modeling. Katholieke Universiteit Leuven. Faculty of Engineering, Heverlee, Belgium.
Vancouver
1.
Wuille P. Functional programming abstractions for CP modeling. [Heverlee, Belgium]: Katholieke Universiteit Leuven. Faculty of Engineering; 2011.
MLA
Wuille, Pieter. “Functional Programming Abstractions for CP Modeling.” 2011 : n. pag. Print.