guile-devel
[Top][All Lists]

## Inclusion of guile-log II

 From: Stefan Israelsson Tampe Subject: Inclusion of guile-log II Date: Tue, 3 Apr 2012 21:18:44 +0200

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) > (<state-set!> s)

scheme@(guile-user) > (<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!