GC for logic programming

GC for logic programming

[Stefan Israelsson Tampe]

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

One of the benefits of using a mutating stack for the variable bindings are
that one can introduce proper gc of prolog programs, that is a feature that
would benifit guile-log logic programs and the kanren and prolog
interfaces. The current options are to use a light version that take care
of some common special cases, but it is error prone path and it is hard to
make programs not leaking memory. A better option is to use the guile log
meta language for the prolog programs, there one have several techniques
available that makes it explicit that variables are not created as prolog
variables. It is a bit clumsy but it works, study the parser tools in guile
log if you want to know more.

Now people have asked for proper gc of logic programs and good prolog
implementation
have them. So I set out to see if we could get bdw-gc to help here.

It turns out that it is not possible as far as I can see to enable such a
feature  without modifying bdw-gc. The basic need is to know if objects
have been marked through normal code or not but still keep the objects from
gc. The reason is that the sweep phase has to be postponed to places in the
code where it is safe to modify the stack.

There are two options as far as I can see
1. Have a secondary mark pass to make sure prolog variables are not gc'd
2. Have a touch feature in the mark phase

The number two solution works as
i)  There is two mark function mark, and mark_and_notouch
ii) There is a mapping between smobtype and a mark bit

The logic for the mark function is
at marking (tag . l), check mark_bit_p[tag]
if true ( != 0 ) then mask it on the tag
continue with the usual mark phase.
If there is a mark function, cast it to a mark_funciton_type_touch with a
boolean argument and call it with true

The logic for the mark_and_notouch function is just the old mark logic. But
for smob types
with a touch flag on, call it with mark function argument false

The essential extra overhead for normal code are the lookup check
mark_bit_p[tag]. it
is essentially a lookup from a quite close cache so it is not a devistating
lookup, but it is done for every mark.

It is possible to skip the mark function entirely for logic programs and
the above approach might be overly complex. But it should not result in an
effective mark phase.

the solution 2 is better because you do not need a special mark funciton on
the prolog variables, so I will try to implement a modded version of the gc.

If anyone have another sane option where we do not mod bdw-gc please let me
know.

Also I would like to have such a feature for assoc based prolog binding
handling as well, I think that it is possible, but for this to work we
really need the same features from
 bdw-gc.

Cheers
Stefan

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

Re: GC for logic programming

[Andy Wingo]

On Wed 30 Apr 2014 08:07, Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:

> It turns out that it is not possible as far as I can see to enable such
> a feature without modifying bdw-gc. The basic need is to know if objects
> have been marked through normal code or not but still keep the objects
> from gc. The reason is that the sweep phase has to be postponed to
> places in the code where it is safe to modify the stack.

I have no idea what this means.  However what if you attach a finalizer
to them, and make the references from the stack weak?  The finalizer can
decide whether they stick around or not.  Or put them in a guardian and
pump the guardian from somewhere that it's safe.

Andy
-- 
http://wingolog.org/