[Top][All Lists]

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

guile log musings

From: Stefan Israelsson Tampe
Subject: guile log musings
Date: Tue, 9 Sep 2014 22:27:43 +0200

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

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);       \
        }                                                               \
    }                                                                   \
... 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);
mark_stack_ptr = GC_MARK_AND_PUSH (SCM2PTR (x),
  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,

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

reply via email to

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