Inclusion of guile-log II

Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

Sorry I pushed the wrong key, I'll try again (sorry for spaming)



The guile-log code is very dependent on guile! It's based on a c-file which
uses
guile C interface in order to get speedy and featureful at the same time.
So basically I have no hope that this codebase could be independent from
guile.

If you want independence use kanren. For guile this approach is 10x faster
then kanren
and 10x slower that a compiled prolog. Previously I thought that kanren has
a more functional
fundament and can express amazing things. But i'm now inclined that
guile-log has a feature
that are very cool and I will try to explain this feature for the fun of it.

The background comes from the study of interleaving constructs in kanren. I
tried to match
those features and still having call/cc like features in order to be ahve
something really cool
to work with e.g. the state has to be stored in order to be able to restart.

So let's start with kanrens all-interleave (<and-i> in guile-log, alli in
reasoned schemer). Consider a goal like

(all (all-interleave P1 P2) P3)

the semantic is tha P1 and P2 shall both be true! at the same time as P3.
Now it can happen that P2 has infiinitely many solutions and for none of
these P3 has a solutions. If we would have an ordinary all in stead of
all-interleave then the solver would get stuck and never return an answer.
with interleaving on the other hand we have in kanren,

 (solve 20 (x y) (all-interleave (any (== x 0) (== x 1) (== x 2))
(any (== y 0) (== y 1) (== y 2))))
$1 = (
((x.0 0) (y.0 0))
((x.0 1) (y.0 0))
((x.0 0) (y.0 1))
((x.0 2) (y.0 0))
((x.0 0) (y.0 2))
((x.0 1) (y.0 1))
((x.0 2) (y.0 1))
((x.0 1) (y.0 2))
((x.0 2) (y.0 2)))

As you can see, the goal dives down one layer at the time. usually this
means a search for a solution with low complexity before one with higher
complexity. But please read the reasoned schemer to better understand this
construct. To also note, the solver needs to store n states  at level n.
but the number of successes are of the order n*n which may many times mean
that computational time is the limiting reasource.

Anyhow trying to do this the naive version would look in guile-log
something like

