CS计算机代考程序代写 prolog flex algorithm .

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

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