guile log musings

guile log musings

[Stefan Israelsson Tampe]

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

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

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