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,gmane.lisp.guile.user Subject: guile log musings Date: Tue, 9 Sep 2014 22:27:43 +0200 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a113336108148ff0502a7c444 X-Trace: ger.gmane.org 1410294487 18459 80.91.229.3 (9 Sep 2014 20:28:07 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 9 Sep 2014 20:28:07 +0000 (UTC) To: guile-devel , "guile-user@gnu.org" Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Sep 09 22:28:02 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 1XRS1A-0002gD-Of for guile-devel@m.gmane.org; Tue, 09 Sep 2014 22:28:01 +0200 Original-Received: from localhost ([::1]:51778 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRS1A-0002gi-Br for guile-devel@m.gmane.org; Tue, 09 Sep 2014 16:28:00 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56838) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRS12-0002de-U6 for guile-devel@gnu.org; Tue, 09 Sep 2014 16:27:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XRS10-0005sf-T7 for guile-devel@gnu.org; Tue, 09 Sep 2014 16:27:52 -0400 Original-Received: from mail-pa0-x233.google.com ([2607:f8b0:400e:c03::233]:61001) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XRS0u-0005px-Q3; Tue, 09 Sep 2014 16:27:45 -0400 Original-Received: by mail-pa0-f51.google.com with SMTP id kx10so6124793pab.10 for ; Tue, 09 Sep 2014 13:27:43 -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=e0uTNzuz6ej/Pq9DFgBrb33pnIhso8o7mLRLiWTYLac=; b=ifPvy7/5rX2G/pI7KAcDRuY2W4kShnPZm0QFiZtC7F5/w/hJgJSEAnMAbig3K3MkFf 8RU3SeTanHct46yIhmiUmdD08J0rf7S7crqEnGZzXIB4NA/Q3gGr89cI0tma87uDJ2ng U1epY5weVrH819l0xlGsf3ZnrXo1/Ss2NSoAcjZgAUwlINUx2fhh4Xh0Tam7KbeCmPkI Bs2MZPzpd0T6WKkfDtc8Ath1rLxK+yKBz4oYMSWAb3O3k3v7MDzTm2XSZ1E2A/fudgO5 40NQtlgafFJns1OiwAXgYNrPt2Kexjif8TT8KEoLRZ85duIhMwg2wxUSiqlIV0xkr5Vs QpMg== X-Received: by 10.66.141.39 with SMTP id rl7mr61096113pab.8.1410294463152; Tue, 09 Sep 2014 13:27:43 -0700 (PDT) Original-Received: by 10.70.95.33 with HTTP; Tue, 9 Sep 2014 13:27:43 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c03::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:17432 gmane.lisp.guile.user:11491 Archived-At: --001a113336108148ff0502a7c444 Content-Type: text/plain; charset=UTF-8 About guile log Guile log is a logic programming environment that implements kanren and prolog. It do sport features that are outstanding. It can basically remmeber effectively a state in an intelligent way and resore it at will. You have all the features you find in scheme like delimeted continuations continuations catch throw closures vhashes hygiene etc. what is lacking is some features you can find in other prologs and especially the prolog engine is a bit slow. With this you can merge programs written in prolog (it is an iso-prolog) with programs in kanren and intermingle those at your will. To learn more head down to the manual at http://c-lambda.se/guile-log/index.html#Top Guile log development have moved slowly forward. The background is that in #prolog there was suggestions to improve the gc capability of prolog engines in order to reclaim prolog variables and stack frames that are not reachable and hence garbage and in respect to this compact the stacks. I entered the quest and quite quickly managed to set up a system by modifying the bdw-gc sources to demonstrate the capabilities. But during more serious stress testing spurious errors would appear and something bad was still in the apple. Now the issue was really difficult to debug and all my tracing revealed that everything worked ok. But the giant test cases still showed bad errors. I then poundered the code numerous of times back and fourth for three months time hoping to find a way to get an isolated test case or some obvious bug. But tough luck, it did not resolve. I did read the bdw gc sources a little and should perhaps have asked for help. But I was hammering on this so seldom so that this never happened. Then on a whim I changed the code strategy a little and magically all test cases just passed. This is by far the toughest thing I coded. It is not good that I know for certain why it worked, just that it came by a hunch of how the bdw-gc sources worked. So what worked? in gc_pmark.h in bdw sources this is needed { \ struct obj_kind * ok = &GC_obj_kinds[hhdr -> hb_obj_kind]; \ if(advp && ok->ok_touch) \ { \ if(!(*((word *)base) & ok->ok_touch)) \ { \ *((word *)base) |= ok->ok_touch; \ SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ, label); \ /*printf("(%p) marked!\n",(word *)base);*/ \ } \ else \ { \ SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ, exit_label); \ } \ } \ else \ { \ SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ, exit_label); \ } \ } \ label: ... code that pushes the object for mark handling of it's internals ... advp is true in ordinary gc of an object and else in case of a variable on the prolog stack it is false. Basically this will hava a bit on the prolog variable that is cleared when on mark a variable on the stack but if it is marked through other references it will be set. This way we can track which variables have been referencede in the custom sweep pass. Then in the custom variable mark we have SCM x = SCM_CELL_OBJECT_1 (cell); if(GP_GC_ISMARKED(SCM_UNPACK(SCM_CELL_OBJECT_0 (cell)))); { mark_stack_ptr = GC_MARK_AND_PUSH (SCM2PTR (x), mark_stack_ptr, mark_stack_limit, NULL); } That is the value is pushed if the variable has been referenced else it will do nothing. The trick was that the step in the mark variable custom function was situated in the gc_pmarjk.h code and it didn't work, by pushing that logic as explained above things started to work. One can possible clean this code further. But for now it I will package the solution so that this gc feature will be selectable if people is willing to run a modded bdw-gc 7.2. Also if we could ask if a variable have been marked through the gc api we could have solved it entirely outside of bdw-gc. But as it is today (and to get a little speed) the modding is nessesary. ----------------------------------------------------------------------------------------- The next step will be to clean this up and document the feature pointing to my gc repo copy inform the bdw gc folks and then continue with .... prolog coprocedures / attributed value Another feature that was asked for on the ##prolog list was to have swi-prologs, http://www.swi-prolog.org/pldoc/man?section=extvar I will code this in, but with the twist that I want more hygiene and less magic then in the swi prolog semantics. A third feature is to implement memoization, for this I want an effective implementation of comparing prolog data structures. We want to check if the arguments matches a database of old arguments and in that case reuse the old value. The twist is to compare structures that contains prolog variables. I plan to make two or three hashes out of the data structure by cutting large datastructures and just index on a few arguments. I will try to push this algorithm into C (ugly me) and play with bit twidling just for fun to achieve performance in hash creation time. The task is to spent just enough time creating hashes to make them complex enough to capture most data structures but speedy enough to not bug normal prolog/kanren/guile-log code. As wingo and other beards says ... Happy hacking --001a113336108148ff0502a7c444 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
About guile log
Guile log is a logic progra= mming environment that implements kanren and prolog. It do sport features t= hat are outstanding. It can basically remmeber effectively a state in an in= telligent way and resore it at will. You have all the features you find in = scheme like delimeted continuations continuations catch throw closures vhas= hes hygiene etc. what is lacking is some features you can find in other pro= logs and especially the prolog engine is a bit slow. With this you can merg= e programs written in prolog (it is an iso-prolog) with programs in kanren = and intermingle those at your will. To learn more head down to the manual a= t=C2=A0http://c-lam= bda.se/guile-log/index.html#Top


Guil= e log development have moved slowly forward. The background is that in #pro= log there was suggestions to improve the gc capability of prolog engines in= order to reclaim prolog variables and stack frames that are not reachable = and hence garbage and in respect to this compact the stacks. I entered the = quest and quite quickly managed to set up a system by modifying the bdw-gc = sources to demonstrate the capabilities. But during more serious stress tes= ting spurious errors would appear and something bad was still in the apple.= Now the issue was really difficult to debug and all my tracing revealed th= at everything worked ok. But the giant test cases still showed bad errors. = I then poundered the code numerous of times back and fourth for three month= s time hoping to find a way to get an isolated test case or some obvious bu= g. But tough luck, it did not resolve. I did read the bdw gc sources a litt= le and should perhaps have asked for help. But I was hammering on this so s= eldom so that this never happened. Then on a whim I changed the code strate= gy a little and magically all test cases just passed. This is by far the to= ughest thing I coded. It is not good that I know for certain why it worked,= just that it came by a hunch of how the bdw-gc sources worked.

So what worked? in gc_pmark.h in bdw sources this is needed
=C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 struct = obj_kind * ok =3D &GC_obj_kinds[hhdr -> hb_obj_kind]; =C2=A0 =C2=A0 = =C2=A0 =C2=A0\
=C2=A0 =C2=A0 =C2=A0 if(advp && ok->ok_= touch) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0\
=C2=A0 =C2=A0 =C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 if(!(*((word *)base) & ok->ok_touch)) =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 *((word *)base) |=3D ok->ok_touch; =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0\<= /div>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 SET_MARK_BIT_EXI= T_IF_SET(hhdr, gran_displ, label); =C2=A0 =C2=A0 =C2=A0 =C2=A0\
<= span class=3D"" style=3D"white-space:pre"> =C2=A0 =C2=A0 =C2=A0/*pr= intf("(%p) marked!\n",(word *)base);*/ \
=C2=A0 =C2=A0} =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 else =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0\
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 SET_MAR= K_BIT_EXIT_IF_SET(hhdr, gran_displ, exit_label); =C2=A0 \
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 } =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 } =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 = =C2=A0 =C2=A0 else =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0\
=C2=A0 =C2=A0 =C2=A0 =C2=A0 { =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ, exit_label)= ; =C2=A0 =C2=A0 =C2=A0 \
=C2=A0 =C2=A0 =C2=A0 =C2=A0 } =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \
=C2= =A0 =C2=A0 } =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 \
label:
... code that pushe= s the object for mark handling of it's internals =C2=A0...
advp is true in ordinary gc of an object and else in case of a= variable on the prolog stack it is false. Basically this will hava a bit o= n the prolog variable that is cleared when on mark a variable on the stack = but if it is marked through other references it will be set. This way we ca= n track which variables have been referencede in the custom sweep pass.

