[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
ideas for guile prolog
From: |
Stefan Israelsson Tampe |
Subject: |
ideas for guile prolog |
Date: |
Wed, 11 Aug 2010 23:35:56 +0200 |
User-agent: |
KMail/1.13.5 (Linux/2.6.34-12-desktop; KDE/4.4.4; x86_64; ; ) |
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
- ideas for guile prolog,
Stefan Israelsson Tampe <=