🚀 go-pugleaf

Tim Lindholm writes:

> ... to get rid of unsafe variables (by immediately globalizing
> them -- I hope that's what we are talking about!).

That is indeed what I meant: put_yvar doesn't store an UNDEF in the
environment, but a REF to the heap where an UNDEF is stored.

I try to list the advantages and the disadvantages + possible remedies:

	+ trail test is cheaper (1): one comparison
	+ no put_unsafe_yval: it is replaced by a put_yval
	+ no overhead in unify_yval to avoid pointers from heap to local stack
	+ possibly less trailing (2)

	- more heap usage (3)
	- reference chains become longer (4)


(1) some people would say this is no advantage: it is sometimes claimed
    that ALWAYS trailing (without testing) is the best ...


(2) Perhaps you will find the following a somewhat contrived example, but here it is:

	a :- b , c(Y) , d(Y) .

	b .
	b .

	c(1) .

    With unsafe variables, Y is in an old part of the local stack when it is bound to 1,
    so that this binding is trailed. (Mind you: this is true for WAM not for VAM)
    Without unsafe variables, Y is in the most recent part of the heap (it is created
    on the heap after the choicepoint for B was created), so that the binding
    of Y to 1 is not trailed.

    Since most Prolog programs are deterministic (sic), and since the extra trailing
    requires the choicepoint, you can make your conclusions yourself.


(3) At the time we got rid of unsafe vars, we worried little about higher heap
    consumption because BIMprolog was probably the only commercial Prolog with
    a garbage collector (maybe M-Prolog had one as well ?). Still, I put an option
    in the compiler which would count the number of permanent variables in the program
    and the number of put_yvar instructions generated, so that I could have an idea
    of the relative importance of unsafe variables. And the figures looked ok.
    Now I think that these figures don't give much information, because
    environments are deallocated on forward execution, and heap is not.
    I observed extra heap usage in the order of 50% for typical programs - but here
    is a program that needs no gc in SICStus (which has unsafe vars) and
    repeatly for BIM:

	a :- b(X) , c(X) , a .
	b(1) .
	c(_) .
	?- a .

    We have the same experience as in VAM that by doing something about builtin
    predicates, the extra heap cost becomes lower.


(4) This can be easily remedied by the introduction of some new instructions, e.g.

	a :- b(Y) , c(Y) . is compiled in WAM to

	allocate
	put_yvar Y,1
	call b/1
	put_unsafe_yval Y,1 (*)
	deallocate
	execute c/1

	the instruction with the (*) is replaced by put_deref_yval Y,1 which does
	something like:
	
		ArgReg[1] := *E[Y]  % this is safe because E[Y] always contains
				    % a ref after a put_yvar of Y

    Without this, refchains might become longer and the introduction of these
    instructions was good for performance. (sorry, I have currently no figures,
    perhaps once later).

I used to like not having unsafe variables - recently I am not so sure any more.
What were Aquarius reasons for choosing not to have them ? I guess that with its
global analysis, they occur very infrequent, so the heap penalty is neglectable.

Two more remarks: I want to make a link with BinProlog (by the way, the
relation between BinProlog and BIMProlog as not the same as between Nu-Prolog
and Mu-Prolog !) or a continuation based implementation of Prolog:
continuations on the heap actually means also environments on the heap, so that
it in fact puts uninitialized 'permanent' variables on the heap. Still, it trails as
much as a WAM implementation with unsafe variables. And it is difficult to get rid
of the extra dereference every time the variable is accessed.

Finally, the unsafe variables fall in the category of variables that are called
'unnecessary' variables by Proietti&Pettorossi and in a PLILP'91 paper they
describe how eliminate them (in logic programs, but their approach can be
applied to Prolog as well). Hoorah, unsafe is unnecessary at last :-)
No kidding, I think the work by Proietti&Pettorossi is very important for anybody
interested in program transformation and compilation.

Bart Demoen