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

From: "Douglas R. Miles" <[email-masked]>
Date: Mon, 25 Feb 2002 01:20:15 -0800

Richard,

     -----Original Message-----
     From: Richard A. O'Keefe [mailto:[email-masked]]
     Sent: Sunday, February 24, 2002 8:21 PM
     To: [email-masked]; [email-masked]
     Subject: RE: [SWIPL] Looking for a way to record a 
     variables reference

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

J:    > The only sensible reference to a variable is another variable.
     
R:   Indeed.
     
D:    I suppose one would do this on a variable that was never
     backtrack over in the program.
     
R:   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.
     
D:    A single or many topvars that woould
     stay arround for the durration of the program.
     
R:    There is no such thing in Prolog as a variable that stays around
     for the duration of a program.  
     
*D:  I too often am unclear,  I meant the 3 variables that would be created
durring:
     ?- run_program(Top1,Top2,Top3).

R:    Global variables are bad in any
     language; added to Prolog they should be sheer black 
     unadulterated evil.

D:    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,propB|_]),v(_G4,[prop1,prop2|_])|_PlaceForNewVars] 
     throughout the depth of a query.
     
R:    Why is 'ordered' in scare quotes?  The term comparison 
     operations compare/3 and relatives are TOTAL ORDERS.  

*D:   I was believing (and implying) that I could consistently X @< Y 
     throughout my membersearch and used terminology incorrectly.   

R:    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.

*D:   That is good to know that the ordering shouldn't change.
     
R:   Accordingly, a binary search tree with variables as keys 
     should work very
     well.  I've often done that.

*D:  I see that storage in a List like I had done is not a good idea.
     I have changed it now to walk its way down a binary tree.

D:   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
     
R:   You should expect term_to_atom/2 to be a comparatively 
     slow operation;
     quite a bit slower than membering down a modest size list.

*D:  Yes, this was one of my many bad ideas.

J:    >  Some systems provide `global variables',
     > possibly not a bad idea and I think not very hard to 
     implement.
     
R:   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.)

*D:  I suppose a global variable is then not much different then:
     
     getGlobal(Name,Value):- (recorded(Name,Value),!);(Value=Name).
     setGlobal(Name,Value):-
(recorded(Name,_,Ref),erase(Ref),fail);recorda(Name,Value).
     unifyGlobal(Name,Target):-
getGlobal(Name,Target),setGlobal(Name,Target). 

     Except that the Name would be like the first instance created for Top1
in 
     ?- run_program(Top1).  And the reference would remain unchained.
     It would be nasty for prolog to have an extra type bolted on for
unification.

D:    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.
     
R:   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.

*D:  Clearification: I am trying to optimize a meta-interpretor so it can
interatively deepen
     in it's use of normal logical variables.

     Also, I meant to say the body term of a clause

     When the body term of a clasue has new variables not found in the head.
     I am trying to determine a heuristic to decide how many times these new
varibles should bind.

     an example would be in a program:

     go(A,B):-y(A,_N1),z(B,_N1).
     go(A,B):-s(A,_N2),z(B,_N3).
     
     y(a1,t1).    z(b1,t1).
     y(a2,t2).    z(b2,t2).

     s(a3,CD):-c(CD).

     c(1). c(2). c(3).

     with a call to:
     ?- go(A,B). 

     the body term: y(A,_N1),z(B,_N1)
     has a variable _N1 that is connected to finding solutions for finding
pairs of A and B.

     the body term: s(A,_N2),z(B,_N3)
     has two variables _N2 and _N3 and bindings for A and B are disconnected
therefore
     I create to different findalls, the A and then B.
     I would like to mark multiple solutions for _N2 as unimportant while
seaching out for A
     When i call s(A,_N2) and find head s(a3,CD) and see that CD is
unimportant therfore body terms
     containing only varible CD are automaticly called in once/1.

     I can look at the program first and rewrite it.  But I might add
clauses that involve 
     the 2nd argument of s/2 to create values for their heads.  So I keep a
table of variables
     that are important or not for proving a goal.
     
     If for example "c(1). c(2). c(3)." was replaced with a clause:

     c(CD):-p(_N4,CD),q(_N5,CD). 

     While only wanting to once(c(_N2)) to prove: s(a3,_N2)  so A could
return a3:

     I would like to set a search depth limit for any binding of _N2 instead
of 
     just call_with_depth_limit once(c(_N2)),Something,_).  
     With the body: p(_N4,CD),q(_N5,CD) _N4 and _N5 are even less important
and wish
     to give searches for them less depth then _N2.
     So the goal is to trace how far removed from the original A,B varaibles
new varialbes are.
     From realivancy, iteratively deepen in seartch space per variable.  So
for binding of 
     A and B I go into a maximum depth.  Since go/2 only has those two
clauses, I would go 
     pretty far to get _N1. But _N2 that is only there to help me find
values for
     A in s(A,_N2) so I would like to give it a limited depth yet not
limiting searching for the 
     first argument of s/2.
     
     Over the years, you have seen many approaches to maximizing the results
of 
     searches.  Which ones, in your opinion, seem to do what I am looking
for?

R:   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.

*D:  That is excellent passing the information in the variable where it
belongs.
       and does effectivly what I want for constraining what can or cant
bind with what.

       with the clasue:

       c(CD):-p(_N4,CD),q(_N5,CD)

       I could see tranforming into:

       c('#VAR'(A,OldInfo)):-
           (
 
decrement_and_get_info(usage_depth,OldInfo,NewInfo,NewDepth),NewDepth>0,
            update_info([called(c(-))],NewInfo),
            merge_info([basedOnVar(A),onlyOneFutureBinding],OldInfo),

            copy_term(#VAR(_,OldInfo),_N4),
            copy_term(#VAR(_,OldInfo),_N5),
            p(_N4,'#VAR'(A,NewInfo),q(_N5,'#VAR'(A,NewInfo))),
            (inside_info(onlyOneFutureBinding,OldInfo),!);true).

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