CS计算机代考程序代写 prolog flex Declarative Programming

Declarative Programming
Difference Lists &

Definite Clause Grammars

Geraint A. Wiggins

Professor of Computational Creativity
Department of Computer Science

Vrije Universiteit Brussel

The problem with (ordinary) lists

I Lists are a very useful structure in all programming
languages, not just Prolog

I They allow us to represent collections of unknown
numbers of items in a manageable way

I However, they are rather inflexible, because they can only
be manipulated from one end, eg

% member/2 – is arg1 member of arg2?

member( Head, [Head| Tail] ).

member( Term, [ Head|Tail] ). :-

member( Term, Tail ).

I So if I am interested in the very end of a list, and it is
10,000,000 items long, I have to do 10,000,000 logical
inferences to get there!

The problem with (ordinary) lists (2)

I For example, append/3 is a very common operation. . .

I . . . but it takes N logical inferences merely to put a list of
N elements on the front of another list

I There is a very elegant solution to this problem, which is
a side-effect of unification

NB: this facility is not in any way built-in to Prolog
– it arises coincidentally from the way Prolog works.

(This causes a minor problem later.)

Difference Lists

I A difference list is a list which is expressed as the
difference between two other lists

I Example: the ordinary list

[a,b,c]

might be expressed as

[a,b,c,d,e]-[d,e]

or as

[a,b,c,a,b,c]-[a,b,c]

NB. the – does not mean anything special to Prolog
– a difference list is just a Prolog term

Difference Lists

I To emphasise this point, we could write a difference list
like any of these:

[a,b,c]*[]

[a,b,c,d]=[d]

dlist( [a,b,c,d,e], [d,e] )

or using separate arguments to a predicate

It’s the way we use difference lists that makes them
special, not their syntax

Using difference lists

I The clever part comes when we allow variables in d-lists

I Example:

[a,b,c|X]-X

I This is the most general way to write the d-list containing
the elements a, b and c.

I We now have access to the head of the list (in the usual
way). . .

and to the tail of the list (by unifying with X).

I NB for this to be a proper difference list, there must be
only one variable name!

Using difference lists (2)

I The effect of this is that we can write append/3 for
difference lists thus:

% append/3 for d-lists

append( X-Y, Y-Z, X-Z ).

. . . so a O(n) operation now becomes a constant-time
operation!

I How does it work? Consider

?- append( [a|D1]-D1, [b|D2]-D2, Ans ).

I Note that:
I D1 and D2 must be different variables
I Ans will become a d-list, and does not have to be a

d-list in advance (though, usually, it will be one)

Using difference lists (3)
append( X-Y, Y-Z, X-Z ).

?- append( [a|D1]-D1, [b|D2]-D2, Ans ).

Call: append( [a|D1]-D1, [b|D2]-D2, Ans ).

Unify: [a|D1]-D1 = X-Y
Unify: [b|D2]-D2 = Y-Z
Unify: Ans = X-Z

Unify: X = [a|D1], Y = D1
Unify: Y = [b|D2], Z = D2

Unify: X = [a,b|D2], Z=D2
Unify: Ans = X – Z

Succeed: Ans = [a,b|D2]-D2

Using difference lists (4)

I Difference lists are likely to help in improving any program
which uses append – but. . .

you cannot unify them!!!

I Writing

[a|X]-X = [a|Y]-Y

has unpredictable results, because X and Y may have
different values

I So even though they represent the same d-list, they may
do so in different ways; thus they are not unifiable

I Unification for d-lists is not the same as identity

Definite Clause Grammars
I An important application of d-lists is in Definite Clause

Grammars (DCGs)
I DCGs are a facility in Prolog which makes it easy to

define languages according to grammar rules
I For example, we might want to define a simple input

command language for a game:
start 1 player

start 2 players

start 3 players

etc.
stop

save game

save player 1

save player 2

save player 3

etc.

Definite Clause Grammars (2)
I There is a standard way of writing this down, borrowed

from linguistics:
StartCommand → ‘start’ ‘1’ ‘player’
StartCommand → ‘start’ Number∗ ‘players’

StopCommand → ‘stop’

SaveCommand → ‘save’ SaveableThing

SaveableThing → ‘game’
SaveableThing → ‘player’ Number

Showing that a string of words is acceptable
according to a grammar like this is very like doing a

prolog proof

Definite Clause Grammars (3)
I To implement this, we have a special clause definition

operator in Prolog, –>, which we use instead of :-

I We assume that the sequences of words we want to
analyse are stored as lists

I Then we can write

startcommand –> [start,1,player].

startcommand –> [start],number gt 1,

[players].

stopcommand –> [stop].

savecommand –> [save],saveable thing.

saveable thing –> [game].

saveable thing –> [player],number.

Definite Clause Grammars (4)

I To deal with numbers, we can use Prolog

(Recall that we are only checking input here, not
generating output, so I assume that the input is ground)

number –> [X], {integer(X), X > 0}.

number gt 1 –> [X], {integer(X), X > 1}.

I So we can include arbitrary bits of Prolog code in our
DCG, by putting them in {}

I Where we put them can be significant, in the usual
Prolog way

Using the DCG

I To make the DCG really useful, we need a further
definition:

command –> startcommand.

command –> stopcommand.

command –> savecommand.

I Now, we can take a list of words and test whether or not
they are a command:

?- command([the,cat,sat,on,the,mat],[]).

false

?- command([save,player,3],[]).

true

I Note the [], and that the definition of command using
–> has led to the creation of a predicate command/2