restivo@POLYA.STANFORD.EDU (Chuck Restivo) (07/14/88)
Date: Thu, 14 July 1988 02:53-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 #46
To: PROLOG@POLYA.STANFORD.EDU
PROLOG Digest Thursday, 14 July 1988 Volume 6 : Issue 46
Today's Topics:
Implementation - Footnote & Call/1
-----------------------------------------------------------------------------------------------------------
Date: Tue, 5 Jul 88 12:22:36 EST
From: pereira
Subject: Footnote
In Digest V6 #26, Richard O'Keefe says
> However, there is an encapsulation which works nicely, due I think to
> Stuart Shieber, which Fernando Pereira told me about.
I did describe the idea to Richard, but I believe I attributed it to
its proper originator, Mark Johnson, formerly from Stanford and
currently at MIT.
-- Fernando Pereira
------------------------------
Date: Sun, 10 Jul 88 14:37:45 EST
From: pereira
Subject: Call/1 and goal processing
uicsrd.csrd.uiuc.edu!sehr@uxc.cso.uiuc.edu (David ?) writes
> It seems that if one allows the interpretation
> of dynamically constructed goals (i.e. those constructed via functor/3,
> arg/3, and univ (=..)), then one must cope with the possibility of
> variable dereferencing during the selection of a goal to process. Does
> anyone out there know how it is done in other interpreters (C-Prolog,
> SB-Prolog, etc.)?
In C-Prolog, that's exactly what happens. In a structure-sharing
system, a goal (or any other compound term) is specified by a
*molecule*, which is a pair consisting of a pointer to a *skeleton*
specifying the input form of the goal (compound term) and of a pointer
to an *environment* specifying the values of the goal's (term's)
variables (see David H. D. Warren's dissertation for details).
C-Prolog uses David Warren's two-stack storage scheme, in which
variables are classified as either local (go away on determinate exit)
or global (survive until backtracking). Ignoring the questions of mode
declarations (which don't exist in C-Prolog), of temporary variables
(which do, but don't make things that different) and last-call
optimization (which C-Prolog doesn't have) variables that occur only
as immediate arguments of a clause-head or goal are local, others
global.
When a *lexical* goal (one whose predicate symbol is defined at
program read-in time) is called, three values are required to get at
the goal: a pointer G to the source form of the goal (the goal's
skeleton), a pointer PL to the local environment for the clause
activation containing the goal, and a pointer PG to the corresponding
global environment (G, PL and PG are not the historically used names
for these pointers, but I can't remember those and I don't have the
appropriate reference material with me).
*Dynamic* goals in C-Prolog occur only through the agency of a
meta-call, either explicitly through a call/1 goal in the source or
implicitly through a variable goal in the source, which I think (I
don't have the C-Prolog sources handy and I haven't looked at them for
4 years) is translated into the explicit form when the clause
containing it is stored. In any case, the main point to observe is
that when call/1 is executed its argument should either be a constant
(trivial case) or a compound term. Assuming the meta-call is call(X),
X is first dereferenced. If its value is neither an atom or a
molecule, an instantiation error is signaled. In the atom case, G
points to the atom, PL to the parent clause's local environment and PG
to the parent clause's global environment. PL and PG won't be needed
for unifying the goal against clause heads, but PL still needs to be
saved for deep backtracking purposes. If X is bound to a molecule, G
is set to the molecule's skeleton, PL to the parent's local
environment and PG to the molecule's environment pointer. PL won't be
needed to get at the goal's variables, but is still needed for deep
backtracking purposes.
As for SB-Prolog, things are very different. I don't know the
internals of that system in detail, but I know it is a WAM-based
structure-copying system rather than a structure-sharing one. This
means that the value of X in call(X) will be an explicitly represented
term in the structure (heap) stack. A single pointer is thus needed to
represent the goal, but additional manoevers will be required to set
up the call as required by the WAM. I haven't studied how this is done
in detail.
-- Fernando Pereira
-------------------------------
End of PROLOG Digest