PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (10/24/87)
PROLOG Digest Sunday, 25 Oct 1987 Volume 5 : Issue 76
Today's Topics:
Query - Backslapping & Difference List & Modules,
& Variadic Predicates & Parallelism,
Standardization - Terminology,
Implementation - Aggregates & Meaning
----------------------------------------------------------------------
Date: 2 Oct 87 13:25:01 GMT
From: ihnp4!chinet!fmsrl7!metavax!umich!dwt@ucbvax.Berkeley.EDU
(Dave West)
Subject: O'Keefe's criticism of Lagache's code.
Richard O'Keefe's contributions to the Prolog community have been immense,
but the depth of knowledge that he has is all but unattainable by the rest
of us, who haven't spent years at a Prolog centre and been involved with
several implementations. I think it would be great if he wrote the Prolog
equivalent of Steele's and Sussman's Lisp implementation papers; but since
he's in the commercial world, he probably won't. (Warren's papers are
only for the very dedicated.)
-- David West
------------------------------
Date: Thu 22 Oct 87 05:31:05-EDT
From: vijay <Vijay.Saraswat@C.CS.CMU.EDU>
Subject: Returning difference list.
Something has always bothered me about Prolog-20. Why don't the
systems procedures that return lists (such as name/2) always return
difference lists (name/3)?
------------------------------
Date: 18 Oct 87 20:16:26 GMT
From: sakthi@sally.utexas.edu (Sakthi Subramanian)
Subject: modules in Prolog
I am looking for literature on introducing modules in Prolog (or its
variants). Does anybody have any suggestions?
Thank you.
-- Sakthi
------------------------------
Date: 23 Oct 87 16:05:00 EDT
From: Andre (A.N.) Vellino <VELLINO%BNR.BITNET@forsythe.stanford.edu>
Subject: variadic predicates
I was wondering if anyone on the Digest could think of a good reason for
objecting to the idea of a Prolog that has
a) functors with variable arity (the only one that springs
to mind is that it is simple to emulate variadic predicates
with lists);
b) variable functors (so that, for example "?- Functor(Arg)."
is a valid query).
-- Andre Vellino
------------------------------
Date: 8 Oct 87 22:14:54 GMT
From: sunybcs!lakshman@ames.arpa (T. Lakshman)
Subject: Parallel Logic Programming
I have been investigating architectures for Parallel Logic Programs.
In this context I am looking for information on Parallel Architectures
and Algorithms for Logic Programs.
Thank you.
-- T.K.Lakshman
------------------------------
Date: 12 Oct 87 15:00:50 GMT
From: eagle!icdoc!doc.ic.ac.uk!cdsm@ucbvax.Berkeley.EDU
Subject: A question of terminology
Earlier I posted to the net the draft version of the Prolog Glossary
prepared for the BSI standardization project but it generated only
general murmurs of discontent. I would therefore like to try to
clarify the discontent felt at Imperial College and other centres
which approach Prolog from a background of logic.
The biggest problem is with the word "atom".
atom One of a set of unstructured objects whose only property
is that equality of two elements can be determined.
Apart from minor quibbles about this definition (does it apply to
numbers?), the word 'atom' or 'atomic formula' have traditionally been
used to describe what is here termed a literal:
literal A predicate of arity N and a sequence of N
arguments.
This definition is almost, but not quite, right. In resolution
terminology, a literal is either a predicate with arguments or its
negation (and thus postive or negative literals). But it shows that a
term is needed for this object. In most Edinburgh systems (and I take
the current Quintus manual as the current example) the only
terminology used is compound term:
compound term A functor of arity N together with a sequence of N
arguments.
The word term is used universally in this sense but there is a strong
distinction with formulas built up using logical connectives (and, or
etc), which Edinburgh systems do not recognize as being distinct.
Question: Where does the Edinburgh usage of 'atom' arise from, since there
is a long history of 'atom' meaning a term consisting of a predicate?
(from Lisp?)
We can certainly derive a long list of precedents on both sides:
Logic: Robinson(1965), Kowalski (1979), Hogger(1984), LLoyd (1984),
Charniak, McDermott(1985), Gallier(1986)
Edinburgh: DEC-10 Prolog Manual (1978), Clocksin, Mellish(1981), Sterling,
Shapiro (1986), Bratko (1986) etc.
Note: If anyone can invoke O'Keefe's "Don't kick the craftsman in the
teeth" rule, it is the logicians.
Proposal: The only way to resolve this conflict is to avoid the term
'atom' as far as possible. A possible lead is given by Giannesini, Kanoui,
Pasero, van Caneghem (1986) who call the basic objects "identifiers"- a
well-known and unambiguous computing term. The logical terms are
"constant" or "individual constant", but these can equally apply to
identifiers or numbers, as is universally recognized (and "constant"
should certainly be used in place of "atomic" as the predicate for this).
It is slightly complicated by the fact that an identifier can be an
arbitrary sequence of characters within single quotes, but this needn't be
fatal. Also a variable may be denoted by an identifier; but in this case
its identifier is precisely the individual constant we are talking about.
We also need a term for "atomic formula", as it is has been agreed to
distinguish these clearly from other terms in the standard. Here it would
seem possible to use the word "predication" (following Robinson, 1979).
This distinguishes it from "predicate", which by itself means the set
denoted by the predicate symbol. It's not reasonable to use predicate to
denote symbol+arity in contradistinction to predicate symbol, as is
proposed and we certainly shouldn't follow Sterling, Shapiro and call them
"goals" as this thoroughly confuses the thing with the usage.
I therefore propose the following (please feel free to improve the wording):
identifier A basic unstructured object which can be used to identify an
individual or name of a function or predicate.
predicate symbol An identifier and an arity, associated with a predication.
predicate (deleted)
predication A term consisting of a predicate symbol
and a list (possibly empty) of arguments
function symbol An identifier and an arity associated with a function
functor (deleted)
functor symbol (deleted)
constant An identifier, number or string
goal A predicate which appears in the body of a clause or a query.
literal (deleted)
connective A logical operator used to combine predications into rules
and queries.
query One or more goals and connectives given as interactive input
to the top level. Variable substitutions found while
executing the query may be output.
Comments please!
-- Chris Moss
------------------------------
Date: 5 Oct 87 10:41:33 GMT
From: mcvax!enea!ttds!draken!sics!lhe@uunet.uu.net (Lars-Henrik
Eriksson)
Subject: Standard of Prolog code
In at least one "high-powered commercial Prolog system" naive reverse
suffers a 35% slowdown (on a SUN) when you change append/3 to
append([],L,L).
append([H|L1], [H|L2], L3) :- append(L1, L2, L3).
i.e. change the order of the second and third arguments! The slowdown
of append itself is obviously greater, although I haven't made any
measurements. Apparently poor handling of inline predicates isn't the
only thing that's going on...
-- Lars-Henrik Eriksson
------------------------------
Date: 13 Oct 87 15:16:51 GMT
From: munnari!mulga!philip@uunet.uu.net (Philip Dart)
Subject: aggregates
Richard O'Keefe writes about aggregate/3 in Quintus Prolog
As well as solutions/3, setof/3, bagof/3 and findall/3, NU-Prolog provides
four aggregate functions: count/3, max/3, min/3 and sum/4
Arguments to these predicates fall into the following categories.
Goal: This acts as a generator, producing solutions of the form Term.
Term: The aggregate is concerned only with distinct instantiations of Term.
Subterm: What the aggregate operation, eg. + or >, is applied to.
Result: What the result of the aggregate is unified with.
count/3 is concerned only with `how many' of something there is; it can
therefore make use of just three of these arguments:
count(Term, Goal, Result)
eg. count(Term, member(Term, [pear, apple, orange, pear]), 3).
max/3 (and similarly min/3) needs to apply a comparison operation to
some term, but repeated occurrences of any term will not change the result:
max(Subterm, Goal, Result)
eg. max(Subterm, member(Subterm, [1, 2, 3, 4, 2, 2, 1]), 4).
sum/4 requires all four arguments: Consider trying to find the sum of the
salaries of all employees in 'sales' or 'service'. If some employee
is in both departments, we still only want to include his salary once
(unless of course he is paid by both :-).
employs(sales, fred). paidTo(fred, 10000).
employs(sales, bill). paidTo(bill, 20000).
employs(service, harry). paidTo(harry, 30000).
employs(service, bill).
sum(Salary, Emp-Salary,
some Dept (
(Dept = sales ; Dept = service),
employs(Dept, Emp),
paidTo(Emp, Salary)
),
60000).
(The use of 'some' simply indicates that the variable Dept is used only
in the Goal in the aggregate.)
In general, sum/4 has the form:
sum(Subterm, Term, Goal, Result)
but since Subterm (or at least all the variables in it) would always
have to be repeated in Term, sum/4 uses the combination of its first
two arguments in looking for unique solutions.
For this reason, in the above example, Emp-Salary should be replaced
by Emp.
A final example:
sum(S*3, T,
member(T/S, [orange/10, pear/100, apple/1, apple/1, apple/1000]),
3333).
count/3 can be defined trivially in terms of sum/4:
count(Term, Goal, Result) :- sum(1, Term, Goal, Result).
There are other issues relating to aggregates to be considered
such as whether solutions should be ground.
------------------------------
Date: 19 Oct 87 15:41 -0700
From: Paul Voda <voda%ubc.csnet@RELAY.CS.NET>
Subject: Where is the meaning?
The discussion of style and methodology of Prolog programming in the
recent issues of Prolog Digest is quite interesting even though it is
mostly a rather lengthy monologue. Important as the style is, let me
ask a fundamental question:
Where is the meaning?
Take the SEND+MORE=MONEY example on page 161 of Bratko's text:
?- sum1([0,S,E,N,D],[0,M,O,R,E],[M,O,N,E,Y],
0,0,[0,1,2,3,4,5,6,7,8,9],_).
sum1([],[],[],0,0,Digs,Digs).
sum1([D1|N1],[D2|N2],[D,N],Ci,Co,Digsin,Digsout) :-
sum1(N1,N2,N,Ci,Cinterm,Digsin,Digs1),
digitsum(D1,D2,Cinterm,D,Co,Digs1,Digsout).
digitsum(D1,D2,Ci,D,Co,Digsin,Digsout) :-
del(D1,Digsin,Digs1),
del(D2,Digs1,Digs2),
del(D,Digs2,Digsout),
S is D1 + D2 + Ci,
D is S mod 10,
Co is S div 10.
del(A,L,L) :-
nonvar(A), !.
del(A,[A|L],L).
del(A,[B|L],[B|L1]) :-
del(A,L,L1).
The predicate del is given in Bratko on page 71 in the standard form
as follows:
del(A,[A|L],L).
del(A,[B|L],[B|L1]) :-
del(A,L,L1).
In this form the meaning of del is straightforward:
del(x,y,z) iff
the list z is exactly like the list y minus the element x
occurring in y.
If x does not occur in y then del(x,y,z) fails. The predicate del in the SEND
problem would seem to succeed in that case. Thus its meaning should be
as follows.
del(x,y,z) iff
the list z is exactly like the list y minus the element x if x occurs
in y, otherwise y = z.
But unfortunately this is not the case because
X = 3, del(X,[1,2],[1,2])
succeeds whereas
del(X,[1,2],[1,2]), X = 3
fails. The use of the 'nonvar' construct destroys the meaning of del.
An attempt to code del without the 'nonvar' as
del(A,L,L) :-
not member(A,L).
del(A,[A|L],L).
del(A,[B|L],[B|L1]) :-
del(A,L,L1).
does solve the problem of the meaning of del, but del cannot be used
as a generator of unused digits when A is not bound.
The beuaty of logic programming is that the meaning of a predicate
depends solely on the meaning predicates used in its definition
(even if the predicate is recursive). This is how meaning is defined
in predicate calculus.
The Bratko's use of del is operational. The "meaning" is obtained by
the sequence of calls to it: Keep on binding different digits to the
unbound variables. As a consequence, the meaning of predicates
'digitsum' and 'sum' cannot be derived from the meaning of 'del'
as it should be in logic. Both predicates achieve the desired goal
only because of clever sequencing of executed operations. The only
way to reason about the predicate sum1 is by the methods taking into account
the operational side, for instance by Hoare's pre- and post-conditions.
If we are reduced to such a reasoning we do not program in a logic programming
language but rather in a backtracking Pascal.
The standard "explanation" of constructs like var is that they are
meta-theoretical: rather than to contribute to the meaning, they control the
theorem prover. The use of the nonvar in the SEND problem does indeed
operationally control the executing mechanism, but whatever the executing
mechanism is, it is not a theorem prover. The mechanism operates above
any meaning. Thus it is meta-theoretical in the very meaning of the word
'meta' of being above any theory.
The proper way of solving the SEND problem is to generate the values of
D1 and D2 in the digitsum by a predicate 'digit', compute the result digit D,
and insert a call to 'alldiff' at the end of recursion.
This method is logical but albeit slower than a Pascal-like
operational solution.
Or alternatively, one could use the delaying of predicates or constraints
if these are available. There is yet another aspect of a logical
solution to the SEND problem along the outlined lines.
It is declarative all-right, but its declarativeness is quite low level
in the sense of specifying the meaning by the predicate 'digitssum' for all
columns of the problem.
Here is the solution to the problem in the constraint based language TRILOGY
(formerly R-Maple), L is the type of 32 bit integers:
pred Send(send::L,more::L,money::L) iff
a::[0..7]->>L[0..9] & a = [s,e,n,d,m,o,r,y] &
{the above line constraints all digts to be different}
send + more = money &
m <> 0 & s <> 0 &
send = 1000*s + 100*e + 10*n + d &
more = 1000*m + 100*o + 10*r + e &
money = 10000*m + 1000*o + 100*n + 10*e + y
-- Paul J. Voda
------------------------------
End of PROLOG Digest
********************