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!