restivo@POLYA.STANFORD.EDU (Chuck Restivo) (07/04/88)
Date: Tuesday, 3 May 1988 0:2:34 PST
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@POLYA.STANFORD.EDU>
Reply-to: PROLOG@POLYA.STANFORD.EDU>
US-Mail: P.O. Box 4584, Stanford CA 94305
Subject: PROLOG Digest V6 #26
To: PROLOG@POLYA.STANFORD.EDU
PROLOG Digest Tuesday, 3 May 1988 Volume 6 : Issue 26
Today's Topics:
Query - Forum & Lisp & AAIS Coversion,
Implementation - Appropriate Usage & Simple Problem & back<-retract,
& Strongs & Precised
--------------------------------------------------------------------------------------------------------------------------
Date: 20 Mar 88 20:41:23 GMT
From: lagache@violet.Berkeley.EDU (Edouard Lagache)
Subject: Thank you for your interest in the PROLOG Forum
This note is to thank everyone who responded to my posting on the
PROLOG forum. Unfortunately, between by busy schedule and the
uncertainties of the mail reply system, I was unable to reply to each
request personally.
I received over 40 requests for the inaugural issue of the PROLOG
Forum newsletter. That alone is an encouraging sign of the strength of
the PROLOG users community.
If there is anyone out there would like to receive a free copy of
the inaugural issue and still hasn't said so, please send me a "paper"
mail address. You can do so by either replying to this message (the
preferable route), or by phone:
(415) 642-9920 Monday and Tuesdays (10 to 4 Pacific Standard time).
(415) 631-0183 Thursday and Friday workdays, and all evenings.
or by paper mail:
PROLOG Forum
P.O. Box 3826
Redwood City, CA, 94064, USA
We hope to start delivering the issues in a week or two,
Unfortunately, progress on the newsletter has been slowed by mechanical
difficulties (the hard disk on our president's computer crashed, taking
a lot of the newsletter with it!)
-- Edouard Lagache
------------------------------
Date: 11 Mar 88 20:09:20 GMT
From: B.GP.CS.CMU.EDU!nch@pt.cs.cmu.edu (Nevin Heintze)
Subject: Implementation of Prolog in Lisp
I am currently involved in a re-implementation of Lambda Prolog in Lisp at
CMU (as part of the ERGO project). At the moment I am trying to find
information on implementations of PROLOG in Lisp. Any pointers
to (recent) papers and/or implementations which address relevant issues
would be greatly appreciated.
-- Nevin Heintze
nch@b.gp.cs.cmu.edu
------------------------------
Date: 12 Mar 88 00:47:02 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: When to use Prolog?
In article <759@cresswell.quintus.UUCP>, ok@quintus.UUCP I wrote:
> Using Prolog is like running up a slightly less steep hill. Using a shell
> is like running along level ground until wham! you hit a brick wall.
I should have made it clear that I had in mind shells like EMYCIN,
not programming languages like M.1.
------------------------------
Date: 12 Mar 88 00:23:09 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: mine embarrassingly simple problem
In article <500@taux01.UUCP>, shahaf@taux01.UUCP (Shahaf Moshe) writes:
> Can someone help me in the following: In translation from WATERLOO
> to Quintus code I need {an ancestral cut}.
(1) A predicate which "searches through the ancestors exactly as for
ancestor and retry" is a rather hard thing to provide in a system
which does last call optimisation, the whole point of which is to
ensure that as many ancestors as possible are completely forgotten
as soon as possible. Quintus Prolog does not provide 'retry' either.
(2) We are currently putting some rather nice things into Quintus Prolog
which I don't think we could implement at all if we supported
ancestral cuts.
(3) Check to see whether your site has a support contract with Quintus.
We *may* be able to advise you how to write your program so that
it doesn't need ancestral cuts.
(4) Could you tell this newsgroup more about your program? It would be
very interesting to hear of something that ancestral cuts were
needed for. (They _aren't_ needed for interpreting Prolog!)
------------------------------
Date: 14 Mar 88 07:50:33 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: Destructive predicates
In article <1797@sics.se>, alf@sics.se (Thomas Sj|land) writes:
> More bluntly put: A D-list is not an object in the Herbrand domain.
Right! This is why I think it is a bad idea to use
Front-Back
or Front\Back
to package the two ends of a difference list as a single object,
and try always to use two separate arguments in my programs.
However, there is an encapsulation which works nicely, due I think to
Stuart Shieber, which Fernando Pereira told me about.
use q(0, X, X) for an empty list
and q(s(s(...(0)...)), [X1,...,Xn|X], X) for a list of N elements.
empty_queue(q(0,X,X)).
queue_first(X, q(s(N),[X|Front],Back), q(N,Front,Back)).
queue_last(X, q(s(N),Front,Back), q(N,Front,[X|Back])).
queue_first(X, Queue1, Queue0) is analogous to List1 = [X|List0]
queue_last( X, Queue1, Queue0) is similar but works at the other end.
------------------------------
Date: 14 Mar 88 12:38:15 GMT
From: pyramid!nsc!taux01!shahaf@lll-lcc.llnl.gov (Shahaf Moshe)
Subject: mine embarrassingly simple problem
The program does Network synthesis from boolean equations for VLSI design.
The ancestral cut was used to stop the search of local transformations
when the rate of new maping is too low.
------------------------------
Date: 15 Mar 88 11:25:43 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: back_retract
In article <1194@kulcs.kulcs.uucp>, bimbart@kulcs.uucp (Bart Demoen) writes:
> See what you can do in BIMprolog:
[ I have reformatted this so that I can read it: if you want to see how
Bart Demoen wrote it, read his message.
]
> back_retract((HeadUsed:- BodyUsed)) :-
> clause(HeadUsed, BodyUsed, Index), % FIND the clause
> functor(HeadUsed, Symbol, Arity),
> functor(HeadCopy, Symbol, Arity),
> clause(HeadCopy, BodyCopy, Index), % COPY the clause
> ( retract((HeadUsed :- BodyUsed), Index) % DELETE the clause
> ; assert((HeadCopy :- BodyCopy), Index), % REPLACE the clause
> fail % resume failing
> ).
Porting problem: DEC-10 Prolog has assert(+Clause, -Ref) and
clause(+Head, ?Body, -Ref) where Ref is a sort of pointer, and several
other Prologs do the same. Even AAIS Prolog tries. But that's a
minor change, just invent new names for the operations.
This will do what the original poster wants,
ONLY IF there are no other changes to the same predicate.
Consider
back_retract(<clause>) -- removes 3rd clause
asserta(<new clause>)
fail
This will shuffle the data base, which was not what was wanted.
This kind of excessively unpleasant interaction is precisely why
the DEC-10 Prolog family hasn't got "positional" data base commands.
We could get around this by having an 'assert_before' predicate
which took a clause and a data base reference and put the clause
before the one the reference pointed to (even if the referenced
clause had since been deleted):
* back_retract(Clause) :-
* prolog_clause(Clause, Head, Body), % see DECONS.PL in DEC-10 lib
* clause(Head, Body, Ref), % FIND the clause
* instance(Ref, Copy), % COPY the clause
* ( erase(Ref) % DELETE the clause
* ; assert_before(Ref, Copy), % REPLACE the clause
* fail % resume failing
* ).
This would be free of shuffling problems, even when other updates to
the predicate in question were being made.
However, both versions of back_retract/1 have a rather more serious
failure mode.
Consider
back_retract(<clause>),
...
!,
...
fail
By analogy with variable bindings, you would expect the back-retracted
clause to reappear. But the cut will have had the effect of pruning
away the "assert". Was it in 1983 or 1984 that I pointed this problem
out in the Prolog Digest, with reference to an 'assume' operation?
This problem is the reason that Quintus Prolog hasn't got backtrackable
assignment to global variables in the library: cuts prune away the
restoration code.
> But there should be a better way of doing what you want.
If back_retract is being used to simulate something even vaguely
logical, there has been some very interesting work done at Stony
Brook on extending Prolog with some features of dynamic logic.
Roughly speaking, there are three classes of predicates:
pure predicates (don't depend on things that change)
state predicates (depend on things that change, but change nothing)
transition predicates (express a relation between states)
For example, we might say
p(X) :-
<-fred(X)> q(X).
p(X) is true in a world W if there is a world W1 such that
-(fred(X), W, W1) -- roughly, retract
and q(X) is true in W1.
Note that this doesn't change W.
Permanent changes are effected by the top level, where queries have
the meaning "let W be the current world; if there is a world W1 and
a substitution S such that the query arrives in W1 with substitution S,
print S and make W1 the current world."
I'm sorry that I can't remember the name of the person who was working
on this. He promised me a copy of a paper about it, but it never
arrived, so I can't give you a reference either. A pity, because this
strikes me as the obviously right way to handle "local" data base
updates, it's even related to an existing logic!
It remains the case that converting an O(N**N) operation to an O(N!)
-- which the original poster cited as motive for having back_retract/1 --
is scarcely worth the trouble.
------------------------------
Date: 16 Mar 88 15:30:07 GMT
From: mcvax!unido!ecrcvax!micha@uunet.uu.net (Micha Meier)
Subject: back_retract
In article <777@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>However, both versions of back_retract/1 have a rather more serious
>failure mode.
>
>Consider
>
> back_retract(<clause>),
> ...
> !,
> ...
> fail
>
>By analogy with variable bindings, you would expect the back-retracted
>clause to reappear. But the cut will have had the effect of pruning
>away the "assert". Was it in 1983 or 1984 that I pointed this problem
>out in the Prolog Digest, with reference to an 'assume' operation?
1983, but not really pointed out :-)
This is only an implementation problem. If you, instead of
using code to implement the backtrackable retract, push
a suitable reference on the trail, then it works fine even
with the cut, provided that you do not tidy up the trail
(as described in the old engine). For some systems this might
be too costly, as they use no special trail entries,
but if the trail is already used to undo different things,
that one is easily incorporated. You can get backtrackable
assignment for free, then.
Since several people here at ECRC asked me to provide
backtrackable assert and retract, I assume that it can
really be useful. One possible application is hypothetical
reasoning - with the asserts and retracts you create
alternative worlds, but you certainly want to be able to
return to your universe. This is completely logical.
Another area where it could be used is for database integrity
constraints checking, or of course for
theorem proving. Since all this stuff is logical,
the above mentioned implementation can be used (there are
no cuts), but sometimes it is desirable to have the old
clause back at the position where it was before.
--Micha
------------------------------
Date: 14 Mar 88 19:18:40 GMT
From: mcvax!prlb2!kulcs!bimbart@uunet.uu.net (Bart Demoen)
Subject: back_retract
See what you can do in BIMprolog:
back_retract((_h :- _b)) :-
clause(_h,_b,_n) ,
functor(_h,_f,_a) , functor(_nh,_f,_a) ,
clause(_nh,_nb,_n) ,
(retract((_h :- _b),_n) ;
assert((_nh :- _nb),_n) , fail ) .
clause/3 has as 3th argument the number of the clause:
ex. database = a(x) .
a(y) .
a(z) .
then ?- clause(a(y),true,2) . succeeds
and ?- clause(a(X),true,3) . says:
X = z
and ?- clause(a(x),true,N) . says:
N = 1
the second argument in retract/2 has a similar meaning ;
in a call to assert/2, the 2nd arg must be instantiated and the clause is
asserted at the arg2'th place in the database; in this way, asserta/1 is just
a special case of assert/2, with definition:
asserta(_x) :- assert(_x,1) .
so the query ?- assert(a(foo),3) . on the above database has as effect that the
database will look afterwards like:
a(x) .
a(y) .
a(foo) .
a(z) .
But there should be a better way of doing what you want.
------------------------------
Date: 17 Mar 88 06:57:23 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Mountain View, CA
Subject: back_retract
Message-Id: <782@cresswell.quintus.UUCP>
References: <1194@kulcs.kulcs.uucp>, <777@cresswell.quintus.UUCP>, <516@ecrcvax.UUCP>
Sender: prolog-request@score.stanford.edu
To: prolog@score.stanford.edu
The point of my message was that the "obvious" way of doing this in Prolog
doesn't work. I think it was worth mentioning this because it is one of
those old chestnuts that keeps popping up. Someone once kindly showed
Quintus how to implement backtrackable global assignment; he'd put a fair
bit of work into it, but the
( change /* exit */
; /* redo */ undo_change, fail
)
pattern was what he had used, so it didn't actually work.
Credit: of the Prologs I know anything about, LM-Prolog has had undoable
side-effects longest. I've seen a demo of LM-Prolog "undrawing" a picture,
I think this was at IJCAI-83. The person who explained the technique of
pushing arbitrary functions onto the trail to me was Preben Folkjaer, then
of InterFace.
Pushing functions on the trail is a neat trick, but it isn't a panacea.
Consider the problem of I/O: you really don't want to push a function
onto the trail for every character you write. Chris Moss has a paper,
I don't know where it appeared, on undoable I/O, and when you can actually
produce the output.
> Since several people here at ECRC asked me to provide
> backtrackable assert and retract, I assume that it can
> really be useful.
You should see the things people ask for in comp.lang.c!
> One possible application is hypothetical
> reasoning - with the asserts and retracts you create
> alternative worlds, but you certainly want to be able to
> return to your universe.
I think Sanjay Manchanda's approach is much cleaner. Undo the side effect
of an assert or retract? But <+X> and <-X> haven't GOT any side effects!
For hypothetical reasoning in general, Ken Bowen's approach to meta-level
reasoning is to make the alternative worlds explicit as data values; in a
system like that you can reason about several worlds at once. If we can
get logical arrays with acceptable efficiency (which would be useful in
any case), it seems that the Manchanda & Bowen approaches need not be
inferior in efficiency to the backtrackable side efffects approach.
What happens if you are using a system with backtrackable side effects
(such as back_retract) and the code aborts (explicit call to abort, or
to some sort of error signalling operation)? Do the side-effects get
unwound then? I'm not asking "how do you do it", but "what do you want
it to do?" What happens if you have an AND-parallel system and one
process executes back_retract, do the other processes notice the change
or not? If you take the Bowen or Manchanda approach to data base updates,
the answer is obvious: nothing is changing, you just get additional
worlds. (The Manchanda approach may be easier for AND-parallel systems.)
------------------------------
Date: 15 Mar 88 07:56:32 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: Strings
In article <5348@utah-cs.UUCP>, shebs%defun.utah.edu.uucp@utah-cs.UUCP (Stanley T. Shebs) writes:
> In article <768@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>
> >When I say that it is more efficient to use lists of character codes
> >rather than packed byte vectors, I am reporting empirical measurements.
> This is a very interesting assertion, because it has a lot of implications
> for *any* vector/array-type representation. The broadest interpretation
> is that any and all vector-like types are bad.
I deny this. The question is >how do you USE these things<.
If you are doing lots of concatenation and deconcatenation (I stole this
word from PL/I), lists are a win. How often do you concatenate bignums?
How often do you concatenate matrices (APL programmers need not apply)?
If you need random access into some collection, a vector-like structure
is going to be a really good idea. The point is that most uses of STRINGS
just aren't like that. (Hint: for which C data-type is the idiom *x++
most often used...)
> The reason I wonder is that Lisp has not used lists to represent bignums
> since the mid-60s, and (for instance) JonL White's bignum paper in the
> 86 Lisp conference assumes a vector-like representation.
Xerox Lisp uses lists for bignums to this very day.
There is a book:
Computer Algebra: Symbolic and Algebraic Computation (2nd ed)
eds Buchberger, Collins, & Loos
Springer-Verlag, 1982, 1983
ISBN 3-211-81776-X (can anyone tell me what it means
ISBN 0-387-81776-X for a book to have 2 ISBNs?)
Price US$ 32.
I bought this book mainly because of the chapter
Arithmetic in Basic Algebraic Domains
Collins, Mignotte, & Winkler
which describes a number of algorithms Knuth didn't.
This chapter claims quite strongly that list representation is better
for bignums. The fact that one seldom if ever accesses the "elements"
of a bignum in other than strict sequential order suggests that this
may be a good idea.
Consider the fact that if you have an N-"bigit" number X,
X and X+k for small values of k can almost always share the most
significant (N-1) "bigits".
> Boxing characters is just as bad as boxing small integers, and just as
> unnecessary. Avoiding the creation of a new string descriptor is harder,
> and requires compiler analysis, but it is possible under many circumstances.
I used "boxing" loosely. I did not, as Shebs excusably thinks, mean
"allocating storage for", but "suitably locating in a register and
supplying with an appropriate tag". This is cheap, but it isn't free.
> I think the real underlying motivation for strings is that languages like C
> can do string processing with essentially zero space and time overhead,
C can do this precisely because it ****HASN'T**** got a string data type!
For example, suppose I want to concatenate four chunks of text in C.
I can do
char *strmov(register char *dst, register char *src)
{
while (*dst++ = *src++) ;
return dst-1;
}
void conc4(char buffer[], char *a, char *b, char *c, char *d)
{
(void) strmov( strmov( strmov( strmov( buffer,
a), b), c), d);
}
Time overhead: each character is examined exactly once, as it is moved.
no check for overflow or overlap.
Space overhead: static allocation of result area.
If you look closely, you will notice that there are no strings in that!
There are only pointers into buffers.
In Fortran 77, concatenation can be efficient because, once again,
Fortran 77 hasn't got strings, only buffers. For example,
CHARACTER *(80) BUFFER
CHARACTER *(20) A, B, C, D
BUFFER = A//B//C//D
There is no storage allocation. (Unlike C, there *is* a check for
overflow, but in this case it can be done at compile time.)
ADA is similar to Fortran 77:
declare
a, b, c, d : string(1..20);
buffer : string(1..a'length+b'length+c'length+d'length);
begin
buffer := a & b & c & d;
end;
The key to not allocating storage is not to have any operations which
create string values, but only commands which change the contents of
an existing buffer. (At the source level you may have operations which
look as though they create string values, but the implementation mustn't
actually do that.) One thing that helps in Fortran 77 and ADA is saying
in advance how big a string each buffer can hold. C obtains a similar
advantage by not bothering to check.
> It's not so much an issue of doing one operation on German titles, but of
> passing a million characters of text through a program without allocating
> so much as one byte of storage dynamically.
Well, if *that* is what you want,
copy_chars :-
get0(Char),
copy_chars(Char).
copy_chars(-1) :- !.
copy_chars(Char) :-
put(Char),
copy_chars.
will pass any number of characters through a program without allocating
so much as one byte of storage dynamically. (:-)
Actually, if that's what you want, AAIS Prolog may be the language for you.
I forget the details, but it has an operation something like
setchar(+Index, +String, +Char)
which changes the Indexth character of String to Char. So in that language
you can have all the fun of buffers (and all the pain of buffer overflow).
------------------------------
Date: 16 Mar 88 10:16:07 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: I don't understand "precised"
In article <1196@kulcs.kulcs.uucp>, bimbart@kulcs.uucp (Bart Demoen) writes:
> could the author of article 599 in comp.lang.prolog behave a bit more respectful
> towards europeans who speak 3 or 4 (natural) languages but whose native
> language is not english ? we are bound to make mistakes in english, but that's
> no reason to sneer at us.
Before flaming me, might it not be an idea to ensure that I have done
something to deserve it? I am well aware that my dialect of English is
not identical to British English nor yet to American, and I have seen
"precised" enough times that this time I thought it was a proper use of
English that I didn't happen to know.
Just because someone has a European name and is writing from Europe
doesn't mean that person isn't a native speaker of English: the writer
could be American, for all I can tell to the contrary.
What I wrote was not ' "precised" isn't proper English ', but
'I don't understand "precised"'.
That's what I wrote, and that, sir, is EXACTLY what I meant.
Well, not exactly, it was an indirect request for clarification.
If Demoen would care to say what it means, I would still like to know.
------------------------------
Date: 15 Mar 88 17:20:56 GMT
From: william@locus.ucla.edu
Organization: UCLA Computer Science Department
Subject: AAIS Prolog for MacIntosh
I've used AAIS Prolog for more than a year, and I am reasonably happy
with it. Programs that works under C-Prolog or SICS Prolog MAY need
a little bit of modification before it can run under AAIS. The major
differences are:
1) The I/O predicates, such as get0/1 and read/1, fails when end of file
is reached. In SICS, get0/1 will return a -1 and read/1 will return
end_of_file when end of file is reached. (This may be nice sometimes.)
2) AAIS has predicates such as append/3 and member/2 built in. However,
you can make the system forget about such built-ins by using the new/2
directive as follows:
:- new(append, 3).
:- new(member, 2).
In porting a program that consists of several files, just create a
file that consults everything, and put the new/2 directives at the
top of this file.
3) File naming convention is different, if you move from a UNIX to the
Mac environment, and if you want to use files not in the current
directory.
4) AAIS implements the clause/2 predicate a little bit differently.
For example, if you have the following clause in the database:
a :- b, c.
When you do clause(a, X), X will become [b, c], instead of the
usual b, c. This may be the biggest problem when you want to
port something to AAIS.
Other than 4), porting is not a big problem. What basically needs to
be done is to create a Mac specific file that handles the differences.
Some of the good things:
1) AAIS is very robust, I don't recall that I've ever got any crashes.
2) It handles GARBAGE COLLECTION. You can also disable/enable the
garbage collection messages.
3) Although it does not have a compiler, it runs a little bit slower
than the C-Prolog on our departmental VAX.
4) It has interface to the Mac toolbox, so graphics is possible,
although I've never tried it.
5) It has a familiar Mac application user interface. It's not like
a product of a garage operation.
6) Very nice debugger. It even pretty-prints the current goal, so
things don't disappear into the right edge of the screen or have
unreadable wrap around.
7) It catches user interrupt (<Cmd>.), just like C-Prolog or SICS
handles <CNTRL>C.
8) It's inexpensive. When I bought it, I cost about $99 or $95.
The price must have gone up. However, to get a full language
system for less than $150 is a very good price. Also, their
support is pretty good. When I wrote to them, they actually responded.
Disclaimer - I am in no way affiliated with AAIS
------------------------------
Date: 16 Mar 88 20:01:32 GMT
From: chiefdan@vax1.acs.udel.edu (Chief Dan Roth)
Subject: AAIS Prolog for Macintosh (Quintus Conversion)
I'd appreciate info on conversion problems from anyone who has used the
above two. I'm currently porting a relatively large program from Quintus on
a Sun to AAIS on a Mac II.
Anyone who has done a similar conversion out there?
-- dan
------------------------------
End of PROLOG Digest
********************thomas@gmdzi.UUCP (Thomas Gordon) (07/08/88)
From article <8807031947.AA28299@polya.Stanford.EDU>, by restivo@POLYA.STANFORD.EDU (Chuck Restivo): > > At the moment I am trying to find > information on implementations of PROLOG in Lisp. Any pointers > to (recent) papers and/or implementations which address relevant issues > would be greatly appreciated. > > -- Nevin Heintze > nch@b.gp.cs.cmu.edu > I read in one of the recent SIGPLAN notices that a group in Italy had implemented a Prolog interpreter in Common Lisp. They claim performance competivitive with commercial Prolog interpreters written in so-called conventional languages. They said they would be posting the sources to Usenet soon, so I have been watching this space carefully, to no avail. I don't have the authors names by me at the moment, but if you guys are out there and listening, it looks like there are a number of us who are interested in receiving a copy of your Prolog in Common Lisp interpreter. Thomas F. Gordon email: thomas@gmdxps.uucp GMD / F3 phone: (+49 2241) 14-2665 Schloss Birlinghoven D-5205 Sankt Augustin 1, FRG -- Thomas F. Gordon email: thomas@gmdxps.uucp GMD / F3 phone: (+49 2241) 14-2665 Schloss Birlinghoven D-5205 Sankt Augustin 1, FRG