[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Stefan Israelsson Tampe
Sun, 15 Aug 2010 15:26:30 +0200
KMail/1.13.5 (Linux/2.6.34-12-desktop; KDE/4.4.4; x86_64; ; )
I just want to mention that I really wan't input from more people. Therefore
I highlighted the postpone facility I made on Advogato to see if I can get
any reactions. I've tried on the #prolog list as well and got some clues from
them. But as far as I understand the postpone facility is right now quite
unique for the unify-guile repo.
The postpone facility is now considerably more firm in it's grounds. And I've
just checked in code so that now we have.
1. recursive postpone frames
2. customizable searches of newframes.
So just to see those in action, consider making a chess solver (again heh)
Assume that we have a function potential : State -> Number, And state is some
datastructure that are builed during the game. State may be large and we want
to tree compress that structure. Also we would like to dive deeply in
strategically interesting paths.
Now, we introduce a token flow onto the tree. The difference now is that
postpone has an token argument, e.g. and we have something like
my_postpone :- potential(X),
we here call potential and put that into X (ouch, my functional liver is
in delerium) and then call postpone with an argument.
This means that the end of the branch will start with a token state of the
There is a scheme function gp-unwind-token that the c-code hooks into at a
branch while unwinding. it is a function f : X,X -> X, X is the token space.
e.g. the result of that function is a new token representing the combined tree
for our case we would like to know the maximum token value in order to
understand if it's worth diving down into the branch later on.
(define (gp-unwind-token Br1 Br2) (max Br1 Br2))
Other choises is Min , expanding intervalls, and a plain cons if the initial
token is a symbol (hence having a set of symbols you can find the redos
associated with them)
Now, the current search function (to execute the redos) has the forms
search(start) -> ((id . tok1) . (id . tok2)) - at branch
search(start) -> lambda - at leaf
search(start) -> EOL - at end
we conclude from the initial token a Maxum value of V, then we can choose
to execute all tokens in the intervall [V,0.9V] in a new postpone frame
that never executes postpones at a lower level of 0.9V. And as we see from
the result from a search at a branch we can see if there is potential
tokens in the branch that match the search criteria and go there if present.
When there are no
more postpones in a frame, the rest of the postpones should hooke onto the
previous frame and continues as before with the previous frame. Cool right!
Now, recursive postpone frames is implemented. I have the code set up for a
token version of the search. After that I need to adjust the code slightly
to move up the leafs with f < 0.9V and then we should have this functionality
Probably for some interesting applications there will be a hughe demand on
memory. And Keeping the redo tree slim can have a great cost benefit. I
believe it is possible to save like 4x in space. And certaily 2x if guile was
on a 32bit. Now it might be interesting to have guile in 64bit, but let guile
sit on a 32 bit adress subspace. And only let the redo tree take advantage of
adressing more then 32bits. This would logically save 2x of memory space. So
it possible to accomplish this?
Hope this was stimulating.
- postpone discussion.,
Stefan Israelsson Tampe <=