From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Inclusion of guile-log II Date: Tue, 3 Apr 2012 21:18:44 +0200 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=14dae93411cde3a36504bccb2c22 X-Trace: dough.gmane.org 1333480739 5232 80.91.229.3 (3 Apr 2012 19:18:59 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 3 Apr 2012 19:18:59 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Apr 03 21:18:56 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1SF9Fn-0003BB-1j for guile-devel@m.gmane.org; Tue, 03 Apr 2012 21:18:55 +0200 Original-Received: from localhost ([::1]:59362 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SF9Fm-0003cx-Bw for guile-devel@m.gmane.org; Tue, 03 Apr 2012 15:18:54 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:39877) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SF9Fi-0003cb-2a for guile-devel@gnu.org; Tue, 03 Apr 2012 15:18:52 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SF9Ff-00055m-Dw for guile-devel@gnu.org; Tue, 03 Apr 2012 15:18:49 -0400 Original-Received: from mail-iy0-f169.google.com ([209.85.210.169]:59425) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SF9Ff-00055R-4S for guile-devel@gnu.org; Tue, 03 Apr 2012 15:18:47 -0400 Original-Received: by iajr24 with SMTP id r24so68298iaj.0 for ; Tue, 03 Apr 2012 12:18:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=dLGte/x75eO5P1kZ78u5shzS/we/Hq4+l+bH4pAQ/xc=; b=AqEoXAhomC/N6oYHuVEbaVDbeXa/o1QEAu76a98tuFPVbp8BM8dhhOkXOq7Y3w1PB4 H1LeAfC9J5RZlZiLwm2BC1hECTPhrWLIyAjZf0DG7uYaYYNwr8JzbTNn4WuRHcobRAra 9w6et13ezgOO5a/RA/euPKBPyXjkY42L17UtBtSiB73QPr9AwCvqzhvIy4m/v3GWxhkX Z1rtaR3dLMCWpGSofu1x1PtkBWC4wPZBiDfAU2LlYk8H/vKVjQalDcECDQ3VHUgwDQIk uaOXSUfULcLbyn+SWkQ5XCphkxjzUJXqifp3mI++imPH3zboe9CLwHByWfZ3EiK/28RW gMHQ== Original-Received: by 10.50.219.194 with SMTP id pq2mr3114518igc.18.1333480724341; Tue, 03 Apr 2012 12:18:44 -0700 (PDT) Original-Received: by 10.50.242.102 with HTTP; Tue, 3 Apr 2012 12:18:44 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.85.210.169 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14206 Archived-At: --14dae93411cde3a36504bccb2c22 Content-Type: text/plain; charset=ISO-8859-1 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 ( 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)> ( 5 (x y) ( ( (<=> x 0) (<=> x 1) (<=> x 2)) ( (<=> y 0) (<=> y 1) (<=> y 2)))) $2 = ((0 0) (1 0) (0 1) (2 0) (1 1)) scheme@(guile-user)> (define s ()) scheme@(guile-user)> ( 5) $3 = ((0 2) (2 1) (1 2) (2 2)) scheme@(guile-user) [1]> ( s) scheme@(guile-user) [1]> ( 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! --14dae93411cde3a36504bccb2c22 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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 fas= ter then kanren
and 10x slower that a compiled prolog. Previously I thou= ght 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 fe= atures 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 g= uile-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 P= 3. 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. wit= h interleaving on the other hand we have in kanren,

=A0(solve 20 (x y) (all-interleave (any (=3D=3D x 0) (=3D=3D x 1) (=3D= =3D x 2))
(any (=3D=3D y 0) (=3D=3D y 1) (=3D=3D y 2))))
$1 =3D (((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 unde= rstand this construct. To also note, the solver needs to store n states=A0 = 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 some= thing like

(define (interleave p cc g1 gs)
=A0 (let ((l '()) = (r '()))
=A0=A0=A0 (define fail
=A0=A0=A0=A0=A0 (lambda ()
=A0= =A0=A0=A0=A0=A0=A0 (let loop ((ll l) (rr r))
=A0=A0=A0=A0=A0=A0=A0=A0=A0 (if (null? ll)
=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0 (if (null? rr)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0 (p)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (loop = (reverse rr) '()))
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (let ((th= unk (car ll)))
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (set! l (cd= r ll))
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (set! r rr)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (thunk))))))
=A0=A0=A0=A0= =A0=A0=A0
=A0=A0=A0 (define (mk-cont p)
=A0=A0=A0=A0=A0 (let ((state= (gp-store-state)))
=A0=A0=A0=A0=A0=A0=A0 (lambda ()
=A0=A0=A0=A0=A0= =A0=A0=A0=A0 (gp-restore-wind state)
=A0=A0=A0=A0=A0=A0=A0=A0=A0 (p))))<= br>
=A0=A0=A0 (let loop ((p p) (g1 g1) (gs gs))=A0=A0
=A0=A0=A0=A0=A0 (match gs
=A0=A0=A0=A0=A0=A0=A0 ((g2)
=A0=A0=A0=A0=A0= =A0=A0=A0 (g1 fail
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (lambda (p2)
= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (set! r (cons (mk-cont p2) r))=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (g2 fail
=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (lambda (p3)
=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (set! r (cons (mk-cont p3) r))
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (cc fail))))))=
=A0=A0=A0=A0=A0=A0=A0 ((g2 . gs)
=A0=A0=A0=A0=A0=A0=A0=A0 (g1 fail= =A0
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (lambda (p2)
=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (set! r (cons (mk-cont p2) r))
=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (loop p2 g2 gs))))))))

This has a = clear syntax and can be understanded without to much work. (the kanren vers= ion
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 q= ue of restarts that updates as we find new
states or consumes as we do a restart at a failure. Then we introduce a fai= lure object that deque the next restart.

The bad thing with this cod= e is set!. we will set! a variable on the heap and hence there is no easy e= legant 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 vari= ables in such a way that we can restore the state. One solution that is ver= y elegant is to use dynwinds like features for the separate prolog stack. A= nd an implementation using this is under 100 lines of scheme. So now we can= write,

(define (alli p cc g1 gs)
=A0 (with-guarded-states guard-set! ((l &#= 39;()) (r '()))
=A0=A0=A0 (define fail
=A0=A0=A0=A0=A0 (lambda ()=
=A0=A0=A0=A0=A0=A0=A0 (let loop ((ll l) (rr r))
=A0=A0=A0=A0=A0=A0= =A0=A0=A0 (if (null? ll)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (if (nu= ll? rr)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (p)
=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (loop (reverse rr) '()))
=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (let ((thunk (car ll)))
=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (guard-set! (cdr ll) rr)
=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (thunk))))))
=A0=A0=A0=A0=A0=A0=A0 =A0=A0=A0 (define (mk-cont p)
=A0=A0=A0=A0=A0 (let ((state (gp-store-state)))
=A0=A0=A0=A0=A0=A0=A0 (l= ambda ()
=A0=A0=A0=A0=A0=A0=A0=A0=A0 (gp-restore-wind state)
=A0=A0= =A0=A0=A0=A0=A0=A0=A0 (p))))

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

In stead an= d be able to do

scheme@(guile-user)> (<run> 5 (x y) (<and-i&g= t; (<or> (<=3D> x 0)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (<=3D> x 1)
=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (<=3D>= ; x 2))
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (<or> (<= =3D> y 0)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0 (<=3D> y 1)
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (<=3D> y 2))))
$2 =3D ((0 0) (1 0) (0 1) (2 0) (1 1))

scheme@(guile-user)> (defi= ne s (<state-ref>))

scheme@(guile-user)> (<take> 5)
$3 =3D ((0 2) (2 1) (1 2) (2 2))

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

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

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

I personally think that the newly introduced feature will make it much simp= ler 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 wi= ll have the birth of guile-kanren. I will try to implement that later on, b= ut I still need to play with this tool a bit more.

Have fun!

--14dae93411cde3a36504bccb2c22--