RESTIVO@SU-SCORE.ARPA (03/05/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Tuesday, 5 Mar 1985 Volume 3 : Issue 7
Today's Topics:
Announcement - Dr. Dobb's Journal & Talk,
Implementation - New Engine & nrev/2 & C-Prolog "Bug",
& Bounded Merge in CP
----------------------------------------------------------------------
Date: Wed, 27-Feb-85 07:34:37 PST
From: decvax!mcnc!BTS@Berkeley
Subject: Prolog in Dr. Dobb's Journal
Dr. Dobb's Journal for March is a "Special Prolog
Issue". Only three articles on Prolog, but there
are lots of ads about Prologs for small systems.
-- Bruce T. Smith
------------------------------
Date: Monday, 4 Mar 1985 14:40:44-PST
From: (Karl Puder) Puder%Bach.DEC@decwrl.ARPA
Subject: Engine
If you really mean David H. D. Warren's SRI report 309
(An Abstract Prolog Instruction Set), the copying of
permanent variables before the deallocate is done by
having the compiler generate put_unsafe_value (and
unify_local_value) instructions where appropriate.
-- Karl.
------------------------------
Date: 28 Feb 1985 21:05-EST
From: Saumya Debray <Debray%SUNY-SB@CSNet-relay.arpa>
Subject: The Warren Prolog Engine and nrev/2
With regard to Clocksin's query about the WPE, we have
an implementation of it here at Stony Brook (with, I
should add, an enlarged instruction set that incorporates
some optimizations, arithmetic, cut &c.). The query
nrev(X,[1,2]) works, producing X = [2,1] as the answer.
It's true that permanent variables in an environment have
to be saved before that environment is deallocated.
Actually, only those permanent variables whose first
occurrence is neither in the head nor inside a structure
need to be so saved (variables occurring in the head have
to occur somewhere deeper in the stack, while variables
occurring in a structure are allocated on the heap). Such
variables are called "unsafe", and may have to be moved to
the heap before the activation record is deallocated. The
instruction that does this in the WPE is the
"put_unsafe_value".
------------------------------
Date: Fri, 1-Mar-85 07:16:10 PST
From: (Ran Ever-Hadani) RAAN%TECHUNIX.BITNET@SRI-Unix
Subject: A bug with general interest in C-Prolog 1.4a
Given is the following goal:
(*once_detract* is a detract that succeeds only once)
assert(a),a,once_detract(a),assert(a),fail.
Assuming an initially empty data base, the first *assert*
will add the clause *a.* to the data base, the *a* will
succeed, the *detract* will delete it, the second *assert*
will add a new one, the second attempt to *once_detract*
will fail, and finally control would try to match another
*a.*.
At this point there are two possibilities:
1) Since a new *a.* has been asserted, it would succeed.
2) After the first time *a* succeeds, it would be
marked somewhere that there are no more *a*'s and even
though another one was added in the meanwhile, the second
attempt will fail.
There are arguments for defining it either way. Unfortunately,
C-Prolog 1.4a takes the first alternative with debug on, and
the second with debug off, which caused me a hell of a headache
trying to figure out why my program does not behave the same
with debug on and off.
The solution that worked for me was to replace every such *a,*
in my program with *clause(a,true),* which takes the first way
with debug on and off.
If someone out there knows who maintains C-Prolog, I will
appreciate it if he passes my letter on.
-- Ran Ever-Hadani
Technion, Haifa, Israel
------------------------------
Date: Sat 2 Mar 85 09:46:14-PST
From: Pereira@SRI-AI.ARPA
Subject: C-Prolog
I wrote C-Prolog, but do not maintain it as such (the last
changes, to create version 1.5, were made over one year ago).
As to that problem, it is a ``feature'', not a bug. The
intended behavior is that provided by non-debug mode, but the
way the debugger is implemented makes it rather difficult to
make debug mode behave in the same way. To make the two modes
consistent would either require a completely new debugger or
make nondebug execution much less efficient. Sorry...
-- Fernando
------------------------------
Date: Fri, 1 Mar 85 12:55:33 -0200
From: Ehud Shapiro <UDI%Wisdom.Bitnet@WISCVM.ARPA>
Subject: Vijai Saraswat's Bounded merge in CP
Unfortunately, Vijay Saraswat's program for bounded
merge in Concurrent Prolog does not work. Before
explaining why, let me show several solutions that do
work.
Since the abtsract execution model of Concurrent Prolog
(and Flat Concurrent Prolog) does not imply clause
ordering, it seems that bounded merge cannot be specified
in it without extralogical facilities. One such facility
stability: a *stable* Concurrent Prolog machine always
picks the first clause for reduction, if several clauses
with an empty guard (or with a trivial guard, in FCP) are
applicable. On a stable machine, the following program
will merge two streams fairly:
merge([X|Xs],Ys,[X|Zs]) :- merge(Ys,Xs?,Zs).
merge(Xs,[Y|Ys],[Y|Zs]) :- merge(Ys?,Xs,Zs).
merge([],Ys,Ys).
Since it alternates the priorities of the two streams.
Another solution is to rely on the fairness of the
underlying Concurrent Prolog machine. Under any
reasonable definition of a fair Concurrent Prolog
machine, the naive merge,
merge([X|Xs],Ys,[X|Zs]) :- merge(Xs?,Ys,Zs).
merge(Xs,[Y|Ys],[Y|Zs]) :- merge(Xs,Ys?,Zs).
merge([],Ys,Ys).
merge(Xs,[],Xs).
would be fair. However, implementing a stable machine is
much easier then implementing a fair machine. And since
fairness can be achieved by higher-level software on top
of a stable machine, it seems to be the better implementation
direction (all implementations of Concurrent
Prolog and Flat Concurrent Prolog I know of are stable).
Another solution does not rely on stability or fairness, but
uses the meta-logical time-dependent predicate var(X), which
succeeds if X is an unbounded variable:
merge([X|Xs],[Y|Ys],[X,Y|Zs]) :- merge(Xs?,Ys?,Zs).
merge([X|Xs],Ys,[X|Zs]) :- var(Ys) | merge(Xs?,Ys,Zs).
merge(Xs,[Y|Ys],[Y|Zs]) :- var(Xs) | merge(Xs,Ys?,Zs).
merge([],Ys,Ys).
merge(Xs,[],Xs).
It is a matter of taste which extralogical feature to
rely on --- stability or meta-logical predicates ---
to ensure fairness. I prefer the former.
The following is Vijay's solution, recoded in Edinburgh
syntax:
merge(X?, [A|Y], [A|Z]):- merge(X?, Y?, Z).
merge([A|X], Y?, [A|Z]):- merge(X?, Y?, Z).
merge([A|X], [B|Y], [A,B|Z]):- merge(X?, Y?, Z).
merge([A|X], [B|Y], [B,A|Z]):- merge(X?, Y?, Z).
The program is similar in spirit to our third solution,
but attempts to use read-only references instead of the
var(X) predicate. This does not work, simply because the
unification of two read-only variables (or to be more
precise, two variables references as read-only) suspends
until both are instantiated to non-variable terms. Hence,
if merge is called with the first and second arguments
read-only, as it should, the first two clauses will never
unify.
By the way, when in doubt whether your proof of correctness
of a program is correct, run your program and see if it works.
Alternatively, you may try to prove that your proof of
correctness is correct. However, when in doubt whether your
proof of correctness of the proof of correctness is correct,
only God can help...
-- Ehud Shapiro
p.s. There is a Concurrent Prolog compiler in the
Prolog library, together with a debugger, for those
of us who prefer not relying on God's help for
matters as mundane as debugging.
p.p.s I am sure it contains some bugs too... but
since it is written in Prolog, you can use the
Prolog debugger to debug it.
------------------------------
Date: Sat, 2 Mar 85 23:21:00 pst
From: Tony Kusalik <Kusalik%UBC@CSNet-elay.arpa>
Subject: Bounded merge in Concurrent Prolog
I found Vijay's solution to the "bounded-wait merge"
problem in CP very interesting and appealing. It uses
the idea of testing for "variable" (as I did in my
"Bounded-Wait Merge..." paper, New Generation Computing
V2, N2), but through read-only annotations instead of
introducing a new meta-predicate. Vijay's solution will
work given MODIFIED semantics of CP; it does NOT work
with the original semantics.
In Shapiro's "A Subset of Concurrent Prolog ...", the case
of unifying two read-only variables (in the specification
of unification) is not explicitly addressed. The Concurrent
Prolog interpreter in that paper actually treats the
following two cases identically:
unify( some_atom?, Var? )
unify( Some_Var?, Var? )
Both fail (and hence suspend within the context of the
Concurrent Prolog program being run). To see this,
recall the definition of the 'unify' predicate within
the interpreter:
unify( X, Y ) :- (var( X ); var( Y )), !, X=Y.
unify( X?, Y ) :- !,
nonvar( X ), unify( X, Y ).
unify( X, Y? ) :- !,
nonvar( Y ), unify( X, Y ).
unify( [X|Xs], [Y|Ys] ) :- !,
unify( X, Y ), unify( Xs, Ys ).
unify( [], [] ) :- !.
unify( X, Y ) :-
X =.. [F|Xs], Y =.. [F|Ys], unify( Xs, Ys ).
Also recall that the read-only annotation is defined
as a post-fix unary operator. Then the resolution of
unify( Some_Var?, Var? )
proceeds as follows (CProlog execution trace):
| ?- trace, unify( Some_Var?, Var? ).
(2) 1 Call: unify(_0?,_4?) ?
(3) 2 Call: var(_0?) ?
(3) 2 Fail: var(_0?)
(4) 2 Call: var(_4?) ?
(4) 2 Fail: var(_4?)
(2) 1 Back to: unify(_0?,_4?) ?
(5) 3 Call: nonvar(_0) ?
(5) 3 Fail: nonvar(_0)
no
Here is a demonstration of the execution of Vijay's new
merge under Shapiro's Concurrent Prolog interpreter
(including CP trace):
| ?- [user].
|
| merge( X?, [A|Y], [A|Z] ) :- merge( X?, Y?, Z ).
| merge( [A|X], Y?, [A|Z] ) :- merge( X?, Y?, Z ).
| merge( [A|X], [B|Y], [A,B|Z] ) :- merge( X?, Y?, Z ).
| merge( [A|X], [B|Y], [B,A|Z] ) :- merge( X?, Y?, Z ).
| user consulted 488 bytes 0.28334 sec.
yes
| ?- cptraceall, solve(merge([foo|Strm1]?,Strm2?, MrgStrm)).
solve(0): merge([foo|_0]?,_8?,_12)
call(0): merge([foo|_0]?,_8?,_12)
unify(0): merge([foo|_0]?,_8?,_12),merge(_149?,[_150|_151],[_150|_152])
unify(0): merge([foo|_0]?,_8?,_12),merge([_149|_150],_151?,[_149|_152])
unify(0): merge([foo|_0]?,_8?,_12),merge([_149|_150]
,[_151|_152],[_149,_151|_153])
unify(0): merge([foo|_0]?,_8?,_12),merge([_149|_150]
,[_151|_152],[_151,_149|_153])
suspension(0): merge([foo|_0]?,_8?,_12)
*** cycles: 1
*** Deadlock detected. Locked processes:
merge([foo|_0]?,_8?,_12)
no
Chikayama and Ueda's Concurrent Prolog-to-Prolog compiler
behaves similarly:
| ?- [-'cp_compiler.plg'].
Concurrent PROLOG Compiler System Vers. 1.13 1984-09-12
Takashi Chikayama, Revision by A. Takeuchi and K. Ueda
cp_compiler.plg consulted 34388 bytes 15.4167 sec.
yes
| ?- trace, unify( Some_Var?, Var? ).
(2) 1 Call: unify(_0?,_4?) ?
(3) 2 Call: nonvar(_0?) ?
(3) 2 Exit: nonvar(_0?)
(4) 2 Call: nonvar(_4?) ?
(4) 2 Exit: nonvar(_4?)
(5) 2 Call: unify_nv(_0?,_4?) ?
(6) 3 Call: nonvar(_4) ?
(6) 3 Fail: nonvar(_4)
no
Also, Jacob Levy in his paper "A Unification Algorithm for
Concurrent Prolog (given @ Second International Logic
Programming Conference, Uppsala, July 1984) specifies that
the unification (in Concurrent Prolog) of two read-only
variables suspends. This is given in Table 3 of that paper.
Further, Colin Mierowsky of the Weizmann Institute in his
thesis on Flat Concurrent Prolog ("Design and Implementation
of Flat Concurrent Prolog," CS84-21, December 1984) specifies
that in Flat Concurrent Prolog the unification of two
read-only variables suspends. This is indicated in the
table at the top of page 33 of said paper.
The semantics of Concurrent Prolog may have undergone
some changes in the past several months, possibly even
regarding unification of two read-only variables.
The following is the most recent specification of
unification in Flat Concurrent Prolog that I have
(from Jacob Levy, 5-Feb-85):
H E A D
|----------|---------------|---------------|---------------|
| | TERM | VAR | RO |
|----------|---------------|---------------|---------------|
| TERM | unify_terms( | trail(HD) | suspend(HD) |
G| | GL,HD) | HD := REF(GL) | |
|----------|---------------|---------------|---------------|
O| VAR | trail(GL) | trail(HD) | trail(HD) |
| | GL := REF(HD) | HD := REF(GL) | HD := REF(GL) |
A|----------|---------------|---------------|---------------|
| RO | suspend(GL) | trail(HD) | trail(HD) |
L| | | HD := RO(GL) | HD := RO(GL) |
|----------|---------------|---------------|---------------|
(The right bottom square is the one of interest.) If this
change carries over to Concurrent Prolog, then Vijay's merge
program works. Otherwise .....
(I have advocated such a change since Jan/84.)
On this note, a few changes to the semantics of
Concurrent Prolog have been considered:
1) multiple attempts to commit for a given goal
2) no notification of instantiation of non-read-only
variables passed into guards
The people at Weizmann Institute are the best to comment
on the current status of these changes.
-- Tony Kusalik
------------------------------
Date: Fri 1 Mar 85 09:50:42-PST
From: Gio <Wiederhold@SRI-AI.ARPA>
Subject: Talk
Tuesday, March 5, 1985
at 4:15 in Terman Auditorium
PROLOG, DATABASES, AND NATURAL LANGUAGE ACCESS
David H.D. Warren
Quintus Computer Systems, Inc.
Prolog is a general purpose programming language based on logic.
It can be viewed either as an extension of pure Lisp, or as an
extension of a relational database query language. It was first
conceived in 1972, by Alain Colmerauer at the University of
Marseille. Since then, it has been used in a wide variety of
applications, including natural language processing, algebraic
symbol manipulation, compiler writing,architectural design,
VLSI circuit design, and expert systems. Prolog was chosen as
the initial kernel language for Japan's Fifth Generation
Computer Systems project, and the project's prototype Prolog
machine, PSI, has recently been unveiled in Tokyo.
In this talk, I will give an overview of the language, and then
focus on one particular application, a domain-independent system
for natural language question answering, called "CHAT". I will
compare the way Chat plans and executes a query with the query
optimization strategies of relational database systems such as
SYSTEM-R. Finally I will discuss the future prospects for Prolog
in the light of Japan's Fifth Generation project.
[ Dave WARREN, of Quintus, is both an original implementor and
a reimplementor of an industrial strength version of Prolog, as
well as a consultant to the Japanese 5th generation project.
He will also present an application, CHAT, which processes
natural language queries against a database, and is of course
wholly written in Prolog.
------------------------------
End of PROLOG Digest
********************