PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (04/30/87)
PROLOG Digest Friday, 1 May 1987 Volume 5 : Issue 33
Today's Topics:
Query - Source Availability,
Implementation - Side Effects & Metainterpreter & Bug
----------------------------------------------------------------------
Date: Thu, 30 Apr 87 9:07:30 BST
From: William Clocksin <wfc%cam.cl@Cs.Ucl.AC.UK>
Subject: Plea for cooperation
Can anyone supply me with the source code of a fast Prolog system? I
do not need any features such as assert/retract, I/O, etc. C code
preferred, but assembler is acceptable. I can do any rehosting
required. This is for an experimental hack, so no money is involved.
------------------------------
Date: Fri, 24 Apr 87 16:41:54 PST
From: Fernando Pereira <pereira@stinson.ai.sri.com>
Subject: Side-effects
There were so many different points in the recent discussion on Prolog
implementations of languages with side effects that I cannot resist
trying to systematize a bit the answers.
1. All the discussion implictly assumes an underlying machine model
with an unbounded array of constant-time accessible and updatable
locations capable of containing arbitrary indexes into the array. This
is clearly an optimistic approximation of reality, but analyzing its
effect on the whole argument is far beyond the scope of this note. It
is also worth nothing that very-large address space virtual-memory
schemes require tree-structured page tables, with obvious consequences
for worst-case access time.
2. Under the above optimistic model, certain datatypes involving
arbitrarily large aggregates of cells with single cell access and
update procedures can be implemented with constant time access and
update provided side-effects are allowed. Arrays are the canonical
example.
3. In languages without side effects implemented on the same machine
model, with bounding tupling as the only data constructor, arrays have
to be represented by tree-like structures, leading to logarithmic
access and update times.
4. However, it is possible to extend side-effect-free languages with
primitive datatypes satisfying the side-effect-free discipline but
with constant time access and update. The work Ken Kahn cited is an
example of this. In such schemes, access and update of OLD versions of
the array will in general require time dependent on the size of the
aggregate data structure. However, this is a capability that is not at
all available in imperative languages, since old versions have been
destroyed by side effects.
5. Even the logarithmic time access/update data structures, such as
the extensible array package in the Prolog library, are very useful
when relatively good access to multiple versions of the data structure
is required. I have some interesting applications of this.
6. Another approach to achieve side-effect-like efficiency in
side-effect free languages is careful flow analysis to determine
whether old versions of the data are no longer in use and can thus be
overwritten by newer versions. Paul Hudak mentioned some of the main
papers in this tradition. Clearly, this could well be combined with 4.
7. With respect to direct implementations of languages from their
semantic specifications, it is interesting to note that denotational
semantics maps well onto higher-order functional languages (no
surprise here, given the lambda-calculus origins of much of denotational
semantics) while Plotkin-style abstract operational semantics maps
well to pure Prolog. In both cases the aggregate data structure problem
has to be dealt with.
I hope this clarifies somewhat the issues being discussed
-- Fernando Pereira
------------------------------
Date: Wed, 29 Apr 87 00:01:18 PDT
From: Dr D Stott Parker <stott@CS.UCLA.EDU>
Subject: bug in O'Keefe's interpreter
The clause
do_body((Goal,Body), AfterCut, HadCut) :- !,
do_goal(Goal),
do_body(Body, AfterCut, HadCut).
does not interpret left-associative conjunctions properly (or more
generally any Goal that is an expression containing a cut).
Admittedly this situation might not arise often in good code, but one
can get burnt by it (I was once here at UCLA).
To make what I am saying clearer, consider the predicate p/2:
p(X,Y) :- ( ((X=1,!),Y=1) ; (X=2,Y=2) ).
Then the two goals
?- setof(X-Y, p(X,Y), L).
?- setof(X-Y, do_goal(p(X,Y)), L).
give different results (on both Quintus Prolog and C-Prolog). The
first gives L=[1-1], while the second gives L=[1-1,2-2]. [For
C-Prolog system_predicate(Goal) must be changed to system(Goal) , and
for Quintus to predicate_property(Goal,built_in) .]
The clause above can be changed to something like the following to
repair the problem:
do_body((Goal,Body), AfterCut, HadCut) :- !,
do_body(Goal, GoalAfterCut,GoalHadCut),
continue_body(GoalHadCut,GoalAfterCut,Body, AfterCut,HadCut).
continue_body(yes,GoalAfterCut,Body, (GoalAfterCut,Body),yes) :- !.
continue_body(no,_,Body, AfterCut,HadCut) :-
do_body(Body, AfterCut, HadCut).
This raises the question:
Can we PROVE this change makes the interpreter correct?
Proving properties of meta-circular programs seems challenging.
-- Stott
P.S. Antonio Porto's "Two-level Prolog" system is another approach
for writing interpreters that respect cuts. Antonio's scheme, which
distinguishes 'object' and 'meta' levels, is elegant and makes writing
such interpreters relatively easy. See his paper: ``Two-Level
Prolog'', Proc. Conf. on Fifth Generation Computer Systems, Kyoto,
1984 (published by North-Holland).
------------------------------
End of PROLOG Digest
********************