.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Declarative Programming
Flexible computation in Prolog
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The idea of flexible computation
▶ If we are really to thnk of our programs only as logic, we
need to get away completely from the idea of a
computation rule which determines execution order
▶ This means that we are forced not to depend on that
order, but to write code which is indeed purely logical
▶ Perhaps surprisingly, making this possible can lead us to
more, and not less, efficient programs
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example 1: floundering
▶ The problem of floundering: negation as failure in Prolog
sometimes gives us logically incorrect results:
?- \+ X = 2, X = 5.
false
?- X = 5, \+ X = 2.
true
▶ The problem here lies in the fixed ordering of the Prolog
clauses
▶ If we could delay the execution of the negated goal until
X was ground, there would not be a problem
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example 2: unbounded recursion
▶ A badly ordered set of clauses:
ancestor( Old, Young ) :-
ancestor( Middle, Young ),
parent( Old, Middle ).
ancestor( Old, Young ) :-
parent( Old, Young ).
▶ Any call to ancestor/2 will result in unbounded
recursion, because of the shape of the recursive clause
▶ But this and the correctly ordered version are logically
equivalent; we would like their behaviour to be the same.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Flexible computation in SWI Prolog
▶ In SWI Prolog Prolog, we can block the execution of a
predicate until one or more of its arguments are
instantiated
▶ In the vast majority of cases, this will solve the problem
▶ For ancestor, we could block execution when the first
argument is uninstantiated:
:- block ancestor( -, ? ).
ancestor( Old, Young ) :-
ancestor( Middle, Young ),
parent( Old, Middle ).
ancestor( Old, Young ) :-
parent( Old, Young ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Flexible computation in SWI Prolog (2)
▶ Here’s a definition of parent/2:
% parent( Older, Younger ).
parent( john, jim ).
parent( jane, jim ).
parent( jack, john ).
▶ Consider the trace of the following goal:
% a simple trace
?- ancestor(john, jim).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Flexible computation in SWI Prolog (3)
?- ancestor(jane,jim).
1 1 Call: ancestor(jane,jim) ?
– – Block: ancestor(_446,jim)
2 2 Call: parent(jane,_446) ?
– – Unblock: ancestor(jim,jim)
3 3 Call: ancestor(jim,jim) ?
– – Block: ancestor(_1172,jim)
4 4 Call: parent(jim,_1172) ?
4 4 Fail: parent(jim,_1172) ?
4 4 Call: parent(jim,jim) ?
4 4 Fail: parent(jim,jim) ?
3 3 Fail: ancestor(jim,jim) ?
2 2 Fail: parent(jane,_446) ?
2 2 Call: parent(jane,jim) ?
2 2 Exit: parent(jane,jim) ?
1 1 Exit: ancestor(jane,jim) ?
true
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Flexible computation in SWI Prolog (4)
▶ But beware: block declarations are very much a blunt
instrument
▶ Look what happens if we call
?- ancestor( Who, jim )?
user:ancestor( Who, jim ) ?
true
▶ This uncompleted goal is called a residue, and it
represents a goal that has never been unblocked.
▶ block declarations may be thought of as static – ie they
are set at compile time once and for all
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Dynamic flexible computation
▶ A more useful and precise method of flexible execution is
the dynamic delay declaration supplied by the when/2
meta-predicate
▶ when/2 has arguments as follows:
1. a specification of when to run the goal – built up from
the following meta-predicates and operators
ground/1
nonvar/1
?=/2
,
;
(?=/2 succeeds iff its arguments are syntactically
identical or non-unifiable)
2. the goal to be run
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
How to deal with floundering!
▶ Delay the negated goal until it is ground:
not( X ) :- when( ground(X), \+ X ).
?- not(X=2),X=5.
1 1 Call: not(_183=2) ?
– – Block: when(ground(_556=2),user:(\+ _556=2))
1 1 Exit: not(_556=2) ?
2 1 Call: _556=5 ?
– – Unblock: prolog:trig_ground(5,[],[5],_561,_561)
3 2 Call: prolog:trig_ground(5,[],[5],_561,_561) ?
– – Unblock: prolog:when(1,ground(5=2),user:(\+ 5=2))
4 3 Call: prolog:when(1,ground(5=2),user:(\+ 5=2)) ?
5 4 Call: 5=2 ?
5 4 Fail: 5=2 ?
4 3 Exit: prolog:when(1,ground(5=2),user:(\+ 5=2)) ?
3 2 Exit: prolog:trig_ground(5,[],[5],1,1) ?
2 1 Exit: 5=5 ?
X = 5 ?
true
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
How to deal with floundering! (2)
▶ NB this is not the same as using a block declaration:
:- block not(-).
not( X ) :- \+ X.
because block will only delay on uninstantiated terms,
and not on partially instantiated ones
▶ So with this definition,
?- not( X = 2 ).
is no different from
?- \+ X = 2.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
How to deal with floundering! (3)
▶ Finally, what about the case where we want
uninstantiated negative calls? Eg,
\+ test( _ )
can be used to mean “test/1 never succeeds” or “for all
inputs, test is false”.
▶ We could give a specific version of not, which allowed us
to name a list of the variables we cared about:
not( Vars, Goal ) :-
when( ground( Vars ), \+ Goal ).
?- not( [X,Y], test( X, Y, Z )).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: the worst correct sorting algorithm in the
world!
▶ The so-called British Museum sort works by permuting its
input and then testing to see if the result is in order:
bmsort( X, Y ) :- perm( X, Y ),
format(‘Try ~w\n’,[Y]),
ord( Y ).
ord( [] ).
ord( [_] ).
ord( [H1,H2|T] ) :- H1 =< H2,
ord( [H2|T] ).
perm( [], [] ).
perm( [X|Y], [U|V] ) :- del( U, [X|Y], W ),
perm( W, V ).
del( X, [X|Y], Y ).
del( X, [Y|U], [Y|V] ) :- del( X, U, V ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
British Museum Sort
▶ Running it gives us this:
?- bmsort([3,2,1],G).
Try [3,2,1]
Try [3,1,2]
Try [2,3,1]
Try [2,1,3]
Try [1,3,2]
Try [1,2,3]
G = [1,2,3] ?
true
▶ So this algorithm is of order n! where n is the length of
the list!
▶ However, the specification of the sorting algorithm is very
elegant
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Delayed British Museum Sort
▶ We can improve the execution of this algorithm until it is
nearly order n2 – a big improvement
▶ First, we arrange to do the checking of ordered-ness as
early as possible – in fact, as soon as we have a
non-variable to check:
dbmsort(X,Y) :-
when( nonvar( Y ), ord2( Y )),
perm( X, Y ).
▶ Second, we need a delayed version of =<, so that we don’t
try and compare uninstantiated values by mistake:
:- block le(-,-), le(-,?), le(?,-).
le( X, Y ) :- X =< Y.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Delayed British Museum Sort (2)
▶ Finally, we need to adjust ord/1 so that it will test each
pair in the list as soon as possible:
ord2( [H1,H2|T] ) :-
le( H1, H2 ),
when( nonvar( T ), ord2( [H2|T] )).
ord2( [_] ).
ord2( [] ).
▶ Note the clause order here – because we have now
delayed ord/1, unbounded recursion is never a problem;
we always go to the right clause first.
▶ Note also that these declarations are nothing more than
good programming style – they ensure that all our
predicates will work sensibly when used in any context
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Delayed British Museum Sort (3)
▶ You can find the code for the two versions of the British
Museum Sort in the library supplied for the module
▶ Compare the behaviours of the two versions using the
debugger (note that if you use the library version, you will
get a less verbose trace output, which may be easier to
follow)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Delayed British Museum Sort (4)
▶ Finally, consider this behaviour:
?- dbmsort( [4,3,V,1], Y ).
Y = [4,V,1,3],
user:le(4,V),
user:le(V,1) ? ;
Y = [3,4,V,1],
user:le(4,V),
user:le(V,1) ? ;
Y = [3,V,1,4],
user:le(3,V),
user:le(V,1) ? ;
etc.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Delayed British Museum Sort (5)
▶ Note that the variable divides the list into two sorted
components…
▶ …and that the residue constrains V to fit in a certain
range of values
▶ However, we could in principle rule out some of these
solutions, because some of the ranges have no members
(eg V >= 3, V =< 1).
▶ In the next lecture, we will extend the flexible execution
idea to well-defined mathematical systems, which will
allow even more powerful reduction of the search space
for solutions