We can think of association lists as database tables (with a single-field key, though this restriction can be relaxed)

can be represented as a list as

We can use the "member" predicate we defined last week to look up elements of the list

For example

will return

In order to look more like a database, we define some "helper" predicates:

We can in turn use association lists to represent dependency graphs:

One of the things we might then wish to discover is what items must precede tiling:

Unfortunately, this will give us repetitions: if House is the list above,

will give the answer

We can avoid this by keeping track of which members of the predecessors list we have already seen:

Now we can do

to get the answer

CLP systems can represent a wide range of dynamic data structures, of which lists are only one example

Another important example is the binary search tree:

An important assumption is made about storage of information in binary search trees: the information is ordered in some way (for example, alphabetical order), and the information is stored in such a way that the root node of any subtree falls between all the information on the left branch, and all the information on the right branch

For example suppose we have a predicate less_than which orders names in alphabetical order (we could write a general rule which would do this, but for the example, we'll just use some simple facts):

Binary search trees have many uses; for example, if the stored item consists of a key and some information, they can be used to implement association lists in an alternative manner:

The advantage is that the search time is logarithmic, rather than linear, in the number of items in the association list

The cost is that there must be an order relation available for the keys

We have effectively covered this in assignment 6

We will omit this topic from the course

Recall that CLP systems search their derivation tree from the top left hand side

If there is an infinite branch to the left of the desired goal, the search won't terminate

Even a large but finite branch to the left of our goal is undesirable (though it sometimes cannot be avoided)

So far, we have largely ignored the order in which we write our constraints (on the basis that the order of constraints does not affect the solutions)

But the order of constraints does very dramatically affect the search strategy (or to put it another way, rotates the tree so we search it in a different order)

We will be looking at ways to

• re-order rules
• re-order literals within rules
• add redundant constraints

in order to improve search efficiency

Some of these improvements are generic - they will speed up the search for any goal; others are specific - they will speed up some goals at the cost of others, so we will need to know ahead of time how the constraints are to be used

We will also look at techniques by which the system may be told to ignore whole branches of the search tree

The latter techniques rely on the assumption that we can know ahead of time that the goal will not lie in the part of the search tree we have pruned

That implies a risk: we might be wrong (so a correctly constrained problem might give wrong answers)

In particular, we might not know ahead of time all the different ways in which users might use the constraints (which affects where the goal will lie)

A mode of usage for a predicate p is a description of the way in which the arguments of calls to p will be constrained at the time when calls to p are evaluated

For example, consider

with the mode where the first argument is a list of fixed length (ie the list is sufficiently instantiated that the number of elements in it is known), but the second argument is free

In this mode, the derivation tree for sumlist has 5|L|+6 nodes, where |L| is the length of the list L

So for this mode, the program is acceptable (linear time algorithms are usually acceptable; in general, we are prepared to accept polynomial algorithms, but exponential or higher algorithms are unacceptable)

On the other hand, for the mode where the second argument is known but the first argument is free, the size of the derivation tree is infinite, indicating that the program is not appropriate for this usage

It is usual to include the intended mode of usage in the comment heading a program:

Even with simple goals such as sum(1,1), this goes into an infinite loop using the first clause - the second clause is never checked, because the first clause never actually fails

A better version reorders the rules:

This leads to a couple of useful slogans:

Obviously we just need to add an extra constraint to the rule, requiring N to be positive (if N is negative, then sum(N,S) should fail because no such S exists):

Unfortunately, this still loops infinitely: the constraint needs to come before the recursion to avoid looping

What we're talking about here is the final reordering above

The rule is to place primitive constraints at the first place in the rule body where they might cause failure

Putting them any later might allow unnecessary search before the constraint is evaluated

Putting them earlier just adds to the number of constraints which the system has to continually re-check

The handling of user-defined constraints relies on the concept of determinism:

A (simplified) derivation tree is deterministic if it is finite and each node has at most one non-failed child (that is, every side track fails immediately, and there is either no success node, or the path to the success node is direct)

For example our "sumlist" is deterministic for the mode in which the first argument is a fixed list

The first three versions of "sum" are not deterministic for the mode in which the first argument is fixed; the final version is deterministic for this mode

Deterministic predicates

• are quick to evaluate
• have at most one success state

so should be placed as early as possible

However the mode of a goal affects its determinism; but the position of a goal in a clause may affect its determinism (ie moving a goal forward may change a deterministic goal to a non-deterministic one)

So the general rule is to move deterministic goals as far forward as is possible without losing their determinism:

If we intend to use this to find the grandfathers of given people (ie the second argument is fixed), the first literal in each of these clauses is non-deterministic and the second is deterministic

We would be better off with a reordering:

Note that in the re-ordered rules, the second literals have become deterministic - but we cannot move them back again, because then they become non-deterministic

A redundant constraint is one which can be removed from a goal without changing any answers

An answer-redundant constraint is one which is redundant with respect to the rest of the literals in the body of a rule

For another, suppose we wish to extend 'sum' to the mode where the sum is fixed, but the number to be summed is unknown

The current version will work for values of S for which there is such an N, but will loop infinitely for other values of S

This can be fixed by further answer redundancy:

The new literal is answer-redundant (all successful computations must generate a positive S), but dramatically improves the termination characteristics of sum

A solver-redundant constraint is one which is redundant with respect to the current state of the constraint store

The point here is that the constraint system may reach a point where the current constraints are unsatisfiable, but the solver is unable to detect this

For example, the CLPR system is unable to detect the unsatisfiability of nonlinear constraint

If we run the program

We might think to add an answer-redundant literal as with sum to get

But the program still loops; after four loops, the system can infer the constraint

which is unsatisfiable, but because it is nonlinear, CLPR cannot detect the unsatisfiability

Further transforming the program to