unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* Inclusion of guile-log II
@ 2012-04-03 19:18 Stefan Israelsson Tampe
  2012-04-04  0:05 ` Mark H Weaver
  2012-04-04 21:52 ` Ludovic Courtès
  0 siblings, 2 replies; 10+ messages in thread
From: Stefan Israelsson Tampe @ 2012-04-03 19:18 UTC (permalink / raw)
  To: guile-devel

[-- 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 --]

^ permalink raw reply	[flat|nested] 10+ messages in thread
end of thread, other threads:[~2012-04-09 20:16 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2012-04-03 19:18 Inclusion of guile-log II Stefan Israelsson Tampe
2012-04-04  0:05 ` Mark H Weaver
     [not found]   ` <CAGua6m1MFNHXgU+qam64Hf1Vt3iNEy=v==q4-Ua48a8AgcXz_Q@mail.gmail.com>
     [not found]     ` <CAGua6m0tu98=qHR5GdC4f84AF=noUdt2RpxJPReMVu8UaUMwzg@mail.gmail.com>
2012-04-04 16:30       ` Fwd: " Stefan Israelsson Tampe
     [not found]       ` <87r4w3eact.fsf@netris.org>
2012-04-04 16:33         ` Stefan Israelsson Tampe
2012-04-04 16:54     ` Fwd: " Stefan Israelsson Tampe
2012-04-04 21:52 ` Ludovic Courtès
2012-04-05  6:02   ` Stefan Israelsson Tampe
2012-04-09 20:15     ` Ludovic Courtès
2012-04-06 18:03   ` Stefan Israelsson Tampe
2012-04-09 20:16     ` Ludovic Courtès

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).