Next: , Previous: , Up: Top   [Index]


2 Guile-log

Guile log is a basic framework of macrology that implements functionality that can be compared to both kanren and prolog plus some extra features. The feature set is close to what can be accomplish with plain kanren but more at the speed of prolog. Usually kanren is a more expressive way of implementation and can many times easier be extended with new features, on the other hand, most features in kanren is available in guile-log and performs about 10x faster then scheme kanren. Other possibilities are using the kanren interface ontop of guile-log and then the speed difference is about a factor of 2 slower then guile-log close to the speed that kanren does in compiled chicken.

Guile log performs it’s actions in a guile-log mode e.g. small scheme like language that behaves in a certain way defining functions for this environment can be done with sugared functions or with a special macro definition.

A guile log function is a function where the first argument represent the current state, the second argument the failure thunk and where the third argument represent a continuation lambda. It’s possible to write macros that works in guile log mode.

A failure thunk is a thunk that is evaluated at failure and usually the stack backtracks in this lambda. The continuation lambda takes a satte and a failure thunk as it’s argument which represent the current failure and then execute it’s body as the continuation of the algorithm. e.g.

guile-log has one aspect that kanren does not have and this is the notion of going up and down a stack at redo and undo. With this we have a notion that is very similar to a dynamic-wind, which can guard constructs. With this it is pretty simple to instrument tracing to not only trace upward but also at the same point track the backtracking. This is not possible in kanren. With this it is possible to keep the number of guarded variables to a minimum something kanren cannot do due to the lack of stack notion. On the other hand it is possible like in the reference implementation of kanren to get away with guarded variables by either using delimited continuations or using special return values. But for some constructs guarded variables is pretty much needed e.g. acumulator like constructs and delimeted continuations.

Kanren does one thing pretty well and that is that it can support a notion of tail-call’s. We do have options for guile-log to accomplish this as well and hence it is possible to write algorithms in guile-log without risk blowing the stack.

To see how the code is designed we can describe,

the failure thunk semantic, (lambda () (unwind) (try-alternative-path))

the continuation lambda (cc) (lambda (state fail) (execute-next-fkn state fail))

To see how they work consider the (<and> (f) (g)), <and> is a directive that represent a sequencing of facts and here the guile-log functions f and g will be tried in sequence e.g.

  (<and> (f) (g)):
     (lambda (state fail cc)
       (f state fail (lambda (state2 fail2) (g state2 fail2 cc))))

Likewise an or (e.g. try f and if f fails try g) clause could be defined

  (<or> (f) (g)):
    (lambda (state fail cc)
      (let ((fr (gp-newframe)))
        (f state
           (lambda () 
              (unwind fr)
              (g satte fail cc))
            cc)))      

Writing these forms in plain scheme is a bit tedious so it is nice to have macros that does this for us. Note here that Kanren very much the same way (A read and understanding of the Kanren source code and/or Reasoned Schemer is a good background in using this tool)

You do find the notion of a cut in prolog and you do have it in guile-log as well. Kanren does not have it explicitly. But basically a cut is maintaining a failure thunk that typically represent backtracking from the function etc. The cut is not a parameter in the functions and hence is a notion that relates to the macrology in the source code, hence typically a guile-log macro looks like

(define-guile-log macro
  (syntax-rules ()
    ((_ (cut s p cc) code ...)
      do-something-here)))

So we see that guile-macros by convention have that quadruple as a first argument. Note the cut parameter, the rest is just the plain old parameters you got in the first three function arguments.

The guile-log is simply looking at forms and if it sees a sexp where the car is a guile-log macro it will insert the (cut s p cc) as a first argument and evaluate that macro. Else the sexp is assumed to be a function and guile log will put the p and the cc in front and execute that. e.g. to define or a non guile-log macro you typically use,

Kanrens version of or-i and and-i e.g. the interleaving versions of ’or’ and ’and’, and scale better, the reason is that in guile-log the stack is moved back and forth between states which is unnecesary in kanren where the interpretation of variables is via a state consisting of a list representing a stack or via a functional tree. On the other hand, in guile-log we can make use of dynamic wind constructs which are impossible to get right in kanren.

