Subject: RE: [SWIPL] Looking for a way to record a variables reference

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 25 Feb 2002 17:21:08 +1300 (NZDT)

"Douglas R. Miles" <[email-masked]> wrote:
    [asking about attaching information to variables,
     as if variables were some kind of long-lived object].

Trying to treat variables this way comes pretty high on the list of
"Prolog Mortal Sins".  The point of using Prolog is to use a _logic_
programming language; if we want Lisp, we know where to find it, and
if we want backtracking search in Lisp, I'm happy to tell anyone who
_doesn't_ know where to find it about Jeff Siskind's "Screamer".

	Understandable about garbage collections shifting them about of
	memory.  I must be more interested in how it gets it's name and
	how dynamic that is.
	
In DEC-10 Prolog (old and TRO compilers), C Prolog, Quintus Prolog, and
some others, variables at run time don't *have* names.  For the purposes
of printing, a name is *generated* from the variable's address.  The
write/print/display code was, in those Prologs, very carefully written to
allocate no storage at all, so there would be no garbage collections, so
the 'name' used for a variable would be consistent _for the duration of
that output call_, but if you do
    write(Term), nl,
    other_code(ArgumentsNotSharingWithTerm),
    write(Term), nl,
and Term contains any variables, you can confidently expect that the
two lots of output will NOT be the same.

Of course, if you use print/1, then your portray/1 will be called, and that
may well allocate storage, so variable 'names' *can* change during a single
call to print/1.

There is a hack, going back to DEC-10 Prolog, that '$VAR'(N) (where N >= 0)
terms are normally written _as if_ they were variables.  Any time I want
to generate output with variable names, it's
    \+ \+ (numbervars(Term, 0, _), print(Term))
time, which is immune to the shifting variable problem.

	> The only sensible reference to a variable is another variable.
	
Indeed.

	I suppose one would do this on a variable that was never
	backtrack over in the program.

Backtracking is not the issue.  Garbage collection and stack shifting
are the issues.  There's also the fact that a compiler is within its
rights to split and join variables, depending on the results of a flow
analysis.  Prolog variables are *LOGICAL VARIABLES*, not objects.

	A single or many topvars that woould
	stay arround for the durration of the program.
	
There is no such thing in Prolog as a variable that stays around
for the duration of a program.  Global variables are bad in any
language; added to Prolog they should be sheer black unadulterated evil.

	Yes, currently I am storing some variables in the exact manner.
	An 'ordered' list like
	[v(_G1,[prop1|_RoomforMoreProperties]),v(_G2,[propA,propC|_]),v(_G3,[prop1,p
	ropB|_]),v(_G4,[prop1,prop2|_])|_PlaceForNewVars] throughout the depth
	of a query.

Why is 'ordered' in scare quotes?  The term comparison operations compare/3
and relatives are TOTAL ORDERS.  They have a defined effect on all terms.
The ordering of unbound variables isn't defined, except that it is total
and STABLE.  That is, var(X), var(Y), X @< Y at time t1 and var(X), var(Y)
at time t2 implies that X @< Y at time t2.

Accordingly, a binary search tree with variables as keys should work very
well.  I've often done that.

I thought that I could give each variable a
'Tracking' number or atom such as using term_to_atom(_G22,'_G22') to be
used as a key

You should expect term_to_atom/2 to be a comparatively slow operation;
quite a bit slower than membering down a modest size list.

	>  Some systems provide `global variables',
	> possibly not a bad idea and I think not very hard to implement.
	
Global variables a la Lisp that can have *ground* terms as their variables
are relatively harmless.  But of course, that's precisely what the data base
(especially the 'recorded') data base is.  Of course, when you stuff something
into the recorded data base, or 'record' it, you have to COPY it, which is
slow.  And of course using global variables like that interferes in rather
nasty ways with multiple threads of control.  (It's a real pity that Tim
Lindholm's concurrent Quintus Prolog was never released.)

	Do global varibles act like standard prolog varibles built from
	a frame higher then your current one.. Or are they just not lost
	on bactrackign?

Don't ask.  Don't even _think_ of thinking about it.
Use Prolog _as_ Prolog, that's the way to clarity and efficiency.

	The is an inference engine I am trying to optimize.  Attempting
	to profile clause head usage per actual == prolog variable to
	detect loops but allow certain variables to enter a clause
	multiple times.

Can you say this another way?  I'm afraid I couldn't follow your explanation
at all.  When you talk about a 'body clause', I don't know what you mean;
a clause has a body, but a body can't be a clause.

	imagine what Sicstus would tell me! ;P
	
Much the same as Jan did.

There's a very simple approach which you don't seem to have thought of,
and it's basically what David H. D. Warren did in his coroutining package
for DEC-10 Prolog.

When you have a variable X in your source, you transform that to
    '#VAR'(X1, XInfo)
where X1 will carry the value that it would otherwise have had,
and XInfo is the extra information you want to add.

Obviously, if X = 1 transformed to '#VAR'(X1,Xinfo) = 1, that would
not work.  So you write your own unification code.

    unify_with_info(T1, T2) :-
        (   T1 = '#VAR'(X1, X1Info) ->
	    (   nonvar(X1) -> unify_with_info(X1, T2)
	    ;   T2 = '#VAR'(X2, X2Info) ->
	        (   nonvar(X2) -> unify_with_info(T1, X2)
	        ;   X1 == X2 -> true
	        ;   X1 = X2, merge_info(X1Info, X2Info)
	        )
	    ;   X1 = T2, update_info(X1Info, T2)
	    )
	;   T2 = '#VAR'(X2, X2Info) ->
	    (   nonvar(X2) -> unify_with_info(T1, X2)
	    ;   X2 = T1, update_info(X2Info, T1)
	    )
	;   functor(T1, F, N),
	    functor(T2, F, N),
	    unify_with_info(N, T1, T2)
	).

    unify_with_info(I, T1, T2) :-
	(   I > 1 ->
	    arg(I, T1, A1),
	    arg(I, T2, A2),
	    unify_with_info(A1, A2),
	    J is I - 1,
	    unify_with_info(J, T1, T2)
	;   I =:= 1 ->
	    arg(I, T1, A1),
	    arg(I, T2, A2),
	    unify_with_info(A1, A2)
	;   I =:= 0
	).

There are a number of special cases you can optimise.
For example,

    unify_const_with_info(T1, C2) :-
        (   T1 = '$VAR'(X1,X1Info),
	    (   nonvar(X1) -> unify_const_with_info(X1, C2)
	    ;   X1 = C2, update_info(X1Info, C2)
	    )
	;   T1 == C2
	).

Then there's no _searching_ for a variable, because you've _got_ the
variable and its associated information right there.  The cost is moved
elsewhere.

Even this is viewed as rather an abuse of Prolog logical variables,
but it uses only standard operations.