PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (05/04/87)
PROLOG Digest Tuesday, 5 May 1987 Volume 5 : Issue 35
Today's Topics:
Implementation - Compare/3 etc. & Meta-Circular Interpreter
----------------------------------------------------------------------
Date: Mon, 4 May 87 09:38:39 PDT
From: Fernando Pereira <pereira@stinson.ai.sri.com>
Subject: Compare/3, write/1, etc.
Much ado about very little, it seems to me. In all reasonable uses of
compare/3 and write/1 with variable arguments I can think of, the
variables are global since they come from inside some preexisting
structure. In any case, there cannot be any guarantee that a global
variable will print in the same way in two successive calls of
write/1, because of global stack garbage collection. Since BIM-Prolog
has it, Alain Callebaut's test gave the result he expected only by
accident. On the other hand, the stack discipline of the global stack
guarantees the relative order of global variables, so globalization is
a solution for the compare/3 problem.
-- Fernando Pereira
------------------------------
Date: Mon, 4 May 87 13:01:35 PDT
From: Richard A. O'Keefe <quintus!cresswell!ok@Sun.COM>
Subject: Alleged bug in meta-circular interpreter
The meta-circular interpreter which has been discussed in this
digest recently does not in fact contain a bug. What we have is
a misunderstanding, because it has been taken out of context.
What is required of a meta-circular interpreter is that it be
sufficiently powerful to interpret ITSELF. The particular
version in question is a stripped down version (about half the
size of the real thing) which was prepared for inclusion in a
published paper that I was squeezing hard to get within the page
limit. All that *I* have ever claimed for that particular
version is that it correctly interprets a subset of Prolog
containing cuts, and that it is written in the subset it
interprets. As various people have realised, it is an utterly
trivial exercise to extend it to something which can handle
non-tail disjunctions and leftist conjunctions. An obvious
trivial extension would be to first rewrite the clause body so
that ((A,B),C) -> (A,(B,C)) and ((A;B),C) -> ((A,C);(B,C)).
There are several extensions of the real thing, including a
Dec-10 style four-port debugger, which is capable (of course)
of debugging itself.
It is interesting to compare an interpreter which uses this
technique (which, for the full language, does entail a certain
amount of copying to handle non-tail disjunction and leftist
conjunction) with an interpreter which uses ancestral cuts.
I have actually performed this comparison on more than one
occasion, and the result is generally that there is no practical
difference. Whatever difference there may be between an
interpreter/debugger using my technique and one using ancestral
cuts is invariably dominated by other costs, such as the cost of
maintaining debugger data structures or the cost of picking up
copies of interpreted clauses in the first place. If you have
the time either to implement ancestral cuts or to implement
indexing for interpreted code, do the latter! It's much more
important. (In fact, it's more important who you pick to write
the interpreter than whether or not ancestral cuts are used.)
Ancestral cuts are such an abominable feature generally that we
should need very strong reasons indeed to include them in the
language; I have been writing Prolog code since 1979 and have
yet to discover any need for them at all.
It is interesting that the if->then;else {note: (a->b;c) is
parsed as ;(->(a,b),c) by Prolog; this has confused some people
but should be "of course, what else?" to Lisp programmers used
to (cond (a b) (T c))} is very nearly equivalent to the cut in
power, yet it is utterly trivial to write a meta-circular
interpreter for Prolog+COND, while writing a meta-circular
interpreter for Prolog+CUT requires rather tricky thinking.
Even more importantly, partial execution of Prolog+COND is
relatively straightforward, while partial execution of
Prolog+CUT is a nightmare. The point of the paper in which the
"mini" meta-circular interpreter appeared was to suggest that
cuts should be regarded as "syntactic arsenic" for
if->then;elses, and to say how this may be done.
To close: yes the "mini" meta-circular interpreter doesn't
handle ((a,!,b),c), and no, that isn't a bug, because that
form doesn't appear in the meta-circular interpreter itself.
------------------------------
End of PROLOG Digest
********************