gc of logical variables

gc of logical variables

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 3275 bytes --]

Hi,

A question come up at ##prolog of guile-log supporting servers that keeps
on tail calling and as a consequence any logical variables not referencable
needs to be gc:ed.

Currently there is a call ideom that will basically do a call and then
transfer a few
variable to results and then backtrack. That is the most efficiently way to
handle the server
issue. Also input and output only variables can be handled on the stack and
this options
is also available. These options are nice and very effective when
applicable.

Still a way to detect that logical variable is not reachable and then clear
them out would be a nice addition for both the kanren and prolog interfaces
in guile-log. I will describe my strategy to do this and please let me know
if there might be any problem.

The setup is that we have allocated a set of variables
V1,V2,....

That associates a value by either referencing a value or is associated to
one in an assoc. It is not possible to track all versions of the
association map hence that solution does not blend well with the gc, there
are a few tricks that can be borrowed from kanren that can improve the
situation somewhat though.

In the other solution we have a control stack that tracks instantiations of
the variables e.g.
(V1,V2,frame,V3,V4,...)
(
   backtracking will go from the top backwards to the frame and undo the
var binding.
   Also variables need to be freed if they come from allocation stack
)

Currently if e.g. V3 has no reference in the scheme runtime it will still
be marked as not
for gc  and live for ever or until backtracking kicks in although it could
be reclaimed semantically.

The idea of solution.

0. All variables are allocated from the gc engine

1. force V1, V2 etc as not available for gc via.
SCM_API SCM scm_gc_protect_object (SCM obj);

2. make sure that there is one bit 'm' that identifies if the variable was
marked.

3. make sure that there is two bits, rc on the variables that identified a
refcount (0 1 2 many)

4. define a variable mark_bit_value = 1

5. after the sweep phase negate 'mark_bit_value' with scm_after_sweep_c_hook

6. Let the variables be smobs and attach a 'scm_set_smob_mark'
This mark function shall set 'm' to 'mark_bit_value' if not set

7. after the mark phase with scm_before_sweep_c_hook, do
a) walk the control stack from top to bottom clear bc to 0 for the pointed
to variables
b) walk the control stack from top to bottom, if a variable points to
another variable
increase the bc of the pointing to variable by min(3,bc + 1)
c) walk the list from top to bottom for each var if 'm' + bc  == 0 then
    if it points to a variable then decrease that bc by one if 0 < bc < 3,
and then clear the
    data record in the control stack for the variable. if the bc for
pointed to variable is 0
    redo c) for that variable.
d) walk the control stack and issue scm_gc_mark on all the pointed to data.
e) compact the free variable list and compact the control stack from top to
the first frame


This is at least the plan, if you see any problems or finds other solutions
please let me now.
The real setup is much more complex to get right at full power but i think
that if the above scheme is doable that we will get a quite god feature
targetting logical server engines.

Cheers!

[-- Attachment #2: Type: text/html, Size: 4451 bytes --]