Lambda the Ultimate

I've skimmed Apt at my local bookstore, and although I've heard it's an excellent text, I didn't feel it was aimed at my level (i.e. complete neophyte on the subject). Will look into some of the other ones you mention.

On the personal side, I noticed your message on the Oz mailing list wrt your thesis the other day. Others here abouts might find your work with CP interesting:

Constraint programming gained much interest in computer aided composition, because it allows to express explicit compositional knowledge in a declarative way. In this field, the user states a music theory and the computer generates music which complies this theory. Music constraint programming is style-independent and is well-suited for highly complex theories (e.g. a fully-fledged theory of harmony). A theory is formulated as a constraint satisfaction problem (CSP) by a set of rules (constraints) applied to a music representation in which some aspects are expressed by variables (unknowns). A generic music constraint system predefines concepts shared by many theories (e.g. duration, pitch, note, chord) and that way greatly simplifies the definition of musical CSPs.

Thank you for your interest. My thesis is not yet available, but meanwhile I uploaded the software which is the offspring of my PhD: Strasheela (together with some documentation, examples and pointers to publications).

While the wikipedia page on local consistency is very well written and has lots of helpful diagrams, it isn't very connected to how CP works in practice.

The different notions of local consistency are defined over a formal framework (CSPs with extensional constraints), which does not really correspond to the way a CP system works. For some basic intuition why, think of the space-complexity of defining (n-ary) constraints as the set of allowed tuples (i.e., O(d^n) where d is the domain-size).

In practice, CP systems typically use so-called propagators for implementing constraints. For some constraint c that references variables x1,...,xn, the propagator p will remove values from the domains of the xi variables that it knows do not belong to a solution of the constraint. Note that that this means that this process usually never considers more than one constraint at a time (in constrast to, for example, path consistency).

Formally, you can think of a propagator as a monotone, narrowing function over the Cartesian product of the domains of the variables. From Knaster-Tarski, we can see that the greatest mutual fixpoint of these functions is uniquely defined, and this is what propagation computes. For the set-up to work, the propagators must be checking (if the variables are all assigned, the propagator must be able to check if the constraint it implements holds or not).

To learn about CP, my suggestion is to first start playing with some system to get a feel for how it works. Starting with either Oz or Alice and following the corresponding tutorial is a good recomendation. Later, you can then look more into the theory behind CP.

Thanks for the explanations. Good to know that complete local search is possible - the Pascal programmer in me still gets disoriented by concepts like nondeterminism.

I understand the primary motivation of the book is local search, but my interest has more to do with the style of the book. The examples seem clear from a notational standpoint, and being a book that has a PL as a backdrop, it looks to be more pragmatically based than the other texts I skimmed through. One of the advantages of using a new PL to teach concepts is that one learns the concepts as a side effect of learning a new language.

Guido gave me warning about some of the code in the tutorial that doesn't work in the currentl released version of Alice. It's not hard to work around these things, once you stumble upon them, as they mostly amount to syntactic sugar. The paper itself will probably undergo quite a few more changes along the line. Still, it does make for some good background and interesting examples. Being in a state of flux, I doubt there is currently a printable version.

Along the same lines, the differences between Gecode and Mozart might be of interest. PvR has said that there is a project to integrate Gecode into Oz, so eventually these differences will likely be rectified.

You only picked up part of the story ;-)

There are tree important ideas working together when a CSP is solved in Oz: partial information, local deduction/propagation (which is by itself incomplete) and programmable search (distributing, branching + exploration of the resulting search tree). Together this yields a complete search method.

You first declare (1) the Domain of the solutions - that is the positions on the chess grid that the queens may be placed; and (2) the Constraint propagators - the limitations that none of the queens may attack each other. Even knowing this, however, you still have not found a solution. To get past this hurdle, you must do (3) a Search to find the various solutions.

The advantage that CP provides is that the search will not be a complete combinatorial search of all the solutions like it would in a complete relational solution. The information from the domains and constraint propagators can immediately rule out certain search paths prior to the search being performed. Since the types of problems that CP is geared towards are those that are thought of as np complete, anything that can reduce the combinatory search is what one focuses on.

In the case of local search as used in COMET, the algorithm and manner of search is much different as it is only looking at its immediate neighbors in the graph, using the constraints as hints about which way to step next. On the other hand, CP is a tree exploration that typically does a depth first search for solutions based on the hints you provide on how to divvy up the search process.

Don't know if it helps, but I did manage to make a small dent in Chapter 12 of CTM. Also, Alice doesn't have a way that I've found to do the Prolog Choice type operation, so I cheated and used CP to solve a couple of problems in Chapter 9.

Propagation alone (i.e., removing inconsistent values from the domains of variables) is indeed incomplete. While there are many complete propagators, these are complete for one constraint only. For the combination of several constraints, however, propagation is incomplete. This is because propagation will remove values based on one constraint at a time.

If propagation was complete (i.e., it removed all values that do not participate in a solution), we would have a backtrack-free method of finding a solution to the problem. After each propagation-round, assign one variable, and then re-propagate. Since we can use CP to solve NP-complete problems, propagation would then also be intractable.

Using the common set-up, we get a reasonably time-bounded deductive process, combined with an exponential search-part.

What are you implying?

Constraint Logic Programming, the combination of Constraint Programming and Logic Programming (Prolog) is recognized as a very good, if not the best, match. The underlying principle, logic, is the same for both paradigms.

There are ways to integrate CP also in other programming paradigms, often as libraries, but these would be less natural integrations where the CP part more contained. Nevertheless, that is very worthwhile as CP is probably still the most convenient for what it does.