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,gmane.lisp.guile.user Subject: dynamic function and functional programming Date: Tue, 15 Oct 2013 23:25:38 +0200 Message-ID: <4752701.fNPdE7pSre@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7Bit X-Trace: ger.gmane.org 1381872365 15712 80.91.229.3 (15 Oct 2013 21:26:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 15 Oct 2013 21:26:05 +0000 (UTC) To: guile-devel@gnu.org, guile-user@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Oct 15 23:26:10 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VWC81-0006Uy-77 for guile-devel@m.gmane.org; Tue, 15 Oct 2013 23:26:09 +0200 Original-Received: from localhost ([::1]:43818 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VWC80-0006ku-QW for guile-devel@m.gmane.org; Tue, 15 Oct 2013 17:26:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51035) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VWC7n-0006kn-V9 for guile-devel@gnu.org; Tue, 15 Oct 2013 17:26:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VWC7f-0005bs-Bb for guile-devel@gnu.org; Tue, 15 Oct 2013 17:25:55 -0400 Original-Received: from mail-lb0-x22f.google.com ([2a00:1450:4010:c04::22f]:47485) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VWC7e-0005Xu-TX; Tue, 15 Oct 2013 17:25:47 -0400 Original-Received: by mail-lb0-f175.google.com with SMTP id y6so15179lbh.6 for ; Tue, 15 Oct 2013 14:25:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:date:message-id:user-agent:mime-version :content-transfer-encoding:content-type; bh=Pk0qlvlBY7EST2QNOklENsSGTCaB+MkI3K2Do1Lcg90=; b=wghidq07DqnIRrGvF4QDZszRIk9XeAPEQ/BeWZu0DR2z1HqrlN0TisU+nqkSxGuKhP RCu+B3ylfUsAQgkkgN/Io1dAIbW36PsyUHiUjMnq3TtAsD5MjWqy85US5mxvJ0T5Mid+ zWEPTyL+jJYVnZqF9h6m2aX0zaglfK64jnRASM7V1rR75nb/Lko3/YeI8rUQO66wDiOe be3YET8FoxwGZbs8Znaer8GJ4z/7UB1QkQZ3+5iJth+Cm51SDp/sP+ftPOOfJ619YGzA Al8+a2ASx1l+nuriAfXaVNIi+k7JPeK/hmPxuXL6WEgzrHvXcAAddfJzu+5n8OSYvrCH Vd9Q== X-Received: by 10.112.29.103 with SMTP id j7mr41312lbh.92.1381872345188; Tue, 15 Oct 2013 14:25:45 -0700 (PDT) Original-Received: from warperdoze.localnet (1-1-1-39a.veo.vs.bostream.se. [82.182.254.46]) by mx.google.com with ESMTPSA id n15sm66357007laa.2.1969.12.31.16.00.00 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 15 Oct 2013 14:25:44 -0700 (PDT) User-Agent: KMail/4.9.5 (Linux/3.5.0-30-generic; KDE/4.9.5; x86_64; ; ) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c04::22f X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16679 gmane.lisp.guile.user:10847 Archived-At: Hi all, Dynamic functions in prolog is a missnomer. At the swi prolog's site they complain about the difficulty to use them, hard bugs with memory leaks etc. And to use them in guile-log, where techniques to move from different dynamic computational states, would lead to even more serious and hard to track down bugs. But it's possible to fix dynamic functions. The solution is functional datastructures. First of all, a dynamic function can be seen as the art of storing pairs of patterns including variables (p1, p2) where p1 is used to match an argument and p2 is a sexp representing code. The idea then is to store these pairs in a list and then at execution with an argument a try each p1 for a match with a, and if so evaluate p2 with nessesary bouded variables. At any failure backtracking will result. Now this list can be added to the top and to the bottom and also can be cleared at all sited where a pattern b matchas a p1. Also, in prolog, dynamic funcitons do not backtrack e.g. one need to make sure to clear the list at times. Also these tables can be very large with a few matchers so that indexing is a valuable tool for scaling. Enter guile. Why not use a functional datastructure for the state. E.g. use ideoms like (with-dynamic (f) code ...) in the code And uppon backtracking f will be restored to the state when backtracking over the dynamic functions. And inside code ... the state of f will remain as in ordinary prolog. It's still a bit tricky to combine postpone etc. with this form but essentially by adding a with-dynamic ideom under the hood to e.g. the interleaving constructs and postpone one can get something that are easy to use, but with a pennalty and extra computational complexity. How to proceed e.g. letting the user have more control, but allow for semantic buggs is unclear. Anyhow we have a full functional indexer and containers, using vhash,vlist etc and plain old theory about how to index, it's cool that it is using bitmaps for moderate sized dynamic variables. For bitmaps of size 1600 with pairs (1..40 1..40) guile-log could lookup the matching set (_ 4), 150.000 times in 1 second. This is kind of cool. Larger sizes of this bitmap will start to decrease the througput. At 1600 it's about 10%. Hence smaller bitmaps will not make much improvement. It is also interesting to note that the speed we get by doing this should on par with C code that scans the list for matches. It would be an interesting exercize to beef up this code by pushing the logic to C code. I almost finished with porting vhashes and vlists to C code and will start to see how much can be gained by using this. Indexes for larger tables then 1000 means that bitmaps, in case they are sparse but of moderate size, should be transformed to hash-sets (smaller ones just need a simple assoc) to represent sets and the value of the hash pair should be the index. Then one can perform set operations on the hashes as we do with bitmaps. This will lead to a lot trickier algorithms e.g. find out how to perform union, difference and intersection effectively, but in essence heuristics for this should be available. I actually suspect that functional datastructures is a boon to do this because we can reuse already setuped datastructures, e.g. (union large-set small-set) can be taken by use large-set as a base and add the small set without reconstructing a new hashlist. Also in a (intersection large-set moderate-set) we can take the moderate set and delete all the elements that are not in large-set, which might be few and hence spare the construction of an entirely new set. So the support for dynamic functions in guile would soon be quite ok with unique features, it seams, compared to many other prolog system out there. Have fun! /Stefan