stack closures for guile-log

stack closures for guile-log

[Stefan Israelsson Tampe]

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

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

retry:
SCM spp = sp
nargs = f(&spp,nargs,clodure_data);
sp = spp;
if(nargs < 0)
  A RETURN VALUE IS ON THE STACK
else
  A NEW FUNCTION IS ON THE STACK
  if(C_STACK_VERSION)
    goto retry:
  else
    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
clambda

  https://gitorious.org/clambda

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
Stefan

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

Re: stack closures for guile-log

[Andy Wingo]

On Tue 08 May 2012 21:16, Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:

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

Have you seen dynstack.[ch] on master?

> 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

I wonder, can you implement these too using something like the dynstack?

Andy
-- 
http://wingolog.org/

Re: stack closures for guile-log

[Stefan Israelsson Tampe]

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

Hi,

Yes, I think that if one go for capturing the stack via copying frames then
that's the way
to go. This makes rewinding and unwinding fast. on the other hand,
currently in guile-log
we use very small linked frames so that essentially all the stored
information is lying in the
heap compressed to a tree and is therefore superior memory wise, because of
the compression and because the GC get better oppertunities to reclaim
memory.

However I need to find more bench mark more in order to understand this
better.

I also must add hooks to handle a satck with stored coses. They serve as a
derefernce and identity objects for the closures which will be reference
throughout the heap. I cannot move
the conses but I can release the references to them and allocate new conses
in essence
move a cons from the stack to the heap. This is quite neat but do decrease
the possibilities of reclaiming memory in some cases so conses on the stack
will be an expert option but is needed to get the last 2x - 3x speedup down
to what compiled prolog can do.

The bulk of the closures stack is quite simple in it's functioning and
there I think it's
a bit over kill to use a dynstack.

Thanks for the info and Cheers!


On Tue, May 15, 2012 at 10:37 PM, Andy Wingo <wingo@pobox.com> wrote:

> On Tue 08 May 2012 21:16, Stefan Israelsson Tampe <stefan.itampe@gmail.com>
> writes:
>
> > I have three stacks
> > 1. a control stack that stores undo information scheme hooks aka
> > dynamic-wind and stack references to the other stacks.
>
> Have you seen dynstack.[ch] on master?
>
> > 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
>
> I wonder, can you implement these too using something like the dynstack?
>
> Andy
> --
> http://wingolog.org/
>

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