ideas for guile prolog

ideas for guile prolog

[Stefan Israelsson Tampe]

Hi,

I have been walking alot outside and thinking.

The question is what can be special with hammering prolog
into scheme. And one thing come to my mind

Continuations

Let's think about continuations. It's all about storing the state associated
with a call so that we can replay it's evaluation. What come to my 
mind then is that it would be nice to do a soft Cut e.g. prolong a branch
for later execution - if resources are available. I find it a very tempting 
tool to have. 

The special thing with this situation is that you may fill up your entire Ram 
with continuations so it would be nice to compact them tree wise and also 
facilitate reasonable fast execution deducing the state before execution of a 
closure. You essentially build a redo tree.

All this is now done and the following trivial example,
-------------------------------
prun() :- L = [[[5],2],1,[3,4]],
          postpone_frame,
          X is 0,
          pk(X),
          f(L,X).

f([H|L],N) :- !, postpone,
              N is N + 1,
              g(H,L,N).
f(H,N)     :- pk([H,N]), fail.
     
g(H,L,N)       :- f(H,N).
g(_,[H|L],N)   :- g(H,L,N).
g(_,[],_)      :- fail.
----------------------------------,

executes to 

   (1 1),(2 2),(3 2),(4 2),(5 3)

in my testbed so I got the basic code in shape.

To explain,
So a postpone_frame will try to collect postponed branches 
in a redo tree. If the code does not sucess in some other branch 
it will start to redo all the batched postponed branches 
one by one and again collect postpones. the  "!, postpone" ideom will 
store a closure representing a continuation as a leaf in the redo tree and 
then fail.

There are some tools to develop in order to make all this general enough to be 
useful. What comes to my mind is
1. Recursive postpone_frames
2. Branch selection framework currently first in first out
3. postpone on stack size  - general approach for trying to find a small 
                             solution before more complex one - e.g. beautiful
                             is better.
4. Ability to trim the redo tree, e.g. some way to cut the redo tree

This is not useful for true continuations. For that you would like to label 
branches in the prolog variable redo-tree with a tree and take the 
branch that contains a continuation token in it's label structure 
(not as expensive that one would think). and of cause make sure that all 
the c-code play nicely in forming the continuations. This would allow for 
cool things like having a prolog system setting up a set of continuations 
that can be played with, generate new continuations etc.

So that is my plan.

Any thoughts?


Cheers
Stefan

Re: ideas for guile prolog

[Andy Wingo]

Hi Stefan,

On Wed 11 Aug 2010 14:35, Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:

> The special thing with this situation is that you may fill up your entire Ram 
> with continuations so it would be nice to compact them tree wise and also 
> facilitate reasonable fast execution deducing the state before execution of a 
> closure. You essentially build a redo tree.

Some Schemes put stack frames on the heap, so that continuations that
"overlap" share state. Guile doesn't do this, but perhaps you could
simulate it by capturing continuations, and storing the stack of
continuations in a variable, or something. When continuations are
captured you could push on a new prompt, and then capturing a subsequent
continuation just captures the continuation up to the prompt.

You can simulate delimited call/cc with prompt/abort, except for
dynamic-wind effects (because aborting unwinds the stack). Guile 2.2
will have a properly delimited call/cc, preserving the dynamic state.

> This would allow for cool things like having a prolog system setting
> up a set of continuations that can be played with, generate new
> continuations etc.
>
> Any thoughts?

Sounds like fun :) Standard disclaimer that this wouldn't be ready for
Guile any time soon, but do have fun :)

Andy
-- 
http://wingolog.org/