From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: GC for logic programming Date: Wed, 30 Apr 2014 08:07:58 +0200 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7b5d472cc2ff8d04f83c5e88 X-Trace: ger.gmane.org 1398838094 23999 80.91.229.3 (30 Apr 2014 06:08:14 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 30 Apr 2014 06:08:14 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Apr 30 08:08:07 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WfNgd-0000Q8-0n for guile-devel@m.gmane.org; Wed, 30 Apr 2014 08:08:07 +0200 Original-Received: from localhost ([::1]:54839 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WfNgc-0007Dh-Hn for guile-devel@m.gmane.org; Wed, 30 Apr 2014 02:08:06 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:46489) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WfNgX-0007Cj-AS for guile-devel@gnu.org; Wed, 30 Apr 2014 02:08:02 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WfNgW-0006Zg-4f for guile-devel@gnu.org; Wed, 30 Apr 2014 02:08:01 -0400 Original-Received: from mail-pd0-x233.google.com ([2607:f8b0:400e:c02::233]:41560) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WfNgV-0006ZG-Pk for guile-devel@gnu.org; Wed, 30 Apr 2014 02:08:00 -0400 Original-Received: by mail-pd0-f179.google.com with SMTP id y10so1262101pdj.38 for ; Tue, 29 Apr 2014 23:07:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=coMszlG+c2HqC1Th+7IzZhtE9ke8lYUZvYet2SLHzwA=; b=lAlq2LYpbI42ifSHtXW/XdwONKNj4mLojMTP8y60hOzQ5D4cKC504wOtgPcZQ+q7jF G94WGkAUGhMKY7daO0dVFXasZDm88CcxD/tpO1xo28ldT0LnPtHGr+bm/XTGJ8iBgF9L n9h51falmEjLkrTCpDXZZnxSDWshBXlovsslqz2WJ9hmVpaGRFT7UnsAa2+yUjfz2625 2Cneujq7LCZnXnM/EmioNROodZYy/8Di8Qv6DFHuV8aGN/mEQU1NYCsRNa0FACTaJ9nS hrpnWw8Je3fwdoeN51DbhRCdD8Dat9E9NZterL0bl9v8Dm06qKPhd8vkl0Y4plZD2an1 zBdw== X-Received: by 10.66.221.4 with SMTP id qa4mr4946452pac.138.1398838078405; Tue, 29 Apr 2014 23:07:58 -0700 (PDT) Original-Received: by 10.70.106.133 with HTTP; Tue, 29 Apr 2014 23:07:58 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c02::233 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:17121 Archived-At: --047d7b5d472cc2ff8d04f83c5e88 Content-Type: text/plain; charset=UTF-8 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 --047d7b5d472cc2ff8d04f83c5e88 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
One of the benefits of using a mutating stack for the vari= able 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 an= d prolog interfaces. The current options are to use a light version that ta= ke 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 gui= le log meta language for the prolog programs, there one have several techni= ques available that makes it explicit that variables are not created as pro= log variables. It is a bit clumsy but it works, study the parser tools in g= uile log if you want to know more.

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

It turns out that it i= s not possible as far as I can see to enable such a feature =C2=A0without m= odifying bdw-gc. The basic need is to know if objects have been marked thro= ugh normal code or not but still keep the objects from gc. The reason is th= at the sweep phase has to be postponed to places in the code where it is sa= fe 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) =C2=A0There is two mark = function mark, and mark_and_notouch
ii) There is a mapping betwee= n smobtype and a mark bit

The logic for the mark f= unction is
at marking (tag . l), check mark_bit_p[tag]=C2=A0
if true ( = !=3D 0 ) then mask it on the tag
continue with the usual mark pha= se.
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, cal= l it with mark function argument false

The essenti= al extra overhead for normal code are the lookup check mark_bit_p[tag]. it<= /div>
is essentially a lookup from a quite close cache so it is not a devist= ating lookup, but it is done for every mark.

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

the solution 2 is better because you do not need a spec= ial mark funciton on the prolog variables, so I will try to implement a mod= ded 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 base= d prolog binding handling as well, I think that it is possible, but for thi= s to work we really need the same features from
=C2=A0bdw-gc.

Cheers
Stefan



--047d7b5d472cc2ff8d04f83c5e88--