[Top][All Lists]

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

stack closures for guile-log

From: Stefan Israelsson Tampe
Subject: stack closures for guile-log
Date: Tue, 8 May 2012 21:16:19 +0200

hi all,

I have now implemented stack closures that can be pushed out to the heap
if we want to store a state. This is how it works.

I have three stacks
1. a control stack that stores undo information scheme hooks aka
dynamic-wind and stack references to the other stacks.

2. stack from which data is allocated from like the bulk of a closure
and special pairs

3. a cons stack, e.g. an array of allocated conses

So to allocate a closure we allocate a cons c and a sequence of bytes transformed
to a vector let the vector be located at the cdr and store a identifying SCM object
that identifies that the cons represents a closure. and the cons is returned as
the closure object with the vector filled with the closure data like C function pointer
and associated closure data. Now If we mark a state as stored we simple mark
the stacks for storage and when unwinding and seeing this mark the closure data is copied
over to a heap allocated vector and then modify the same cons cell cdr position with it
and then remove the cons from the cons stack and allocate a new cons to that position.

I'm about to make this robust but I can run the einstein case quite fine right now.

That is in managing these closures. The c function signature for these closures is designed as

int f(SCM **sp, int nargs, SCM *closure_data)

So for the VM code we do not need any extra instructions, just modify the call logic
to add a check for a cons with a car object that matched the identity for this kind of
closure. it will also unpack a reference to the closure data and call the c function f

SCM spp = sp
nargs = f(&spp,nargs,clodure_data);
sp = spp;
if(nargs < 0)
    goto retry:
    goto vm_tail_call or vm_call
E.g. we have constructed a trampoline for the c code to use. The logic code in kanren and guile-log is
centered around tail calls and this tool does not infere much with the rest of guile.

Now this is a bit dangerous to use but I have compiled a macro package in scheme called

And with this one can write essentially
(:define: (memb x l)
  (:match: (l)
    ((x . _)  (:cc:))
    ((_ . ,l) (:call: member x l))))

(:define: (righ x y l)
  (:match: (l)
    ((x y .  _) (:cc:))
    ((_   . ,l) (:call: right x y l))))

(:define: (nextto item1 item2 rest)
  (:or: (:call: right item1 item2 rest)
        (:call: right item2 item1 rest)))

compile it to C, write a little hook code that can be automized and
then the einstein case takes 25ms compared with compiled gprolog
that takes 12ms on my machine.
I did  test how far I could take this code and with some reworking it's possible
to run the code as fast as 13.5ms which was about 7.5 times faster when using an
assq which took around 100ms to run.

So there is some overhead due to a more complex mechanism then in ordinary prolog
but it's pretty close in the what it can be capable of.

Have fun

reply via email to

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