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