Threading is not supported in the lower levels, e.g. umatch in guile-log and here Kanren is much better off. In principle this is something that can be improved uppon, but we postpone that to later versions of guile-log.

guile-log is safe with respect to undo/redo, you can stall everywhere and expect to be able to store the state, and later retrieve it.

Functions (f args ...) in guile-log is defines as

  (define (f s p cc args ...) code ...)

2.1 Basic logic

G.L. (<and> p1 p2 ...), perform p1, if success then p2 and so on.

G.L. (<or> p1 p2 ...), perform p1, if p1 fail then backtrack and try p2 ...

G.L. (<and!> p1 p2 ...), same as <and> but yields at most one answer.

G.L. (<and!!> p1 p2 ...), the same as (<and> (<and!> p1) (<and!> p2) ...) e.g. at most one answer from p1 and at most one answer from p2 etc.

<and!> and <and!!>, are useful when we want to restrict the search space and when a local success correlates to a global one.

G.L. (<not> p ...), successes if (<and> p ...) fail and fails otherwise. In either case the form will always backtrack and no variables will be bound inside this form.

G.L. (<if> p x), if p is a success then x, p will only success at most one time.

G.L. (<if> p x y), if p is success then x, else backtrack and use y, the same condition holds on p as the previous version of if.

G.L. (<if-some> p x), the same as (<and> p x).

G.L. (<if-some> p x y), logicaly the same as (<or> (<and> p a) (<and> (<not> p) b)).

G.L. (<cond> (P X) ...), like the ordinary cond, but using <if> in stead of if

G.L. (<or-i> p1 p2 ... pn), if p1 successes and we later backtrack then try p2 etc and so on until pn if pn successes and we later backtrack then p1 is tried again and interleave like that. To note here is that this form uses both bank a and b and in order to function correctly when storing a state both bank a and bank b need to be stored.

G.L. (interleave l), the same as <or-i> but with the difference l is a list of lambdas typically made by (</.> ...).

G.L. (<or-union> p1 ...), this is like <or-i> but if pk has a success and if, the goal pl, l > k, succeses like in (<and> pk pl) then we will backtrack, this means that duplication of results is in a sense removed.

G.L. (interleave-union l), see interleave.

G.L. (<and-i> p1 p2 p3 ...), and interleaving! this is an and which will in parctice behave as

  (<and-i> (<or> A B) (<or> C D))
  <=>
  (<or> (<and> A C) (<and> B C) (<and> A C) (<and> B C))

e.g. backtracking is shallow and we will backtrack all the first combinations, then all the second combinations then all the third ones etc. To accomplish this state information needs to be stored hence using this tool can be slow and memory intensive.

G.L. (and-interleave l), the same as <and-i> but with the difference l is a list of lambdas typically made by (</.> ...).

G.L. (<succeeds> p) will try p and if it succeeds undo any bindings and continue.

G.L. (<zip>  (w        g ...) 
             ((v ...)  h ...) ...)

