guile_002dlog.html 40.4 KB
Newer Older
1 2 3 4 5
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "">
<!-- This is a preliminary manual of guile-log package for guile-2.0
Copyright (C) 2012 Stefan Israelsson Tampe -->
<!-- Created by GNU Texinfo 5.2, -->
7 8 9 10 11 12 13 14 15 16 17 18 19 20
<title>Preliminary Manual: guile-log</title>

<meta name="description" content="Preliminary Manual: guile-log">
<meta name="keywords" content="Preliminary Manual: guile-log">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Index.html#Index" rel="index" title="Index">
<link href="index.html#Top" rel="up" title="Top">
<link href="acumulators_002fgenerators.html#acumulators_002fgenerators" rel="next" title="acumulators/generators">
<link href="umatch.html#umatch" rel="prev" title="umatch">
<style type="text/css">
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit} {font-family: serif} {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal} {list-style: none}

51 52

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="guile_002dlog"></a>
<div class="header">
Next: <a href="acumulators_002fgenerators.html#acumulators_002fgenerators" accesskey="n" rel="next">acumulators/generators</a>, Previous: <a href="umatch.html#umatch" accesskey="p" rel="prev">umatch</a>, Up: <a href="index.html#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="Index.html#Index" title="Index" rel="index">Index</a>]</p>
58 59
<a name="Guile_002dlog"></a>
<h2 class="chapter">2 Guile-log</h2>
<p>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.
62 63 64 65 66 67 68 69 70 71 72 73 74 75
<p>Guile log performs it&rsquo;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.
<p>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&rsquo;s possible to write macros that works in guile log mode.
<p>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&rsquo;s argument which represent the current failure and then execute it&rsquo;s body as the continuation of the algorithm. e.g.
<p>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.
<p>Kanren does one thing pretty well and that is that it can support a notion of tail-call&rsquo;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.
<p>To see how the code is designed we can describe,
<p>the failure thunk semantic,
<code>(lambda () (unwind) (try-alternative-path))</code>
77 78
<p>the continuation lambda (cc)
<code>(lambda (state fail) (execute-next-fkn state fail))</code>
80 81 82 83
<p>To see how they work consider the <code>(&lt;and&gt; (f) (g))</code>, <code>&lt;and&gt;</code> is a directive that represent a sequencing of facts and here the guile-log functions <code>f</code> and <code>g</code> will be tried in sequence e.g.
<pre class="verbatim">  (&lt;and&gt; (f) (g)):
84 85 86
     (lambda (state fail cc)
       (f state fail (lambda (state2 fail2) (g state2 fail2 cc))))