Then in the custom variable mark we have
SCM x =3D SCM_CELL_OBJECT_1 (cell);
=C2=A0 =C2=A0 =C2=A0 if(GP= _GC_ISMARKED(SCM_UNPACK(SCM_CELL_OBJECT_0 (cell))));
=C2=A0 =C2= =A0 =C2=A0 {
m= ark_stack_ptr =3D GC_MARK_AND_PUSH (SCM2PTR (x),
=C2=A0 mark_stack_ptr,
=C2=A0 mark_stack_lim= it, NULL); =C2=A0
=C2=A0 =C2=A0 =C2=A0 }

That is the value is pushed if the variable has been referenced else= it will do nothing. The trick was that the step in the mark variable custo= m function was situated in the gc_pmarjk.h code and it didn't work, by = pushing that logic as explained above things started to work.=C2=A0

One can possible clean this code further. But for now it = I will package the solution so that this gc feature will be selectable if p= eople is willing to run a modded bdw-gc 7.2. Also if we could ask if a vari= able have been marked through the gc api we could have solved it entirely o= utside of bdw-gc. But as it is today (and to get a little speed) the moddin= g is nessesary.
-------------------------------------------------= ----------------------------------------

The next = step will be to clean this up and document the feature pointing to my gc re= po copy inform the bdw gc folks and then continue with ....

<= /div>
prolog coprocedures / attributed value

A= nother feature that was asked for on the ##prolog list was to have swi-prol= ogs,=C2=A0= http://www.swi-prolog.org/pldoc/man?section=3Dextvar

I will code this in, but with the twist that I want more hygiene and= less magic then in the swi prolog semantics.

A th= ird feature is to implement memoization, for this I want an effective imple= mentation of comparing prolog data structures. We want to check if the argu= ments matches a database of old arguments and in that case reuse the old va= lue. The twist is to compare structures that contains prolog variables. I p= lan to make two or three hashes out of the data structure by cutting large = datastructures and just index on a few arguments. I will try to push this a= lgorithm into C (ugly me) and play with bit twidling just for fun to achiev= e performance in hash creation time. The task is to spent just enough time = creating hashes to make them complex enough to capture most data structures= but speedy enough to not bug normal prolog/kanren/guile-log code.

As wingo and other beards says ...
Happy hacking=

--001a113336108148ff0502a7c444--