(define (interleave p cc g1 gs)
  (let ((l '()) (r '()))
    (define fail
      (lambda ()
        (let loop ((ll l) (rr r))
          (if (null? ll)
              (if (null? rr)
                  (p)
                  (loop (reverse rr) '()))
              (let ((thunk (car ll)))
                (set! l (cdr ll))
                (set! r rr)
                (thunk))))))

    (define (mk-cont p)
      (let ((state (gp-store-state)))
        (lambda ()
          (gp-restore-wind state)
          (p))))

    (let loop ((p p) (g1 g1) (gs gs))
      (match gs
        ((g2)
         (g1 fail
             (lambda (p2)
               (set! r (cons (mk-cont p2) r))
               (g2 fail
                   (lambda (p3)
                     (set! r (cons (mk-cont p3) r))
                     (cc fail))))))
        ((g2 . gs)
         (g1 fail
             (lambda (p2)
               (set! r (cons (mk-cont p2) r))
               (loop p2 g2 gs))))))))

This has a clear syntax and can be understanded without to much work. (the
kanren version
in reasoned schemer is not too bad either) But the sorce code for kanren I
looked at is very difficult to follow and will be demanding for an outsider
to work with.

The semanticis to keep a state l,r that represent a que of restarts that
updates as we find new
states or consumes as we do a restart at a failure. Then we introduce a
failure object that deque the next restart.

The bad thing with this code is set!. we will set! a variable on the heap
and hence there is no easy elegant way to store a state and restore that
state later on. What we would like to have, of cause, is r and l to behave
as above but maintain the variables in such a way that we can restore the
state. One solution that is very elegant is to use dynwinds like features
for the separate prolog stack. And an implementation using this is under
100 lines of scheme. So now we can write,

(define (alli p cc g1 gs)
  (with-guarded-states guard-set! ((l '()) (r '()))
    (define fail
      (lambda ()
        (let loop ((ll l) (rr r))
          (if (null? ll)
              (if (null? rr)
                  (p)
                  (loop (reverse rr) '()))
              (let ((thunk (car ll)))
                (guard-set! (cdr ll) rr)
                (thunk))))))

    (define (mk-cont p)
      (let ((state (gp-store-state)))
        (lambda ()
          (gp-restore-wind state)
          (p))))

    (let loop ((p p) (g1 g1) (gs gs))
      (match gs
        ((g2)
         (g1 fail
             (lambda (p2)
               (guard-set! l (cons (mk-cont p2) r))
               (g2 fail
                   (lambda (p3)
                     (guard-set! l (cons (mk-cont p3) r))
                     (cc fail))))))
        ((g2 . gs)
         (g1 fail
             (lambda (p2)
               (guard-set! l (cons (mk-cont p2) r))
               (loop p2 g2 gs))))))))

In stead and be able to do

scheme@(guile-user)> (<run> 5 (x y) (<and-i> (<or> (<=> x 0)
                                                   (<=> x 1)
                                                   (<=> x 2))
                                             (<or> (<=> y 0)
                                                   (<=> y 1)
                                                   (<=> y 2))))
$2 = ((0 0) (1 0) (0 1) (2 0) (1 1))

scheme@(guile-user)> (define s (<state-ref>))

scheme@(guile-user)> (<take> 5)

$3 = ((0 2) (2 1) (1 2) (2 2))

scheme@(guile-user) [1]> (<state-set!> s)

scheme@(guile-user) [1]> (<take> 5)

$4 = ((0 2) (2 1) (1 2) (2 2))

I personally think that the newly introduced feature will make it much
simpler to
improve on guile-log user base then kanren or?, well you can add a similar
interface to
kanren. You just need to maintain a prolog stack in parallell with kanren
and hook it into the kanren framework. And you will have the birth of
guile-kanren. I will try to implement that later on, but I still need to
play with this tool a bit more.

Have fun!

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

Re: Inclusion of guile-log II

[Mark H Weaver]

Hi Stefan,

Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:
> The guile-log code is very dependent on guile! It's based on a c-file
> which uses
> guile C interface in order to get speedy and featureful at the same
> time. So basically I have no hope that this codebase could be
> independent from guile.

Several libraries for Guile (e.g. guile-gnome) include C code that uses
Guile's C interface, and this does not pose any difficulties for making
it an external package.  Can you please explain more clearly why
guile-log is impractical to package separately?

FWIW, I find guile-log to be very interesting work, but I also get the
impression that it is a somewhat experimental and unproven approach to
logic programming in Scheme.  Only time will tell whether it proves to
be a successful approach.

One of my concerns is the extensive use of mutable state in guile-log.
Recently I have been thinking about how best to support scalable
lock-free concurrency in Guile, so this question looms large in my mind:
How effectively will guile-log be able to make use of a potentially
large number of processor cores.  Do you have any thoughts on that?

It's unclear whether individual processors can be made much faster than
they are today.  Making efficient use of a large number of processors
will likely become increasingly important in the future.  In that
context, there is a significant advantage to avoiding mutation of shared
state, since that causes cache lines to bounce back and forth between
processors, which kills performance.

Kanren is written in a purely functional style, and this may well prove
to a significant performance advantage in the multi-core future, even
though it runs slower on a uniprocessor.

    Regards,
      Mark

Fwd: Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

I missed to send this to guile-devel, sorry!
---------- Forwarded message ----------
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
Date: Wed, Apr 4, 2012 at 5:36 PM
Subject: Re: Inclusion of guile-log II
To: Mark H Weaver <mhw@netris.org>


Mark I must give you right,

Actually contemplating it some more, consider having a large tree vith
variables in defined
in thread 1 that starts two subthread 2 and 3, How do one set those
variables burried in the tree? You would not like to treat the
datastructures uniquely. Here Kanren works really well and so well that I'm
contemplating to have both an assoc list and a stack and use the assoc for
just this case e.g. when going from datastructure in thread 1 to
datastructure in thread 2 or 3. And not only this, one of the drawback with
changing variable in thread 0 to for example set the variable to a list of (
tread.id . key) pairs is that the synchronsisation has pretty dramatic
effects on performance as you know. But I would just not dwell too much
into trying to optimize that synchronisation. Because what would be cool
though is to use an assoc-list as in kanren and when it grows to large
issue a batch synchronisation and bring out that whole assoc into modifying
the thread0 datastructure in one go. The amortized cost on each
synchronisation should than decrease by say a factor of 20  e.g. about 20ns
per op. with about 10 interations and the transfer cost should be small
compared to the overall lookup cost
that needed to be done in order to create a 20 element assoc What do you
think?

WDYT


On Wed, Apr 4, 2012 at 10:23 AM, Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> Hi Mark,
>
> Thanks for the reply!
>
>
> > Several libraries for Guile (e.g. guile-gnome) include C code that uses
> > Guile's C interface, and this does not pose any difficulties for making
> > an external package.  Can you please explain more clearly why
> > guile-log is impractical to package separately?
>
> Actually I have now strong feelings more that it would be cool to have
> logic programming abilities in guile from the startup and that I started
> all my guile involvenment suggesting to add that to guile. I'm actually
> pretty fine with maintaining a lib of it's own.
>
>
> > FWIW, I find guile-log to be very interesting work, but I also get the
> > impression that it is a somewhat experimental and unproven approach to
> > logic programming in Scheme.  Only time will tell whether it proves to
> > be a successful approach.
>
> I have actually used it quite a lot in examples but that's only me, I do
> find it stable enough
> to do good work in it. It's that I feel that I constantly find new cool
> things I would like to
> add to it and feel hey it's experimental cause it's only me using it.
>
>
> >One of my concerns is the extensive use of mutable state in guile-log.
> >Recently I have been thinking about how best to support scalable
> >lock-free concurrency in Guile, so this question looms large in my mind:
> >How effectively will guile-log be able to make use of a potentially
> >large number of processor cores.  Do you have any thoughts on that?
>
> For multicore you would like to support both traditional lock centered
> programming
> and lock free programming. For lock free you will for each variable that
> is seen by
> m threads be matched by m variables that points to the global one, if we
> assume that
> the global one does not change, then binding the variable in a thread will
> only relate to that
> thread. So to conceptually match kanrens datastructure multicore
> capability can be done.
> the main current problem though is that for each core you would like to
> maintain a local stack
> and currently this is a fixed sized stack. So before starting implementing
> multicore lock free
> programming to guile-log I would like to introduce resizable stacks which
> probably is a much more difficult programming task that later make the lock
> free threading.
>
> If on the other hand we would like to connect one thread local prolog
> variable with another tread local prolog variable (think a fluid that
> points to another fluid) we would probably want som synchronisation ideoms
> attached to them but that is also not difficult especially difficult and
> could be maintained beside the lock free versions, I guess that this is not
> inluded in kanren (I think that I would add these to guile-kanren though
> when thinking about it)
>
>
> > Kanren is written in a purely functional style, and this may well prove
> > to a significant performance advantage in the multi-core future, even
> > though it runs slower on a uniprocessor.
>
> Kanren is not going to be faster then prolog multicore versions or
> guile-log If I implement it
> correctly for most cases I've seen. But the functional way of kanren has
> use cases
> where it can really shine due to it's way of mainting the variable binding
> datastructure.
>
> One thing that can lead to a dramatic improvement is in memoizing states
> in backtracking
> so that when we try to evaluate a goal we look if we have had this state
> before and if so
> reuse that expensive deduction. Another use case is when the code uses
> interleaving constructs guile-log stack based approaches is inferior here
> now due to the fact that we
> need to unwind and restore the stack meaning that the stack need to grow
> back and forth
> and in the process recreate the variable bindings which is a bit clumsy.
> Here guile-log lacks
> the ability to do this but it's on my TODO list to have something usable
> here.
>
> Another reason is that sometimes the kanren ideom lead to elegant
> expressions of algorithms and sometimes guile-log win's, I'm trying to make
> that even by bringing over fetures from kanren to guile-log and vice verse
> so that in the end there would only need to be a performance question of
> when one or the other is used.
>
> /Stefan
>
>
> On Wed, Apr 4, 2012 at 2:05 AM, Mark H Weaver <mhw@netris.org> wrote:
>
>> Hi Stefan,
>>
>> Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:
>> > The guile-log code is very dependent on guile! It's based on a c-file
>> > which uses
>> > guile C interface in order to get speedy and featureful at the same
>> > time. So basically I have no hope that this codebase could be
>> > independent from guile.
>>
>> Several libraries for Guile (e.g. guile-gnome) include C code that uses
>> Guile's C interface, and this does not pose any difficulties for making
>> it an external package.  Can you please explain more clearly why
>> guile-log is impractical to package separately?
>>
>> FWIW, I find guile-log to be very interesting work, but I also get the
>> impression that it is a somewhat experimental and unproven approach to
>> logic programming in Scheme.  Only time will tell whether it proves to
>> be a successful approach.
>>
>> One of my concerns is the extensive use of mutable state in guile-log.
>> Recently I have been thinking about how best to support scalable
>> lock-free concurrency in Guile, so this question looms large in my mind:
>> How effectively will guile-log be able to make use of a potentially
>> large number of processor cores.  Do you have any thoughts on that?
>>
>> It's unclear whether individual processors can be made much faster than
>> they are today.  Making efficient use of a large number of processors
>> will likely become increasingly important in the future.  In that
>> context, there is a significant advantage to avoiding mutation of shared
>> state, since that causes cache lines to bounce back and forth between
>> processors, which kills performance.
>>
>> Kanren is written in a purely functional style, and this may well prove
>> to a significant performance advantage in the multi-core future, even
>> though it runs slower on a uniprocessor.
>>
>>    Regards,
>>      Mark
>>
>
>

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

Re: Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

On Wed, Apr 4, 2012 at 6:21 PM, Mark H Weaver <mhw@netris.org> wrote:

> Hi Stefan,
>
> Did you intend to send this as private email?  Wouldn't it be better to
> discuss this on the mailing list?
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:
> > Because what would be cool though is to use an
> > assoc-list as in kanren and when it grows to large issue a batch
> > synchronisation and bring out that whole assoc into modifying the
> > thread0 datastructure in one go.
>
> Another possibility is to simply replace the assoc-list with a more
> efficient purely-functional map structure.  Guile already has vhashes,
> but even better would be persistent Hash Array Mapped Tries (HAMT) as
> used in Clojure.  See Phil Bagwell's paper "Ideal Hash Trees" for the
> basic idea, and the persistent purely-functional variant used in Clojure
> simply copies the path from the new leaf to the root in the obvious way
> to add or delete without mutation.  I'd like to add a highly-optimized
> implementation of this to Guile soon.
>

I do think that this can be interesting to try out. Also the lookup could
be coded in C in order
to speed up kanren for guile.

/Stefan

>
>   Regards,
>     Mark
>

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

Fwd: Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

I having a bad day, forgetting to mail the list as well :-(

Anyway here is a missing bit in the conversation with mark!

---------- Forwarded message ----------
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
Date: Wed, Apr 4, 2012 at 10:23 AM
Subject: Re: Inclusion of guile-log II
To: Mark H Weaver <mhw@netris.org>


Hi Mark,

Thanks for the reply!


> Several libraries for Guile (e.g. guile-gnome) include C code that uses
> Guile's C interface, and this does not pose any difficulties for making
> an external package.  Can you please explain more clearly why
> guile-log is impractical to package separately?

Actually I have now strong feelings more that it would be cool to have
logic programming abilities in guile from the startup and that I started
all my guile involvenment suggesting to add that to guile. I'm actually
pretty fine with maintaining a lib of it's own.


> FWIW, I find guile-log to be very interesting work, but I also get the
> impression that it is a somewhat experimental and unproven approach to
> logic programming in Scheme.  Only time will tell whether it proves to
> be a successful approach.

I have actually used it quite a lot in examples but that's only me, I do
find it stable enough
to do good work in it. It's that I feel that I constantly find new cool
things I would like to
add to it and feel hey it's experimental cause it's only me using it.


>One of my concerns is the extensive use of mutable state in guile-log.
>Recently I have been thinking about how best to support scalable
>lock-free concurrency in Guile, so this question looms large in my mind:
>How effectively will guile-log be able to make use of a potentially
>large number of processor cores.  Do you have any thoughts on that?

For multicore you would like to support both traditional lock centered
programming
and lock free programming. For lock free you will for each variable that is
seen by
m threads be matched by m variables that points to the global one, if we
assume that
the global one does not change, then binding the variable in a thread will
only relate to that
thread. So to conceptually match kanrens datastructure multicore capability
can be done.
the main current problem though is that for each core you would like to
maintain a local stack
and currently this is a fixed sized stack. So before starting implementing
multicore lock free
programming to guile-log I would like to introduce resizable stacks which
probably is a much more difficult programming task that later make the lock
free threading.

If on the other hand we would like to connect one thread local prolog
variable with another tread local prolog variable (think a fluid that
points to another fluid) we would probably want som synchronisation ideoms
attached to them but that is also not difficult especially difficult and
could be maintained beside the lock free versions, I guess that this is not
inluded in kanren (I think that I would add these to guile-kanren though
when thinking about it)


> Kanren is written in a purely functional style, and this may well prove
> to a significant performance advantage in the multi-core future, even
> though it runs slower on a uniprocessor.

Kanren is not going to be faster then prolog multicore versions or
guile-log If I implement it
correctly for most cases I've seen. But the functional way of kanren has
use cases
where it can really shine due to it's way of mainting the variable binding
datastructure.

One thing that can lead to a dramatic improvement is in memoizing states in
backtracking
so that when we try to evaluate a goal we look if we have had this state
before and if so
reuse that expensive deduction. Another use case is when the code uses
interleaving constructs guile-log stack based approaches is inferior here
now due to the fact that we
need to unwind and restore the stack meaning that the stack need to grow
back and forth
and in the process recreate the variable bindings which is a bit clumsy.
Here guile-log lacks
the ability to do this but it's on my TODO list to have something usable
here.

Another reason is that sometimes the kanren ideom lead to elegant
expressions of algorithms and sometimes guile-log win's, I'm trying to make
that even by bringing over fetures from kanren to guile-log and vice verse
so that in the end there would only need to be a performance question of
when one or the other is used.

/Stefan


On Wed, Apr 4, 2012 at 2:05 AM, Mark H Weaver <mhw@netris.org> wrote:

> Hi Stefan,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:
> > The guile-log code is very dependent on guile! It's based on a c-file
> > which uses
> > guile C interface in order to get speedy and featureful at the same
> > time. So basically I have no hope that this codebase could be
> > independent from guile.
>
> Several libraries for Guile (e.g. guile-gnome) include C code that uses
> Guile's C interface, and this does not pose any difficulties for making
> it an external package.  Can you please explain more clearly why
> guile-log is impractical to package separately?
>
> FWIW, I find guile-log to be very interesting work, but I also get the
> impression that it is a somewhat experimental and unproven approach to
> logic programming in Scheme.  Only time will tell whether it proves to
> be a successful approach.
>
> One of my concerns is the extensive use of mutable state in guile-log.
> Recently I have been thinking about how best to support scalable
> lock-free concurrency in Guile, so this question looms large in my mind:
> How effectively will guile-log be able to make use of a potentially
> large number of processor cores.  Do you have any thoughts on that?
>
> It's unclear whether individual processors can be made much faster than
> they are today.  Making efficient use of a large number of processors
> will likely become increasingly important in the future.  In that
> context, there is a significant advantage to avoiding mutation of shared
> state, since that causes cache lines to bounce back and forth between
> processors, which kills performance.
>
> Kanren is written in a purely functional style, and this may well prove
> to a significant performance advantage in the multi-core future, even
> though it runs slower on a uniprocessor.
>
>    Regards,
>      Mark
>

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

Re: Inclusion of guile-log II

[Ludovic Courtès]

Hi Stefan,

Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:

> If you want independence use kanren. For guile this approach is 10x faster
> then kanren
> and 10x slower that a compiled prolog. Previously I thought that kanren has
> a more functional
> fundament and can express amazing things. But i'm now inclined that
> guile-log has a feature
> that are very cool and I will try to explain this feature for the fun of it.

Any idea why there’s such a performance difference?

Regardless, I’d be reluctant to use (or include in Guile) a logic
programming system that uses an interface different from that of Kanren,
because (1) there’s a book explaining that interface, and (2) it’s very
well thought out, concise, elegant, and powerful.

AIUI Guile-Log uses a different interface, right?  What would it take to
implement Kanren’s?

Thanks,
Ludo’.

Re: Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

On Wed, Apr 4, 2012 at 11:52 PM, Ludovic Courtès <ludo@gnu.org> wrote:

> Hi Stefan,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> > If you want independence use kanren. For guile this approach is 10x
> faster
> > then kanren
> > and 10x slower that a compiled prolog. Previously I thought that kanren
> has
> > a more functional
> > fundament and can express amazing things. But i'm now inclined that
> > guile-log has a feature
> > that are very cool and I will try to explain this feature for the fun of
> it.
>
> Any idea why there’s such a performance difference?
>

Yes the lookup cost can be substancially higher (in guile-log that's just a
one or two dereferenses) but on kanren you need to search an alist of all
bindings, the number of lambdas is more for each operations and, maybe not
that important but the allocations in guile-log is from  a stack, but
kanren uses a heap. the unify function in guile-log is in C while the same
function is kanren is in scheme. And lastly guile-log is a heavy macrology
in order to support cut's but kanren uses no cut and can stay functional,
but this means that kanren features more lambda constructions and i'm
uncertain if peval can counteract this.

N.B. 1, I took a testcase (einstein problem) for kanren on chicken,
compiled and compared
with the same case on guile using vm operation support. That showd about 5x
speed difference in that case.

N.B. 2, heavy use of interleaving constructs may insteafd point for kanren
as a better method. Especially If we can make use of functional lookup
structure with better lookup performance
like VLISTS, but I have a version of functional self organizing trees as
well which can perform
close to a hash lookup mechanism (the datstructure is in C that is)

Regardless, I’d be reluctant to use (or include in Guile) a logic
> programming system that uses an interface different from that of Kanren,
> because (1) there’s a book explaining that interface, and (2) it’s very
> well thought out, concise, elegant, and powerful.
>

Well if you want to translate prolog programs to scheme guile-log is
actually a better fit
cause you may want to support cut's, that's why I designed another
interface. It's not hard to mimic most of kanren though, It's even simpler.
You need to supply a functional version e.g. operations that return a
function and use functions in stead of macros in many places. On a lower
level kanren uses it's lambda@ constructs e.g. to allow currying, that's
sweet but I'm uncertain if that is needed, But yes I plan to support a
translational module to higher level kanren!


> AIUI Guile-Log uses a different interface, right?  What would it take to
> implement Kanren’s?
>
> Thanks,
> Ludo’.
>
>
> 3 day's of coding perhaps. F.Y.I. i'm going through the reasoned schemer
right now and remakes most of the examples in guile-log. That had gave my
quite insight and therefore I don't think a translation is that hard.

/Stefan

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

Re: Inclusion of guile-log II

[Stefan Israelsson Tampe]

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

> Regardless, I’d be reluctant to use (or include in Guile) a logic
> programming system that uses an interface different from that of Kanren,
> because (1) there’s a book explaining that interface, and (2) it’s very
> well thought out, concise, elegant, and powerful.

F.Y.I.

I have now a kanren interface for guile-log, I do not support
partially-eval-sgl
otherwise everything should be in I think.

To use it install guile-log and use
 (use-modules (logic guile-log kanren))

There is some tests carried over from the kanren sources in the test
directory.

Have fun!

On Wed, Apr 4, 2012 at 11:52 PM, Ludovic Courtès <ludo@gnu.org> wrote:

> Hi Stefan,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> > If you want independence use kanren. For guile this approach is 10x
> faster
> > then kanren
> > and 10x slower that a compiled prolog. Previously I thought that kanren
> has
> > a more functional
> > fundament and can express amazing things. But i'm now inclined that
> > guile-log has a feature
> > that are very cool and I will try to explain this feature for the fun of
> it.
>
> Any idea why there’s such a performance difference?
>
> Regardless, I’d be reluctant to use (or include in Guile) a logic
> programming system that uses an interface different from that of Kanren,
> because (1) there’s a book explaining that interface, and (2) it’s very
> well thought out, concise, elegant, and powerful.
>
> AIUI Guile-Log uses a different interface, right?  What would it take to
> implement Kanren’s?
>
> Thanks,
> Ludo’.
>
>
>

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

Re: Inclusion of guile-log II

[Ludovic Courtès]

Hi Stefan,

Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:

> On Wed, Apr 4, 2012 at 11:52 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>
>> Hi Stefan,
>>
>> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>>
>> > If you want independence use kanren. For guile this approach is 10x
>> faster
>> > then kanren
>> > and 10x slower that a compiled prolog. Previously I thought that kanren
>> has
>> > a more functional
>> > fundament and can express amazing things. But i'm now inclined that
>> > guile-log has a feature
>> > that are very cool and I will try to explain this feature for the fun of
>> it.
>>
>> Any idea why there’s such a performance difference?
>>
>
> Yes the lookup cost can be substancially higher (in guile-log that's just a
> one or two dereferenses) but on kanren you need to search an alist of all
> bindings,

That’s no excuse: Kanren could use a vhash or similar, as you noted.  ;-)

> the number of lambdas is more for each operations and, maybe not that
> important but the allocations in guile-log is from a stack, but kanren
> uses a heap. the unify function in guile-log is in C while the same
> function is kanren is in scheme. And lastly guile-log is a heavy
> macrology in order to support cut's but kanren uses no cut and can
> stay functional, but this means that kanren features more lambda
> constructions and i'm uncertain if peval can counteract this.

Hmm, OK.

[...]

> Well if you want to translate prolog programs to scheme guile-log is
> actually a better fit

But I’m not sure whether getting Prolog programs translated is a worthy
cause.  :-)

Thanks,
Ludo’.

Re: Inclusion of guile-log II

[Ludovic Courtès]

Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:

> I have now a kanren interface for guile-log, I do not support
> partially-eval-sgl
> otherwise everything should be in I think.
>
> To use it install guile-log and use
>  (use-modules (logic guile-log kanren))

OK, nice!

Thanks,
Ludo’.