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