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
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.
(f args ...) in guile-log is defines as
(define (f s p cc args ...) code ...)
G.L. (<and> p1 p2 ...), perform
p1, if success then
p2 and so on.
G.L. (<or> p1 p2 ...), perform
p1 fail then backtrack and try
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
<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
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
G.L. (<or-i> p1 p2 ... pn), if
p1 successes and we later backtrack then try
p2 etc and so on until
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
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
(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
(<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
l. At backtracking the state will be reinstated. Use this when you want to avoid side effets when calling a stub.
(<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.
(<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))
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.
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.
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
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
rguard in stead. That stack space between
rguard is strongly guarded e.g. one can mutate
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
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
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
m = (+ ++ - *) and then pattern-match the next and so on and lastly execute a
(<and> code ...).
G.L. (<=> X Y), unifies
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
G.L. (<let> ((V X) ...) code ...), Will introduce bindings
V with values
X and then evaluate code in guile-log mode with an implicit
G.L. <let*>, relates to
let* relates to
G.L. <letrec>, this th
letrec version of
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.
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.
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
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
Scm (<<case-lambda>> ((p ... code) ...) ...), this is the
case-lambda version of
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.
Scm (tr x), translate unbound variables with a prefix governed by
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.
G.L. (<format> port str arg ...), as with format, but under G.L.
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
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
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
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.
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
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
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
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
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
#t. Doing this will mean that the program almost works as plain kanren.
(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
(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
<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))
(<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.
(<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
(<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.
(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))
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
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.
(<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
(<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))