guile-devel
[Top][All Lists]
Advanced

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

dynamic function and functional programming


From: Stefan Israelsson Tampe
Subject: dynamic function and functional programming
Date: Tue, 15 Oct 2013 23:25:38 +0200
User-agent: KMail/4.9.5 (Linux/3.5.0-30-generic; KDE/4.9.5; x86_64; ; )

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




reply via email to

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