[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

postpone discussion.

From: Stefan Israelsson Tampe
Subject: postpone discussion.
Date: Sun, 15 Aug 2010 15:26:30 +0200
User-agent: 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
potential value.

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.

so ...
(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
in place.

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]