ddgg0881@uxa.cso.uiuc.edu (10/09/89)
I have two questions about Prolog implementations: 1. I've discovered one implementation that gives 3 solutions to member(a,[a,a,a]) even though there aren't 3 ways to instantiate variables. Another implementation I've used gives only one solution. Which way is standard? Are there arguments for doing things one way or the other? 2. I find reading text files very painful in Prolog because you always have to keep a lookahead character. This way of doing things doesn't feel like Prolog. One of the main selling points of Prolog is the efficient way that it backtracks upon failure. Are there any implementations of Prolog that allow 'get' or 'get0' to backtrack and unread characters? Dale Gerdemann University of Illinois, Dept of Linguistics Cognitive Science Group, Beckman Institute dale@tarski.cogsci.uiuc.edu d-gerdemann@uiuc.edu
ok@cs.mu.oz.au (Richard O'Keefe) (10/10/89)
In article <111000002@uxa.cso.uiuc.edu>, ddgg0881@uxa.cso.uiuc.edu writes: > I have two questions about Prolog implementations: > 1. I've discovered one implementation that gives 3 solutions to > member(a,[a,a,a]) even though there aren't 3 ways to instantiate > variables. Another implementation I've used gives only one solution. > Which way is standard? Are there arguments for doing things one way > or the other? There is precisely one "standard" way of defining member/2, modulo spelling of variable names and dot-vs-bracket syntax for lists: member(X, [X|_]). member(X, [_|L]) :- member(X, L). Prolog does *not* find solutions. Prolog finds **proofs**, and shows you (part of) the substitution it found for each proof. The goal ?- member(a, [a,a,a]). has three proofs. So that's the number of times Prolog should come back to you with an answer substitution. However, there is a fine point to do with the user interface. Many Prolog systems check the query that you type in, and if it hasn't got any variables, just say "yes" or "no". NU Prolog does this, except it says "true" or "false". Transcript: % np NU-Prolog 1.4 1?- member(a, [a,a,a]). true. However, if you put a variable in there to fool it, you will see that it is prepared to find the other proofs. Transcript: 2?- X=dummy, member(a, [a,a,a]). X = dummy ; X = dummy ; X = dummy ; fail. Another way of seeing that the three proofs are found is 3?- member(a, [a,a,a]), write(*), fail. ***fail. > 2. I find reading text files very painful in Prolog because you > always have to keep a lookahead character. So? You need a lookahead character for tokenising anyway, all you have to do is remember not to drop it on the floor. Just write down your DFSA and the transcription into Prolog is direct, but DIRECT. > This way of doing things doesn't feel like Prolog. Of course not, because it uses side effects. Depending on the size of the files you want to process, and the memory capacity of your machine, you might want to consider slurping the entire file into memory as a list of character codes, and parsing that using grammar rules. I'm quite serious about this: get_file(FileName, Chars) :- seeing(CurrentInput), see(FileName), get0(C), slurp(C, Cs), seen, see(CurrentInput), Chars = Cs. slurp(-1, []) :- !. slurp(C, [C|Cs]) :- get0(D), slurp(D, Cs). In SICStus Prolog 0.6 it takes about 6 seconds to read 30kbytes this way on a discless Sun-3/50. > One of the main selling points of Prolog > is the efficient way that it backtracks upon failure. Are there any > implementations of Prolog that allow 'get' or 'get0' to backtrack > and unread characters? Yes. Sort of. If you are reading from a file there is no problem. But what if you are reading from a source that can't back up? (For example, reading from a terminal --very likely-- or a UNIX command --I do that quite often-- or a named pipe --quite possible-- or a streaming tape --just joking.) Then the Prolog system would have to buffer an arbitrary amount of information just in case you decided to back up. Your Prolog system probably provides some kind of file positioning feature. Just for grins, here's how to hook it into grammar rules. file(NonTerminal, File) :- open(File, read, Stream), stream_position(Stream, Position), phrase(NonTerminal, @(Stream,Position), @(Stream,End)), stream_position(Stream, _, End), % high-water mark get0(-1). % is end-of-file get_char(Char, @(Stream,OldPos), @(Stream,NewPos)) :- stream_position(Stream, _, OldPos), % go to OldPos get0(Char), % pick up Char Char >= 0, % check not EOF stream_position(Stream, NewPos). % where are we now? Now your grammar rules, instead of saying [Char] will say get_char(Char) as a non-terminal. In NU Prolog, which provides the non-portable ftell/2 and fseek/3 constructs (they are fine in UNIX, but not so good in VMS or MVS or CMS), it's even simpler: stream_phrase(NonTerminal, Stream) :- open(File, read, Stream), ftell(Stream, Start), fseek(Stream, 0, end), ftell(Stream, Finish), call(NonTerminal, @(Stream,Start), @(Stream,Finish)). get_char(Char, @(Stream,OldPos), @(Stream,NewPos)) :- plus(1, OldPos, NewPos), fseek(Stream, OldPos, beginning), get0(Char), Char >= 0. call(Closure, X1, X2) :- Closure =.. L0, append(L0, [X1,X2], L2), Goal =.. L2, call(Goal).
ok@cs.mu.oz.au (Richard O'Keefe) (10/10/89)
In article <2365@munnari.oz.au>, ok@cs.mu.oz.au I wrote > file(NonTerminal, File) :- which should have been file_phrase(NonTerminal, File) > stream_phrase(NonTerminal, Stream) :- which should also have been file_phrase(NonTerminal, File)
gupta@surya.cs.unc.edu (Gopal Gupta) (10/10/89)
In article <111000002@uxa.cso.uiuc.edu>, ddgg0881@uxa.cso.uiuc.edu writes: > > > I have two questions about Prolog implementations: > > 1. ........ > > 2. I find reading text files very painful in Prolog because you > always have to keep a lookahead character. This way of doing things > doesn't feel like Prolog. One of the main selling points of Prolog > is the efficient way that it backtracks upon failure. Are there any > implementations of Prolog that allow 'get' or 'get0' to backtrack > and unread characters? We implemented a logic language with functional syntax called EqL that allows both backtrackable as well as non-backtrackable reads and writes. Thus, if computation fails over a backtackable read, the file pointer is set back accordingly (however, this is actually not how this was implemented). In case of backtrackable writes, for obvious reasons the data can be output to a file only after the query execution is over. The EqL interpreter (for a Sun or a Vax) and manual can be obtained by anonymous ftp from dopey.cs.unc.edu (Internet Addr. 128.109.136.82), if someone is interested. EqL is also compilable to DEC 3100s and Apollos. I vaguely remember some Prolog implementation also having backtrackable reads and writes but I can't recall the name right now. More knowledgable people in the net would perhaps know better. Regards. ------------------------------------------------ --Gopal Gupta, gupta@unc.cs.unc.edu Department of Computer Science, ..!decvax!mcnc!unc!gupta CB# 3175 Sitterson Hall, University of North Carolina , Chapel Hill, N.C. 27599-3175. U.S.A.
miller@CS.ROCHESTER.EDU (Brad Miller) (10/11/89)
Prolog does *not* find solutions. Prolog finds **proofs**, and shows you
(part of) the substitution it found for each proof. The goal
?- member(a, [a,a,a]).
has three proofs. So that's the number of times Prolog should come back
to you with an answer substitution. However, there is a fine point to do
with the user interface. Many Prolog systems check the query that you
type in, and if it hasn't got any variables, just say "yes" or "no".
NU Prolog does this, except it says "true" or "false". Transcript:
% np
NU-Prolog 1.4
1?- member(a, [a,a,a]).
true.
However, if you put a variable in there to fool it, you will see that it
is prepared to find the other proofs. Transcript:
2?- X=dummy, member(a, [a,a,a]).
X = dummy ;
X = dummy ;
X = dummy ;
fail.
Another way of seeing that the three proofs are found is
3?- member(a, [a,a,a]), write(*), fail.
***fail.
On the other hand, it seems perfectly reasonable for a PROLOG or any logic
language implementation to note that in the variable case above, reproving
the member doesn't change the binding of X and refuse to do it, rather
simply fail. This is what would happen if "intelligent backtracking" were
being used. Similarly, in the last example, since no variable can be rebound
by the current frame, fail should exit the proof immediately after the first
write.
I think part of the issue is that Prolog really doesn't find "proofs" in the
logical sense, rather it does SLD resolution. That is to say, one shouldn't
confuse PROLOG, which is a programming language, with LOGIC which isn't.
That is, it does not return proof trees. If it did, then techniques like
intelligent backtracking could not be used, nor could "side effects" be
allowed (Side effects in the programming language sense).miller@CS.ROCHESTER.EDU (Brad Miller) (10/11/89)
[[Protect quoted material from broken mail interface to pnews]]
Date: 10 Oct 89 02:02:18 GMT
From: ok@cs.mu.oz.au (Richard O'Keefe)
Prolog does *not* find solutions. Prolog finds **proofs**, and shows you
(part of) the substitution it found for each proof. The goal
?- member(a, [a,a,a]).
has three proofs. So that's the number of times Prolog should come back
to you with an answer substitution. However, there is a fine point to do
with the user interface. Many Prolog systems check the query that you
type in, and if it hasn't got any variables, just say "yes" or "no".
NU Prolog does this, except it says "true" or "false". Transcript:
% np
NU-Prolog 1.4
1?- member(a, [a,a,a]).
true.
However, if you put a variable in there to fool it, you will see that it
is prepared to find the other proofs. Transcript:
2?- X=dummy, member(a, [a,a,a]).
X = dummy ;
X = dummy ;
X = dummy ;
fail.
Another way of seeing that the three proofs are found is
3?- member(a, [a,a,a]), write(*), fail.
***fail.
On the other hand, it seems perfectly reasonable for a PROLOG or any logic
language implementation to note that in the variable case above, reproving
the member doesn't change the binding of X and refuse to do it, rather
simply fail. This is what would happen if "intelligent backtracking" were
being used. Similarly, in the last example, since no variable can be rebound
by the current frame, fail should exit the proof immediately after the first
write.
I think part of the issue is that Prolog really doesn't find "proofs" in the
logical sense, rather it does SLD resolution. That is to say, one shouldn't
confuse PROLOG, which is a programming language, with LOGIC which isn't.
That is, it does not return proof trees. If it did, then techniques like
intelligent backtracking could not be used, nor could "side effects" be
allowed (Side effects in the programming language sense).ok@cs.mu.oz.au (Richard O'Keefe) (10/11/89)
In article <1989Oct10.170254.9642@cs.rochester.edu:, miller@CS.ROCHESTER.EDU (Brad Miller) writes:
(I wrote)
: Prolog does *not* find solutions. Prolog finds **proofs**, and shows you
: (part of) the substitution it found for each proof. The goal
: ?- member(a, [a,a,a]).
: has three proofs.
: On the other hand, it seems perfectly reasonable for a Prolog or any logic
: language implementation to note that in the variable case above, reproving
: the member doesn't change the binding of X and refuse to do it, rather
: simply fail. This is what would happen if "intelligent backtracking" were
: being used. Similarly, in the last example, since no variable can be rebound
: by the current frame, fail should exit the proof immediately after the first
: write.
Reasonable? I'd be happy for NU Prolog to do something like that because
NU Prolog has the ":- pure" declaration. In the absence of such a declaration,
it is NOT reasonable for a Prolog system to do that. (Think: repeat/0 has
ONE solution but infinitely many proofs; it's used precisely because of the
latter property.)
There's another sense of "reasonable"; intelligent backtracking ranges from
outrageously costly to unpleasantly costly. There are affordable versions
of intelligent backtracking around, but they become affordable by sacrificing
much of the intelligence. You can avoid repeated solutions to a goal _this_
simple, but the problem is going to come right back in more complicated
situations. Another method is to use extension tables (applicable only to
:- pure predicates), which have their own problems.
: I think part of the issue is that Prolog really doesn't find "proofs" in the
: logical sense, rather it does SLD resolution. That is to say, one shouldn't
: confuse Prolog, which is a programming language, with LOGIC which isn't.
: That is, it does not return proof trees. If it did, then techniques like
: intelligent backtracking could not be used, nor could "side effects" be
: allowed (Side effects in the programming language sense).
Miller confuses FINDING proofs with REPORTING them. Just because Prolog
"does not return proof trees" doesn't mean that it "doesn't find proofs".
As a matter of fact some debugging tools _do_ return proof trees, which
doesn't make them any the less Prolog. Predicate's such as findall/3
and VM/Prolog's call/2 (at least I think that's what they call it) let
you discover how many proofs were found for a goal; intelligent backtracking
would yield different answers.
As they say in the satellite business, there's no such thing as a free
launch. Prolog strikes a balance between cost and power; it's fast and
stupid rather than slow and smart.ferguson@cs.rochester.edu (George Ferguson) (10/11/89)
In article <111000002@uxa.cso.uiuc.edu>, ddgg0881@uxa.cso.uiuc.edu writes: > I have two questions about Prolog implementations: > One of the main selling points of Prolog > is the efficient way that it backtracks upon failure. Are there any > implementations of Prolog that allow 'get' or 'get0' to backtrack > and unread characters? WUP (Waterloo Unix Prolog) claimed to implement both _logical_ (ie. back- trackable) I/O predicates based (I think) on streams as well as the standard non-logical I/O predicates. The best reference I can find is the User's manual which reads: WUP Version 3.0 User's Manual David J. McClurkin Logic Programming and AI Group Department of Computer Science University of Waterloo Waterloo, Ontario, Canada [ version of August 6, 1987 ] Perhaps you can track it down if you're interested, I never used the system myself. -- George Ferguson ARPA: ferguson@cs.rochester.edu University of Rochester UUCP: {decvax,rutgers}!rochester!ferguson Rochester NY 14627 VOX: (716) 275-2527
lee@munnari.oz.au (Lee Naish) (10/12/89)
In article <111000002@uxa.cso.uiuc.edu>, ddgg0881@uxa.cso.uiuc.edu writes: > implementations of Prolog that allow 'get' or 'get0' to backtrack > and unread characters? From the bts list of Prologs: NAME: Basser Prolog VERSION: 3 SRC/MACHINE/OS: C/Unix (V7, 4.?BSD & others) also VMS AVAILABILITY: Educational license, source or binary COST: A$300 or US$300 or negotiable, VMS version extra STATUS: running, some development & support FEATURES: Fast interpreter, full interface to Unix, Dec-10 debugging facilities, real arithmetic, backtrackable I/O, good docu- ^^^^^^^^^^^^^^^^^ mentation (user manual & tutorial). CONTACT: Andrew Taylor (USENET: mulga!basser!andrewt) Department of Computer Science Sydney University Sydney, N.S.W. 2006 Australia NOTES: Yet another prolog syntax. Most of the code is clean and readable. Generally similar to DEC-10 prolog. Basser Prolog has sufficient "features" to make it a reasonable programming environment and a useful tool. DATED: May 1984 As far as I know Andrew is still at S.U. The address is a bit out of date - try andrewt@cs.su.oz.au lee
goldfain@osiris.cso.uiuc.edu (10/17/89)
] /* Oct 11, 1989 ok@cs.mu.oz.au writes in comp.lang.prolog */
] ...
] There's another sense of "reasonable"; intelligent backtracking ranges from
] outrageously costly to unpleasantly costly. There are affordable versions
] of intelligent backtracking around, but they become affordable by sacrificing
] much of the intelligence. You can avoid repeated solutions to a goal _this_
] simple, but the problem is going to come right back in more complicated
] situations. Another method is to use extension tables (applicable only to
] :- pure predicates), which have their own problems.
] ...
] As they say in the satellite business, there's no such thing as a free
] launch. Prolog strikes a balance between cost and power; it's fast and
] stupid rather than slow and smart.
/* End of text from comp.lang.prolog */
Hmmm... This is one other place where one could explore parallelism: have
separate processors hunting for the best or simplest backtrack scheme.
This sounds vaguely like it might be a psychologically plausible model. I
don't know what kind of a nightmare this would be to implement.
I think the general approach to parallelism in Prolog is somewhat incompatible
with this idea - all promising approaches are being explored, so an
intelligent backtrack would never be involved. But I see no proof that the
idea doesn't have unique benefits in some problem areas, so I can't dismiss it
as a pointless investigation.
- Mark Goldfainmiller@CS.ROCHESTER.EDU (Brad Miller) (10/18/89)
[]
Date: 17 Oct 89 09:40:15 GMT
From: goldfain@osiris.cso.uiuc.edu
I think the general approach to parallelism in Prolog is somewhat incompatible
with this idea - all promising approaches are being explored, so an
intelligent backtrack would never be involved.
Consider the case where a proof deep in the tree (admitably in parallel)
identifies a culprit high up in the tree. You want to prune the tree and
kill off all the processes currently exploring proofs in that part of the
tree, freeing them up as a resource for exploring other branches.
Proof cacheing probably buys you more in most cases than intelligent
backtracking, but that's another case where [member ?x (:A :A :A)] would
only succeed once. (Sorry for the Rhet syntax :-); I'm sure the translation
is obvious).