Kanren and guile-log

Kanren and guile-log

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 2646 bytes --]

Hi,

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
program.

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.

Regards
Stefan

[-- Attachment #2: Type: text/html, Size: 2779 bytes --]

Re: Kanren and guile-log

[Andy Wingo]

On Fri 12 Aug 2011 19:56, Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:

> 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.

Thanks, this was an interesting read.

Andy
-- 
http://wingolog.org/