From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: postpone discussion. Date: Sun, 15 Aug 2010 15:26:30 +0200 Message-ID: <201008151526.30908.stefan.tampe@spray.se> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1281881114 6626 80.91.229.12 (15 Aug 2010 14:05:14 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 15 Aug 2010 14:05:14 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Aug 15 16:05:12 2010 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Okdpo-00061R-5y for guile-devel@m.gmane.org; Sun, 15 Aug 2010 16:05:12 +0200 Original-Received: from localhost ([127.0.0.1]:43739 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Okdpn-0008PT-H8 for guile-devel@m.gmane.org; Sun, 15 Aug 2010 10:05:11 -0400 Original-Received: from [140.186.70.92] (port=32853 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Okdpe-0008PO-RL for guile-devel@gnu.org; Sun, 15 Aug 2010 10:05:03 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Okdpd-0004jr-Gu for guile-devel@gnu.org; Sun, 15 Aug 2010 10:05:02 -0400 Original-Received: from spsmtp02oc.mail2world.com ([74.202.142.198]:2242) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Okdpd-0004j4-Au for guile-devel@gnu.org; Sun, 15 Aug 2010 10:05:01 -0400 Original-Received: from mail pickup service by spsmtp02oc.mail2world.com with Microsoft SMTPSVC; Sun, 15 Aug 2010 07:04:58 -0700 auth-sender: stefan.tampe@spray.se Original-Received: from 82.182.254.46 unverified ([82.182.254.46]) by spsmtp02oc.mail2world.com with Mail2World SMTP Server; Sun, 15 Aug 2010 07:04:57 -0700 User-Agent: KMail/1.13.5 (Linux/2.6.34-12-desktop; KDE/4.4.4; x86_64; ; ) X-OriginalArrivalTime: 15 Aug 2010 14:04:58.0222 (UTC) FILETIME=[D84840E0:01CB3C82] X-detected-operating-system: by eggs.gnu.org: Windows 2000 SP4, XP SP1+ X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:10765 Archived-At: Hi, 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 complex 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), postpone(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 is it possible to accomplish this? Hope this was stimulating. Regards Stefan