This is executing n guile-log programs in paralell e.g. when backtracking all of the programs are backtracked in one go. The interface to the outside is via variables w (v ...) etc. (one can either specify a variable or a list of variables. The variables represents the interface for the continuation of the program. So all the programs are executed one by one staring with the first one yielding a construction of what for example w should be bound to, that information is stored and then everything done from the state at the start of the <zip> is unwinded and restored. Then the stored representation of w etc. are at the end of the zip where we have unwinded back to the start the information is unified with the original variables and then the code will continue with the continuation. A backtracking to the zip will backtrack all of the goal sets in paralell again starting with the first and new values for the interfacing variables are constructed.

Conside the following definition of a function f,

(<define> (f x n)
  (<or> (<=> x n)
        (f x (+ n 1))))

this function can be used to illustrate the zip by,

(<run> 5 (x y) 
  (<zip> (x (f x 0)) 
         (y (f y 1))))

> ((0 1) (1 2) (2 3) (3 4) (4 5))

G.L. (<call> ((l x) ...) code ...), This will call (<and> code ...) and at success it will store the values x ... and then backtrack and unify the copied x to l. At backtracking the state will be reinstated. Use this when you want to avoid side effets when calling a stub.

Example:

(<run> 5 (x y) 
   (<call> ((x y)) (f y 10))
   (<=> y -1))

=> ((10 -1) (11 -1) (12 -1) (13 -1) (14 -1))

G.L. (<//> ((fail ((xx x) ... ) code ...) ...) body ...) G.L. (<update> (fail vals ...) ...) This is close to functionality to <zip> but somewhat on steroids and a few 4 - 5 times slower. The main usage is when we need to try out two logics in paralell and they are not nessesary in sync. In (fail ((xx x) ...) code ...), (<and> code ...) will be evaluated and any resulting values x will be copied and stored in the introduced variable xx. The failure tag can be used to tell guile-log to only backtrack that part of the arm. This is done via a (<update> (fail vals ...) ... ). Typically the first part of the body is a guard that evaluates if they are on synch and if not, say branch f1, needs to update you can do so by (<update> (f1)) or (<update> (f1 p)) with p a variable containing a failure thunk captured inside the arm. Typically p has before been intrioduced with (letg ((p #f)) co ...) and then p is setted to for example the Current failure thunk P inside the arm.

Example:

(<run> 1 (x y) 
   (<//> ((f1  ((xx x)) (f x 1))
          (f2  ((yy y)) (f y 10)))
      (if (< (<scm> xx) (<scm> yy))
          (<update> (f1))
          <cc>)
      (<=> (xx yy) (x y))))

=> ((10 10) (11 11) (12 12) (13 13) (14 14))

2.2 Probing The Control Variables

It is possible to probe the curretn variables that is transported behind the sceene, use the syntax-parameters S,CC,CUT,P to reach them inside guile-log code.

2.3 Guarded variables

This are lower level constructs usable for designers of logical ideoms. Their purpose is to allow for constructs that need to add variables to store a state across multiple backtrackings to mix well with postpone and undo/redo.

G.L. (<let-with-guard> wind guard ((var init) ...) code ...), This construct will bind var ... with init values init ... just as with let. The difference is that we can guard execution of no mutation with e.g.

G.L. (guard Lam) e.g. Lam neede to be a guile log closure for which the code should be safe to undo and redo if not mutated. wind refers to the current wind level and use it in

(gp-restore-wind state wind)

To restore at the current wind level meaning that any let-with-guard construct inside code ... will be restored but the defined var ... will not be restored, if that is wanted then use (- wind 1) instead.

G.L. (<let-with-lr-guard> wind lguard rguard ((var init) ...) code ...) This is very similar to the previous construct but for this ideom we define a lguard and rguard in stead. That stack space between lguard and rguard is strongly guarded e.g. one can mutate var ... inside that space. To the right of rguard the variables are guarded if no mutation is done in that space.

scm (let-with-guard s wind guard ((var init) ...) code ...) scm (let-with-lr-guard s wind lguard rguard ((var init) ...) code ...) This is scheme macro that will defined scheme macros lguard and rguard or just a guard. And the code executed inside them e.g.

(guard gcode ...)

will be protected accordingly the description above for the guile log macrology versions. Finally note that s should be a symbol bounded to the current environment.

2.4 Unify Constructs

In the forms below remember to use unquote for forms that need to be scheme evaluated inside the patterns.

G.L. (let<> ((m pat val) ...) code ...), this will pattern-match val using m = (+ ++ - *) and then pattern-match the next and so on and lastly execute a (<and> code ...).

G.L. (<=> X Y), unifies X and Y with occurs check

G.L. <==>, the same as <=> but using the - matcher in stead of + meaning that no unifying is used.

G.L. <r=>, the same as <=> but using ++ in stead of +.

2.5 variable binding

G.L. (<let> ((V X) ...) code ...), Will introduce bindings V with values X and then evaluate code in guile-log mode with an implicit <and>.

G.L. <let*>, relates to <let> as let* relates to let

G.L. <letrec>, this th letrec version of <let>.

G.L. (<var> (v1 v2 ...) code ...), will make fresh new unify variables v1 v2 ... and use them in a G.L. (<and> code ...) e.g. the same as (<let> ((v1 (gp-var!)) ...) code ...).

G.L. (<hvar> (v1 v2 ...) code ...), like <var>, but variable identities is located on the heap instead.

2.6 failure and cc

G.L. <cc>, represent a continuation or success can be used like (<if> P <cc> Y)

G.L. <fail>, will issue a failure and start backtracking.

G.L. (<fail> p), will use p as a failure backtracking object.

G.L. <cut>, will issue a cut e.g. we will stop backtracking from here on used like (<and> P1 <cut> P2) if P2 fails it will typically jump over P1 and back to where the cut point is defined. G.L. (<cut> code ...), the same as (<and> <cut> code ...)

G.L. (<next>), will backtrack to the next clause in a match (TODO: this has not been tested).

G.L. (<with-fail> p code ...), this will use p as a failure for G.L. (<and> code ...)

G.L. (<with-cut> cut code ...), this will use cut as a cut failure for G.L. (<and> code ...)

G.L. (<with-cc> cc code ...), this will use cc as the continuation.

G.L. (<with-s> s code ...), this will use s as the state.

G.L. (<peek-fail> p code ...) This will bind p to the failure thunk at this instruction.

2.7 defining function and matching

Scm (<define> (f x ...) code ...), this will define a guile-log function named f with arguments x ... the code will be executed under the G.L environment with an implicit <and> around code ... then f can be used inside G.L. like (<and> (f x y) ...)

Scm (<<define>> (f a ...) (p ... code) ...), default #:mode = +

Scm (<<define>> (#:mode mode f a ...) (p ... code) ...),

This is close to prolog functions. E.g. a ... is the signature, p ... is the pattern that umatches the arguments and if there is a match then code is evaluated in G.L. context. if code failes the next line is tried unless there is a <cut> that forses a return from the function.

Scm (<<define->> (f a ...) (p ... code) ...), default #:mode = - e.g. non unifying match.

Scm, (<def> (f a ...) (p ... code) ...),

Scm, (<def-> (f a ...) (p ... code) ...),

This is as with <<define>>,<<define->> but if code fails it will issue a cut and leave the function.

Scm (<lambda> (x ...) code ...), this similar like define but an anonymous function.

Scm (<<lambda>> (p ... code) ...), this is anonymous <<define> without explisit arguments and mode.

Scm (<case-lambda> ((a ..) code ...) ...), th guile-log case-lambda version.

Scm (<<case-lambda>> ((p ... code) ...) ...), this is the case-lambda version of <<lambda>>.

Scm (</.> code ...) This is (<lambda> () code ...).

G.L. (<recur> n ((w v) ...) code ...), this works like the corresponding named let but in guile-log mode but it defines the loop function n to work inside G.L. and the form itself is in G.L.

G.L. (<letrec> ((v x) ...) code ...), this will bind v ... with x ... in a letrec manner and then execute code ... with an implicit <and> around it.

G.L. (<match> [#:mode +] (pat ... code) ...), this is a small wrapper around umatch the difference is that if works under G.L. and that code is evaluated under G.L. and that backtracking is correctly setup-ed.

Scm (<def>      (f [#:mode +] a ..) (p ... code) ...))
Scm (<<define>> (f [#:mode +] a ..) (p ... code) ...))

This is a sugar for essentially, (<define> (f a ...) (<match> [#:mode +] (a ...) (p ... code) ...)). The difference is that <<define>> will never backtrack to a new match row and <def> will backtrack to the next matcher if the code part fails.

G.L. (<funcall> f . l), this is actually funcall with the difference is that it will make sure to lookup f if it is a unify variable pointing to a lambda.

G.L. (<apply> f a ... l), this is as with apply, but logic variables will be looked up.

2.8 printing information

Scm (tr x), translate unbound variables with a prefix governed by *gp-var-tr* fluid.

Scm (tr pre x), the same as above but using pre as the prefix.

G.L. (<pp> x), this will pretty-print x and print it as a list-version of the code

(<pp-dyn> redo-print undo-print), when the current unify stack backtracks across the current position in the stack it will do a (<pp> undo-print), it redoes across this dynwind it will pretty-print e.g. (<pp> Redo-print).

G.L. (<format> port str arg ...), as with format, but under G.L.

2.9 evaluate scheme expressions

G.L. (<code> code ...), will execute (begin code ...) as scheme and then success.

G.L. (<tail-code> (p cc) code ...), this will bind the failure thunk p and continuation cc inside code ... which is evaluated under Scm e.g. an implicit begin. It is the scheme code’s responsibility to continue using cc or backtrack using p.

G.L. (<when> S), the same as (if S <cc>).

G.L. (if S X)
G.L. (if S X Y)

S is an ordinary scheme expression and if true will execute X in G.L else Y in G.L. or fail if the scheme expression return #f.

Similarly there is (without =>)

G.L. (when p c ...)
G.L. (cond (p a ...) ...)
G.L. (case a (p a ...) ...)

G.L. (<return> code ...), this will do a Scm: (begin code ...) and simply return that form in the guile log pass.

G.L. (<ret> val), the same as (<return> (u-scm val))

G.U. (<dynwind> redo-thunk undo-thunk), dynwind that when the unify stack is going in forward direction the redo-thunk is evaluated and else when we backtrack over this barrier the undo-thunk is evaluated.

2.10 go from scheme to guile-log

Scm (<with-guile-log> (p cc) code ...), this will start a guile-log session using failure think p and continuation cc and use p as a cut as well.

Scm (<with-guile-log> (cut p cc) code ...), this will start a guile-log session using failure thunk p and continuation cc and use cut as the cut failure thunk.

Scm (<ask> P ...), will execute (<and> P ...) and if success return #t else if fail return #f

Scm (<eval> (v1 ...) code fini cc), this will bind new variables v1 ... and execute code with failure thunk fini and continuation cc under G.L.

Scm (<run> n (v ...) code ...), bind v ... with variables and execute the code and collect the list of list of bindings of v at success if (v ...) = (w) then it will return a list of values. n is the maximum numbers of success results and skipping n results in no limit on the number of successes.

Scm (<clear>), cleares the stack back to start, use this when finished with <take>,<run> etc.

G.L. (<stall>), this will stall a computation and allow it to continue at the users will and also be able to store the state.

Scm (<continue>), this will make it possible to continue a stalled run, but if the run opted out after n successes then must ask for the number of more successes as well by using:

Scm (<continue> n), with n the number of more successes to returnif we started with (<run> n () ...).

Scm <take>, this is the same as <continue>.

Scm (<state-ref>), this returns a value of the current state for which the system can restore later on.

Scm (<state-set!> s), restores the state represented by the datadtructure s that was produced by <state-ref>.

2.11 Using logical variables in scheme mode.

When the guile-log system enters scheme mode one may for example need to use state information. But as entering scheme from guile-log the state is implicitly marked for the following macros to work without actually explicitly bound a state variable as may be done as well e.g.

(<scm> x) returns essentially a scheme representation of x but where logical variables are included as themselves.

<cons>, <car>, <cdr>, used exactly as with corresponding scheme functions.

If by some reason one need to do the whole program using (almost) only the state information, one can do so by setting the variable *kanren-assq* to #t. Doing this will mean that the program almost works as plain kanren.

2.12 Guile-log macro definitions

(define-guile-log name . l), this works like define-syntax, but it will mark the symbol as a guile-log macro.

(log-code-macro x), marks x as a log-code macro e.g. it will inline it’s code into the continuation in an and sequence hence reduce the number of needed closures.

Scm (parse<> (cut w fail cc) code), used to continue guile-log macro expansion e.g. we could define <and!!> using

  (define-guile-log <and!!>
     (syntax-rules ()
       ((_ meta arg ...)
        (parse<> meta (<and> (<and!> arg) ...)))))

That is a guile-log macro is an ordinary macro but in guile-log expansion it will add the first argument a meta to that macro that are then used in an ordinary expansion where we indicate a continue in guile-log mode by using parse<>.

<define-guile-log-rule>, this is a fast one-liner version of define-guile-log and throws one into the G.L. context of the producer without explisitly using (cut s p cc).

Scm (define-and-log name . l), used in and log context to get the next lines in the <and> into the macro. the match matching signature in the macro is

(f (cut s p cc) (f . l) e ...), for a function like signature and

(f (cut s p cc) () e ...), for a symbol like signature.

An example using this is to for example have constructs that avoids nesting. For example we can define G.L. (<v> v ...)) through,

(define-and-log <v>
  (syntax-rules ()
    ((_ w (<v> v ...) e ...)
     (<let> w (v ...) e ...))))

And we would use it as

(<define> (f x)
  (<v> y z)
  (<=> x (y . z))
  (g y z))

2.13 Controling the kind of variable binding used, kannren assq, or a prolog stack.

(<logical++>),(<logical-->), turn on/off the usage of assq logical variables. Works by introducing a

To make the whole session in kanren assq mode one can set *kanren-assq* to #t.

Example:

(<run> 1 (x) (<=> x 1) (<pp> (pk S)))
;;; ((<gp-stack> 5404676))

(<run> 1 (x) (<logical++>) (<=> x 1) (<pp> (pk S)))
;;; ((<gp-stack> 5404676 (<#0 : 1> . 1)))

(<run> 1 (x) (<logical++>) (<var> (y) (<=> y 1) (<pp> (pk S))))
;;; ((<gp-stack> 5404676 (<#0 : 1451764> . 1)))

The format of the state is for the car to be the stack object and the cdr will represent the association list. Here we see how we associated 1 to the guile-variable <#0 : 1>. Also note in the last example how <#0 : 1451764> indicates that it has been allocated on the heap in logical++ mode.

2.14 Returning multiple values.

(<and> (<values> (v ...) (f args ...)) ...) This is a way to define multiple values v ... as a return from f. For this to work we need to add (<cc> x ...) at the logical end of the definition of the functione.

Example:

(define-syntax s-pair!? 
  (syntax-rules ()
    ((_ x)   (gp-pair!? (s-lookup x)   S))
    ((_ x S) (gp-pair!? (s-lookup x S) S))))

(define-syntax s-lookup 
  (syntax-rules ()
    ((_ x)   (gp-lookup x S))
    ((_ x S) (gp-lookup x S))))

(define (<pair?> s p cc x)
  (let ((ss (s-pair!? x s)))
    (if ss
        (cc ss p)
        (p))))

(<define> (!car! x)
  (<pair?> x)
  (<cc> (<car> x)))

and use it as,

(<run> 1 (x y) (<=> x '(1 2)) (values (z) (!car! x)) (<=> y z))
=> (((1 2) 1))

2.15 Acumulators

These constructs will accumulate all possible values of a construct.

G.L. (<fold> kons knil Lam X L), This will initiate an accumulator to knil and then use kons as the acumulating function. The guile log closure Lam is executeded and X will represent the result that will be accumulated. The final result is then added to L.

G.L. (<fold-step> kons knil Lam X L), the semantic is similar to <fold>, but the form will at each iteration succeeds with L bound to the current accumulator value.

Example:

(<define> (f x n m) (if (< n m) (<or> (<=> x n) (f x (+ n 1) m))))

(<run> * (l) (<var> (x) (<fold> + 0 (</.> (f x 0 10)) x l)))
=> (45)

(<run> * (l) (<var> (x) (<fold-step> + 0 (</.> (f x 0 10)) x l)))
=> (0 1 3 6 10 15 21 28 36 45)

G.L. (<fix-fold> kons knil Lam X Y L),

G.L. (<fix-fold-step-> kons knil Lam X Y L),

this is as with <fold> etc, but the acumulation is done for each fixed Y.

Example:

(<define> (f x n m) 
   (if (< n m) (<or> (<=> x n) (f x (+ n 1) m))))

(<run> * (l) 
  (<var> (x y) 
    (<fix-fold> cons '() 
         (</.> (f x 0 5) (f y 0 (<scm> x))) 
         x y l)))
=> ((4 3 2 1) (4 3 2) (4 3) (4))

(<run> * (l) 
   (<var> (x y) 
     (<fix-fold-step> cons '() 
        (</.> (f x 0 5) (f y 0 (<scm> x))) 
        x y l)))
=> ((1) (2 1) (3 2 1) (4 3 2 1) (2) (3 2) (4 3 2) (3) (4 3) (4))

Next: , Previous: , Up: Top   [Index]