[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

GC for logic programming

From: Stefan Israelsson Tampe
Subject: GC for logic programming
Date: Wed, 30 Apr 2014 08:07:58 +0200

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]