87 88
<p>Likewise an or (e.g. try <code>f</code> and if <code>f</code> fails try <code>g</code>) clause could be defined 
</p><pre class="verbatim">  (&lt;or&gt; (f) (g)):
89 90 91 92 93 94 95 96
    (lambda (state fail cc)
      (let ((fr (gp-newframe)))
        (f state
           (lambda () 
              (unwind fr)
              (g satte fail cc))
<p>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)
99 100 101
<p>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
102 103 104 105 106
<pre class="verbatim">(define-guile-log macro
  (syntax-rules ()
    ((_ (cut s p cc) code ...)
<p>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.
109 110 111
<p>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 <code>(cut s p cc)</code> as a first argument 
112 113
and evaluate that macro. Else the sexp is assumed to be a function and guile log
will put the <code>p</code> and the <code>cc</code> in front and execute that. e.g. to define or a non guile-log macro you typically use,
114 115 116 117 118 119 120 121 122
<p>Kanrens version of or-i and and-i e.g. the interleaving versions of &rsquo;or&rsquo; and &rsquo;and&rsquo;, 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.
<p>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.
<p>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.
<p>Functions <code>(f args ...)</code> in guile-log is defines as
</p><pre class="verbatim">  (define (f s p cc args ...) code ...)
123 124

<a name="Basic-logic"></a>
<h3 class="section">2.1 Basic logic</h3>
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
<a name="index-_003cand_003e"></a>
<a name="index-_003cor_003e"></a>
<a name="index-_003cand_0021_003e"></a>
<a name="index-_003cand_0021_0021_003e"></a>
<a name="index-_003cnot_003e"></a>

<p><code>G.L. (&lt;and&gt; p1 p2 ...)</code>, perform <code>p1</code>, if success then <code>p2</code> and so on.
<p><code>G.L. (&lt;or&gt; p1 p2 ...)</code>, perform <code>p1</code>, if <code>p1</code> fail then backtrack and try <code>p2</code> ...
<p><code>G.L. (&lt;and!&gt; p1 p2 ...)</code>, same as <code>&lt;and&gt;</code> but yields at most one answer.
<p><code>G.L. (&lt;and!!&gt; p1 p2 ...)</code>, the same as <code>(&lt;and&gt; (&lt;and!&gt; p1) (&lt;and!&gt; p2) ...)</code> e.g. at most one answer from <code>p1</code> and at most one answer from <code>p2</code> etc. 
<p><code>&lt;and!&gt;</code> and <code>&lt;and!!&gt;</code>, are useful when we  want to restrict the search space and when a local success correlates to a global one.
<p><code>G.L. (&lt;not&gt; p ...)</code>, successes if <code>(&lt;and&gt; p ...)</code> fail and fails otherwise. In either case the form will always backtrack and no variables will be bound inside this form.
<a name="index-_003cif_003e"></a>
<a name="index-_003cif_002dsome_003e"></a>
<a name="index-_003ccond_003e"></a>
<a name="index-_003cor_002di_003e"></a>
<a name="index-_003cor_002dunion_003e"></a>
<a name="index-_003czip_003e"></a>
<a name="index-_003ccall_003e"></a>
<a name="index-_003c_002f_002f_003e"></a>
<a name="index-_003cupdate_003e"></a>
<a name="index-_003csucceeds_003e"></a>
<a name="index-_003cand_002di_003e"></a>
<a name="index-interleave"></a>
<a name="index-interleave_002dunion"></a>
<a name="index-and_002dinterleave"></a>
<p><code>G.L. (&lt;if&gt; p x)</code>, if <code>p</code> is a success then <code>x</code>, <code>p</code> will only success at most one time.
<p><code>G.L. (&lt;if&gt; p x y)</code>, if <code>p</code> is success then <code>x</code>, else backtrack and use <code>y</code>, the same condition holds on <code>p</code> as the previous version of if.
<p><code>G.L. (&lt;if-some&gt; p x)</code>, the same as <code>(&lt;and&gt; p x)</code>.
<p><code>G.L. (&lt;if-some&gt; p x y)</code>, logicaly the same as <code>(&lt;or&gt; (&lt;and&gt; p a) (&lt;and&gt; (&lt;not&gt; p) b))</code>.
<p><code>G.L. (&lt;cond&gt; (P X) ...)</code>, like the ordinary cond, but using <code>&lt;if&gt;</code> in stead of <code>if</code>
<p><code>G.L. (&lt;or-i&gt; p1 p2 ... pn)</code>, if <code>p1</code> successes and we later backtrack then try <code>p2</code> etc and so on until <code>pn</code> if <code>pn</code> successes and we later backtrack then <code>p1</code> 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.
<p><code>G.L. (interleave l)</code>, the same as <code>&lt;or-i&gt;</code> but with the difference l is a list of lambdas typically made by <code>(&lt;/.&gt; ...)</code>.
<p><code>G.L. (&lt;or-union&gt; p1 ...)</code>, this is like <code>&lt;or-i&gt;</code> but if <code>pk</code> has a success and if, the goal <code>pl</code>, l &gt; k,  succeses like in (&lt;and&gt; pk pl) then we will backtrack, this means that duplication of results is in a sense removed.
<p><code>G.L. (interleave-union l)</code>, see <code>interleave</code>.
<p><code>G.L. (&lt;and-i&gt; p1 p2 p3 ...)</code>, and interleaving! this is an and which will in parctice behave as
</p><pre class="verbatim">  (&lt;and-i&gt; (&lt;or&gt; A B) (&lt;or&gt; C D))
  (&lt;or&gt; (&lt;and&gt; A C) (&lt;and&gt; B C) (&lt;and&gt; A C) (&lt;and&gt; B C))
</pre><p>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.
<p><code>G.L. (and-interleave l)</code>, the same as <code>&lt;and-i&gt;</code> but with the difference l is a list of lambdas typically made by <code>(&lt;/.&gt; ...)</code>.
<p><code>G.L. (&lt;succeeds&gt; p)</code> will try <code>p</code> and if it succeeds undo any bindings and continue.
<pre class="verbatim">G.L. (&lt;zip&gt;  (w        g ...) 
             ((v ...)  h ...) ...)
</pre><p>This is executing n guile-log programs in paralell e.g. when backtracking all
190 191
of the programs are backtracked in one go. The interface to the outside is via
variables <code>w</code> <code>(v ...)</code> 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 <code>&lt;zip&gt;</code> is unwinded and restored. Then the stored representation of <code>w</code> 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.
192 193 194 195 196
<p>Conside the following definition of a function <code>f</code>,
<pre class="verbatim">(&lt;define&gt; (f x n)
  (&lt;or&gt; (&lt;=&gt; x n)
197 198
        (f x (+ n 1))))
199 200 201 202
<p>this function can be used to illustrate the zip by,
<pre class="verbatim">(&lt;run&gt; 5 (x y) 
  (&lt;zip&gt; (x (f x 0)) 
203 204
         (y (f y 1))))

&gt; ((0 1) (1 2) (2 3) (3 4) (4 5))
207 208 209 210 211 212 213 214 215
<p><code>G.L. (&lt;call&gt; ((l x) ...) code ...)</code>, This will call <code>(&lt;and&gt; code ...)</code> and at success it will store the values x ... and then backtrack and unify the copied <code>x</code> to <code>l</code>. At backtracking the state will be reinstated. Use this when you want to avoid side effets when calling a stub.
<pre class="verbatim">(&lt;run&gt; 5 (x y) 
   (&lt;call&gt; ((x y)) (f y 10))
   (&lt;=&gt; y -1))

=&gt; ((10 -1) (11 -1) (12 -1) (13 -1) (14 -1))
<p><code>G.L. (&lt;//&gt; ((fail ((xx x) ... ) code ...) ...) body ...)</code>
218 219
<code>G.L. (&lt;update&gt; (fail vals ...) ...)</code>
This is close to functionality to <code>&lt;zip&gt;</code> 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 <code>(fail ((xx x) ...) code ...)</code>, <code>(&lt;and&gt; code ...)</code> will be evaluated and any resulting values <code>x</code> will be copied and stored in the introduced variable <code>xx</code>. The failure tag can be used to tell guile-log to only backtrack that part of the arm. This is done via a <code>(&lt;update&gt; (fail vals ...) ... )</code>. Typically the first part of the <code>body</code> is a guard that evaluates if they are on synch and if not, say branch <code>f1</code>, needs to update you can do so by <code>(&lt;update&gt; (f1))</code> or <code>(&lt;update&gt; (f1 p))</code> with <code>p</code> a variable containing a failure thunk captured inside the arm. Typically <code>p</code> has before been intrioduced with <code>(letg ((p #f)) co ...)</code> and then <code>p</code> is setted to for example the Current failure thunk <code>P</code> inside the arm.
220 221 222 223 224
<pre class="verbatim">(&lt;run&gt; 1 (x y) 
   (&lt;//&gt; ((f1  ((xx x)) (f x 1))
          (f2  ((yy y)) (f y 10)))
226 227 228 229
      (if (&lt; (&lt;scm&gt; xx) (&lt;scm&gt; yy))
          (&lt;update&gt; (f1))
      (&lt;=&gt; (xx yy) (x y))))

=&gt; ((10 10) (11 11) (12 12) (13 13) (14 14))
<a name="Probing-The-Control-Variables"></a>
<h3 class="section">2.2 Probing The Control Variables</h3>
235 236 237 238 239 240 241
<a name="index-S"></a>
<a name="index-CC"></a>
<a name="index-CUT"></a>
<a name="index-P"></a>
<p>It is possible to probe the curretn variables that is transported behind the sceene, use the syntax-parameters <code>S,CC,CUT,P</code> to reach them inside guile-log code.
<a name="Guarded-variables"></a>
<h3 class="section">2.3 Guarded variables</h3>
243 244 245 246 247 248
<a name="index-_003clet_002dwith_002dguard_003e"></a>
<a name="index-_003clet_002dwith_002dlr_002dguard_003e"></a>
<a name="index-let_002dwith_002dguard"></a>
<a name="index-let_002dwith_002dlr_002dguard"></a>
<p>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.
250 251 252 253 254
<p><code>G.L. (&lt;let-with-guard&gt; wind guard ((var init) ...) code ...)</code>, This construct will bind <code>var ...</code> with init values <code>init ...</code> just as with <code>let</code>. The difference is that we can guard execution of no mutation with e.g.
<p><code>G.L. (guard Lam)</code> e.g. <code>Lam</code> neede to be a guile log closure for 
which the code should be safe to undo and redo if not mutated. <code>wind</code> 
refers to the current wind level and use it in
256 257 258 259
<p><code>(gp-restore-wind state wind)</code>
<p>To restore at the current wind level meaning that any <code>let-with-guard</code>
Stefan Israelsson Tampe's avatar
Stefan Israelsson Tampe committed
 construct inside <code>code ...</code> will be restored but the defined <code>var ...</code> will not be restored, if that is wanted then use <code>(- wind 1)</code> instead.
261 262
<p><code>G.L. (&lt;let-with-lr-guard&gt; wind lguard rguard ((var init) ...) code ...)</code>
263 264
This is very similar to the previous construct but for this ideom we define a
<code>lguard</code> and <code>rguard</code> in stead. That stack space between <code>lguard</code>
265 266
 and <code>rguard</code> is strongly guarded e.g. one can mutate <code>var ...</code> 
inside that space. To the right of <code>rguard</code> the variables are guarded if 
no mutation is done in that space.
268 269
<p><code>scm (let-with-guard s wind guard ((var init) ...) code ...)</code>
<code>scm (let-with-lr-guard s wind lguard rguard ((var init) ...) code ...)</code>
This is scheme macro that will defined scheme macros <code>lguard</code> and 
<code>rguard</code> or just a <code>guard</code>. And the code executed inside them e.g.
273 274 275 276
<p><code>(guard gcode ...)</code>
<p>will be protected accordingly the description above for the guile log macrology
277 278
versions. Finally note that <code>s</code> should be a symbol bounded to the current

<a name="Unify-Constructs"></a>
<h3 class="section">2.4 Unify Constructs</h3>
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
<a name="index-let_003c_003e"></a>
<a name="index-_003c_003d_003e"></a>
<a name="index-_003c_003d_003d_003e"></a>
<a name="index-_003cr_003d_003e"></a>

<p>In the forms below remember to use <code>unquote</code> for forms that need to be scheme evaluated inside the patterns.
<p><code>G.L. (let&lt;&gt; ((m pat val) ...) code ...)</code>, this will pattern-match <code>val</code> using <code>m = (+ ++ - *)</code> and then pattern-match the next and so on and lastly execute a <code>(&lt;and&gt; code ...)</code>.
<p><code>G.L. (&lt;=&gt; X Y)</code>, unifies <code>X</code> and <code>Y</code> with occurs check 
<p><code>G.L. &lt;==&gt;</code>, the same as <code>&lt;=&gt;</code> but using the <code>-</code> matcher in stead of <code>+</code> meaning that no unifying is used.
<p><code>G.L. &lt;r=&gt;</code>, the same as <code>&lt;=&gt;</code> but using <code>++</code> in stead of <code>+</code>.

<a name="variable-binding"></a>
<h3 class="section">2.5 variable binding</h3>
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
<a name="index-_003clet_003e"></a>
<a name="index-_003clet_002a_003e"></a>
<a name="index-_003cletrec_003e"></a>
<a name="index-_003cvar_003e"></a>
<a name="index-_003chvar_003e"></a>

<p><code>G.L. (&lt;let&gt; ((V X) ...) code ...)</code>, Will introduce bindings <code>V</code> with values <code>X</code> and then evaluate code in guile-log mode with an implicit <code>&lt;and&gt;</code>.
<p><code>G.L. &lt;let*&gt;</code>, relates to <code>&lt;let&gt;</code> as <code>let*</code> relates to <code>let</code>
<p><code>G.L. &lt;letrec&gt;</code>, this th <code>letrec</code> version of <code>&lt;let&gt;</code>.
<p><code>G.L. (&lt;var&gt; (v1 v2 ...) code ...)</code>, will make fresh new unify variables <code>v1 v2 ...</code> and use them in a G.L. <code>(&lt;and&gt; code ...)</code> e.g. the same as <code>(&lt;let&gt; ((v1 (gp-var!)) ...) code ...)</code>.
<p><code>G.L. (&lt;hvar&gt; (v1 v2 ...) code ...)</code>, like <code>&lt;var&gt;</code>, but variable identities is located on the heap instead.
<a name="failure-and-cc"></a>
<h3 class="section">2.6 failure and cc</h3>
319 320 321 322 323 324 325 326 327 328 329 330
<a name="index-_003ccc_003e"></a>
<a name="index-_003cfail_003e"></a>
<a name="index-_003ccut_003e"></a>
<a name="index-_003cnext_003e"></a>

<p><code>G.L. &lt;cc&gt;</code>, represent a continuation or success can be used like <code>(&lt;if&gt; P &lt;cc&gt; Y)</code>
<p><code>G.L. &lt;fail&gt;</code>, will issue a failure and start backtracking.
<p><code>G.L. (&lt;fail&gt; p)</code>, will use <code>p</code> as a failure backtracking object.
<p><code>G.L. &lt;cut&gt;</code>, will issue a cut e.g. we will stop backtracking from here on used like <code>(&lt;and&gt; P1 &lt;cut&gt; P2)</code> if <code>P2</code> fails it will typically jump over <code>P1</code> and back to where the cut point is defined.
<code>G.L. (&lt;cut&gt; code ...)</code>, the same as <code>(&lt;and&gt; &lt;cut&gt; code ...)</code>
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351
<p><code>G.L. (&lt;next&gt;)</code>, will backtrack to the next clause in a match (TODO: this has not been tested).
<a name="index-_003cwith_002dfail_003e"></a>
<a name="index-_003cwith_002dcut_003e"></a>
<a name="index-_003cwith_002dcc_003e"></a>
<a name="index-_003cwith_002ds_003e"></a>
<a name="index-_003cpeek_002dfail_003e"></a>
<p><code>G.L. (&lt;with-fail&gt; p code ...)</code>, this will use <code>p</code> as a failure for <code>G.L. (&lt;and&gt; code ...)</code>
<p><code>G.L. (&lt;with-cut&gt; cut code ...)</code>, this will use <code>cut</code> as a cut failure for <code>G.L. (&lt;and&gt; code ...)</code>
<p><code>G.L. (&lt;with-cc&gt; cc code ...)</code>, this will use <code>cc</code> as the continuation.
<p><code>G.L. (&lt;with-s&gt; s code ...)</code>, this will use <code>s</code> as the state.
<p><code>G.L. (&lt;peek-fail&gt; p code ...)</code> This will bind <code>p</code> to the failure thunk at this instruction.

<a name="defining-function-and-matching"></a>
<h3 class="section">2.7 defining function and matching</h3>
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
<a name="index-_003cdefine_003e"></a>
<a name="index-_003clambda_003e"></a>
<a name="index-_003c_002f_002e_003e"></a>
<a name="index-_003crecur_003e"></a>
<a name="index-_003cletrec_003e-1"></a>
<a name="index-_003cmatch_003e"></a>
<a name="index-_003cdef_003e"></a>
<a name="index-_003cdef_002d_003e"></a>
<a name="index-_003c_003cdefine_003e_003e"></a>
<a name="index-_003c_003cdefine_002d_003e_003e"></a>
<a name="index-_003cfuncall_003e"></a>
<a name="index-_003capply_003e"></a>
<a name="index-_003c_003clambda_003e_003e"></a>
<a name="index-_003ccase_002dlambda_003e"></a>
<a name="index-_003c_003ccase_002dlambda_003e_003e"></a>

<p><code>Scm (&lt;define&gt; (f x ...) code ...)</code>, this will define a guile-log function named <code>f</code> with arguments <code>x ...</code> the code will be executed under the G.L environment with an implicit <code>&lt;and&gt;</code> around <code>code ...</code> then <code>f</code> can be used inside G.L. like <code>(&lt;and&gt; (f x y) ...)</code>
<p><code>Scm (&lt;&lt;define&gt;&gt; (f a ...) (p ... code) ...)</code>, default <code>#:mode = +</code>
<p><code>Scm (&lt;&lt;define&gt;&gt; (#:mode mode f a ...) (p ... code) ...)</code>,
<p>This is close to prolog functions. E.g. <code>a ...</code> is the signature, <code>p ...</code> is the pattern that umatches the arguments and if there is a match then <code>code</code> is evaluated in <code>G.L.</code> context. if code failes the next line is tried unless there is a <code>&lt;cut&gt;</code> that forses a return from the function.
<p><code>Scm (&lt;&lt;define-&gt;&gt; (f a ...) (p ... code) ...)</code>, default <code>#:mode = -</code> e.g. non unifying match.
<p><code>Scm, (&lt;def&gt; (f a ...) (p ... code) ...)</code>, 
<p><code>Scm, (&lt;def-&gt; (f a ...) (p ... code) ...)</code>, 
<p>This is as with <code>&lt;&lt;define&gt;&gt;,&lt;&lt;define-&gt;&gt;</code> but if <code>code</code> fails it will issue a cut and leave the function.
<p><code>Scm (&lt;lambda&gt; (x ...) code ...)</code>, this similar like define but an anonymous function.
<p><code>Scm (&lt;&lt;lambda&gt;&gt; (p ... code) ...)</code>, this is anonymous <code>&lt;&lt;define&gt;</code> without explisit arguments and mode. 
<p><code>Scm (&lt;case-lambda&gt; ((a ..) code ...) ...)</code>, th guile-log <code>case-lambda</code> version.
<p><code>Scm (&lt;&lt;case-lambda&gt;&gt; ((p ... code) ...) ...)</code>, this is the <code>case-lambda</code> version of <code>&lt;&lt;lambda&gt;&gt;</code>.
<p><code>Scm (&lt;/.&gt; code ...)</code> This is <code>(&lt;lambda&gt; () code ...)</code>.
<p><code>G.L. (&lt;recur&gt; n ((w v) ...) code ...)</code>, this works like the corresponding named let but in guile-log mode but it defines the loop function <code>n</code> to work inside G.L. and the form itself is in G.L.
<p><code>G.L. (&lt;letrec&gt; ((v x) ...) code ...)</code>, this will bind <code>v ...</code> with <code>x ...</code> in a letrec manner and then execute <code>code ...</code> with an implicit <code>&lt;and&gt;</code> around it.

<p><code>G.L. (&lt;match&gt; [#:mode +] (pat ... code) ...)</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.
<pre class="verbatim">Scm (&lt;def&gt;      (f [#:mode +] a ..) (p ... code) ...))
Scm (&lt;&lt;define&gt;&gt; (f [#:mode +] a ..) (p ... code) ...))
</pre><p>This is a sugar for essentially, <code>(&lt;define&gt; (f a ...) (&lt;match&gt; [#:mode +] (a ...) (p ... code) ...))</code>. The difference is that <code>&lt;&lt;define&gt;&gt;</code> will never backtrack to a new match row and <code>&lt;def&gt;</code> will backtrack to the next matcher if the code part fails.

<p><code>G.L. (&lt;funcall&gt; f . l)</code>, this is actually funcall with the difference is that it will make sure to lookup <code>f</code> if it is a unify variable pointing to a lambda.
<p><code>G.L. (&lt;apply&gt; f a ... l)</code>, this is as with <code>apply</code>, but logic variables will be looked up.
<a name="printing-information"></a>
<h3 class="section">2.8 printing information</h3>
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
<a name="index-_003cpp_003e"></a>
<a name="index-_003cpp_002ddyn_003e"></a>
<a name="index-_003cformat_003e"></a>
<a name="index-tr"></a>
<a name="index-_002agp_002dvar_002dtr_002a"></a>

<p><code>Scm (tr x)</code>, translate unbound variables with a prefix governed by <code>*gp-var-tr*</code> fluid.
<p><code>Scm (tr pre x)</code>, the same as above but using <code>pre</code> as the prefix.
<p><code>G.L. (&lt;pp&gt; x)</code>, this will pretty-print <code>x</code> and print it as a list-version of the code
<p><code>(&lt;pp-dyn&gt; redo-print undo-print)</code>, when the current unify stack backtracks across the current position in the stack it will do a <code>(&lt;pp&gt; undo-print)</code>, it redoes across this dynwind it will pretty-print e.g. <code>(&lt;pp&gt; Redo-print)</code>.
<p><code>G.L. (&lt;format&gt; port str arg ...)</code>, as with format, but under G.L.
<a name="evaluate-scheme-expressions"></a>
<h3 class="section">2.9 evaluate scheme expressions</h3>
431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
<a name="index-_003ccode_003e"></a>
<a name="index-_003ctail_002dcode_003e"></a>
<a name="index-_003cwhen_003e"></a>
<a name="index-if"></a>
<a name="index-cond"></a>
<a name="index-case"></a>
<a name="index-_003creturn_003e"></a>
<a name="index-_003cret_003e"></a>
<a name="index-_003cdynwind_003e"></a>

<p><code>G.L. (&lt;code&gt; code ...)</code>, will execute <code>(begin code ...)</code> as scheme and then success.
<p><code>G.L. (&lt;tail-code&gt; (p cc) code ...)</code>, this will bind the failure thunk <code>p</code> and continuation <code>cc</code> inside <code>code ...</code> which is evaluated under Scm e.g. an implicit begin. It is the scheme code&rsquo;s responsibility to continue using <code>cc</code> or backtrack using <code>p</code>.
<p><code>G.L. (&lt;when&gt; S)</code>, the same as <code>(if S &lt;cc&gt;)</code>.
447 448
<pre class="verbatim">G.L. (if S X)
G.L. (if S X Y)
449 450 451 452
</pre><p><code>S</code> is an ordinary scheme expression and if true will execute <code>X</code> in G.L else <code>Y</code> in G.L. or fail if the scheme expression return <code>#f</code>.
<p>Similarly there is (without <code>=&gt;</code>)
</p><pre class="verbatim">G.L. (when p c ...)
453 454 455
G.L. (cond (p a ...) ...)
G.L. (case a (p a ...) ...)
456 457 458 459 460 461 462
<p><code>G.L. (&lt;return&gt; code ...)</code>, this will do a Scm: <code>(begin code ...)</code> and simply return that form in the guile log pass.
<p><code>G.L. (&lt;ret&gt; val)</code>, the same as <code>(&lt;return&gt; (u-scm val))</code>
<p><code>G.U. (&lt;dynwind&gt; redo-thunk undo-thunk)</code>, 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.
<a name="go-from-scheme-to-guile_002dlog"></a>
<h3 class="section">2.10 go from scheme to guile-log</h3>
464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499
<a name="index-_003cwith_002dguile_002dlog_003e"></a>
<a name="index-_003cask_003e"></a>
<a name="index-_003ceval_003e"></a>
<a name="index-_003crun_003e"></a>
<a name="index-_003cclear_003e"></a>
<a name="index-_003cstall_003e"></a>
<a name="index-_003ccontinue_003e"></a>
<a name="index-_003ctake_003e"></a>
<a name="index-_003cstate_002dref_003e"></a>
<a name="index-_003cstate_002dset_0021_003e"></a>

<p><code>Scm (&lt;with-guile-log&gt; (p cc) code ...)</code>, this will start a guile-log session using failure think p and continuation <code>cc</code> and use <code>p</code> as a cut as well.
<p><code>Scm (&lt;with-guile-log&gt; (cut p cc) code ...)</code>, this will start a guile-log session using failure thunk <code>p</code> and continuation <code>cc</code> and use <code>cut</code> as the cut failure thunk.
<p><code>Scm (&lt;ask&gt; P ...)</code>, will execute <code>(&lt;and&gt; P ...)</code> and if success return <code>#t</code> else if fail return <code>#f</code>
<p><code>Scm (&lt;eval&gt; (v1 ...) code fini cc)</code>, this will bind new variables <code>v1 ...</code> and execute code with failure thunk <code>fini</code> and continuation <code>cc</code> under G.L.
<p><code>Scm (&lt;run&gt; n (v ...) code ...)</code>, bind <code>v ...</code> with variables and execute the code and collect the list of list of bindings of <code>v</code> at success if <code>(v ...) = (w)</code> then it will return a list of values. <code>n</code> is the maximum numbers of success results and skipping <code>n</code> results in no limit on the number of successes.
<p><code>Scm (&lt;clear&gt;)</code>, cleares the stack back to start, use this when finished with <code>&lt;take&gt;,&lt;run&gt;</code> etc.
<p><code>G.L. (&lt;stall&gt;)</code>, this will stall a computation and allow it to continue at the users will and also be able to store the state.
<p><code>Scm (&lt;continue&gt;)</code>, 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:
<p><code>Scm (&lt;continue&gt; n)</code>, with <code>n</code> the number of more successes to returnif we started with <code>(&lt;run&gt; n () ...)</code>.
<p><code>Scm &lt;take&gt;</code>, this is the same as <code>&lt;continue&gt;</code>.
<p><code>Scm (&lt;state-ref&gt;)</code>, this returns a value of the current state for which the system can restore later on.
<p><code>Scm (&lt;state-set!&gt; s)</code>, restores the state represented by the datadtructure <code>s</code> that was produced by <code>&lt;state-ref&gt;</code>.
<a name="Using-logical-variables-in-scheme-mode_002e"></a>
<h3 class="section">2.11 Using logical variables in scheme mode.</h3>
<p>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.
502 503 504 505 506 507 508 509 510 511 512 513 514
<a name="index-_003cscm_003e"></a>
<a name="index-_003ccons_003e"></a>
<a name="index-_003ccar_003e"></a>
<a name="index-_003ccdr_003e"></a>

<p><code>(&lt;scm&gt; x)</code>  returns essentially a scheme representation of <code>x</code> but where logical variables are included as themselves.
<p><code>&lt;cons&gt;, &lt;car&gt;, &lt;cdr&gt;</code>, used exactly as with corresponding scheme functions.
<p>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 <code>*kanren-assq*</code> to 
<code>#t</code>. Doing this will mean that the program almost works as plain kanren.
516 517
<a name="Guile_002dlog-macro-definitions"></a>
<h3 class="section">2.12 Guile-log macro definitions</h3>
519 520 521 522 523 524 525 526 527 528 529
<a name="index-define_002dguile_002dlog"></a>
<a name="index-log_002dcode_002dmacro"></a>
<a name="index-define_002dand_002dlog"></a>
<a name="index-_003cdefine_002dguile_002dlog_002drule_003e"></a>
<a name="index-parse_003c_003e"></a>

<p><code>(define-guile-log name . l)</code>, this works like define-syntax, but it will mark the symbol as a guile-log macro.
<p><code>(log-code-macro x)</code>, marks x as a log-code macro e.g. it will inline it&rsquo;s code into the continuation in an and sequence hence reduce the number of needed closures.
<p><code>Scm (parse&lt;&gt; (cut w fail cc) code)</code>, used to continue guile-log macro
expansion e.g. we could define <code>&lt;and!!&gt;</code> using
</p><pre class="verbatim">  (define-guile-log &lt;and!!&gt;
532 533
     (syntax-rules ()
       ((_ meta arg ...)
        (parse&lt;&gt; meta (&lt;and&gt; (&lt;and!&gt; arg) ...)))))
<p>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 <code>parse&lt;&gt;</code>.
538 539 540 541 542 543 544 545 546 547
<p><code>&lt;define-guile-log-rule&gt;</code>, this is a fast one-liner version of define-guile-log and throws one into the <code>G.L.</code> context of the producer without explisitly using <code>(cut s p cc)</code>.
<p><code>Scm (define-and-log name . l)</code>, used in and log context to get the next lines in the <code>&lt;and&gt;</code> into the macro. the match matching signature in the macro is 
<p><code>(f (cut s p cc) (f . l) e ...)</code>, for a function like signature and
<p><code>(f (cut s p cc) ()      e ...)</code>, for a symbol like signature.
<p>An example using this is to for example have constructs that avoids nesting.
For example we can define <code>G.L. (&lt;v&gt; v ...))</code> through,
549 550
<pre class="verbatim">(define-and-log &lt;v&gt;
  (syntax-rules ()
552 553
    ((_ w (&lt;v&gt; v ...) e ...)
     (&lt;let&gt; w (v ...) e ...))))
555 556 557 558 559
<p>And we would use it as
<pre class="verbatim">(&lt;define&gt; (f x)
  (&lt;v&gt; y z)
  (&lt;=&gt; x (y . z))
560 561 562
  (g y z))

Stefan Israelsson Tampe's avatar
Stefan Israelsson Tampe committed

564 565
<a name="Controling-the-kind-of-variable-binding-used_002c-kannren-assq_002c-or-a-prolog-stack_002e"></a>
<h3 class="section">2.13 Controling the kind of variable binding used, kannren assq, or a prolog stack.</h3>

567 568 569
<a name="index-_003clogical_002b_002b_003e"></a>
<a name="index-_003clogical_002d_002d_003e"></a>
<a name="index-_002akanren_002dassq_002a"></a>

571 572 573 574 575 576 577
<p><code>(&lt;logical++&gt;),(&lt;logical--&gt;)</code>, turn on/off the usage of assq logical variables. Works by introducing a 
<p>To make the whole session in kanren assq mode one can set *kanren-assq* to #t.
</p><pre class="verbatim">(&lt;run&gt; 1 (x) (&lt;=&gt; x 1) (&lt;pp&gt; (pk S)))
;;; ((&lt;gp-stack&gt; 5404676))

579 580
(&lt;run&gt; 1 (x) (&lt;logical++&gt;) (&lt;=&gt; x 1) (&lt;pp&gt; (pk S)))
;;; ((&lt;gp-stack&gt; 5404676 (&lt;#0 : 1&gt; . 1)))

582 583
(&lt;run&gt; 1 (x) (&lt;logical++&gt;) (&lt;var&gt; (y) (&lt;=&gt; y 1) (&lt;pp&gt; (pk S))))
;;; ((&lt;gp-stack&gt; 5404676 (&lt;#0 : 1451764&gt; . 1)))
<p>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 <code>&lt;#0 : 1&gt;</code>. Also note in the last example how <code>&lt;#0 : 1451764&gt;</code> indicates that it has been allocated on the heap in <code>logical++</code> mode.
587 588
<a name="Returning-multiple-values_002e"></a>
<h3 class="section">2.14 Returning multiple values.</h3>
590 591
<a name="index-_003cvalues_003e"></a>
<p><code>(&lt;and&gt; (&lt;values&gt; (v ...) (f args ...)) ...)</code>
This is a way to define multiple values <code>v ...</code> as a return from <code>f</code>. For this to work we need to add <code>(&lt;cc&gt; x ...)</code> at the logical end of the definition of the functione.
593 594 595
</p><pre class="verbatim">(define-syntax s-pair!? 
596 597 598 599 600 601 602 603 604
  (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 (&lt;pair?&gt; s p cc x)
606 607 608 609 610
  (let ((ss (s-pair!? x s)))
    (if ss
        (cc ss p)

611 612 613
(&lt;define&gt; (!car! x)
  (&lt;pair?&gt; x)
  (&lt;cc&gt; (&lt;car&gt; x)))
614 615 616

and use it as,

617 618
(&lt;run&gt; 1 (x y) (&lt;=&gt; x '(1 2)) (values (z) (!car! x)) (&lt;=&gt; y z))
=&gt; (((1 2) 1))
<a name="Acumulators"></a>
<h3 class="section">2.15 Acumulators</h3>
622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640
<a name="index-_003cfold_003e"></a>
<a name="index-_003cfold_002dstep_003e"></a>
<a name="index-_003cfix_002dfold_003e"></a>
<a name="index-_003cfix_002dfold_002dstep_003e"></a>

<p>These constructs will accumulate all possible values of a construct.
<p><code>G.L. (&lt;fold&gt; kons knil Lam X L)</code>, This will initiate an accumulator to <code>knil</code> and then use <code>kons</code> as the acumulating function. The guile log closure  <code>Lam</code> is executeded and <code>X</code> will represent the result that will be accumulated. The final result is then added to <code>L</code>.
<p><code>G.L. (&lt;fold-step&gt; kons knil Lam X L)</code>, the semantic is similar to <code>&lt;fold&gt;</code>, but the form will at each iteration succeeds with <code>L</code> bound to the current accumulator value.
</p><pre class="verbatim">(&lt;define&gt; (f x n m) (if (&lt; n m) (&lt;or&gt; (&lt;=&gt; x n) (f x (+ n 1) m))))

(&lt;run&gt; * (l) (&lt;var&gt; (x) (&lt;fold&gt; + 0 (&lt;/.&gt; (f x 0 10)) x l)))
=&gt; (45)

(&lt;run&gt; * (l) (&lt;var&gt; (x) (&lt;fold-step&gt; + 0 (&lt;/.&gt; (f x 0 10)) x l)))
=&gt; (0 1 3 6 10 15 21 28 36 45)
642 643 644 645 646 647 648 649 650 651 652 653 654 655
<p><code>G.L. (&lt;fix-fold&gt; kons knil Lam X Y L)</code>, 
<p><code>G.L. (&lt;fix-fold-step-&gt; kons knil Lam X Y L)</code>, 
<p>this is as with <code>&lt;fold&gt;</code> etc, but the acumulation is done for each fixed <code>Y</code>.
</p><pre class="verbatim">(&lt;define&gt; (f x n m) 
   (if (&lt; n m) (&lt;or&gt; (&lt;=&gt; x n) (f x (+ n 1) m))))

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

659 660 661 662
(&lt;run&gt; * (l) 
   (&lt;var&gt; (x y) 
     (&lt;fix-fold-step&gt; cons '() 
        (&lt;/.&gt; (f x 0 5) (f y 0 (&lt;scm&gt; x))) 
        x y l)))
=&gt; ((1) (2 1) (3 2 1) (4 3 2 1) (2) (3 2) (4 3 2) (3) (4 3) (4))
666 667 668 669 670 671
<div class="header">
Next: <a href="acumulators_002fgenerators.html#acumulators_002fgenerators" accesskey="n" rel="next">acumulators/generators</a>, Previous: <a href="umatch.html#umatch" accesskey="p" rel="prev">umatch</a>, Up: <a href="index.html#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="Index.html#Index" title="Index" rel="index">Index</a>]</p>

672 673

674 675