peter@yetti.UUCP (Runge) (08/12/85)
The User's Manual for DEC10 Prolog (circa 1978) had several useful sections
on definite-clause grammars, grammar rules for "Edinburgh" syntax, example
programs, and (early) Prolog references. None of this information was in
the C-Prolog manual distributed with C-Prolog 1.5, so before our beloved
(:-)) TOPS-10 machine vanished into oblivion, I converted these sections into
"troff -ms" format to serve as an appendix to the C-Prolog manual which we
distribute to students in a LP course here. There is no copyright on this
material, as far as I can tell, so I hope F. Pereira & Co. won't mind. I'm posting
the excerpts to the net, at the suggestion of a colleague. I wouldn't mind
hearing from anyone who found it useful (or who objects to long articles
containing material of ancient vintage); it's hard for me to gauge whether
or not purely pedagogical material such as this should be circulated on the
net.
The excerpts follow:
-----------------------------------------------------------------------------
.RP
.TL
GRAMMARS, SYNTAX, EXAMPLES,
and REFERENCES
Excerpts from
"User's Guide to DECsystem-10 PROLOG",
September 1978.
.AU
Fernando C. N. Pereira, Luis Moniz Pereira, and David H. D. Warren
.AB no
The following excerpts from the DEC-10 Prolog manual provided by the
Department of Artificial Intelligence, University of Edinburgh, contain
useful information for C-PROLOG programmers, and so are included
as an "addendum" to the
.I
C-Prolog User's Manual.
.R
.LP
The first excerpt, DEFINITE CLAUSE GRAMMARS, describes
the syntax and semantics of grammar rules in Prolog.
These are mentioned fleetingly at the end
of the C-Prolog User's Manual but are not otherwise documented.
They are, however, implemented in Version 1.5, exactly as described
in the DEC-10 manual.
.LP
The FULL SYNTAX section provides a detailed description of
DEC-10 Prolog syntax. This is useful for debugging syntax
errors, and is of interest if one wishes to consider alternative
or additional constructs to Prolog.
.LP
The EXAMPLES section illustrates a number of Prolog programming
techniques.
.LP
REFERENCES contains useful references
to the original papers defining resolution and definite-clause
grammars.
.LP
Some small editorial changes have been made to the original text.
.DS
P. H. Roosen-Runge
.DE
.AE
.SH
DEFINITE CLAUSE GRAMMARS
.PP
Prolog's
.I
grammar rules
.R
provide a convenient notation for
expressing
.I
definite clause grammars
.R
[Colmerauer 1975] [Pereira &
Warren 1978]. Definite clause grammars are an extension of the
well-known context-free grammars.
.PP
A grammar rule takes the general form:
.DS
.I
LHS --> RHS.
.R
.DE
meaning "a possible form for
.I LHS
is
.I RHS
". Both
.I LHS
and
.I RHS
are
sequences of one or more items linked by the standard Prolog
conjunction operator ','.
.PP
Definite clause grammars extend context-free grammars in the
following ways:
.IP (1)
A non-terminal symbol may be any Prolog term (other than a
variable or integer).
.IP (2)
A terminal symbol may be any Prolog term. To distinguish
terminals from non-terminals, a sequence of one or more terminal
symbols is written within a grammar rule as a Prolog list. An empty
sequence is written as the empty list '[]'. If the terminal symbols
are ASCII character codes, such lists can be written (as elsewhere) as
strings. An empty sequence is written as the empty list '[]' or '""'.
.IP (3)
Extra conditions, in the form of Prolog procedure calls, may be
included in the right-hand side of a grammar rule. Such procedure
calls are written enclosed in '{' '}' brackets.
.IP (4)
The left-hand side of a grammar rule consists of a non-terminal,
optionally followed by a sequence of terminals (again written as a
Prolog list).
.IP (5)
Alternatives may be stated explicitly in the right-hand side of a
grammar rule, using the disjunction operator ';' as in Prolog.
.IP (6)
The cut symbol may be included in the right-hand side of a grammar
rule, as in a Prolog clause. The cut symbol does not need to be
enclosed in '{' '}' brackets.
.LP
.PP
As an example, here is a simple grammar which parses an
arithmetic expression (made up of digits and operators) and computes
its value:
.DS
expr(Z) --> term(X), "*", expr(Y), {Z is X * Y}.
expr(Z) --> term(X), "/", expr(Y), {Z is X / Y}.
expr(X) --> term(X).
term(Z) --> number(X), "+", term(Y), {Z is X + Y}.
term(Z) --> number(X), "-", term(Y), {Z is X - Y}.
term(Z) --> number(Z).
number(C) --> "+", number(C).
number(C) --> "-", number(X), {C is -X}.
number(X) --> [C], {"0"=<C, C=<"9", X is C - "0"}.
.DE
.PP
In the last rule, C is the ASCII code of some digit.
.PP
The question
.DS
?- expr(Z,"-2+3*5+1",[])
.DE
will compute Z=14. The two extra arguments are explained below.
.PP
Now, in fact, grammar rules are merely a convenient "syntactic
sugar" for ordinary Prolog clauses. Each grammar rule takes an input
string, analyses some initial portion, and produces the remaining
portion (possibly enlarged) as output for further analysis. The
arguments required for the input and output strings are not written
explicitly in a grammar rule, but the syntax implicitly defines them.
We now show how to translate grammar rules into ordinary clauses by
making explicit the extra arguments.
.PP
A rule such as
.DS
p(X) --> q(X).
.DE
translates into:
.DS
p(X,S0,S) :- q(X,S0,S).
.DE
If there is more than one non-terminal on the right-hand side, as in:
.DS
p(X,Y) --> q(X), r(X,Y), s(Y).
.DE
then corresponding input and output arguments are identified, as in:
.DS
p(X,Y,S0,S) :- q(X,S0,S1), r(X,Y,S1,S2), r(Y,S2,S).
.DE
Terminals are translated using the predicate 'c(S1,X,S2)', read
as "point S1 is connected by terminal X to point S2", and defined by
the single clause:
.DS
c([X|S],X,S).
.DE
Then, for instance:
.DS
p(X) --> [go,to], q(X), [stop].
.DE
is translated by:
.DS
p(X,S0,S) :-
c(S0,go,S1), c(S1,to,S2), q(X,S2,S3), c(S3,stop,S).
.DE
.PP
Extra conditions expressed as explicit procedure calls naturally
translate as themselves, e.g.
.DS
p(X) --> [X], {integer(X), X>0}, q(X).
.DE
translates to:
.DS
p(X,S0,S) :- c(S0,X,S1), integer(X), X>0, q(X,S1,S).
.DE
Similarly, a cut is translated literally.
.PP
Terminals on the left-hand side of a rule translate into an
explicit list in the output argument of the main non-terminal, e.g.
.DS
is(N), [not] --> [aint].
.DE
becomes:
.DS
is(N,S0,[not,..S]) :- c(S0,aint,S).
.DE
.PP
Disjunction has a fairly obvious translation, e.g.
.DS
args(X,Y) --> dir(X), [to], indir(Y); indir(Y), dir(X).
.DE
translates to:
.DS
args(X,Y,S0,S) :-
dir(X,S0,S1), c(S1,to,S2), indir(Y,S2,S);
indir(Y,S0,S1), dir(X,S1,S).
.DE
.bp
.SH
FULL SYNTAX
.LP
A Prolog program consists of a sequence of sentences. Each
sentence is a Prolog term. How terms are interpreted as sentences is
defined in Section 2 below. Note that a term representing a
sentence may be written in any of its equivalent syntactic forms. For
example, the 2-ary functor ':-' could be written in standard prefix
notation instead of as the usual infix operator.
.LP
Terms are written as sequences of tokens. Tokens are sequences
of characters which are treated as separate symbols. Tokens include
the symbols for variables, constants and functors, as well as
punctuation characters such as brackets and commas.
.LP
Section 3 below defines how lists of tokens are interpreted as
terms. Each list of tokens which is read in (for interpretation as a
term or sentence) has to be terminated by a full-stop token. Two
tokens must be separated by a space token if they could otherwise be_
interpreted as a single token. Both space tokens and comment tokens
are ignored when interpreting the token list as a term. A comment may
appear at any point in a token list (separated from other tokens by
spaces where necessary).
.LP
Section 4 below defines how tokens are represented as strings
of characters. But first Section 1 describes the notation used in
the formal definition of Prolog syntax.
.NH
Notation
.IP (1)
Literal characters in rules appear in inverted-quotes (` `). If not so quoted,
punctuation such as
.I -->
,
.I |
,
.I ?
, and
.I ...
are part of the syntax of the grammar rules themselves.
.IP (2)
A syntactic rule takes the general form:
.DS
.I
C --> F1 | F2 | F3 . . .
.R
.DE
which states that an entity of category C may take any of the
alternative forms F1, F2, F3, etc.
.IP (3)
Certain definitions and restrictions are given in ordinary
English, enclosed in { } brackets.
.IP (4)
A category written as
.I
C...
.R
denotes a sequence of one or more Cs.
.IP (5)
A category written as
.I
?C
.R
denotes an optional C. Therefore
.I
?C...
.R
denotes a sequence of zero or more Cs.
.IP (6)
A few syntactic categories have names with arguments, and rules in
which they appear may contain meta-variables in the form of
capital letters. The meaning of such rules should be clear from
analogy with rules in definite clause grammars.
.bp
.NH
Syntax Of Sentences As Terms
.PP
.DS
.I
sentence --> clause | directive | grammar-rule
clause --> non-unit-clause | unit-clause
directive --> command | question | file-list
non-unit-clause --> ( head `:-` goals )
unit-clause --> head
{ where head is not otherwise a sentence }
command --> ( `:-` goals )
question --> ( `?-` goals )
file-list --> list
head --> term
{ where term is not an integer or variable }
goals --> ( goals `,` goals )
| ( goals `;` goals )
| goal
goal --> term
{ where term is not an integer
and is not otherwise a goals }
grammar-rule --> ( gr-head `-->` gr-body )
gr-head --> non-terminal
| ( non-terminal `,` terminals )
gr-body --> ( gr-body `,` gr-body )
| ( gr-body `;` gr-body )
| non-terminal
| terminals
| gr-condition
non-terminal --> term
{ where term is not an integer or variable
and is not otherwise a gr-body }
terminals --> list | string
gr-condition --> { goals }
.R
.DE
.NH
Syntax Of Terms As Tokens
.PP
.DS
.I
term-read-in --> subterm(1200) full-stop
subterm(N) --> term(M) { where M is less than or equal to N }
term(N) --> op(N,fx)
| op(N,fy)
| op(N,fx) subterm(N-1)
{ except the case `-` number }
{ if subterm starts with a `(`, op must be followed by a space }
| op(N,fy) subterm(N)
{ if subterm starts with a `(`, op must be followed by a space }
| subterm(N-1) op(N,xfx) subterm(N-1)
| subterm(N-1) op(N,xfy) subterm(N)
| subterm(N) op(N,yfx) subterm(N-1)
| subterm(N-1) op(N,xf)
| subterm(N) op(N,yf)
term(1000) --> subterm(999) , subterm(1000)
term(0) --> functor ( arguments )
{ provided there is no space between the functor and the '(' }
| ( subterm(1200) )
| { subterm(1200) }
| list
| string
| constant
| variable
op(N,T) --> functor
{ where functor has been declared as an operator of type T
and precedence N }
arguments --> subterm(999)
| subterm(999) , arguments
.DE
.DS
.I
list --> `[]`
| `[` listexpr `]`
listexpr --> subterm(999)
| subterm(999) `,` listexpr
| subterm(999) `|` subterm(999)
| `..` subterm(999)
.DE
.DS
.I
constant --> atom | integer
atom --> name { where name is not a prefix operator }
integer --> number | `-` number
functor --> name
.R
.DE
.NH
Syntax Of Tokens As Character Strings
.PP
.DS
.I
token --> name
| number
| variable
| string
| punctuation-char
| decorated-bracket
| space
| comment
| full-stop
name --> quoted-name
| word
| symbol
| solo-char
| `[]`
| `{}`
quoted-name -->`'` quoted-item... `'`
quoted-item --> char { other than ' }
| `''`
.DE
.DS
.I
word --> capital-letter ?alpha...
{ in the 'NOLC' convention only }
word --> small-letter ?alpha...
symbol --> symbol-char...
{ except in the case of a full-stop
or where the first 2 chars are /* }
number --> digit...
variable --> underline ?alpha...
variable --> capital-letter ?alpha..
{ in the 'LC' convention only }
.DE
.DS
.I
string --> `"` ?string-item... `"`
string-item --> char { other than " } | ""
decorated-bracket --> `%(` | `%)`
space --> space-char...
comment --> `/*` ?char... `*/` { where ?char... must not contain */ }
| `%` { up to end of the line }
full-stop --> `.` space-char
.DE
.DS
.I
char --> { any ASCII character, i.e. }
space-char
| alpha
| symbol-char
| solo-char
| punctuation-char
| quote-char
space-char --> { any ASCII character code up to 32,
includes <blank>, <cr> and <lf> }
alpha --> letter | digit | underline
letter --> capital-letter | small-letter
capital-letter --> { any character from the list
ABCDEFGHIJKLMNOPQRSTUVWXYZ }
small-letter --> { any character from the list
abcdefghijklmnopqrstuvwxyz }
digit --> { any character from the list 012346789 }
.DE
.DS
.I
symbol-char --> { any character from the list +-*/ ~<>= ^:.?@#$& }
solo-char --> { any character from the list ;!% }
punctuation-char --> { any character from the list ()[]{},| }
quote-char --> { any character from the list '" }
underline --> { the character _ }
.R
.DE
.NH
Notes
.PP
.IP (1)
The expression of precedence 1000 (i.e. belonging to syntactic
category term(1000)) which is written:
.DS
X,Y
.DE
denotes the term ','(X,Y) in standard syntax.
.IP (2)
The bracketed expression (belonging to syntactic
category term(0)):
.DS
(X)
.DE
denotes simply the term X.
.IP (3)
The curly-bracketed expression (belonging to syntactic category
term(0)):
.DS
{X}
.DE
denotes the term '{}'(X) in standard syntax.
.IP (4)
The decorated brackets `%(` and `%)` are alternatives for the
curly brackets `{` and `}` respectively. E. g.
.DS
{X} = %(X%)
.DE
.IP (5)
Note that, for example, `-3` denotes an integer whereas `-(3)`
denotes a compound term which has the 1-ary functor `-` as its
principal functor.
.IP (6)
The character `"` within a string must be written duplicated;
similarly for the character `'` within a quoted atom.
.bp
.SH
EXAMPLES
.PP
Some simple examples of Prolog programming are given below. To
clearly differentiate the examples themselves, they are marked with a
vertical bar in the left margin.
.PP
.NH 0
Simple List Processing
.PP
The goal 'concatenate(L1,L2,L3)' is true if list L3 consists of
the elements of list L1 concatenated with the elements of list L2.
The goal 'member(X,L)' is true if X is one of the elements of list L.
The
goal 'reverse(L1,L2)' is true if list L2 consists of the elements of
list L1 in reverse order.
.DS
| concatenate([X|L1],L2,[X|L3]) :- concatenate(L1,L2,L3).
| concatenate([],L,L).
|
| member(X,[X|L]).
| member(X,[_|L]) :- member(X,L).
|
| reverse(L,L1) :- reverse_concatenate(L,[],L1).
|
| reverse_concatenate([X|L1],L2,L3) :-
| reverse_concatenate(L1,[X|L2],L3).
| reverse_concatenate([],L,L).
.DE
.NH
A Small Database
.PP
The goal 'descendant(X,Y)' is true if Y is a descendant of X.
.DS
| descendant(X,Y) :- offspring(X,Y).
| descendant(X,Z) :- offspring(X,Y), descendant(Y,Z).
|
| offspring(abraham,ishmael).
| offspring(abraham,isaac).
| offspring(isaac,esau).
| offspring(isaac,jacob).
.DE
.PP
If for example the question:
.DS
?- descendant(abraham,X).
.DE
is executed, Prolog's backtracking results in different descendants of
Abraham being returned as successive instances of the variable X, i.e.
.DS
X = ishmael
X = isaac
X = esau
X = jacob
.DE
.NH
Quick-Sort
.PP
The goal 'qsort(L,[],R)' is true if list R is a sorted version of
list L. More generally, 'qsort(L,R0,R)' is true if list R consists of
the members of list L sorted into order, followed by the members of
list R0. The algorithm used is a variant of Hoare's "Quick Sort".
.DS
| qsort([X|L],R0,R) :-
| partition(L,X,L1,L2),
| qsort(L2,R0,R1),
| qsort(L1,[X|R1],R).
| qsort([],R,R).
|
| partition([X|L],Y,[X|L1],L2) :- X =< Y, !,
| partition(L,Y,L1,L2).
| partition([X|L],Y,L1,[X|L2]) :- X > Y, !,
| partition(L,Y,L1,L2).
| partition([],_,[],[]).
.DE
.NH
Differentiation
.PP
The goal 'd(E1,X,E2)' is true if expression E2 is a possible form
for the derivative of expression E1 with respect to X.
.DS
| :-op(300,xfy,~).
| d(U+V,X,DU+DV) :-!, d(U,X,DU), d(V,X,DV).
| d(U-V,X,DU-DV) :-!, d(U,X,DU), d(V,X,DV).
| d(U*V,X,DU*V+U*DV) :-!, d(U,X,DU), d(V,X,DV).
| d(U~N,X,N*U~N1*DU) :-!, integer(N), N1 is N-1, d(U,X,DU).
| d(-U,X,-DU) :-!, d(U,X,DU).
| d(exp(U),X,exp(U)*DU) :-!, d(U,X,DU).
| d(log(U),X,DU/U) :-!, d(U,X,DU).
| d(X,X,1) :-!.
| d(C,X,0) :- atomic(C), C == 0, !.
.DE
.NH
Mapping A List Of Items Into A List Of Serial Numbers
.PP
The goal 'serialise(L1,L2)' is true if L2 is a list of serial
numbers corresponding to the members of list L1, where the members of
L1 are numbered (from 1 upwards) in order of increasing size,
e.g. ?-serialise([1,9,7,7],X). gives X = [1,3,2,2].
.DS
| serialise(Items,SerialNos) :-
| pairlists(Items,SerialNos,Pairs),
| arrange(Pairs,Tree),
| numbered(Tree,1,N).
|
| pairlists([X|L1],[Y|L2],[pair(X,Y)|L3]) :- pairlists(L1,L2,L3).
| pairlists([],[],[]).
|
| arrange([X|L],tree(T1,X,T2)) :-
| split(L,X,L1,L2),
| arrange(L1,T1),
| arrange(L2,T2).
| arrange([],void).
|
| split([X|L],X,L1,L2) :-!, split(L,X,L1,L2).
| split([X|L],Y,[X|L1],L2) :- before(X,Y),!, split(L,Y,L1,L2).
| split([X|L],Y,L1,[X|L2]) :- before(Y,X),!, split(L,Y,L1,L2).
| split([],_,[],[]).
|
| before(pair(X1,Y1),pair(X2,Y2)) :- X1 < X2.
|
| numbered(tree(T1,pair(X,N1),T2),N0,N) :-
| numbered(T1,N0,N1),
| N2 is N1+1,
| numbered(T2,N2,N).
| numbered(void,N,N).
.DE
.NH
Use Of Meta-Predicates
.PP
This example illustrates the use of the meta-predicates 'var' and
'=..'. The procedure call 'variables(Term,L,[])' instantiates variable
L to a list of all the variable occurrences in the term Term.
For example,
.DS
variables(d(U*V,X,DU*V+U*DV), [U,V,X,DU,V,U,DV], []).
| variables(X,[X|L],L) :- var(X),!.
| variables(T,L0,L) :- T =.. [F|A], variables1(A,L0,L).
|
| variables1([T|A],L0,L) :- variables(T,L0,L1), variables1(A,L1,L).
| variables1([],L,L).
.DE
.NH
Prolog In Prolog
.PP
This example shows how simple it is to write a Prolog interpreter
in Prolog, and illustrates the use of a variable goal. In this
mini-interpreter, goals and clauses are represented as ordinary Prolog
data structures (i.e. terms). Terms representing clauses are specified
using the unary predicate 'clause', e.g.
.DS
clause( (grandparent(X,Z):-parent(X,Y),parent(Y,Z)) ).
.DE
.PP
A unit clause will be represented by a term such as:
.DS
clause( parent(john,mary) :- true )
.DE
.PP
The mini-interpreter consists of four clauses:
.DS
| execute(true) :-!.
| execute((P,Q)) :- !, execute(P), execute(Q).
| execute(P) :- clause((P:-Q)), execute(Q).
| execute(P) :- P.
.DE
The last clause enables the mini-interpreter to cope with calls to
ordinary Prolog predicates, e.g. evaluable predicates.
.NH
Translating English Sentences Into Logic Formulae
.PP
The following example of a definite clause grammar defines in a
formal way the traditional mapping of simple English sentences into
formulae of classical logic. By way of illustration, if the
sentence:
.DS
Every man that lives loves a woman.
.DE
is parsed as a 'sentence(P)', P will get instantiated to:
.DS
all(X):(man(X)&lives(X) => exists(Y):(woman(Y)&loves(X,Y)))
.DE
where ':', '&' and '=' are infix operators defined by:
.DS
:-op(900,xfx,=>).
:-op(800,xfy,&).
:-op(300,xfx,:).
.DE
.PP
The grammar follows:
.DS
| sentence(P) --> noun_phrase(X,P1,P), verb_phrase(X,P1).
|
| noun_phrase(X,P1,P) -->
| determiner(X,P2,P1,P), noun(X,P3), rel_clause(X,P3,P2).
| noun_phrase(X,P,P) --> name(X).
|
| verb_phrase(X,P) --> trans_verb(X,Y,P1), noun_phrase(Y,P1,P).
| verb_phrase(X,P) --> intrans_verb(X,P).
|
| rel_clause(X,P1,P1&P2) --> [that], verb_phrase(X,P2).
| rel_clause(_,P,P) --> [].
|
| determiner(X,P1,P2, all(X):(P1=>P2) ) --> [every].
| determiner(X,P1,P2, exists(X):(P1&P2) ) --> [a].
|
| noun(X, man(X) ) --> [man].
| noun(X, woman(X) ) --> [woman].
|
| name(john) --> [john].
|
| trans_verb(X,Y, loves(X,Y) ) --> [loves].
| intrans_verb(X, lives(X) ) --> [lives].
.DE
.bp
.SH
REFERENCES
.LP
.nj
.nf
Colmerauer A [1975]
"Les Grammaires de Metamorphose".
Groupe d'Intelligence Artificielle,Marseille-Luminy. Nov 1975.
Appears as "Metamorphosis Grammars" in "Natural Language
Communication with Computers", Springer Verlag, 1978.
van Emden M H [1975]
"Programming with Resolution Logic".
Report CS-75-30, Dept. of Computer Science, University of
Waterloo, Canada. Nov 1975.
Kowalski R A [1974]
"Logic for Problem Solving".
DCL Memo 75, Dept of AI, Edinburgh. Mar 74.
Pereira F C N & Warren D H D [1978]
"Definite Clause Grammars Compared with Augmented Transition
Networks".
Forthcoming report, Dept. of AI, Edinburgh.
Robinson J A [1965]
"A Machine-Oriented Logic Based on the Resolution Principle".
JACM vol 12, pp.23-44. 1965.
Roussel P [1975]
"Prolog : Manuel de Reference et d'Utilisation".
Groupe d'Intelligence Artificielle, Marseille-Luminy. Sep 1975.
Warren D H D [1977]
"Implementing Prolog - Compiling Predicate Logic Programs".
Research reports 39 & 40, Dept. of AI, Edinburgh. 1977.
Warren D H D, Pereira L M, Pereira, F C N [1977]
"Prolog - the Language and its Implementation Compared with
Lisp".
Procs. of the ACM Symposium on Artificial Intelligence and
Programming Languages, SIGART/SIGPLAN Notices, Rochester, N.Y.,
Aug 1977.
--
Peter H. Roosen-Runge, Department of Computer Science, York University
Toronto M3J 1P3 , Ontario, Canada
_____________________________________________________________________________
"Eccles, is the ship sinking?" "Only below the sea."
"We must try to save the ship -- help me get it into the lifeboat."
_____________________________________________________________________________