[Top][All Lists]

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

Kanren and guile-log

From: Stefan Israelsson Tampe
Subject: Kanren and guile-log
Date: Fri, 12 Aug 2011 19:56:00 +0200


I have read the source code for kanren and want to put the system in relation to the work I have been doing which I will
call guile-log.

So the basic difference between kanren and guile-log are that kanren is general and guile log is close to two orders
of magnitude faster on either the VM or a future compiled version.

One should note that two orders of magnitude is quite a lot and motivates the existance of guile-log. On the other hand
the generality of kanren is nice to have at hand and can lead to faster development time to reach an advanced logic

The basic reason to all this are that kanren, in a functional style, have a variable that manages dynamic variable bindings in a linked
list. This structure is passed as the first argument to relation functions. So in order to interpret the value of a unifying prolog variable
this list is scanned. New binding info is then consed ontop of the list and generally many states variables can be alive at a moment
where they composes of a tree representing all collected state.

All this means that in kanren it is very simple to change classic algorithms to do breath searches or similar devices. Now two orders of
magnitude may seam to be very slow. But there are examples where a breath first algorithm can dramatically improve searches.
Now it's possible to do these kind of searches in guile-log as well - but that means that a lot of code needs to be written and debugged.

In guile-log though, there is a possibility to postpone searches and redo a selection of them in order to cut down the search space. E.g. at a branch one can calculate a performance index, store that and a continuation of the search. Then the redo tree is stored and the code will search for the most potent indices and continue them. This algorithm is quite simple to implement in kanren as well, but the guile log version is much faster and complicated under the hood but simple to use.

Due to the very nice setup of kanren it is possible to zip two predicates. E.g. backtrack both predicates in parallell. This is a generalization of zipping two sequences together but it beats me what more uses this has apart from simply zipping sequences.
Anyway it's very complicated to implement this in guile-log.

So why are guile-log faster then kanren and more complicated. It all boils down to the fact that and guile log are array oriented and kanren is list oriented. Also looking up a value is faster in guile-log because that is a simply a couple of pointer lookups. Also kanren
allocates from the heap and guile-log allocates from a stack.

At least this is my 2c observations.


reply via email to

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