This is a preliminary manual of guile-log package for guile-2.0 Copyright © 2012 Stefan Israelsson Tampe

Guile Log
*********

Documentation for the Guile-Log Logic Programming Environment for Guile 2.0 v0.4

Overview
********

umatch in (logic guile-log umatch) represent the lower level routines implemented in C code and loaded by that module. A matcher targeted to be used in code handling the unify variables is defined here as well.

umatch
======

umatch is a matcher that derives from (ice-9 match) with some extra features that relates to unifying variables. The usage is

  (umatch [#:status s] [#:mode *] [#:status #f] [#:tag w] [#:name "anon"] [#:raw #f] (m ...)
     (pat ... code)
     ...)

   with pat utilizing:

     (p . q) _ , and set! get! #(...) = `

   form ice-9/match plus ',' and the following symbols should not be used in
   fuctional position:

      or not cond ... ___ ,@ *** <> arguments $
',' can be used to quote a variable from the outside of the match

(set! s) will define a setter s that can be used in e.g. (<and> (s 1) ...), for <and> refere to guile-log.

(get! g) will define a getter g used with an argument representing the current state like e.g. (g S), with S beeing define in the guile-log section.

[#:mode +] is used to set the kind of matcher that is initially valid it can be either of + ++ - * (see below for an explanation of these)

[#:tag w], that tag that related to backtracking to the next matcher. e.g.

  (umatch #:tag next ('(1 2 3))
      ((x y z) (if (number? x) (next) x))
      ((x . l) l))
  => '(2 3)

[#:name "anon"], this is used when outputting error messages

[#:raw #f], do not use this, this + #:mode + is the same as #:mode ++

[#:status #f], This is where the state variable should be it must be a variable which contains the current state at the entering of the matcher. This syntax symbol is resetted with new state at unifications and similar constructs which may enter new information onto implicit stack or explicit state info.

(m ...), is a sequence of elements to be matched in parallel

(pat ... code), if pat is a pattern to use to match a m the last form is the code to execute if all patterns matches.

Directives
==========

The following feature is added to the ice-9 matchers

  * (+ p ...) will match (p ...) with the framework +

  * (+ + p) will match p       with the framework +

The frameworks are,
  (*   (car    cdr    pair?     null?       equal?         id)))))
  (+   (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify!      gp-lookup))
  (+r  (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify!-     gp-lookup))
  (+r  (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify!-     gp-lookup))
  (++  (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify-raw!  gp-lookup))
  (+r  (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify!-     gp-lookup))
  (++r (gp-car gp-cdr gp-pair!? gp-null!?   gp-unify-raw!- gp-lookup))
  (-   (gp-car gp-cdr gp-pair?  gp-null?    gp-m-unify!    gp-lookup))

Toe explain more,

  * * : the usual list framework

  * + : (match (+)  (1 v) (w 2)) matches and v=2,w=1 with a recurrence check e.g. if any self referenceing will appera in the matcher then the match fails. This is the safe way to do a unifying match.

  * ++ : (match (+)  (1 v) (w 2)) matches and v=2,w=1 with no recurrence check e.g. if any self referenceing will appera in the matcher then the match will not fails. This is the unsafe way to do a unifying match because it may get into infinite recursion.

  * ++ : (match (++) (1 v) (w 2)) matches and v=2,w=1 without a recurrence check. Do this with care cause cyclisity is unsupportand and can lead to a blowup of the stacks.

  * - : (match (-)  (1 (v = 2)) ((w = 1) 2)) matches unify variable v = 2 at the start e.g. unify variable is looked up but never bounded.

Finally the r modifications are primitive versions that are used sometimes.

Also unquote directive is used in the matcher to signal an evaluation e.g. in
  (umatch (x)
    ((a ,(+ z w)) a))
     (+ z w)))
(+ z w) will be first evaluated and then used in matching.

and can be used and just as expected from ice-9 match. or also works but any successful match will not backtrack.

low level api
=============

in (logic guile-log umatch) a large set of unify constructs are loaded from a library defined in C, this api are,

stack banks
===========

The work is done with state objects containing appropriate stacks, rewind information and the assoq list of bindings. You will have the notion of a current 'gp' state that is a fluid representing the current stack in use. Also there is a *current-state* fluid that holds the current assoq binding list/tree. You can create new stacks. The setup can be thread safe in the meaning that if you try to set a logic variable that is not associated to the supplied stack then a binding will be done by logically consing it to a datastructure that has the same functional behavior as an assoq list on the supplied state data and returned. This means that a large class (but certainly not all) of interop issues between multiple threads is solved. A state or stack datastructure will hold information on what thread-id it belongs and also have a unique id. The stack consists of actualy 4 stacks, one control stack (nc) one datastack (ns) and a stack of allocated cons cells (ncs) and one that holds the equivalent of fluids and guards. The control stack will contain unwind information, dynwinds and binding information. The cons stack is not used currently, it can be used to implement closure objects that is created from the stack in stead of the heap, we currently do not use this becuase other overhead is more significant currently e.g. the guile call overhead to C-funcitons. The dynstack is specaial in that its data is recreated at each wind. It represent the expensive winding that essentially originates from the guards and from the equivalent of fluids. Note that multiple reinstation of the other stacks are really cheap in that it does no consing, by allowing e.g. gp-fluid-set! we must pay with copying the stack at each wind, now by separating the small dynstack from the rest we get an important optimization.

*gp*, fluid that holds the current gp-stack *current-stack*, fluid that holds the current assoq (gp-make-stack id thread-id nc ns ncs) Allocate a new state datastructure with identity number id, thread identity number thread-id and the sizes of the different stacks. Also it will be stupped so it can be used to unwind to e.g. w can reset the stack to the initial state calling gp-unwind with it.

(gp-clear state), Reset the state to it's initial setup.

Redo safe variables and redo safe parameters.
=============================================

A redo safe variable is a ordinary scheme variable object or fluid object that has the property that its state will be intelligently stored and retrieved under various premisses. Essentially if there is no mutattion further down the stack we can use the guard version. Else between lguard and rguard the variable is guaranteed to have restorage property independent of mutation or not.

(gp-undo-safe-variable-guard var kind s (gp-undo-safe-variable-lguard var kind s (gp-undo-safe-variable-rguard var kind s

var is a guile variable or fluid. We have a control parameter kind which must not be a GP variable. and s containes the guile-log assoq state.

At rewind in context K, the rules for restoring the state is as follows

  * kind = #t, restore the state.

  * kind = #f, do not restore.

  * K = #t, restore the state.

  * K = #f, do not restore.

  * kind, number and K, number Then we will restore the state if K <= kind.

  * else do not restore the state.

Managing stack frames
=====================

Stack has a stack pointers to undo stacks a data stack and a cons stack and dynstack, by walking up and down these stacks we can recreate a state. The most lightweight way of winding is to use gp-newframe and gp-unwind where you can only go to a previous stack point stored by gp-newframe and doing that the system forgets everything. This is fast and with no memory overhead. The other mode of operation using gp-store-state,gp-restore-state and gp-restore-wind will go the full way and keep everything in memory until you drop and references to the returned state information and the gc can kick in at recollect the data. gp-store-state will make a state data structure suitable to be for this mode of operation and gp-restore-state will restore the infromation either backward or forward in time. Then the setup will be precisely as when the store operation was issued. To note here is that sometimes you would like to use the store and restore operation in a mode that follows a calculation like with the interleaving constructs for this operation it is very nifty to have global variables like if they lived on the heap to implement the logic. The downside is that with heap objects you typically cannot restore a state if you would like to do that. Guile log has a nifty framework to define variables that behaves just like these heap variables but with the difference that they are automagicaly restored when the user issues the gp-restore-state. In order for this to work we use gp-restore-wind internally when we store and restore information as we follow an algorithmic calculation path.

(gp-newframe s), returns the current frame incorporated in a state variable state of the stack in order to be able to backtrack.

(gp-unwind s), backtrack to state represented by s that should have been returned by (gp-newframe s) e.g. a state data structure.

The next two command is mirroring the two commands above. But for these we don't impose the restriction to only go back in time, we can freely restore a state. Memory wise and performance this is heavier. But to note is that we do tree compression e.g. we try to reuse as much data as possible.

(gp-store-state s) -> state, Gives a state that can be used to restore a state, this makes the unify stack act well together with call/cc constructions or using continuation closures e.g. it is possible to do continuations with these prolog stacks. Note that this is a very effective storage mechanism, basically the continuation is stored in a tree like structure.

(gp-restore-state state), Restore a state that is saved by gp-store-state

(gp-restore-wind state wind), the same as above, but they will not change the dynamic globals e.g. guarded variables to the old state depending an the algorithm described in teh beginning of this section.

The gp fluid
============

For a guile variable or more prefereble (it is thread safe) for a fluid we can model it as a guile fluid but living on the guile-log stacks in stead. For this to work just use variable-ref, variable-set!, fluid-ref, fluid-set! and

(gp-fluid-set var val) This will bind var to val for the rest of the guile log stacks, e.g. similar to guile's with-fluids.

The guile log variables
=======================

(gp-var!), generate a new unify variable. E.g.
  scheme(guile-user)> (define a (gp-var!))
  scheme(guile-user)> (define b (gp-var!))
  scheme(guile-user)> a
  $7 = <#0>
  scheme(guile-user)> b
  $8 = <#1>
  scheme(guile-user)> (gp-unify! a b)
  $9 = #t
  scheme(guile-user)> a
  $10 = <#1>
  scheme  (guile-user)> b
  $11 = <#1>

If executed under logical kanren assq feature then the variable is created on the heap, else it is created on the stack.

(gp->scm x s),  Take a unify variable and a state and turn it into a list representation, variables is transfered as is.

  scheme(guile-user)> (u-set! a '(1 2))
  scheme(guile-user)> a
  $17 = <#gp (1 2)>
  scheme(guile-user)> (gp->scm a)
  $18 = (1 2)

(gp-budy x), it is possible to pair variable if you do
  (let ((x (gp-var!))
        (y (gp-var!)))
    ...)
Then inside ...  y = (gp-budy x).

(gp-var? x s), #t if x is a not bounded unify variable. s is the current state.

(gp-lookup x s) If x is a unify variable it tries to find the element it points at using state information in s. If it is a unify variable that is returned, if it's a scheme object that is returned If it's a unify cons, that is returned.

(gp-var-number x), the variable number identifying a gp variable.

(gp-set! v a s) -> s, set looked up unify variable v to a. using state s e.g. v is looked up until the last variable pointing to a scheme variable. It may change the state and a new state is returned.

guile log pairs
===============

(gp-cons! x y), makes a unify cons variable out of x and y. To note here is that these conses are faster to allocate and they work well with rebounding later on and backtracks correctly.

(gp-pair? x s) -> s, checks to see if x is a pair or a unify pair not a variable is will retrun false- Here the returned state is always the same as the input. x is assumed to have been looked up.

(gp-car x), takes the car of a unify pair or ordinary pair. x is assumed to have been looked up.

(gp-cdr x), takes the cdr of a unify pair or a ordinary pair x is assumed to have been looked up.

unifying
========

(gp-unify! x y s) -> s or #f, s if x and y unifies with a recurrence check e.g. loop detection. #f if they do not unify (note that although this is false variables could have been unified so #f is usually followed by a (gp-unwind Frame)) e.g.
  (let ((Fr (gp-newframe)))
     (if (gp-unify! x y)
          #t
         (begin (gp-unwind Fr) #f)))

(gp-unify-raw! x y s) -> s or #f, the same as gp-unify! but now loop detection e.g. we can end up in an infinite c-recursive loop and the stack will eventually be consumed and an error reported.

(gp-m-unify! x y s) -> s or #f, the same as gp-unify! but now variables are not bounded, if x is a variable then y must be the same variable and vice verse in order to unify.

guile log fluids guile log dynwinds
===================================

Fluids functions does not change the stack parameters it is a buggy interface because the kind of stack sign should be in the state parameter that should be used as well as input.

(gp-make-var),(gp-make-var init) makes guile log variable on the heap and an optional init value, init.

(gp-var-set! v x) set! a guile-log variable without backtracking !danger! do not use this anywhere else then a before a first gp-var-set have been issued on the variable.

(gp-var-set v x) set a guile-log variable with backtracking the guile stack is forced to be used to handle the backtracking.

(gp-var-ref v) reference a guile-log var.

(gp-dynwind Redo Do Undo) a similar tool as the dynwind construction but this one follows the current bank stack and not the call stack. Again

These two should only be used by experts. (push-setup thunk), this will push a thunk on the push stack, a setup is code that is run after the winding has ben done, typically this is used inside a dynwind.

(que-setup thunk), this will que thunk on the setup que  that is executed after the winding of the stack have been done.

N.B. the setup stack is executed before the setup que.

Kanren logical variables support
================================

In kanren the interpretation of a variable is goverend in a state that behaves as an assq list. To find a value of a binding that list are searched for a binding. now this datastructure need not be a assq list, only sematically behave like it and that it need to be functional. The benifit is mainly that multiprocessor support is trivial by having such a feature. The intention is to execute the usage seamlessly in the background but uit can be beneficial to force the usage of them and therefore there is a public interface with primitives.

SCM (use-logical) SCM (leave-logical) To mark that the engine enters a region where it uses kanren logical structure excecute the use-logical function, and to leave use the other form. These codes will add guards on the stack as well in order for it to work seamlessly with regards to backtracking and state restorage.

(gp-stack-set! x v s) -> s, forces the usage of the stack as a method of doing an undoable set.

spurious commands
=================

(gp-print x) debug tool, prints out information of the internal representation of x.

(gp-printer port x), the printer used to print unify variables

(gp-copy x) Makes a copy of x, but copy the references to variables and not the variables them self

(gp-get-stack), a debug tool. Yields the control stack containing undo information.

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 ...)

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))

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.

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.

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 +.

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.

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.

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.

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.

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.

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>.

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.

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))

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.

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))

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))

Acumulators/generators
**********************

In the guile-log chapter we defined the basic framework to fold a sequence of solutions into a variable. With this we can support e.g prolog's bagof and similar constructs. In the module (guile-log logic collects), we have defined a few specialisations of the fold operator in order to standardize these common abstractions.

Acumulators API
===============

To explain the Api we have a gl-thunk, e.g. a guile-log lambda with zero arguments. it, will be the pattern to store. when it successes typically this variable will be copied and added to the resulting data structure which is list, sum, .... There is a possibility to keep some elements fixed and this is the -2 forms with the variable fixed naming the variable that needs to be fixated. e.g. first all solutions for the first found representation of the variable fixed will be found and added, then the then all solutions with the next found variant of the fixed will be used and so on, very much like how bagof in prolog is working. The -step versions of the acumulators will produce produce all the intermediate acumulator solutions.

The following forms will cons all solutions to a list e.g. prodice lists in reverse order.

G.L. (<collect>        gl-thunk it list)

G.L. (<collect-2>      gl-thunk it fixed list)

G.L. (<collect-step>   gl-thunk it list)

G.L. (<collect-step-2> gl-thunk it fixed list)

--------------------------------------------------------------------

The following forms will sum all solutions.

G.L. (<collect>        gl-thunk it sum)

G.L. (<collect-2>      gl-thunk it fixed sum)

G.L. (<collect-step>   gl-thunk it sum)

G.L. (<collect-step-2> gl-thunk it fixed sum)

-------------------------------------------------------------------

The following forms will take the product of all solutins

G.L. (<collect>        gl-thunk it prod)

G.L. (<collect-2>      gl-thunk it fixed prod)

G.L. (<collect-step>   gl-thunk it prod)

G.L. (<collect-step-2> gl-thunk it fixed prod)

--------------------------------------------------------------------

The following forms will take the max of all solutions.

G.L. (<max>        gl-thunk it max)

G.L. (<max-2>      gl-thunk it fixed max)

G.L. (<max-step>   gl-thunk it max)

G.L. (<max-step-2> gl-thunk it fixed max)

--------------------------------------------------------------------

The following forms will take the max of all solutions.

G.L. (<min>        gl-thunk it min)

G.L. (<min-2>      gl-thunk it fixed min)

G.L. (<min-step>   gl-thunk it min)

G.L. (<min-step-2> gl-thunk it fixed min)

--------------------------------------------------------------------

The following forms will take the and of all operations returning the last one as a solution.

G.L. (<soland>        gl-thunk it and)

G.L. (<soland-2>      gl-thunk it fixed and)

G.L. (<soland-step>   gl-thunk it and)

G.L. (<soland-step-2> gl-thunk it fixed and)

--------------------------------------------------------------------

The following forms will take the or of all operations returning the first solution.

G.L. (<solor>        gl-thunk it or)

G.L. (<solor-2>      gl-thunk it fixed or)

G.L. (<solor-step>   gl-thunk it or)

G.L. (<solor-step-2> gl-thunk it fixed or)

Local Non backtracking Genrators API
====================================

This tool is found directly in the module (logic guile-log),

G.L. (<with-generators> ((var init) ...) code ...), This will bound the variables var ... initiated to init ... inside code ....

These variables can then be changed by using set! and if the updating is functional, the state of the variables will be managed and store and restore will be managed in such a way that jumping below the initiation with <with-generators> and back will produce the same values, but inside this form it will not be restored to the old value. Especially a simple generator can be applied by using,

G.L. (<next-generator-value> sum var val), e.g. perform var <- (sum var val) each time this line is executed and no backtracking will be done. --------------------------------------------------------------------

Postpone, a framework for postponing guile-log evaluations.
***********************************************************

This code is available from (logic guile-log postpone) You may have noticed that guile log is a framework to do tree searches to meet a certain criteria and during the path in the tree create data structures that are able to undo and also redo it's state. Most people when approaching this will sooner or later be bitten by the NP hardness of many interesting problems. The solution might then be to try intelligent guesses in which branch the gold is hiding. What one would like to do is try a set of branches, freeze the different states and at that point create some sort of index that represent the likelihood of the gold lying buried beneath. Then an overall global decision can be taken and only the most promising paths will be further examined. It is for this use case the following system is constructed. Postpone mix well with the rest of prolog, but especially the <zip>, forms might behave unexpectedly due to teh postpone mechansim interfering with the synch and produce bad result.

Api.
====

G.L. (postpone val power)
G.L. (postpone-frame limit fact maxsize)
To be able to postpone we must have a baseline from which we will base our restarts e.g. postpone-frame. The postpone command will basically evaluate val and postpone if it's larger then a certain limit that is governed by an initial value limit and fact - a factor that adds to the limit each postpone turn. The power is the sorting index used to manage a list of possible restarts for and this list is sorted so that we at restarts will try to use maxsize first elements of the list. The list is never larger then 10 * maxsize.

Make sure to use positive values for the power, value. If all postponing functions leave a negative value, then postpone-frame will fail. This is useful in tabling where this teqnicque is used to produce all possible solutions (recursive application as well) for a given input until a fixpoint with no more new solutions are reached.

Dynamics
********

The main work has been to enable delimeted continuation in guile-log. To do this is not easy because we want to support interleaving, postponing, store/restore, zip like construct as well as acumulation all in one theoretically and computationally sound environment. It's not just to store and restore a stack as in scheme. Guile log is targetted to be effective reinstating states and keep a huge number of states in memory, to do this we note 1. we store a tree of states to compress the overall memory need and keep consing to a lower degree. 2. reinstating state information multiple times is cheap because there is no consing the second time for the main stack (we keep another dynamic stack where we need to reinstate new datastructures at each reinstation. All this means that we must reinstate the same datastructure. Also generally the cc and p fields at the in and out of the generated continuation needs to be patched and in order to support all of guile-log seamlessly one need to make use of guarded variables. In all stackless dynamics like kanren employ is not well suited because this is a nonfunctional modification. The resulting continuation will work almost as one would expect, but one can imagine problematics if the evaluation of the continuation returns a failure thunk intended to jump back into the continuation without normal backtracking. This is not a serious flaw and we do not try to add functionality to support this more than that we would implement new versions of the frameworks, looking at that source code it would be clear how to proceed.

Api
===

G.L. (<prompt> tag data thunk handler), This will evaluate the guile-log version of a thunk and continue just as with any other thunk. But if an abort with a tag that matches the prompt tag or if the prompt tag is true, any abort will be catched. data will be guile-log dynamic data that will be captured at the abort and transferd back to the prompts context. The handler is of the form

(handler tag next kk args ...), tag is the abort tag, next is a guile-log thunk, that evaluated will try the next handler in the stack. kk is a meta continuation. typically to get the continuaiton k, you do

(let ((k (kk))) ...)

But we can also do

(let ((k (kk new-handler))) ...), in cases where one want to use a new handler for the continuation which is a common pattern in producing generators. Technically this is not needed, but doing so means the difference between dog slow code and performant code. Finally we can use,

(let ((k (kk tag new-handler))) ...), with the obvious interpretation. The return continuation k will have a few arguments that represents the arguments used in the continuation of the abort.

The arguments (args ...) are the arguments returned by the abort.

G.L. (<catch> tag data thunk handler) this is exactly the same interface as with prompts, but with the difference that the handler has the form

(handler tag next args ...), This is the same as prompts, but does not have any continuation argument. This ideom has significantly lower overhead.

G.L. (<abort> tag lambda args ...), will look for a handler matching the tag and then call the handler with (args ...), see the doc for <prompt>. The lambda should be a guile-log lambda and defines the signature that the continuation inside the handler have.

Example
=======

(use-modules (logic guile-log))
(use-modules (logic guile-log umatch))

(<define> (f)
  (<values> (i x) (<abort> 'tag (<lambda> (i x) (<cc> i x))))
  (<or-i>
   (<or> (<=> x i)      (<=> x ,(+ i i)))
   (<or> (<=> x ,(- i)) (<=> x ,(- (+ i i))))))

(<define> (test x y)
  (<prompt> 'tag #f f
    (<lambda> (tag next kk)
        (<let> ((k (kk)))
	   (<zip> (x (k 1  x))
		  (y (k 10 y)))))))

(<run> 10 (x y) (test x y))

--> $1 = ((1 10) (-1 -10) (2 20) (-2 -20))

Dynamic functions
*****************

An interesting category of functionality in prolog is their dynamic function framework. They are a generalization of databases and allow to do matching in a scalable manner through indexing. Guile log also support a full indexer for a simplified matcher. And for all matched clauses they will be executed in order acording to how the database is setuped. One can add clauses to the head or to the end, remove clauses according to a pattern and also store states for later rewinding. The state guarding mechanism is either cheap (weak) e.g. it will not remember states as long as the action is above in the stack, else if it backtracks below the stack, state will be stored and restored at reentrence. We also support strong state storage at e.g. postpone support.

To use the api use (use-modules (logic guile-log functional-database)).

Api
===

SCM (define-dynamic f), this will make a dynamic function object and bind it to f

G.L. (<push-dynamic> f lambda-dyn), push a match onto the head of dynamic function f. lambda-dyn is a special lambda typically created through,

SCM (<lambda-dyn> pat ... code), here pat ... will be simplified patterns only supporting quote,unquote all else directive is not allowed. code is evaluated in guile-log mode.

Similarly we can add code to the end of the dynamic function, e.g.

G.L. (<append-dynamic> f lambda-dyn).

Also to remove elements one can use,

G.L. (<remove-dynamic> (f a ...)), where f is the dynamic function and a ... the patterns for the arguments that, which matches will be retracted.

The previous set of API is typically what you get to use in prolog. The downside is that they posses problem w.r.t. leaking data and therefor the next ideom is preferable to use in order to make sure both that one undo any changes to the dynamic variable, but also at reinstation of a state inside the form, it will resore to the same state as when control left the inner of the ideom e.g. The design is to favor fast lookup and adding and removing information is a bit expensive.

G.L. (<with-dynamic-functions> (f ...) code ...), for this form f ..., will be weakly guarded throughout the form e.g. if control leaves the form  then the state is stored if needed and at reinstation of state inside code ..., the old state of the dynamic variable will be reinstated. But inside the form state of the dynamic functions is not saved or restored.

A stronger form of guard can be used in case one would like to make sure that the dynamic functions state can be reinstated in case of e.g. postpone is used, then use,

G.L. (<guard-dynamic-functions> (f ...) code ...),

Finally the last section conserns the ability to compile the dynamic function for as fast lookup as possible, use

G.L. (<dynamic-compile> f ...), comiles the dynamic functions f ... for fast lookup. This ideom takes time and if used freely can cause a high memory consumption.

Memoizing
*********

it is possible to perform most operation in guile-log using ratioanl datastructures, The printer supports printing recursive data structures in guile-log and prolog. Generally the handling of rational datstructures are expensive, therefore mechanisms to turn this feture on and off have been designed. Yoy may use the .rec interactive directive. Or you can use the -functorize(recursive) functor to tell that the function shall be evaluated with recursives on. Or in code use

prolog recursive(Code).

Memoizing
*********

In prolog there is a notion of memoizing datastructures, guile-log elaborates on these datastructures somwhat and also define structures that can work as a sledgehammer in order to handle recursive datastructures, also memoizing somthing that is wrong means that the memoizer in the most general situation needs to backtrack, there is possibility however to cut corners in e.g. algorithms where there is no state storage or where there is no backtracking. The interface is as follows, memo, memo-rec, tabling can all be use as functors in guile log prolog with he help of functorize wrapper.

G.L. (memo     fkn arg ...) This will assume that fkn only have one result and uses simplified logic to memoize the result and when similar args is available then it will use the old value.

G.L. (memo-rec fkn arg ...) The same as above but in stead the function can call itself this means that
(<define> (ff x) (f x))
(<define> (f z) (memo-rec ff x))
Will not diverge and yield a solution.

G.L. (tabling fkn arg ...), as above but it can handle many solutions for the same arguments at the beginning of the funciton, this function also behaves well for recursive definitions and will cut the tree search and yield mostly recursive or rational datastructures. This function is not perfect and the same answer might be given multiple times, there is no garantee

Scm (rec f guard action) This creates a guile log goal funciton that modifies f, f is taking the same vars as the lambda, and make sure to call action if it sees the an old term that have already been processed action takes a list of all incoming args. The guard is of the following signature, G.L. (guard inp s), with inp the list of vars and s the state data that flows with the guile-log program. Rec is a pretty expensive function that behaves well under backtracking and state store and restore. Use this ideom and it's sibling ideoms as a prolog functor as
/* prolog code comes here */

-rec(guard,action)
f(X) :- ....

/* end prolog */

Scm (rec-once f guard action) An optimized verison of rec for cases when you only take one value of f

Scm (rec-00 f guard action) Does nothing fancy and is therefore fast, assume that there is no backtracking in f and that it is atomic in the sense that no state store restore is done inside it.

rec-lam, rec-lam-once, rec-lam-00 The same as the three above but the resulting goal has the signature,

G.L. (*-lam-* action arg ...), with action beeing executed just like the overall action in the mother functor.

G.L. (rec-action action x) Will execute action in case a term show up a second time in scanning the datastructure x.

G.L. (rec-action00 action x) Will execute action in case a term show up a second time in scanning the datastructure x. This assume no backtracking in action.

G.L. (rec= X Y) , a recursive safe unify procedure. G.L. (rec== X Y), a recursive safe eqvivalence procedure.

(recursive f arg ...), this functor can be used to modify f so that it will do all of it's work using recursive safe unifyeres etc. This can be used as a functor modifyier in prolog.

Attributed meta programming
***************************

attributes are basically a method to attache meta data to a prolog variable and customize the unification between attributes and other data structures, we will describe the interface. Attributing means that the variable has an explicit special datastructure and any lookup will get stuck on that datastructure although the attribute is bound to a value, this basically means that the attribute variable value need to be peeked at. The data an attribute has is essentially the underlying data and then a list of identifiers plus meta data, the identifiers identifying a certain type of attribute and also at the same time is the stub that is called at unification. Currently ther eis weak support for handling attributed variables in e.g. the utility functions. One need to explicitly get the raw value in case of attributed variables in these functions arguments so currently this feature is a bit experimental. Here is the interface in guile log.,

G.L. (<attvar?> x), sucesses if x is either a normal variable or an attributed variable.

G.L. (<attvar-raw?> x), success if x is only an attributed variable.

G.L. (<put-attr> x m v), puts on an attributed variable x, the attributed indentity m and meta data v. m has the signature

G.L. (m a1 a2 unify?), if unify? is true then the code should unify a1,a2 with the appropriate customized algorithm e.g. prolog's =, else if false then the it should berform an identity comparison e.g. prologs ==.

G.L. (<get-attr> x m v), get the attributed var x, meta data unified to v for attribute identity m.

G.L. (<del-attr> x m), remove the attributed variable x, attribute m.

G.L. (<raw-attvar> x)), get the underlying variable value associated to the attributed variable x.

Parsing
*******

Prolog has historically been used for setting up parsers for various languages and has an extensible expression parser where one congigure the operator handling. We continue in this tradition to produce elements to do backtracking enabled parsing for guile. With this, one can explore the new interesting constructs in guile-log to enable new features with respect to parsing.

Generally in guile-log a parser is a function that follows a certain call semantics. It is a guile log function e.g. it takes the standard arguments S P CC. But ontop of this it takes X XL N M e.g. current char on line (X), current line in stream of lines (XL), current line column (N) and current line number (M). Typically in code these elements are hidden in return values as calling signatures and hence the resulting code is less littered with standard ideoms and tons of variables. This design allows the programmer to easier spot errors and also produce fewer of them and we belive that it is a boon for productivity when writing parsers. Ontop of this semantics an extra output stream field in both imputt and output may be supplied e.g. the tool needed to produce a syntax tree. Code look typically like this,  when using this tool to produce a parser function

(<p-lambda> (c)
  (.. (c) (ws c))                                    ;; Match whitespace
  (<let> ((n N) (m M))                               ;; store M and N
    (.. (c) (exponent c))                            ;; The actual number
    (.. (q) (ws c))                                  ;; Match whitespace
    (<p-cc> `(#:number ,(string->number c) ,n ,m)))) ;; Ret value

We see that we use <p-lambda> in stead of <lambda>. '..' is a special <values> form that has the effect to rebind X,XL,N,M to the new returned values. We also see the technique to bind e.g. N,M to different values. this code would look like this if we did use pure guile-log.

(<lambda> (x xl n m c)
  (<values> (x xl nn mm c) (ws x xl n m c))
  (<values> (x xl n m c) (exponent x xl nn mm c))
  (<values> (x xl n m q) (ws x xl n m c))
  (<cc> x xl n m `(#:number ,(string->number c) ,nn ,mm))))
Not nice on the eye's right. Anyway a bonus point is that we have a framework to create stream like translaters like parsing this through a little macrology and hence it is a 'notime' thingie to change the call idioms. This is the power of guile in action. Ontop of this we build parser combinators which is a functional kanren influenced way of combining parser functions. If we have parser functions f,g we would like to combine them into new parser functions, there are typical ideoms suitable for all translators of sequences e.g. combinators that can be employed e.g. (f-and f g) that successes if both does and outputs the last translation into the value stream. Se the combinators subsection to find out more.

The parsing lib is structured in subnodes according to,

Stream ideom api
================

There is a little framework in guile-log imported with (logic guile-log) that enables the setup of syntactic sugar for streams. The api is

SCM: (define-guile-log-parser-tool (lam (X ...)) def oo xx cc)

lam will be the name of the new lambda object that can be used to produce a matcher. X ... will be the name of the syntax parameters and also define the standard positions for them in call and return. def is the corresponding define. To do an actual match in guile-log with parser function call one need to use oo and when one issues a whole new expression we use xx. To return values from the matcher we use cc. The use of oo is twofold. First G.L (oo (v ...) (f a ..)), does a call in nontail possition. G.L (oo         (f a ..)), does a call in tail position.

xx is used to capture the return of a subexpression like in the example below. It cannot be used to call parser funcitons.

Example
-------

The parsing framwork is using

(define-guile-log-parser-tool (<p-lambda> (X XL N M)) <p-define> .. xx <p-cc>)

An example to use xx is,
(<p-define> (f c1)
  (xx (c2) (<or> (.. (g c1)) (.. (h c1))))
  (<p-cc> `(g-or-h ,c2)))

in practice one keeps the numbers of needed uses of all of the above framework by using functional combinators of matchers. But it is practical to just use this framework to e.g. define a c-parser.

Parser Combinators
==================

The combinators are basic elements that you get from the module (logic guile-log parser). To note here is with these we define elements to do parsing in a ``functional'' way together with som utilities to memoize sections and produce tokens. Tokens are more interned scheme data then the standard way of matching that is lightweight and just represent sequences of the incoming chars. They are also cheap to backtrack over but will put a demand on the supply of prolog variables.

higher order elements,
----------------------

In the arguments to the combinators below a string will be automatically converted to (f-tag "string").

(f-and f ...), higher order function, matches if all f ... matches and returns the values from the last one. Similarly and! only successes ones and for and!! all f ... only sucesses once.

(f-or f ...), higher order funciton, matches if at least one of f ... matches, similarly f-or! matches only once.

(f-seq f ...), higher order function. Matches if f ... macthes in sequence. Similarly f-seq! only matches once and for f-seq!! each f only matches once.

(f-not f), higher order function. matches one char if not f maches. Similarly f-not! stores and returns the matched character in the match standard way of storing data and f-not-pr prints the character on standard output.

(f-not* f), this will not consume any characters and fail if f is true.

(f* f), higher order function, matches f 0 or more times.

(f+ f), higher order function, matches f 1 or more times.

(fn f n m), matches f n to m times

Basic parser functions
----------------------

(f-tag str), produces a matcher of the tag str. f-tag! stores that match the standard way and f-tag-pr prints the match on standard output.

(f-reg char-regexp), produces a matcher that will macth one char according to char-regexp. Similarly we have f-reg! to store the standard way and

f-true, f-false macthers that represt a successful match and a failed match. These are mute constructs and does not consume any data.

f-eof, matches end of file. f-nl, do not use newlines with e.g. f-reg, it will not work use this in stead to match a newline. There is also f-nl! and f-nl-pr versions.

tok-ws*, tok-ws+, this is an non token generator token e.g. it returns the input state of the out stream. But it does tokenizing by issuing a freeze so it memoizes and will not reparse whitespace. the * version is for 0 or more whitespaces and + for one or more whitespaces. A whitespace is here defined as 'space' 'tab' and 'newline'.

constructor combinators,
------------------------

The argument to these functions will auto output keyword arguments e.g. it does an automatic (f-out #:keyword) in the place.

(f-cons f1 f2), as (f-seq f1 f2), but the output is consed.

(f-list f ...), as (f-seq f ...), but the outut is combined in a list.

(f-cons* f ...), similarly as f-list above.

(f-out tag), will produce a matcher that conses tag to the output at the end of a matching.

(ff* f), as (f* f), but makes a list of the output.

(ff* f tag), as aboove but prepends the list with tag.

(ff+ f), (ff+ f tag), as for ff* above but matches one or more elements.

(ff? f), Matches one or if zero matches outputs #f. (ff? f default), Matches one or if zero matches outputs default.

utilities
---------

(p-freeze tok f mk) This will freeze the interpretation of the comming characters according to the parser function f as token tok. Using backtracking, one can get into the unfourtunate stage of reparsing things over and over again. WIth p-freeze we will memoize the reseult and the second time we try to parse the token at the same position we will just use the memoized data. this is how we tokenize and gives the guile-log parsing system a slower tokenizer on one hand, then traditional tokenizers, but on the other hand allows far more advanced tokens to be builed e.g. tokenize a parenthesied expression in C. mk is a function whos purpose is to construct that value that should be memoized it has the signature

(mk s in-value out-value), where s is state value neede to tarnslate any prolog variables, in-value is the value that get's into the resulting parser function, and out-value is the value out of the parser function f above. typical uses are (define (mk s cin cout) cout).

(mk-token f), this is the lower level tokenizer that just produces a string token out of the all the matched characters by the parser function f.

(Ds f), will delay the evaluation of the parser matcher f. This function is needed in recursive definitions in order to avoid infinite recursion.

(parse f) (parse string f) The first version will read from standard input and produce an output as returned by the parser function f. We may also in the second version use a string as input to the parser as per convinience.

Expressions
===========

This is a configureable expression parser that can be used for prolog parsing as well as parsing C and C++ expressions. To note is that the data is functionally updated and hence one can store the state at will and later reinstate the parser. The parser ideom is a direct translation of the commonly described prolog parser written in prolog to guile-log. It is then extended to allow ternial operators like ? in c as well. To use it load the module (logic guile-log parsing operator-parser)

Api
---

(make-opdata), initiates a datastructure to containe needed operator data. The result is a fluid pointing to a functional datastructure.

(add-operator data type name level lf), This will add operator data to the opdata fluid data. type is the type of operator e.g. any of xf,yf,fx,fy,xfx,xfy,yfx, as of the standard meaning of these operators in prolog. name is a string or symbol representing the name of the operator and level is the anti binding strength of the operator e.g. higher value bind less. lf is a parser function that represents possible values to the right of the op-symbol matched, typically this will be tok-ws, but also for e.g. ? it can be a parser function matching the middle part of in this operayor which ends with :.

(rem-operator data type name), removes from the opdata fluid data, the slot represented by the type type and the operator name name.

(mk-operator-expression atom rest-atom data), will return a parser meta function representing the operator configuration in data, with atom parser function atom and a secondary choised atom if that fails in rest-atom. The returned meta parser function, say ff is typically turned into a parser function for the expression through:

(ff high-level), with high-level, the highes level found in the table.

The generator parser f can then be used to match an expression and outpits a syntactic tree with nodes according to e.g.
(parse ``1 + -2'' f)

-->

(('xfy ``+'' _ _) (#:number 1) (('yf ``-'' _ _) (#:number 2) 4 0) 2 0)

That is a binary oparator is of the form,

((type operator-name level _) term-left term-right column line)

And a unary operator is matched by

((type operator-name level _) term column line).

Tooling a parser,
=================

It is possible to change the fundamental behavior of the parser and for that function define all the parser combinators and tools needed to effectively generat AST or just parse out information. The tool is in (logic guile-log parser). Use it as

(setup-parser  <p-define> <p-lambda> <fail> <p-cc> <succeds> .. xx
               X XL ((N 0) (M 0))
               s-false s-true s-mk-seq s-mk-and s-mk-or)

The first row points to the basic parser framework. The second line defines the name of X and XL, that is standard on all parsers. But then rhe second two syntax parameters N,M has also initial values. The last line need also to have been defined before and is usually made by make-guile-log.scanner -tools. As an example this is a basic parser tool for python,

(begin
  (define-guile-log-parser-tool (<p-lambda> (X XL N M INDENT)) <p-define> ..
    xx <p-cc>)

  (make-guile-log-scanner-tools <p-lambda> <fail> <p-cc> <succeds> ..
                              (X XL N M INDENT)
                              (c) (d)
                              s-false s-true s-mk-seq s-mk-and s-mk-or)

  ;; Sets up a standar parser functionals with INDENT field added
  (setup-parser
   <p-define> <p-lambda> <fail> <p-cc> <succeds> .. xx
   X XL ((N 0) (M 0) (INDENT (list 0)))
   s-false s-true s-mk-seq s-mk-and s-mk-or))

And then you can create your parser to AST, by simply translating the grammar in the python docs. Happy Parsing!!

Debugging,
==========

It's possible to get an trace from the output of the parser. In all higher order constructors, if the first element is a symbol that will tag the trace output of that ideom. Then to enable parsing use the boolean variable do-print, that is located in (logic guile-log parser). If that variable is true then you will get a parse trace of the parser. To note is that parsing is both traced at success and when the logic leaves that state in e.g. backtracking.

Sed/grep overview
*****************

To overengineer and test out the framework a simple grep and sed utility has been designed. It knows about scheme and can locate and translate scheme files as well as having traditional grep/sed funcitonality. The main interface is in the module (logic guile-log grep).

Api
===

(grep match code #:key (a 0) (b 0) (c 0)), this will evaluate code in a separate thread and capture standard output and only print what the parser function match matches. a,b,c defines an interval [min(-b,-c),max(a,c)] around the matched line which is printed.

(sed match code), will print everything but if match matches, it's output will be printed instead by the matcher, e.g. use the pr versions of the parser combinators for printing matches.

(par-grep match code #:key (str q-false) (com q-false) (a 0) (b 0) (c 0)), This is a grep funciton that knows about scheme, it works as before but will print the sexp or part of sexp that is matching. The extra fields are, str, the matcher used inside strings, com, the matcher used in comments, and d prints the lines containing the d level enclosing sexp.

(par-sed match code #:key (str q-false) (com q-false)), This is a sed utility that knows about scheme.

The scheme matcher.
===================

In order to translate scheme code we have a nice little monster framework to to the grunt work. You may use it by importing (logic guile-log parsing sch-match). To use this one need to know about how syntax-parse works. We only support a subset of the syntax-parse interface, namlely the directives ~and ~or ~not ~var _) added to this we make use of ice-9 match notation for symbols.

To define a match abstraction use,

(define-match-class [nm | (nm . args)] (pattern pat l ...) ...), just use this as with define-syntax-class, but with the exception that you will build and match according to some whitespace rules stated below.

(define-splicing-match-class [nm | (nm . args)] (pattern pat l ...) ...), This works just as with define-splicing-syntax-class in syntax-parse, but again with some extra twarts.

The actual matchers are,

(scm-sed (pat res ...) ...), this works just as with syntax-parse, but with the extra build-rules.

(scm-match pat), use this as a matcher in par-grep, but with the syntax-parse pattern interface to define a match.

Building the result.
====================

The philosophy is to treat the sed translation as a special syntax transform. A variable x in the pattern will produce three sub matches, x.l,x.it.x.r. e.g. left whitespace, sexp, right whitespace. By matching #(l it r) l will be left whitespace, it the sexp and r the right whitespace, and this is how you define the output as well in order to surround an element with whitespace.

Example
=======

This is an example how one may define a sed translator that swaps the meaning of variable and value in a let form and preserving whitespace as much as possible.

(define-match-class swap
  (pattern #(l (x y) r)
     #:with tr #'#(l (x.l y.it x.r y.l x.it y.r) r)))

(define-match-class (tr-it oldval newval)
  (pattern #(l ,oldval r)
     #:with tr #`#(l #,(datum->syntax #'a newval) r)))

(define (test f)
  (par-sed (scm-sed (#(l ((~var let (tr-it 'let 'tel))
			      #(a ((~var bind swap) ...) b)
			 body ...) r)
		     #'#(l (let.tr #(a (bind.tr ...) b) body ...) r)))
      (f)))

setomat
*******

Setomat automate the task to construct a functional ordered sets/maps and functional ordered complemented set/maps and introduce a range of such implementations.

the-ordered-set
===============

This takes an assoc like library and transforms it to an ordered/undordered set and setmap. There is a small change to the setup from scheme's assoc e.g. the key value pair is not explicit in stead we assume the form (acons kv a).

So consider every set constructed from a union if singletons, if an element is ordered, then they are guarrantead to be reproduced as they appear in the ordered list of union operations with a first come first defined principle. in a difference the oredered list remains but with the removed elements sieved out. This is as well for intersection. elements kan be key value pairs or just a key part, generally there is a poperty of beeing a value, a key value pair may be considered as having the value property but may be configured to not be a value. a value will be used in an assoc manner the value used is the first value that appears in the sequence of operations: unification or intersection, one can for example take an ordered set of non key-values and intersect on a key value set, then the resulting set/map will have the same order of the elements as in the non-value set, but have the values in the key-value set. We construct both a order perserving operations and non order preserving sets in order to be able to make a more effective set operation.

It is a higher order library, it takes a set of functions and construct set opaerations,  amongst defined are, ∪,∩,∖,≡,⊕, ordered and unordered.

API
---

You can reach this code by importing (ice-9 set set)

scm (make-set-from-assoc-mac ...) the macro version of the below

scm (make-set-from-assoc null assoc acons delete hash mk-kv mk-kv kv? kv-key kv-val size value? order? equal? ar->l l->ar)

Input
.....

null    =  the empty assoc/set
assoc   =  (assoc x set/map),  maps to either a key value pair or x itself if x is a member of set, else @code{#f}
acons   =  (acons x set/map),  funcitonally add x to set/map
delete  =  (delete x set/map), functionally delete x from set/map
size    =  (size set/map)    , >= the number of elements, if deleted elements conses a delete operation to the assoc then this is greater then the number of elements in the set element operations

mk-kv   = (mk-kv x), makes an element from a normal scheme value
kv?     = check for a key value structure
kv-key  = key accessor
kv-val  = value accessor
hash    = (hash x hashsize), creates a hash value from the kv element
value?  = if this kv is a key-value pair and the order of the kv pairs in set operations are important
order?  = if the element's construction order is reflected by the set and maintaind through the ordering of the set
equal?  = (equal? x y) the equality predicate used for the kv elements.
ar->l   = the identity map TODO remove this from the api
l->ar   = the identity map TODO remove this from the api

Output
......

The outputs are a value list according to
(values #:=   ≡  #:u   u  #:n   n  #:-  s- #:+  s+ #:<   ⊂ #:<=   ⊆
	#:o=  o≡ #:ou  ou #:on  on #:o- o- #:o+ o+ #:o< o⊂ #:o<= o⊆
	#:n- tripple
        #:fold fold #:map map #:for-each for-each #:empty ∅
	#:set->list   set->list   #:set->assoc set->assoc
	#:set->kvlist set->kvlist #:make-one make-one)

#:=           :   set identity
#:u           :   set union
#:n           :   set intersection
#:-           :   set difference
#:+           :   set plus
#:<           :   subset of
#:<=          :   subset or equal of
#:o=          :   ordered set identity
#:ou          :   ordered set union
#:on          :   ordered set intersection
#:o-          :   ordered set difference
#:o+          :   ordered set plus
#:o<          :   ordered subset of
#:o<=         :   ordered subset or equal of
#:n-          :   the tripple(a,b,c) =  (a n c) u (a / d)
#:fold        :   (fold f seed set), f : (f kv seed) => new-seed
#:map         :   (map f set), conses the value of f : (f kv) to a list.
#:for-each    :   (for-each f set), executes f : (f kv) in the set order
#:empty       :   The empty set
#:set->list   :   Creates a list from the set/map
#:set->assoc  :   Creates an assoc of the k-v pairs from the set/map
#:set->kvlist :   Crates a list of the kv structures from the set/map
#:make-one    :   Maps a set or one element to a set

FUNCTIONAL COMPLEMENTABLE SETS AND ORDERED SETS AND SETMAPS
===========================================================

This is a higher order library that will based on a programmable set datatype without complement construct a library for doing set operations by taking complement without a universe defined.

This library treat complements without defining a world. Mathematically that leads to nondecidability issues, but if one construct all such sets from factual discrete elements no technical problems will appear. To actually get a set define a world as the underlying set lib and intersect it with the complemented set, that results in the underlying set. Bitsets has lognot and in guile (gmp) manages bitset complements with lognot and the minus sign. One can define complement for bitsets as well with this library but that's not nessesary the gmp has all the magic for this.

All nessessry set operators are defined with complement feature included The working code is using the fact that every complemented set that is constructed from atoms and set operations can be defined as A ⊔ Bᶜ. This is not unique definition, to make it unique one could specify that B ∖ A = B that is ̧A⊆Bᶜ and this is also what we constrain the complements to be. FOr unordered sets one can assume that Bᶜ=∅. But when the order is importane one need to be more careful and a more complex solution results. Ordering is defined through the ordering of operands in X ∪ Y and X ∩ Y, that is in a serialisation of X op Y, then elements in sets in X comes befor elements if sets in Y. Ordered sets has a well defined order and can can seen as an assoc list e.g. we can consider mapings from key elements to values in which case lookup of mappings is through the ordered list and hence defines a more generalised lookup. complements of an ordered map sets have no map defined for them, any such maps need to be taken from the world at instantiation of a complemented set into that world, or the real sets it is intersecting with.

API
---

To use this library import (ice-9 set complement).

scm (make-complementable-set ∅ union intersection difference triple equiv? set-size set? make-one)

and the macro scm (make-complementable-set-mac ∅ union intersection difference triple equiv? set-size set? make-one)

results in:
(values #:u  uSS  #:n  nSS  #:c  cS #:+  ⊕SS  #:-  ∖SS
	#:ou uSSo #:on nSSo #:oc cS #:o+ ⊕SSo #:o- ∖SS
	#:world Ω #:= ≡SS #:< ⊂SS #:<= ⊆SS)

Ω = ∅⊔∅ᶜ == (make-set ∅ ∅) defines the world.

We also export a complement set struct according to ($ <set> set complement), cset?.

Input
.....

union          A,B   -> {x|x∈A or  x∈B}               (A∪B)
intersection   A,B   -> {x|x∈A and x∈B}               (A∩B)
difference     A,B   -> {x|x∈A and x∉B}               (A∖B)
triple         A,B,C -> {x|x∈A and (x∈B or x∉C)}      (A∩(B∪Cᶜ))
∅              the empty set
equiv?         the set equal predicate
set-size       get the size of a set for the underlying set structure
set?           predicate for beeing a set of the underlying set structure
make-one       Map a set to a set and an element to a set with one element

Output
......

#:u     : ∪  - union for complemented sets         0,1,... arguments
#:n     : ∩  - intersection for complemented sets  0,1,... arguments
#:c     : *ᶜ  - set complement                     1 argument
#:-     : ∖  - set difference =  A∩Bᶜ              2 arguments
#:+     : ⊕  - set adition    = (A∖B ∪ B∖A)        0,1,.... arguments
#:world : the world object
#:=     : equality of sets
#:<     : subset of
#:<=    : subset or equal of

#:ou, #:on, #:oc, #:o+, #:o- : ordered versions of it.

Theory
......

For a full solution one need to track orders in the complement channel as well as the non complement channel.

It looks like we must store either A/B or (A/B)c = B u Ac and do this properly.

1) Q  = A/B u C/D = Q Qc = (A/B)c n (C/D)c = = (B u Ac) n (D u Cc) =  U + Vc, U = B/C  u  D/A U u Qc = Qc (Q/U)c = Qc  => Q/U = Q => stored pair Q,U

2) Q = A/B n C/D = AnC Qc = (A/B)c u (C/D)c = (Ac u B) u (Cc u D) = (B u D) u (AnC)c Qc = U + Vc, U = B u D => stored pair Q,U

3) Q = A/B u (C/D)c = A/B u Cc u D = (A/B u D) u Cc = Q u Cc Qc = C / (ABc u D) = C (Ac u B) n Dc = C(B u Ac) BC / (A+D) = BCAcDc  = BCAc CAc /(A+D) = CAcAcDc = CAc BCAc + CAc

4) Q  = A/B n (C/D)c = A/B n(D u Cc) = Q=A(D u Cc) Qc = (B u Ac) u (C n Dc) = U + Vc, U = B u C => stored pair Q,U

5 It implements complementable set and setmaps from different underlying vhash datastructures.) Q = (A/B)c u (C/D)c = B u D u (AnC)c AnC / (B u D)

6) Q = (A/B)c n (C/D)c = (B u Ac) n (C u Dc) = ..  It implements complementable set and setmaps from different underlying vhash datastructures.as before

implementations
===============

This api is reached from (ice-9 vset). It implements complementable set and setmaps from different underlying vhash datastructures.

API
---

There are several versions of datastructures that we create and the API for those will come in the subsectons to this section, but all these datastructures have in common the following.

empty            : the empty set
world            : the world representation

(mk-kv key val)  : make a key value pair for non x structures
(mk-kvx key val #:key  (equal? equal?)
		       (hash   hash)
		       (value? #t)
		       (order? #t))
(mk-kx key #:key (equal? equal?)
		 (hash   hash)
		 (value? #f)
		 (order? #t))

equal? : the equality predicate used for this key
hash   : the hash used for this key
value? : if the value need to be important
order? : if ordering of this key is important

vset that is based on equal? vhash datastructure
................................................

   vset-equal?
   vset-union
   vset-intersection
   vset-difference
   vset-addition
   vset-complement
   vset-subset<
   vset-subset<=

   voset-equal?
   voset-union
   voset-intersection
   voset-difference
   voset-addition
   voset-complement
   voset-subset<
   voset-subset<=

   vset-fold
   vset-map
   vset-for-each
   vset-empty

vset that is based on eq? vhash datastructure
.............................................

   vsetq-equal?
   vsetq-union
   vsetq-intersection
   vsetq-difference
   vsetq-addition
   vsetq-complement
   vsetq-subset<
   vsetq-subset<=

   vosetq-equal?
   vosetq-union
   vosetq-intersection
   vosetq-difference
   vosetq-addition
   vosetq-complement
   vosetq-subset<
   vosetq-subset<=

   vsetq-fold
   vsetq-map
   vsetq-for-each
   vsetq-empty

vset that is based on eqv? vhash datastructure
..............................................

   vsetv-equal?
   vsetv-union
   vsetv-intersection
   vsetv-difference
   vsetv-addition
   vsetv-complement
   vsetv-subset<
   vsetv-subset<=

   vosetv-equal?
   vosetv-union
   vosetv-intersection
   vosetv-difference
   vosetv-addition
   vosetv-complement
   vosetv-subset<
   vosetv-subset<=

   vsetv-fold
   vsetv-map
   vsetv-for-each
   vsetv-empty

vset that is based on per element hash and equal redicates vhash datastructure
..............................................................................

   vsetx-equal?
   vsetx-union
   vsetx-intersection
   vsetx-difference
   vsetx-addition
   vsetx-complement
   vsetx-subset<
   vsetx-subset<=

   vosetx-equal?
   vosetx-union
   vosetx-intersection
   vosetx-difference
   vosetx-addition
   vosetx-complement
   vosetx-subset<
   vosetx-subset<=

   vsetx-fold
   vsetx-map
   vsetx-for-each
   vsetx-empty

weak vset that is based on per element hash and equal redicates vhash datastructure
...................................................................................

   wsetx-equal?
   wsetx-union
   wsetx-intersection
   wsetx-difference
   wsetx-addition
   wsetx-complement
   wsetx-subset<
   wsetx-subset<=

   wosetx-equal?
   wosetx-union
   wosetx-intersection
   wosetx-difference
   wosetx-addition
   wosetx-complement
   wosetx-subset<
   wosetx-subset<=

   wsetx-fold
   wsetx-map
   wsetx-for-each
   wsetx-empty

inheritance
***********

Consider a set of objects and that we can add arrow links between the objects that forms a forest of  acyclic directed graphs. This is the same as defining a multiple inheritance relation to the objects. What we can compile is lookup structures that enables fast understanding if one object is an ancester to another object or not, use function compile-sup-sub. and vice versa. Another useful lookup structure origiates from associating each set obect with a value and then ask for all objects of an object and all it's decendants. This is a kind of tree lookup and one needs to reorder the objects to enable an effective lookup, this is dine in the special compiliation function, compile-set-representation or order-the-set. It's possible to build a search tree through function mktree. To use this lookup tree one can use fold-matching-sets which folds all decendants from a paren set object.

API
===

this code is found in (logic guile-log inheritance)

scm   (make-set-theory)         : make a fresh new set theory
scm   (make-set-theory parent)  : make a new set theory with parent theory
fluid *current-set-theory*      : contains current set theory

scm   (print-theory)            : print current set theory
scm   (print-theory th)         : print theory th

scm   (new-set set)             : add a new set element to the current theory
scm   (new-set theory set)      : add a new set element to the theory and
                                  return it

scm   (lookup set)              : lookup set object o's coding from current
                                  theory

scm   (lookup theory set)       : lookup set object o's coding from theory

scm   (reverse-lookup set)        : lookup the set object from coding using
                                    current theory

scm   (reverse-lookup theory set) : lookup the set object from coding using
                                    theory

scm   (a->b a b)                : add an arrow link from a to b in current
                                  theory
scm   (a->b theory a b)         : add an arrow link from a to b in theory and
                                  retrun the new theory

scm   (a->b-o a b)              : add an arrow link from a to b in current
                                  theory and update parenthood information
                                  assuming that all perents have no parent yet.

scm   (a->b-o theory a b)       : add an arrow link from a to b in theory
                                  and update parenthood information assuming
                                  that all perents have no parent yet. returns
                                  the new theory.

scm   (compile-sup-sub)         : compile the parenthood information in current
                                  theory

scm   (compile-sup-sub theory)  : compile the parenthood information theory
                                  and return the new theory.

scm   (compile-set-representation) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in current theory.

scm   (compile-set-representation setbits) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in setbits in current theory.

scm   (compile-set-representation theory) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in theory.

scm   (compile-set-representation theory setbits) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in setbits in theory.

scm   (order-the-set) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in current theory. updates current theory

scm   (order-the-set theory) :
       compile all remaining datastructures for inheritance analysis using all
       set objects in theory.

scm   (mk-tree i->f #:key (setbits current-setmask))       :
      make a lookup tree using equal? hash-table, i->f, and including setbits
      mask in current theory

scm   (mk-tree theory i->f #:key (setbits theory-setmask)) :
      make a lookup tree using equal? hash-table, i->f, and including setbits
      mask in theory

scm   (set< x y) :
      checks if x is a parent of y in current theory

scm   (set< theory x y) :
      checks if x is a parent of y in theory

scm   (assoc=>tree theory a) :
      Take an assoc list and make a inherentance lookup tree for the values

scm   (find-matching-sets theory set tree) :
      find all decendants to set using the lookup structure tree in theory

scm   (fold-matching-sets f seed set tree) :
      fold all decendand data for set (set-object value) using f and seed for
      current theory and lookup tree tree.
      (f set-object value seed) -> new seed

scm   (fold-matching-sets f seed theory set tree)
      fold all decendand data for set (set-object value) using f and seed for
      theory and lookup tree tree.
      (f set-object value seed) -> new seed

Kanren
******

Almost all of the kanren interface is implemented ontop of guile-log to use it import logic guile-log kanren. One could say that the kanren interface is the functional sister to guile-log which is more a macro framework as such guile-log is about 2x faster the kanren, but kanren has more beutifull semantics. E.g. the kanren operation maps function arguments to functions. The kanren interface is divided into two categories of functionals, facts and relations. One combine facts into relations. The main difference is that fact functions have standardized arguments and relations have customized arguments. Also conversely evaluating the relation will return back a fact.

The fact building blocks
========================

succed, This functional item repressents a term that always succeeds.

fail,sfail, Both of these will always fail.

(all f ...), all will produce a functional item representing success if all f ... will success.

(all! f ...), all! will produce only one success where all f ... successes.

(all!! f ...), all!! sucesses where all f ... successes only one time.

(all-interleave f ...), As with all, this construct sucesses if all of the parts sucesses, but the backtracking is designed so that it backtracks evenly and hence avoids problems due to some of the constructs can backtrack an infinite amount of times berfore the success is found. To note is also that this construct has exponential memory complexity with the depth of the search.

(any f ...), this will success if any of f ... sucesses.

(any-interleave f ...), as any, but one at a time will be tried cyclically and hence will find a solution in finite time if there exists one, else it could risk getting stuck in an infinite bacltracking sequence.

(any-union f ...) This is similar to any-interleave, but it will skipp multiples of similar sucesses e.g. if (all f1 f2) is a success, it will skipp the f1 and continue trying with the f2 which will success. Esentially this capture the case when all f ... bind the same variable to a value and we do not backtrack to the same value multiple times.

(if-only pred x), (if-only pred x y), The first form is equivalent to (all (all! pred) x). For the second form if pred successes then the form will fail if x fails. If pred first fails, then y is executed.

(if-some p x), (if-some p x y), The first form is equivalent to (all p x) and in the second form y is executed if p fails.

(succeeds f ...), is similar to (all f ...) but if this success it will backtrack and undo any bindings and continue.

(fails f ...), if (all f ...) fails then this form will backtrack and undo any bindings and continue with a success.

(== a b), unifies the terms.

(*equal? a b), this will try to unify without any variable binding.

(let-lv (id ...) code), this will bind id ... to new fresh variables inside code.

(project (var ...) gl), This will take a specification of a functional item represeting a fact, gl and use the lookuped values of var ... inside the gl spec. This logic is captured in a new functinal fact. If the lookup results in a variable an error will be produced.

(project/no-check (var ...) gl), As with project, but there is no error reported if the lookup results in a variable.

(predicate scheme-expr code), Succeeds if scheme-expr is true.

(var? x), true if x is a logical variable.

(reify x), will produce a scheme representation of x.

_, produces a fress new logical variable in it's place.

relations
=========

This is documentation derived from the kanren sources.

(relation (VAR ...) (to-show TERM ...) [GL], Defines a relation of arity (length '(TERM ...)) with an optional body GL. VAR ... are logical variables that are local to the relation, i.e., appear in TERM ... or GL. It's better to list as VAR ... only logical variables that appear in TERM .... Variables that appear only in GL should be introduced with exists. That makes their existential quantification clearer. Variables that appear in TERM ... are universally quantified.

(relation (head-let TERM ...) [GL]) A simpler, and more efficient kind of relation. The simplicity comes from a simpler pattern at the head of the relation. The pattern must be linear and shallow with respect to introduced variables.  The gl is optional (although omitting it doesn't make much sense in practice) There are two kinds of head-terms.  One kind is an identifier. This identifier is taken to be a logical identifier, to be unified with the corresponding actual argument.  Each logical identifier must occur exactly once.  Another kind of a head-terms is anything else. That anything else may be a constant, a scheme variable, or a complex term that may even include logical variables such as _ -- but not logical variables defined in the same head-let pattern.  To make the task of distinguishing logical identifiers from anything else easier, we require that anything else of a sort of a manifest constant be explicitly quoted or quasiquoted. It would be OK to add `, to each 'anything else' term.

Examples:

(relation-head-let (x y z) (foo x y z)) Here x y and z are logical variables.

(relation-head-let (x y '7) (foo x y)) Here we used a manifest constant that must be quoted

(relation-head-let (x y `(1 2 . ,_)) (foo x y)) We used a quasi-quoted constant with an anonymous variable.

relation (ANNOT-VAR ...) (to-show TERM ...) [GL] where ANNOT-VAR is either a simple VAR or (once VAR) where 'once' is a distingushed symbol. The latter form introduces a once-var, aka linear variable. A linear variable appears only once in TERM ... and only at the top level (that is, one and only one TERM in the to-show pattern contains ONCE-VAR, and that term is ONCE-VAR itself). In addition, ONCE-VAR must appear at most once in the body GL. (Of course, then ONCE-VAR could be _, instead.) If these conditions are satisfied, we can replace a logical variable ONCE-VAR with a regular Scheme variable.

(fact (VAR ...) TERM ...), this is syntactic sugar for (relation (VAR ...) (to-show TERM ...) succeed).

(extend-relation (id ...) rel ...), this relation will simply try each sub relation rel one at a time acording to any calling them with arguments (id ...) which is the arguments of the resulting relation.

Example:

(extend-relation (a1 a2)
   (fact () 'sam 'rob)
   (fact () 'roz 'sue)
   (fact () 'rob 'sal))

Here a1 and a2 will be tried with one fact after the other until a match is found. At backtracking this process will continue untill another match is found.

(extend-relation-with-recur-limit limit (id ...) rel ...), this is the same as the previous term, but the resulting relation cannot be called recursively more then limit times.

(lift-to-relations (id ...) (g rel ...)), This will generate a combination of the relation rel ... according to g and with the argument variables id .... E.g.

Example:

(lift-to-relations (a1 b1)
  (any  (fact () 'sam 'rob)
        (fact () 'roz 'sue)
        (fact () 'rob 'sal)))

Is equivalent to the previous example in the section for extend-relation.

(intersect-relation (id ...) rel ...), This is the same as extend-relation, but it will use all in stead of any.

(let-gls (id ...) ((name rel) ...) code), this will create a new realation with arguments id ... and in that create a set af relations names name ... representing rel ... and the names are used in code.

Queries
=======

query (redo-k subst id ...) A SE ...) -> result or '(), The low level macro 'query' runs the goal A in the empty initial substitution, and reifies the resulting answer: the substitution and the redo-continuation bound to fresh variables with the names supplied by the user e.g. redo-k and subst. The substitution and the redo continuation can then be used by Scheme expressions SE ... Before running the goal, the macro creates logical variables id ... for use in A and SE ... If the goal fails, '() is returned and SE ... are not evaluated. Note the similarity with shift/reset-based programming where the immediate return signifies "failure" and the invocation of the continuation a "success" Returning '() on failure makes it easy to create the list of answers.

(solve n (v ...) g ...), This will create fresh new variables v ... and solve (all g ...). It will output a list of solution which depends on the value of n. If this is equal to * then all solutions will be included. Else if n is a number at must that number of solutions will be publishied in the list.

(solution (v ...) g ..., This is the same as (solve 1 (v ...) g ...).

Misc
====

(trace-vars title (var ...)), Will print out a trace expression for var ....

partially-eval-sgl, not implemented, because guile-log is also directed towards stacks and assq lists and hence usually uses another kind of implementation for the interleaving constructs.

Examples
========

Example 1, any-union,
(let* ((fact1 (fact () 'x1 'y1))
       (fact2 (fact () 'x2 'y2))
       (fact3 (fact () 'x3 'y3))
       (fact4 (fact () 'x4 'y4))

       ; R1 and R2 are overlapping
       (R1 (extend-relation (a1 a2) fact1 fact2))
       (R2 (extend-relation (a1 a2) fact1 fact3))
       ; R1 will first try fact1 then fact2
       ; R2 will first try fact1 then fact3, hence overlapping
       )

    (solve 10 (x y)
           (any-union (R1 x y) (R2 x y))))
=>    '((x1 y1) (x2 y2) (x3 y3)))

Note how R1 and R2 first both bind x and y to the same values in their first
match and how any-union avoid duplicate the results. This works independent of
the orders of fact1 and fact2 etc in the definitions of R1 and R2.

Minikanren
**********

minikanren is a more modern streamlined kanren. The traditional implementation is interesting, but we implement the semantic differently using guile-log internals in stead. The basic implementation in minikanren is to construct a special trampolines that enables code to search the space of solutions in a breth first way. Also there is a logaritmic addition of clauses meaning that the first clauses in an or have higher rate of trying then the last one so that by ordering the most likely clauses first you get a higher hit ratio. Also in minikanren one maintains multiple stack datastructures and does a great degree of groveling in them in order to implement the needed features. Here we take anothre approach and use attributes instead. In all we reproduce the sematics of minikanren but with a completely different appoach that mix well with the rest of guile-log. The minikanren primitives is also used to enable those in guile-prolog and a few operators is defined that enable the minikanren features in prolog programs.

API
===

To use this library reference (logic guile-log minikanren).

The method of the api is to combine functions and finally evaluate the result yielding the logic program. A minikanren goal mk-goal can be executed in guile log as (mk-goal) and you can construct a minikanren goal directly by wrapping it in (<lambda> () ...).

mk-goal (conde (mk-goal ....) ...), This will produce a minkanren goal from 'or'-ing a sequence ao 'and'-ing. This construct will do breath first like search and is safe from producing unwanted infinite searches.

mk-goal (conda (mk-goal ....) ...), This will produce a minkanren goal from 'or'-ing a sequence of 'and'-ing. The first value will produce only one value.

mk-goal (condu (mk-goal ....) ...), This will produce a minkanren goal from 'or'-ing a sequence of 'and'-ing. As conda, but the whole ideom will produce only one solution.

mk-goal (once mk-goal), Makes a goal that take only one solution from the goal mk-goal.

mk-goal (fresh (v1 ...) mk-goal ...), this will bind a set of variables v1 ... and then execute the minikanren goals according to an and in a safe way regarding unwanted infinities in the search

mk-goal (== a b), will unify scheme object a with scheme object b.

mk-goal (=/= a b), will put a non equal constraint on the scheme objects a,b.

mk-goal (symbolo a), Constrain a to be a scheme symbol.

mk-goal (numbero a), Constrain a to be a scheme number.

mk-goal (booleano a), Constrain a to be a scheme boolean.

mk-goal (absento a b), Constrain a to not be included in the b datastructure consisting og atoms and conses.

mk-goal (project (v ...) mk-goal ..., This will walk all v ... values and then execute the goals mk-goal ... inside and. This ideom is safe for infinites in the searching.

scm (run n (v ...) mk-goal ...), execute a list of mk-goals, mk-goal ... inside an and in a infinite searching safe way using logical variables v .... A list of list of variable values of no more than n solution(s) results.

scm (run* (v ...) mk-goal ..., the same as run, but with no limit on the number of solutions, my stall.

Prolog
******

Guile log also sports an iso-prolog interface as a logic programming interface besides kanren. The interface is pretty complete at this point appart a few points that have not yet been resolved but sure it is currently alpha software and help is very very much appriciated. With this most programs written in iso prolog should probably work. The intention is to enhance this interface so that the bulk of already written prolog programs should be able to run on guile. We will also add the fetures unique to guile-log and hence enhance the prolog experience. Featurewise guile-log prolog is taking over many properties of scheme like closures, continuations, delimeted continuations, the interleaving constructs of kanren and a delicate system to treat dynamic objects like dynamic functions, dynamic hashes and a library to tell how you want the dynamism to work at a fine grained level.

Seting up and running prolog programs
=====================================

At this point compiling prolog is not supported via the general compiling framework. But you can run macros that takes a string and outputs a compiled guile log snippet and by this e.g. define logic functions using prolog. It is also possible to refere to a file and by that load a prolog file's contents into a scheme file. There is also tools to reset the prolog parser in case it changes it's state by e.g. defining operators or character translations. The typical usecase is to provide a small module wrapper, reset the parser and then add the prolog file.

Api
---

The iso-prolog library is resolved by,

(use-modules (logic guile-log iso-prolog))

First the compiler macros,

(compile-prolog-string string), this will compile a prolog program in string and output a guile-log program at macro expansion time.

(compile-prolog-file filename), this will replace the form with a macroexpanded scheme verision of the a prolog program referenced by filename.

Then to reset the parser and prolog flags use,

(reset-operator-map)

(reset-char-conversion)

(reset-flags)

(reset-prolog), will do all of the above rest functions.

To run a prolog program one need to use a special program that essentially will setup an suitable error handler for prolog and issue a guile-log <run> command e.g.,

(prolog-run n (v ...) code ...), here  n is the maximum number of solutions to search for, or * to search for all solutions.  v ... is a set of logical variables used and for which solution are collected, code ... is a guile-log command, but to make it simple just call a startup prolog function with it.

Example
-------

  (use-modules (logic guile-log iso-prolog))
  (reset-prolog)
  (compile-prolog-string "f(X,Y) :- (X=1,Y=2;Y=3);X=Y.")
  (prolog-run * (X Y) (f X Y))
$1 = ((1 2) (v0 3) (v0 v0))

Interpreter
===========

guile version >= 2.0 support an interpreter that can switch between different shells. To start the prolog interpreter use the standard way of switching the language through

scheme@(guile-user)> ,L prolog

Happy hacking with Prolog!  To switch back, type `,L scheme'.
prolog@(guile-user)>
This will have the namespce guile-user, so we need to import the prolog code bt

prolog@(guile-user)> .[use-modules (logic guile-log iso-prolog)]
prolog@(guile-user)>
This is pretty hackable, you will have all guile and all prolog in the same environment. If you want to be more prolog centric environment, you can in case the is-prolog is loaded do

prolog@(guile-user)> default_module().
prolog@(prolog-user)>
This will make sure that we hack in a module where all scheme is preficed by scm- this together with the naming convention in prolog to use '_' in stead of '-' we risk less mixups.

As we saw, if the first character is '.[', then in everything until the next ] will be treated as a scheme expression. This is handy to evaluate scheme without switching the language. What's nice is that all shell commands that guile has (prefixed with ',') is preserved so that one can basically do all of
prolog@(guile-user)> ,h all
Help Commands [abbrev]:

 ,help [all | GROUP | [-c] COMMAND]
                              [,h] - Show help.
 ,show [TOPIC]                     - Gives information about Guile.
 ,apropos REGEXP              [,a] - Find bindings/modules/packages.
 ,describe OBJ                [,d] - Show description/documentation.

Module Commands [abbrev]:

 ,module [MODULE]             [,m] - Change modules / Show current module.
 ,import [MODULE ...]       [,use] - Import modules / List those imported.
 ,load FILE                   [,l] - Load a file in the current module.
 ,reload [MODULE]            [,re] - Reload the given module, or the current module if none was given.
 ,binding                     [,b] - List current bindings.
 ,in MODULE COMMAND-OR-EXPRESSION  - Evaluate an expression or command in the context of module.

Language Commands [abbrev]:

 ,language LANGUAGE           [,L] - Change languages.

Compile Commands [abbrev]:

 ,compile EXP                 [,c] - Generate compiled code.
 ,compile-file FILE          [,cc] - Compile a file.
 ,expand EXP                [,exp] - Expand any macros in a form.
 ,optimize EXP              [,opt] - Run the optimizer on a piece of code and print the result.
 ,disassemble EXP             [,x] - Disassemble a compiled procedure.
 ,disassemble-file FILE      [,xx] - Disassemble a file.

Profile Commands [abbrev]:

 ,time EXP                    [,t] - Time execution.
 ,profile EXP                [,pr] - Profile execution.
 ,trace EXP                  [,tr] - Trace execution.

Debug Commands [abbrev]:

 ,backtrace [COUNT] [#:width W] [#:full? F]
                             [,bt] - Print a backtrace.
 ,up [COUNT]                       - Select a calling stack frame.
 ,down [COUNT]                     - Select a called stack frame.
 ,frame [IDX]                [,fr] - Show a frame.
 ,procedure                [,proc] - Print the procedure for the selected frame.
 ,locals                           - Show local variables.
 ,error-message           [,error] - Show error message.
 ,break PROCEDURE        [,br ,bp] - Break on calls to PROCEDURE.
 ,break-at-source FILE LINE
                   [,break-at ,bs] - Break when control reaches the given source location.
 ,step                        [,s] - Step until control reaches a different source location.
 ,step-instruction           [,si] - Step until control reaches a different instruction.
 ,next                        [,n] - Step until control reaches a different source location in the current frame.
 ,next-instruction           [,ni] - Step until control reaches a different instruction in the current frame.
 ,finish                           - Run until the current frame finishes.
 ,tracepoint PROCEDURE       [,tp] - Add a tracepoint to PROCEDURE.
 ,traps                            - Show the set of currently attached traps.
 ,delete IDX                [,del] - Delete a trap.
 ,disable IDX                      - Disable a trap.
 ,enable IDX                       - Enable a trap.
 ,registers                [,regs] - Print registers.

Inspect Commands [abbrev]:

 ,inspect EXP                 [,i] - Inspect the result(s) of evaluating EXP.
 ,pretty-print EXP           [,pp] - Pretty-print the result(s) of evaluating EXP.

System Commands [abbrev]:

 ,gc                               - Garbage collection.
 ,statistics               [,stat] - Display statistics.
 ,option [KEY VALUE]          [,o] - List/show/set options.
 ,quit        [,q ,continue ,cont] - Quit this session.

prolog@(guile-user)>
All such commands has to be the first commands in the input. But there are a set of prolog commands added (they are prefixed with ., let's see them

prolog@(guile-user)> .h

(.n           )             try to find n solutions
(.all    | .* )             try to find all solutions
(.once   | .1 )             try to find one solution
(.mute   | .m )             no value output is written.
(.unmute | .um)             output values is written.
---------------------------------------------------------------------
(.save   | .s ) <ref>       associate current state with name ref
(.load   | .l ) <ref>       restore associate state with name ref
(.cont   | .c )             continue the execution from last stall point
(.lold   | .lo)             restore the last state at a stall
(.clear       )             clear the prolog stack and state
(.rec         )             enable rational tree handling
(.unrec       )             disable rational tree handling
---------------------------------------------------------------------
(.ref         ) <ref>       get value of reference user variable ref
(.set         ) <ref> <val> set user variable ref to value val
---------------------------------------------------------------------
(.setp        ) <key>       associate current state to key
(.refp        ) <key>       instate state referenced by key
(.savep       )             save all referenced states to disk
(.loadp       )             load new referenced states from disk

So now we can time the execution of one solution with no output by doing
prolog@(guile-user)> ,time .1 .m f(X,Y).

;; 0.000900s real time, 0.000836s run time.  0.000000s spent in GC.

prolog@(guile-user)>

There is an api that can be used with convinience goals to be used in code to talk with the interactive shell, to use them do

scheme (use-modules (logic guile-log guile-prolog interpreter))

state
-----

It is possible to store a state interactively and later retrieve the state through a mechansim that brings back control to the interpreter. You do that with prolog stall/0. This will escape the program and return control to the shell.

in the shell you can store the state, retrieve a state and continue the execution from the actual state. Then by using global variables or user variables (preserved when storing the state) it is possible to create very nice interactive conversations for e.g. proof solvers and such. Also by using the dynamic feature framework one can contoll very fine grained how the state should be stored and restored.

user variables.
---------------

It is possible to use a special global variable in code and in the interactive prolog shell. They differ from global variables in that they are stored and restored relative the state. To use normal global variables just use the scheme globals and the scm[...] idiom to get the value. Ther is an accompanion

prolog user_ref(name,Var) To ref a user variable called name int Var.

prolog user_set(name,val) To set a user variable name to val

Known deviations from iso prolog specification.
===============================================

The known deviations are

function/arity
--------------

In prolog the module + function/arity combination identifies the actual predicate. Scheme does not have such a distinction and in order to keep a tight interface between scheme functions and prolog functions a function is identified with its module + name only. This can create problems for certain prolog programs.

"string" is not atoms.
----------------------

The logic is currently, that to specifiy an atom with general characters we use as in is prolog 'atom-+-'. But some functions returns a string and they will not be translated to atoms unless there is a module cast or at the final application of an string as an goal, where it will be translated to the current module. The reason for this complexity is to have non module objects or to allow for creation of module objects through construction of strings. We choose a composable method of ideoms that control the namespaces of prolog objects (se the modules chapter) and strings. Strings can be specified directly via "string". Also a unification of an atom with a string will unify on the name of the string. This means that character handling in guile prolog becomes a smooth experience if one learn the ideoms.

unified namespace
-----------------

Don't expect guile-log to separate names in evaluation expressions and goals, they are the same, so by defining a predicate log you will overwrite the normal log function. Also if you have a variable X in scope and use an atom 'X', then they will mean the same thing.

closed files
------------

Closed files cannot be gotten through a general seek of streams.

seek
----

seek in binary files is not supported (yet).

modules
-------

there is some effort to standardize modules but its unclear how to choose, we therefore do not explicitly add module functionality to prolog, users are advised to write scheme wrappers or inlined scheme code in the prolog file/string. there are extentions to the parser to enable module aware unifications and module atoms.

Module system and prolog
========================

We support @ and @@ operators to resolve atoms module meaning. The syntax is name@module which names files in a special module directory in the guile namespace (language prolog modules). @ is refering to symbols in the public interface and @@ refers to symbols in the whole private module namespace. We also support a guile-log reference through e.g. name@(logic,guile-log,iso-prolog). As a short cut to specify the module that issues a compilation of a prolog part we have the atom@ and atom@@, in principle this forces the module to the lexical module the code belongs to which is handy when we translate strings to atoms via the namespacing mechanism. compound objects can be specified belonging to a namespace which forces the objects inside the lexical atoms and strings to be namespaced to that namespace e.g. [a,'a-b',"axa"]@mod_a will translate all atoms inside the list to objects inside the public interface of module mod_a. The general rule is that lexical translation of objects outside the current module will need to be defined, the current module though will be created if it does not exist. For dynamic creation of atoms, we allow the objects to be created under some constraints.

prolog objects can be namespaced and contain namespace wrappers,  which are transparent in the unification, but for logical variables that are namespaced if the matching object is a string, the variable will be located in the namespace if it exists or it will be constructed under some constraints.

We do not define a full prolog api for module handling, but refere to the usual scheme module system in guile and suggest that the user use the scheme stubs that can be inserted into guile prolog.

Example
-------

:- scm[(use-modules (logic guile-log guile-prolog zip)]
:- scm[(export a b c)]
:- scm[(re-export e f g)]

module aware unification,
-------------------------

Strings will only in proven goals be translated to an atom in the module defining the string, else a string representation will remain. Still the evaluator understands that a string term shouled be represented by a procedure representing the predicate. The algorithm is to search in the current module runtime. But one may whish to explicitly translate strings to a correct module located predicate. The mechansim to achieve this is through the unification. The unification with respect to modules can also be used to verify that data adheres to a certain module convention. The rules for this is essentially

1) A variable in a module will if the other one is a string bind to a term/predicate found/defined in that module.

2) A term in a module will need to be proven to be defined in that module. unfourtunately it is possible that from scheme imported predicates does not declare in what module it is defined in which case we will not unify.

3) A namespaced object that is a datastructure like a list, closure etc, will make sure that all sub variables are bounded to a directly namespaced variable.

4) If a namespaced object has another namespaced object either the new one will take over or the unification fails depending on the state of the unifier to control what will happen see the api below.

subsubsection Example
 X@@module_a                 = ``alpha'',
 [X,Y,Z@@module_b]@@module_a = [``alpha'',''beta'',''gamma'']. % this may fail

Controling module unification
-----------------------------

Sigilling a variable with X@module_a means that we will validate the curent data of the variable. It is desireable e.g. in sandboxing that the module environment cannot change. In the future we will be able to produce sandboxing, but in the current version it is not safe to use it, but we have prepared a little with the current codebase. To control this we can use the api that can be reached from,

scheme (use-modules (logic guile-log prolog namespace)).

prolog error_on_namespace_switch/0, fail_on_namespace_switch/0, ok_on_namespece_switch/0, with the obvious semantic.

Also to get an handle to restrict and guard this information one may use,

get_namespace_switch_handle(Handle),

then if handle can be used by the dynamic features framework and make sure that we will never success although we move from state to state friously and a value can be guaranteed to be fixed inside a code segment.

It's possible to specify a whitelist to handle if one allow changes of namespaces in a unification that include namespacing e.g.

prolog set_no_whitelist/0

prolog namespace_white_list_set([[Local, RW, dir, ...] ...])

prolog namespace_white_list_ref(ListOfList)

prolog namespace_white_list_handle(Handle)

Here Local = true/0 or false/0 specifies that the directory is allows referencing local defines or not,  and RW = true/0 or false/0 specifies if the directory allow writing or not. If dir ends with "*" then any directories after that is included in the spec.

hooking in scheme expressions,
==============================

We can insert scheme expressions with the construct scm[sexp]. You can insert it like, remember that this ideam is always executed at the composition of a list e.g. they are not lazy by any means.

1) directives :- scm[(export a b c)]

2) function arguments and list arguments f(X) :- g(X, scm[(dub (<scm> X))], scm[*global-variable*])

3) In expression constructs f(X) :- X is scm[(dub X)].

It's possible to execute a scheme expression in a goal for secondary effects by e.g. do[...], the value of the scheme expression inside the bracket will never be exposed and, it's fine to put the do expressions inside a list, they will be constructed a lazy expression and only evaluated if it later is executed as a goal. Another variant if this is with[...], the difference is that the value of the scheme expression inside a bracked will guide the success of the goal if it is false then the goal failes.

To note is that currently we have no way of protecting code that are read by e.g. read_term to include any of these expressions, hence there it is not safe to read in code and execute it, beware. A feature request is an ability to turn off this feature when reading in terms. There is two other holes left in order to safely be able to execute code inside a sandbox. First namespacing has to be controlled and secondly namespaced code that are read in, that refers to a macro inside the guile code base will run. The solution to the first is already implemented, we can specify which namespaces we allow for the code read in. And for the second issue we can add code that checks that the read in functions does not refer to a macro, again included in our Todo.

Also you #t,#f can be used as literals as well as keywords like #:keyword. The reason for this is to be able to interoperate with scheme and kanren as well as be able you ues goal functions that have keyword argument(s).

Functor modifiers
=================

Scheme it's strength in it's strong foundation of theory and most things are composable in a general and sound way. For example the ability to take a function goal and output a new function goal to attach properties to that function is a bit clumsy in prolog. Therefore if you prepend a functor that map functions to functions you may get a nice an tidy syntax. The rule is

- rec(guard,action).
- functorize(tabling).
f(X) :- ...

- recursive.
g(X) :- ....

- recursive.
- functorize(tabling).
h(X) :- ...

We see two ways of entering a functor, the first one is prolog -functor(arg1, ..., argn). This is assuming that functor is a scheme function defined as

Scm (functor f arg1 arg2 ... argn). f is the lambda that is defined by all the functors below and the actual function definition.

The othe uses the meta functor functorize, the signature is prolog functorize(goal, arg , ...)  Here goal would be something like G.L.  (goal f arg ... x ...) e.g. goal will be as executeing G.L. (f x ...) but with the new properties added. The reason for this complexity are that normal functors are not goals, but goal functions that maps goal functions, in it's first argument, need to be wraped with functorize.

Examples of functors and goal functors to use are recursive, memo, rec, tabling etc found in (logic guile-log memoize), and also adaptable_vars that tells that all variables created in the function should use a default attribute constructor if defined, this defined in (logic guile-log).

sets and maps in prolog
=======================

We are going to explore how set's are handled in guile-log prolog. Lets start off simple.

To define a set just do:

    X is {1,2,3}.

    X = {1,2,3}

We have added common set operators e.g.

    % union e.g. all combined elements (cup in latex).
    ?- X is {1,2} ∪ {2,3}.

    X = {1,2,3}.

    % intersection, e.g. all elements located in both sets (cap in latex)
    ?- X is {1,2} ∩ {2,3}.

    X = {2}.

    % set addition e.g. all elements of the sets not located in both (oplus in latex)
    ?- X is {1,2} ⊕ {2,3}.

    X = {1,3}.

    % sed difference e.g. removing all elements in the second set from the first (setminus in latex).
    ?- X is {1,2} ∖ {2,3}.

    X is {1}.

A new set is not nessesary constructed at each operation, usually we take one of the arguments datastructure and modify that. Ouch you may say, well it's not that terrible. We are working with functional hashmaps that mimics a cons list e.g. vhashes E.g. we are building a new datastructure with the old one semantically untouched. Removing an element a is also not that terrible, just add a map a->deleted and only when there is a lot of fluff we reconstruct the whole map. This means that we can efficiently support a functional interface in stead of the standard mutable interface you see in languages like java and C#. Later we will se that new map bindings will override already stored maps. This is simple to implement using these functional hashmaps.

An element as a datastructure will be interpretted value wise, e.g. two lists with the same content will be equal. Any found prolog varibles will be interpreted as an adress identity. This means that if we have an object X put as a set member and it is later bound to 1, then the variable edentity will still remain and the key does not change. So the set element will be flatted into a scheme datastructure. In the future we will introduce a gard symbol so that you can do e.g. X is {[1,guard(X)]}, then with this X will be copied over verbatim. In all we recomend that varibles are not used as set elemets unless you really now what you are doing.

The first special addition we will make is that a det is a union of a finite set and the complement of a finite set e.g. Aᶜ (unicode superscript c) we can then define the set operators as,

    (A∪Bᶜ) is (B∖A)ᶜ
    (A∩Bᶜ) is (A∖B)

    (Aᶜ∪Bᶜ) is (A∩B)ᶜ
    (Aᶜ∩Bᶜ) is (A∪B)ᶜ
⊕,∖ follows from these relations. The conclusion is that any such set can indeed be represented as a generilized set where we define a generalized set as either Set = A or Set = Aᶜ. This is well defined. When one wants a a true set from this representatation one takes a world Ω and intersect it with theSet and for the complement you get (Ω∖A).

The next addition to our set datastructure is to assume that the elements in the set can be a key value pair where the key is the usual set element, e.g. to enable the set to be a map. The basic set operations defined on this will always bind the key to the value located for this in the leftmost set where it is defined. We will see how to preserve this operation even for complemented sets, but's lets see the simple things,

    % notise how the keys follow the set logic with the addition that leftmost
    % value take precedence

    X is {1-a,2-a}∪{2-b,3-b}.

    X = {1-a,2-a,3-b}

    X is {1-a,2-a}∩{2-b,3-b}.

    X = {2-a}

Now, there is two roads to go from here. Either we are satisfied or we can demand that the information of the complement for a set be recorded in case complements is used e.g. Basically we want this to be true,

    % This shows that we want the elements in the complement to be saved later
    % for use if used before the other operator.
    X is {1-a}ᶜ, Y is Xᶜ ∩ {1-b}

    X = {1-a}ᶜ.
    Y = {1-a}.

    % {1-a} is in the complement of X and the system remembers that in
    % the calculation of Y.
    X is {1-a,2-a}∩{2-b}, Y is Xᶜ ∩ {1-c}

    X = {2-a}.
    Y = {1-a}.

If we first forget about complement, we could just focus on set's and simply for each map A also collect the information that have been skipt in the complement you would then simply have another set B, in the complement of A that contains the extra key value information that will later be materlized in taking a complement. We simply realize that we can use the notation A = A∖B and this is our notation which is both true acording to set theory and contains all extra information that is needed for retrieving correct values associated to the keys. The union and intersection becomes:

    (A1∖B1)∩(A2∖B2) = (A1∩A2)∖(B1∪(A1⊕A2)∪B2).
    (A1∖B1)∪(A2∖B2) = (A1∪A2)∖((B1∖A2)∪(B2∖A1)).

Note that the order is important here, this means that basically every set element that has ever been touched uppon is stored in either A or B which is kind of expensive. Therefore this is an issue that is critical to control and it is possible to inhibit this feature. Therefore it is good to separate a generlized set/map in one set part and one map part and therfore we end up with the following representation:

    % A is a pure map, B is a pure map and C is a pure set,
    % The set representation is then A∖B∪C, with A∩B=∅,
    % the union and intersection becomes
    (A1∖B1 ∪ C1) ∩ (A2∖B2 ∪ C2) = (   ((A1∩A2)∪(A1∩C2)∪(A2∩C1))
                                       ∖ ((B1∪(A1⊕A2)∪B2)∖(A1∩C2)∖(A2∩C1))
                                       ) ∪ (C1 ∩ C2).

    (A1∖B1 ∪ C1) ∪ (A2∖B2 ∪ C2) = (   (A1∪A2)
                                        ∖ ((B1∖A2)∪(B2∖A1))
                                   ) ∪ (C1 ∪ C2).

When we finally add complemented sets we end up with the representation:

    % A is a pure map, B is a pure map and C is a pure set,
    % For repr A∖B∪C:  A∩B=∅.
    % For repr A∖B∪Cᶜ: A∩B=∅.

    (A∖B ∪ Cᶜ)ᶜ = (B∪Aᶜ)∩C = (B∩C)∖(A∪(B∖C)) ∪ (C∖A)
    (A∖B ∪ C)ᶜ  = (B∪Aᶜ)∩Cᶜ = (B∖C)∖(A∪(B∩C))∪(A∪C)ᶜ

And we see that the operation of complement is closed, e.g. taking the complement the representation still holds.

The intersection becomes:

    (A1∖B1 ∪ C1) ∩ (A2∖B2 ∪ C2) = (
                                       ((A1∩A2)∪(A1∩C2)∪(A2∩C1))
                                     ∖ ((B1∪(A1⊕A2)∪B2)∖(A1∩C2)∖(A2∩C1)))
                                   ) ∪ (C1∩C2)

    (A1∖B1 ∪ C1) ∩ (A2∖B2 ∪ C2ᶜ) = (
                                       ((A1∩A2)∪(A1∖C2)∪(A2∩C1))
                                     ∖ ((B1∪(A1⊕A2)∪B2)∖(A1∖C2)∖(A2∩C1)))
                                   ) ∪ (C1∖C2)

    (A1∖B1 ∪ C1ᶜ) ∩ (A2∖B2 ∪ C2) = (
                                       ((A1∩A2)∪(A1∩C2)∪(A2∖C1))
                                     ∖ ((B1∪(A1⊕A2)∪B2)∖(A1∩C2)∖(A2∖C1)))
                                   ) ∪ (C2∖C1)
    (A1∖B1 ∪ C1ᶜ) ∩ (A2∖B2 ∪ C2ᶜ) = (
                                       ((A1∩A2)∪(A1∖C2)∪(A2∖C1))
                                     ∖ ((B1∪(A1⊕A2)∪B2)∖(A1∖C2)∖(A2∖C1)))
                                    ) ∪ (C1∪C2)ᶜ

E.g. The representation is closed under intersection.

Finally we need to check it for union as well e.g.

    (A1∖B1 ∪ C1) ∪ (A2∖B2 ∪ C2) = (
                                      (A1∪A2)
                                    ∖ ((B1∖A2)∪(B2∖A1))
                                   ) ∪ (C1 ∪ C2)

    (A1∖B1 ∪ C1) ∪ (A2∖B2 ∪ C2ᶜ) = (
                                      (A1∪A2)
                                    ∖ ((B1∖A2)∪(B2∖A1))
                                    ) ∪ (C2∖C1)ᶜ

    (A1∖B1 ∪ C1ᶜ) ∪ (A2∖B2 ∪ C2) = (
                                      (A1∪A2)
                                    ∖ ((B1∖A2)∪(B2∖A1))
                                    ) ∪ (C1∖C2)ᶜ

    (A1∖B1 ∪ C1ᶜ) ∪ (A2∖B2 ∪ C2ᶜ) = (
                                       (A1∪A2)
                                     ∖ ((B1∖A2)∪(B2∖A1))
                                    ) ∪ (C1∩C2)ᶜ

And this is also closed. Because all other operations can be expressed from these operations the system is closed under all set operations.

Testing for an element etc is done through ∈ ("in" in latex) , the semantics is easiest to show with examples:

    ?- X is {1,2-a,3-a}, K ∈ X.

    K = 2.

    K = 3.

    K = 1.

    ?- X is {1,2-a,3-a}, 1 ∈ X.

    yes

    ?- X is {1,2-a,3-a}, 4 ∈ X.

    no

    ?- X is {1,2-a,3-a}, 1-V ∈ X.

    V = #f.

    ?- X is {1,2-a,3-a}, 2-V ∈ X.

    V = a.

    ?- X is {1,2-a,3-a}, K-V ∈ X.

    K = 2,
    V = a.

    K = 3,
    V = a.

    K = 1,
    V = #f.

Now ordering of the entering objects is preserved for pure sets and pure map sets. And this is in the spec. Actually the underlying datastructure allows to tag a set element or a key value pair as unordered e.g. some optimisations can be done if we relax the ordering condition, taking advantage of this will come in the future. Let's in stead look at prolog code in action using the set framework. First list_to_set (defined in the module):

    list_to_set(L,S) :-
      reverse(L,LL),
      list_to_set(LL,∅,S).

    list_to_set([],S,S).

    list_to_set([X|L],S,SS) :-
     (
      (\+var(X), X = K-V) ->
        S2 is {K-V} ∪ S;
        S2 is {X}   ∪ S
     ),
     list_to_set(L,S2,SS).

    ?- list_to_set([1,2],S).

     S = {1,2}.

Simple as a pancake. Now here is a useful procedure, `mapset`:

    mapset(S,Map,SS) :-
      findall(V, (_-V ∈ (Map ∩ S), V \= #f),L),
      list_to_set(L,SS).

    ?- X is {2,1},Map is {1-2,2-1,3-0}, mapset(X,Map,S).

    S = {2,1}.

Note that we take the intersection with S last. This will mean that Map decides the order of the resulting set, but in case S containes a key value pair Map take precidence and this is more important.

We define an equal function for sets, and this means that =,== etc do works as expected up to a certain level. The value part is not seen by equal? e.g.:

    ?- X is {1}, Y is {1-1}, X==Y.

    yes

This might be unsatisfying and it is unsure what to do, probably we will define a fluid that specify wha kind of equal we would like to have for set's (there is many thinkable variants).

Also worth noting is that testing to find that two sets are different are cheap, it is when two sets are equal, that generally we need to check n times. We do that by using a nifty hash and explore the properties of the xorfuntion. Namely:

    xor(a1,a2,a3,...) = ? % does not depend of the order
    xor(a1,a1)        = 0
    xor(0 ,a )        = a

This means that maintaining the hash for deletion and addition is a simple one op. So a ~64bit hash is always maintaind for the set and they most often different for different sets. This means that set of sets is much more effective than what you first would think.

Finally we have the subset operators: ⊆,⊂ (subseteq, subset in latex) The second one test for subset or equal and the second one for a pure subset e.g:

    ?- {1,2} ⊆ {1}.

    no

    ?- {1,2} ⊆ {1,2}.

    yes

    ?- {1,2} ⊆ {1,2,3}.

    yes

    ?- {1,2} ⊂ {1}.

    no

    ?- {1,2} ⊂ {1,2}.

    no

    ?- {1,2} ⊂ {1,2,3}.

    yes

There has been a missing piece when it comes to set and maps regarding how to interpret unification identity and structural unification or arbritrary unifications. Also in exploring how to do this it is advicable to piggy pack on attributed variables which already enables unification for it's content. The quest is to extend this to a higher degree to allow general extensible unifications and other constructs. So currently we have in guile log internal ways to do this but it's easy to extend this to prolog. So the predicate needed for prolog unifier writers is to have a get_attr_data(X,L), where X is the attributed variable (or this will fail), and L=[[Unify|Data],...] with the Fkn and Data taken from put_attr(X,Unify,Data). in guile-log we don't use modules as a field for Unify but in stead it is an identifying predicate, it has arbritrary signature, but when testing for = unification you do Unify(X,Y,#t) and for == you do Unify(X,Y,#f). We added the following hook in guile-log for =@= e.g. Unify(X,Y,IX,IY,HX,HY,EX,EY,'mk-variant') I will later change this to Unify(X,Y,variant). With variant taken from (logic guile-log prolog variant).

It's a cludge to use `#t` and `#f` here and this should be fixed. What we do is to take out the actual sets from the attributes and then check of they are identical. Pure sets and maps are identical if the keys are we also check the complement if they are the same. If the keys are the same (we keep a hash so if they are different the test is really quick), then we callect all key value pairs and match them with the other set and then iterate the operation on the value elements. Some experiments.

In comparison one of the set/maps has to be in a attribute. if it is a pure set then it is not needed to wrap them in a attribute. Anyway attribute generated operatoins is needed, so I added.

mk({1},X), Makes a attributed variable from the set in the first argument.

u is attributed generating union n  is attributed generating intersection o  is attributed generating set addition m  is attributed generating set minus c  is attributed generating complement.

So now we have

    > mk({1-A,2-A},X),mk({1-C,2-B},Y),X=Y.

     C = A,
     X = Y,
     B = A,
     put_attr(Y, set_unify, ({1-X0,2-X0}∖∅ ∪ ∅)).

Note that the printer is not recognizing that X0 is  A, this can be fixed by writing a custom Unify(X,Y,write) that translates the set back to custom printer.

We also have.

    > mk({1-A,2-B},X),mk({1-A,2-C},Y),[A,X]=@=[A,Y].
    put_attr(Y, set_unify, ({1-X0,2-X1}∖∅ ∪ ∅)),
    put_attr(X, set_unify, ({1-X0,2-X1}∖∅ ∪ ∅)).

Some new operators added, first of all we have the negations, ⊈ ⊄ ⊉ ⊅ ∉ which are self explanatory. The task for this post is that ski on ##prolog asked about solving equations or similar in order to state set equations a little implicit, but also easy generate the set of sets etc. We added two new operators ⊔ and ∖∖. The first one in equations tell you that the varaibles in the terms are a disjoint union and the second one tell you that the variable to the left does not contain the variable to the right. If possible finite sets the system will generate all solutions which means that X ∪ Y = Z will behave nicely and generate solutions if Z is a attributed set, but  X ∩ Y = Z would not because the number of solutions are infinte. We have also added support for solutions the subset operator to generate all subsets in case the l.h.s. is variable or formula. The system is not general and quite in it's beginning, but still a bit cool. Now you can do

    %generates all subsets (note that X must be a attribute guarded).
    f1(Z) :- mk({1,2,3},X),Z⊆X.

    %generate all disjoint decompositoins.
    f2(A,B) :- mk({1,2,3},X),(A⊔B)=X.

    %generate all unions decompositoins.
    f3(A,B) :- mk({1,2},X),(A∪B)=X.

    %generate all decompositions of subsets.
    f4(A,B) :- mk({1,2},X),(A⊔B)⊂X.

Runing this gives output:

first case:

    > .* f1(X).
    X = {3,2,1}.
    X = {2,1}.
    X = {3,1}.
    X = {1}.
    X = {3,2}.
    X = {2}.
    X = {3}.
    X = ∅.

second case:

    > .* f2(A,B).

    A = {3,2,1}, B = ∅.
    A = {2,1},   B = {3}.
    A = {3,1},   B = {2}.
    A = {1},     B = {2,3}.
    A = {3,2},   B = {1}.
    A = {2},     B = {1,3}.
    A = {3},     B = {1,2}.
    A = ∅,       B = {1,2,3}.

third case:

    > .* f3(A,B).

    A = {2,1}, B = {1,2}.
    A = {2,1}, B = {2}.
    A = {2,1}, B = {1}.
    A = {2,1}, B = ∅.
    A = {1},   B = {1,2}.
    A = {1},   B = {2}.
    A = {2},   B = {2,1}.
    A = {2},   B = {1}.
    A = ∅,     B = {1,2}.

fourth case:

    > .* f4(A,B).

    A = {1,2}, B = ∅.
    A = {2},   B = {1}.
    A = {1},   B = {2}.
    A = ∅,     B = {2,1}.
    A = {1},   B = ∅.
    A = ∅,     B = {1}.
    A = {2},   B = ∅.
    A = ∅,     B = {2}.
    A = ∅,     B = ∅.

closures in prolog
==================

A closure can be created simplest with name{X,...Z|Goal} or for non arguments,  name{|Goal} it will be directly inserted into the forms meaning that you can't currently manage these lambdas as code objects en e.g. macros. So an example would be

    prolog> X is lam{X|X is 1},X(A).
    --->
    X = lam
    A = 1

Note that we name the closure creation function  lam and enter it in the name space which means that now this will be equivalent,

    prolog> X is lam(), X(A).
    --->
    X = lam
    A = 1

This is useful, but you might not want to name it in that case use lambda or λ and then a unique name will be generated. Anyway naming the lambdas can lead to interesting applications as a way to create closures generating functions. A problem in prolog is to close variables over, we depart here from swi prolog implementation in that closed over variables is marked like v[X]. This means that we can now design more useful lambdas. Here is a show case

    prolog> var(Y),G is lam{X|X is v[Y]},Y is 1,G(A),set(Y,2),G(B).
    –>
    G = lam,
    Y = 2.
    A = 1,
    B = 2.

Note here that all variables in is,<,>,... is has an implicit lookup which is why this works. If you used X = Y in stead we would get A=2.

A closure can create closures which can create closures. This works

    prolog> var(Y),F=lam{S,G|S is s{X|set(v[Y],X)},
                             G is g{X|X is v[Y]  }},
            F(S,G),S(1),G(A),S(2),G(B).
    –>
    F = lam
    S = s
    G = g
    A = 1
    B = 2
    Y = 2

Now if anywhere in the chain of closures a Y is bound that will take precedence and therefore we could have introduced Y in the first closure like,

    prolog> F=lam{S,G|var(Y),S is s{X|set(v[Y],X)},
                             G is g{X|X is v[Y]  }},
            F(S,G),S(1),G(A),S(2),G(B).
    –>
    F = lam
    S = s
    G = g
    A = 1
    B = 2

Note also that we can use the named closure creators and the below is now equivalent

    prolog> S is s(Y), G is g(Y),S(1),G(A),S(2),G(B).
    –>
    S = s,
    G = g,
    A = 1,
    B = 2,
    Y = 2.

Another thing that departs from swi prologs closures is that we have another form that is quite general and we call it a letrec form. the prototype is lam{LHS1 :- RHS1. ... LHS10 :- RHS10.} the predicate shoosen as a closure is also named lam or in case we use annynomous prefix the last predicate inside the bracket. So with this we can do

    prolog> Y=1,X is lam{
               f(X) :- X = v[Y].

               lam([]).
               lam([X|L]) :-
                  f(X),
                  lam(L).},

            length(A,3),X(A).
    –>
    Y = 1
    X = lam
    A = [1,1,1]

Which get's a little more interesting when we can do this after evaluating the above,

    prolog> X is lam(1), Y is lam(2), Z is lam(_), Y=Z,
            length(A,3),X(A),
            length(B,3),Y(B),
            length(C,3),Z(C).
    –>
    X = lam,
    Y = lam,
    Z = lam,
    A = [1,1,1],
    B = [2,2,2],
    C = [2,2,2].

Note how we unified two closures. to se more output of the lambdas, please write the term with quoted(true).

    prolog> Y=1,X is {X|X is Y},write_term(X,[quoted(true)]),nl.
    "A1=lam(1)"

    X = lam,
    Y = 1.

Replacing {...} with {{...}} means that the first one is not closed and the second one is. See below for the definition of closed.

To control the behavior of unification of closed closures, we will have the following api found in [use-modules (logic guile-log prolog closed)].,

prolog error_at_closed_p_handle(Handle), this predicate fetches a handle that represent the predicate of issuing a fail at non matching unification of the codes part of a closed closure. This handle can be guarded by the ideoms in the section about dynamic features so it is really simple to restrict the value to just one part of the code. For a true value of the handle, error will happen at a code missmatch in a unification with at least one closed closure, and else if false, backtracking will result.

prolog close_error_true/0 close_error_false/0, use these funcitons to turn on/off the throwing of error at unification missmatcehs of closed closures code part.

To reflect the closure we have from [use-modules (logic guile-log guile-prolog closures)], and api.

prolog closure_p(Cl), true if Cl is a closure.

prolog closure_state_ref(Cl,L), will expose the state of the closure Cl into L.

prolog closure_is_closed(Cl), true if Cl is a closed closure.

prolog closure_code_ref(Cl,F), will expose the code of the closure Cl into F.

continuation expressions
========================

Prolog passes all in,out,in/out values as arguments to the predicate. This has the drawback, for out variables, that the variables need to be allocated from the heap and adds complexity and overhead to the predicate. If in stead the out variables could be passed over without making a box for it first we get possible much less complexity of the predicate and hence better performance. So let's see the semantics that I plan to add to guile-log and already works today in a experimental compiler of an experimental prolog VM that is included in the guile-log sources. Also vy managing the continuation return values we increase the expressability of our program. The extension uses the binary <= operator and for annonymous continuation forms cc. So the basic form is

    % Executing a goal with out variables
    [V1, ..., Vn] <= goal.

    % Executing a goal with named out variables placed where out may be
    % referenced by executing the goal 'F(...)'

    F(V1, ..., Vn) <= goal.`
    % lets make a predicate that outputs a pure out variable, cc(X,...)
    % exits to the prevoius `<=` and return X,... to it.

    sum(X,Y) :-
       Z is X + Y,
       cc(Z).

    % and let's use it
    printsum(X,Y) :-
      [Z1] <= sum(X,Y),
      write(output(Z1)),nl.

    % we can also just inline code
    printsum(X,Y) :-
      [Z1] <= (X < Y -> (Q is X + Y, cc(Q)) ; cc(X)),
      write(output(Z1)),nl.

Now, it it is possible to compile ordinary old versions of prolog code to take advantage of this system. But I tend to like the clarity of the code where out variables are explicit.

A possible extention for this would be a Tag(V1,...) version, e.g.

    % we can also just inline code
    printsum(X,Y) :-
      A(Z1) <= (X < Y -> (Q is X + Y, cc(Q)) ; A(X)),
      write(output(Z1)),nl.

Then if we have multiple exit points then one can sellect the outer one with the correct tag. Note that this is very similar to catch/throw in prolog. The taged one only works in explicit code, if tags needs to be catched from inside an evaluation of a predicate, then use catch/throw. This system has it's value because the catch/throw is pinned down to assume a predicate can indeed make a throw, but with the cc(...) and F(...) the predicates at tail position in the goal clause is the only one that allow a cc/F-throw. Also a difference is that cc is a continuation, hence the name, e.g. it is not a throw or return in which the bindings are undone as with throw catch.

So to summarize, this extension is only to enable more effective code and enable more opertunity for uses of the stack, catach/throw is more generall and don't enable this oppertunity due to this.

Some examples:

    ?- [X] <= cc(1).

    X = 1.

    ?- [X] <= cc(1,2).

    no

    ?- [X,Y] <= cc(1,2).

    X = 1,
    Y = 2.

    ?- X <= cc(1,2).

    X = [1, 2].

    ?- F(X) <= ((Y <= F(1)),(write(y(Y)),nl))

    X = 1,
    F = lam.

    ?- F(|X) <= ((Y <= F(1)),(write(y(Y)),nl))

    X = [1],
    F = lam.

    ?- F(A|X) <= ((Y <= F(1,2,3)),(write(y(Y)),nl))

    A = 1,
    X = [2, 3],
    F = lam.

Extended Matching.
==================

Good indexing of prolog clauses means mainly that fewer misstakes of leaving a branch in the trail of the control stack in case the algorithms rely on garbage collection. Now there are also speedups potentials for large predicates to be gain as well. Lists is matched and destructed, but not all predicate versions and alternative matches is also not covered but needs to be coded explicitly inside the goal. Let's show how guile-log's extensions solve this.

The first example is how we matched predicates.

    f(F(X|L),g(|M)) :- append(L,M,N), X=h(F|N).

    % f is the same as f2 below
    f2(A,B) :-
       A =.. [F,X|L],
       B =.. [g|M],
       append(L,M,N),
       X =.. [h,F|N].

Guile-log destructs the arguments of a predicate just as with lists and have added a prefix version of | to enable a destruction of all arguments to a list. It is also clear code that can be understood immediately and it is terse, also a good thing is that the destruction in the head is much less general and indexing works much better. The drawback is that | has a special meaning inside matches.

The parser in prolog have been modified to allow expressions in the finction  argument as well and we can now also do (f+g)(X,Y) in extended matching we also allow meaning to , ; - + \+ here A ; B in the head means ((match(A) ; match(B)),! e.g. no backtracking and A , B is matching the same thing with both A and B therefore for:

    -extended.
    f((Op,(< ; >))(X,Y),W) :- ...

Here we will match either (X < Y) or (X > Y) and bind the actual operator to Op which is useful and gainful because the indexer is designed to do the right thing with all extra operators. The ideom above is a really great tool that enables efficient analyzation of expressions. \+ is negation that is good to have and unary + enables normal unification and unary - enables == matching. The default is always that the expression starts in + mode e.g. =.

    -extended.
    f(-f(+X),X).

    ?- f(f(1),X).
      X = 1

    ?- f(X,Y).
      no

In extended matching it is possible to change the operators by using

    -extended(',',och,';',eller).
    f(och(Op,eller(;,','))(X,Y) :- ...

In the future we will allow som basic tests like var,integer,... etc that can increase the potential of the indexer somewhat, but it is not coded yet. also inside == matching it can look clumsy to use +X this is needed in order for terms to be allowed to be simply copied and used in a unification construct that follows the rules of the extended matching. These kind of unifications is not yet coded and is a todo for the future. But in principle variable binding should not need a + and in the future I would like this to be skipt in order to streamline == matching.

Explaing the guile-log dynamic functions
========================================

Dynamic functions in guile-log prolog follows the iso prolog interface. But they are more powerful. They belong to a class of object that we can call dynamic objects for which dynamic features can be added how to backtrack store and restore state. The driving feature is that the state infromation is updated in a funcitonal manner and that its encapsulated with a thread safe handle. But the datastructure are not only functional, in order to have decent properties in prolog program and let them for example back track with the logic program we allow a mark and reset feature. To understand this scope please read about dynamic features. The dynamic functions are optimized for fast lookup and guile log prolog is fully indexed and can yield the matching items faster than it takes to actually perform any common match consequent. The target is for systems that update seldom and do lookup often. The dynamic functions assert* compainion will compile the program to bytecode/native for faster execution. Do not use dynamic functions as a hash table that updates often, for that use the hash table library. Also currently at most 10000 elements can be stored for a dynamic function. (The algorithm scales badly after that and we do not support larger than that).

Dynamic features
================

A dynamic feature is a feature that can be added to the update flow of a dynamic variable, you may want it's state to be saved and restored when a continuation is stored and later executed. You may want the state to be started and restored in a more fine grained pattern when you do paralell. You may want the state to be restored when controls leaves a function either by sucessing or by back tracking and so on. Guile log sports the feature to allow all stateful data such as dynamic functions dynamic vlists, vhashes, operator tables, character translations, flags, and any functional datastructure you can think of that you define in guile scheme and exposed to prolog.

API.
----

There is a section about the scheme part of this interface, here we concentrate on the prolog part. The dynamin objects constructures will be defined in their associated library section, here we just describes what we can impose on them

handles
.......

Use the below accessors to get a handle of various prolog aspects like operator table char conversion table and prolog flags table for defining dynamic features on them.

get_prolog_operators_handle(Handle)

get_prolog_flags_handle(Handle)

get_prolog_conversion_handle(Handle)

backtracking versions
.....................

backtrack_dynamic_object(o, ...) Make sure that after this position and forward in the execution o,... will follow any backtracking and also backtrack to the value that they had at the junction unless a new dynamic feature is encountered.

not_backtrack_dynamic_object(o, ...) Make sure that after this position and forward in the execution o,... will not follow a backtracking unless a new dynamic feature is encountered.

with_backtrack_dynamic_object(o, ...,code) Make sure that inside code the execution o,... will follow any backtracking unless a new dynamic feature is encountered

with_not_backtrack_dynamic_object(o, ...,code) Make sure that inside code the execution o,... will not follow any backtracking unless a new dynamic feature is encountered

guarding states
...............

state_guard_dynamic_object(o, ...), A left limit for which state is restored if the state reinstated over the guard, unless other guards are encountered after this guard.

state_guard_dynamic_object_zip(o, ...), A left limit for which state is restored if the state reinstated over the guard, unless other guards are encountered after this guard. The difference to the above is that this can be placed before a control construct that do parallell execution like interleaving disjunciton or zipping of goals. Hence we do not need to place it in each branch essentially meaning that when each branch is reinstated the dynamic objects value is reinstated for that branch else the control would not pass over the guard and no reinstation would result.

always_state_guard_dynamic_object(o, ...), A left limit for which state is restored always independentof if the state reinstates over the guard, unless other guards are encountered after this guard.

with_state_guard_dynamic_object(o,...,code), will guard the state only in code. But reinstation will not happen unless reinstation is from a backtracked state. That is if reinstation i essentially back tracking it will not restire the state.

with_state_guard_dynamic_object_zip(o,...,code), will guard the state only in code. The same as above but the state will be reinstated when zip et all switches branches.

with_always_state_guard_dynamic_object(o,....,code), ditto but inside code always reinstate state.

guarding values
...............

fluid_guard_dynamic_object(o,...), this will make sure that o,... is resetted to the value they had when the program passed over the guard, and reset to the value it had when control backttraced over it at reinstation over the guard.

with_fluid_guard_dynamic_object(o,...,code), the same as above, but with an extra fluid guard at the success edge of code.

with_fluid_guard_dynamic_object_once(o,...,code), the same as above but takes an optimization by forcing the code to only succeeds once.

utils,
......

There are a few general util funcitons used to manage the state of the dynamic objects in a safe way.

set_dynamic_object(m1 -> m2), the state m1 state is transferd to m2

copy_dynamic_object(m1 -> M2),   M2 will bind to a newly created object containing the state of m1.

Added ontop of this is how to evolve the state data like asserting new facts or to add a new pair on a map. But these operations is defined in each of the library sections.

Prolog libraries exposing guile-log features
============================================

There are a few interesting datastructures and algorithm taken from guile-log that can be directly used in guile-log prolog, here we describe them:

Interleaving constructs.
------------------------

Generally prolog empowers a depth first search. But with the interleaving constructs it is at least in principle possible to do a wide search. Especially if there is branches that are huge or infinite, a solver can get stuck in that branch, missing a simple shallow solution in another branch. The interleaving constructs can cure this.

Api
...

or_i(branch,...), will execute branch... cyclically e.g. first try branch1, if that fails, then try branch2 and if branch-n, the end branch fails, then start all over from the beginning with the next try of branch1 and so on.

and_i(factor,...), will interleave the backtracking of factor... when the whole expression backtracks.

or_union(branch,...), The same as with or_i, but any results will be unique.

Examples
........

/* X = A,A+1,A+2,...,A+10  */
c(X,A)   :- c(X,A,0).
c(X,A,N) :- N < 10,
              (X = A ; (B is A + 1, M is N + 1, c(X,B,M))).

/* or_i test */
f1(X) :- or_i(c(X,0),c(X,100)).

/* and_i test */
f2(X,Y) :- and_i(c(X,0),c(Y,100)).

/* or_union test */
f3(X) :- or_union(c(X,0),c(X,2)).

(prolog-run 10 (X)   (f1 X))
$1 = (0 100 1 101 2 102 3 103 4 104)

(prolog-run 10 (X Y) (f2 X Y))
$2 = ((0 100) (1 100) (0 101) (2 100) (1 101)
      (0 102) (3 100) (2 101) (1 102) (0 103))

(prolog-run 10 (X)   (f3 X))
$3 = (0 2 1 3 4 5 6 7 8 9)

Delimited continuation goals.
-----------------------------

Continuations are a freezed state that is encapsulated by a lambda and can resstart at the stored location when one executes the lambda. Delimited continuations means that one can compose the continuations freely and basically mean thta from a control point the continuation evaluation returns what the lambda inside the control point returns, delimited continuations can therefore be construted and used like any other funciton in a composable way, normal continuatins can be more difficult to handle and does not compose nicely. The delimited continuation goal will fail if the enclosing code fails and it will fail according to the new setup. Also when a delimeted continuation goal succeeds if the continuated enclosed code suceeds (that we restarted in) and the goal works just like any other goal.

Api
...

with_prompt(tag,code,handler_data,handler), The enclosing code is code, which will first executed, if inside this, a abort_to_prompt is executed with a tag, matching this ideoms tag, then the handler will be executed with handler_data unified to,

handler_data = [intag,next,kont,data_from_abort], The actual intag will be intag. A goal, next(), will be supplied which can be used to instruct the code to search for the next handler if executed. The actual continuation goal kont, is supplied as well as data send from the abort_to_prompt in data_from_abort. kont is a term with one argument and is executed like call_k(kont,Arg), sending an Arg to the restart to the continuation. kont is live for the rest of the execution and the handler will at backtracking fail the whole with_promt ideom.

call_k(kont,A), execute a continuation goal.

abort_to_prompt(tag,data_to_handler, data_from_continuation), will abort with tag tag, for which a handler is searched. data_to_handler, is data sent to the handler, and data_from_continuation, is the data that is put inside the argument of the continuation.

re_prompt(tag,kont,handle_data handle kont_data))

re_prompt(kont,handle_data handle kont_data)) (old tag is reused),

an efficiency hack to handle the case when a continuation is executed, but with a new handler in stead of the old one that that continuation came from. This is useful because with this a generator built with this tool does not build up stack.

Example:
........

(use-modules (logic guile-log guile-prolog continuations))

/* produce a value X to the user */
yield(X) :- abort_to_prompt(generator,X,_).

/* consume a value X from the user */
eat(X)   :- abort_to_prompt(generator,_,X).

/* execute Goal and put the resulting generator state in F */
generator(Goal,F) :-
       with_prompt(generator, Goal,[generator,_,K,X], F=[K,X]).

/* [K,X] is the state argument, X will be the next value argument, F will
   bind to the new state */
next([K,X],X,F)        :- re_prompt(K,[generator,_,K2,XX],F=[K2,XX],_).

/* same as next, but Y will be a value fed to the consumer generator */
feed([K,_],Y,F)        :- re_prompt(K,[generator,_,K2,_ ],F=[K2,_ ],Y).

/* the full two way ideom */
translate([K,X],X,Y,F) :- re_prompt(K,[generator,_,K2,XX],F=[K2,XX],Y).

/* sum consumes via eat(X) and add X to the S */
sum(S) :- eat(X),
          SS is S + X,
          sum(SS).

/* yields N,N+1,..,9 */
iter(N) :- N < 10 -> ( yield(N),
                       N2 is N + 1,
                       iter(N2) ).

/* create a producer F and a consumer S */
run :-  generator(iter(0),F),
        generator(sum(0),S),
        pr(F,S).

/* transfers data from the producer to the feeder */
pr(F,S) :- next(F,X,FF) -> feed(S,X,SS), pr(FF,SS).

Zip like constructs
-------------------

This is a construct that let you execute several goals in paralell. currently this is not the same as executing it on multiple threads or processors, it's more that you want to synch solutions to several goal at the same time. The interface sports two commands, one simpler zip, for use, when the goal's are synchronized, and another one usr_zip, for the case when one would like to test the output and in depending on the outcome take the next solution for a subset of the branches.

Api
...

zip(lane(V,Goal),...), will execute Goal ..., in parallel and output the values of the variables V..., for the different branches.

usr_zip(lane(tag,V,Goal),...,guard), this is the same as zip, but we will tag the lane as well. Inside guard, one can execute a command

update(tag,...), where the lanes associated to the tags tag ... is backtracked and updated with new solutions.

Examples
........

  c(X,A)   :- c(X,A,0).
  c(X,A,N) :- N < 10,
                (X = A ; (B is A + 1, M is N + 1, c(X,B,M))).

  f(X,Y) :- zip(lane(X, c(X,0)    ),
                lane(Y, c(Y,100)  )).

  (prolog-run * (X Y) (f X Y))

$1 = ((0 100) (1 101) (2 102) (3 103) (4 104)
      (5 105) (6 106) (7 107) (8 108) (9 109))

  g(X,Y) :- usr_zip(lane(Tag_a,X,c(X,0)),
                    lane(Tag_b,Y,c(Y,0)),
                    (((X mod 2) == 0 -> update(Tag_a)),
                     ((Y mod 1) == 0 -> update(Tag_b)))).

$2 = ((1 100) (3 102) (5 104) (7 106) (9 108))

Hash datastructure
------------------

The main hash datastructure is a vhash datastructure which is a assoc like hash with good lookup properties.

API.
....

make_vhash(Handle), Constructor, generate a dynamic featured vhash unified to Handle.

vhashp(Handle). Succeeds if Handle is a vhash datastructure.

vhash_ref(Handle, Key). References the vhash datastructure.

vhash_cons(Handle, Key, Val). (conses a Key,Val pair onto the Handle.

vhash_for_each(Handle,Key,Val). Will successivly at backtracking bind new values in Key and Val. The generated values will be those defined at the start of the execution of this ideom.

Postpone.
---------

The basic documentation is tha same as the postpone section for guile-log in the main section. The only addition is that this module exposes postpone_frame with an underscore.

Prolog attributed variables interface
-------------------------------------

you find this library at (logic guile-log guile-prolog attribute), the interface is as follows. Also see the main chapter about attributes for details.

prolog attvar(X), successes if X is a attributed variable. or variable.

prolog put_attr(X,Attr,Meta), put put attribute Attr onto X, with metadata Meta.

prolog get_attr(X,Attr,Res), fetch attribute metadata from X.

prolog del_attr(X,Attr), remove attribute from the variable.

prolog raw_attvar(X,Res), fetch the underlying raw variable.

Prolog coroutines framework
---------------------------

Guile prolog coroutining is a development ontop of attributed variables, it contains code that can be used from the library (logic guile-log guile-prolog coroutine).

prolog freeze(Var,Goal), evaluate Goal when Var is bound.

prolog freezeBig(Var, Goal, Unwinder), the same as above, but Unwinder, will be called at backtracking over this signal.

prolog@(guile-user)> freeze(X,write(bound)),X=1.
bound
   X = #(<#gp X0>)
   Y = X1
more (y/n/a/s) >

prolog@(guile-user)> freeze(X,write(bound)),X=Y.
   X = #(<#gp X0>)
   Y = X1
more (y/n/a/s) >

prolog frozen(Var, Goal), find the goals Goal associated to fromzen var Var

freezeId, the identity of the attribute associated with freeze

prolog when(Signal, Goal), Signal is an expression using operators ``,'' ``;'' ``='', nonvar(X) and ground(X). When an binding appears this expression will be checked for validity and if so Goal is executed.

prolog when(Signal, Goal, Off), the same as above but Off is true a no signals will be applied if the variable is reseted to a new value.

prolog whenBig(Signal, Goal, PreGoal, Unwinder), the same as above, but PreGoal is executed before the binding is done, and Unwinder is code that is executed at the unwinding of an successful signaled.

prolog@(guile-user)> when(X=1,write(bang)),X=2.

   X = 2
more (y/n/a/s) > n
prolog@(guile-user)> when(X=1,write(bang)),X=1.
bang
   X = 1
more (y/n/a/s) > n

prolog whenBig(Signal, Goal, Off, PreGoal, Unwinder) The same as above but with an Off variable.

with_coroutines(X,Constructor, Code), this will apply a coroutine constructor Constructor, and in that there is a reference to X, that needs to be an attribute, this will then be a model for variables that are created under an auto atributize environmentm kike using a functor adaptable_vars. inside the Code goal.

prolog with_coroutines(X,[References,...],Constr,Code), the same as above, but all variables inside References will not be copied but referenced. The default is to copy.

prolog auto(Var), this will asume that Var is a variable and will bless is throug binding it to an auto coroutine variable as descrived above.

/* code -----------------------*/
scm[(use-modules (logic guile-log))].
scm[(use-modules (logic guile-log iso-prolog))].
scm[(use-modules (logic guile-log guile-prolog coroutine))].

- adaptable_vars.
f1(X) :- X=[1,Y],Y=1.

- adaptable_vars.
f2(X) :- X=[1,Y],Y=2.
/* --------------------------- */
/* interaction */
prolog@(guile-user)> with_coroutines(X,[Z],when((nonvar(X),X=1,X=Z),
                                                  write(ok))
                                            ,(Z=2,f1(Y))).

   X = #(<#gp X0>)
   Z = 2
   Y = [1, 1]

prolog@(guile-user)> with_coroutines(X,[Z],when((nonvar(X),X=1,X=Z),
                                                  write(ok))
                                            ,(Z=1,f1(Y))).
ok
   X = #(<#gp X0>)
   Z = 1
   Y = [1, 1]

Prolog Canonical Representation
-------------------------------

In especially tablating, but also in other recursive datastructures like printing of these datastructures one need a canonical representation that conforms to a unique referential structure. One such is implemented in (logiv guile-log guile-prolog canon). To enable this feature in e.g. tablating one need to use,

prolog canonize(f,arg ...), this goal will apply the goal f to args arg ... so that any tablating operation or memo operation will be done using a canonical representation, it is also possible to use this goal function together with functorize, as a prolog functor. You may get a direct representation through,

prolog recursive_canonize(X,Out), which will produce as output a canonical representation of X.

Prolog Extensions Of Findall Bagof Etc
--------------------------------------

There are quite a number of acumumulations and related constructs defined in guile-log's prolog, we will discuss them here,

prolog findall(Template,Goal,Result), this will simply copy the template values for all solutions of goal and put it in result. prolog bagof(Template,Goal,Result), this will simply copy the template values for all solutions of goal and put it in result. any templates prefixed like Goal = A^B^Goal2 means that variables A,B will be free to change for each solution of Goal2 e.g. it will find the first acumulation of solutions with all other variables inside Goal2 fixed to the first solution, then at backtracking the next one will be shown etc, here is an example
prolog@(prolog-user)> bagof([X,Y],X^(between(1,3,X),between(1,3,Y)),L).

   Y = 1,
   L = [[1, 1], [2, 1], [3, 1]].
more (y/n/a/s) > y

   Y = 2,
   L = [[1, 2], [2, 2], [3, 2]].
more (y/n/a/s) > y

   Y = 3,
   L = [[1, 3], [2, 3], [3, 3]].
more (y/n/a/s) > y

no

prolog setof(Template,Goal,Result), is the same as bagof, but the fixed variables will not be duplicated if they are. Example

%This will generate two solution with the same X,Y values
prolog@(prolog-user)> setof([X,Y],X^(between(1,3,X),between(1,3,Y),(true;true)),L).

   Y = 1,
   L = [[1, 1], [2, 1], [3, 1]].
more (y/n/a/s) > y

   Y = 2,
   L = [[1, 2], [2, 2], [3, 2]].
more (y/n/a/s) > y

   Y = 3,
   L = [[1, 3], [2, 3], [3, 3]].
more (y/n/a/s) > y

no

The next section will document plain acumulations with numerics. The important adition is that template is evaluated which means that things like sumof(X*X,between(1,10,X),SumOfSquares) does the right thing. The acumulators are: prolog sumof(Expr,Goal,Result), the sum of all expressions, like bagof. prolog prodof(Expr,Goal,Result), the product of all expressions, like bagof. prolog countof(Goal,Result), the count of all solutions, like bagof. prolog maxof(Expr,Goal,Result), the maximum of all expressions, like bagof. prolog minof(Expr,Goal,Result), the minimum of all expressions, like bagof. prolog lastof(Template,Goal,Result), the last expression, like bagof. prolog foldof(Template,Goal,Result).

prolog sumall(Expr,Goal,Result), the sum of all expressions, like findall. prolog prodall(Expr,Goal,Result), the product of all expressions, like findall. prolog countall(Goal,Result), the count of all solutions, like findall. prolog maxall(Expr,Goal,Result), the maximum of all expressions, like findall. prolog minall(Expr,Goal,Result), the minimum of all expressions, like findall. prolog lastall(Template,Goal,Result), the last expression, like findall. prolog foldall(Template,Goal,Result).

The next section describes ideoms like forall that for each acumulated value the predicate suceeds and at backtracking the next value is tried. e.g.
prolog@(prolog-user)> sumstp(X*X,between(1,3,X),L).

   X = 1,
   L = 1.
more (y/n/a/s) > y

   X = 2,
   L = 5.
more (y/n/a/s) > y

   X = 3,
   L = 14.
more (y/n/a/s) > y

no
prolog sumstp(Expr,Goal,Result), the sum of all expressions. prolog prodstp(Expr,Goal,Result), the product of all expressions. prolog countstp(Goal,Result), the count of all solutions. prolog maxstp(Expr,Goal,Result), the maximum of all expressions. prolog minstp(Expr,Goal,Result), the minimum of all expressions. prolog foldstp(Template,Goal,Result).

There is class named as above with the suffix n. This add an extra element first which if an integer n then it will acumulat at most n times and if n == strict(m), then in order for it to sucess exactly m times and if less. So we get the interfaces example:

prolog@(prolog-user)> sumalln(3,X*X,between(1,3,X),L).

   L = 14.
prolog@(prolog-user)> sumalln(2,X*X,between(1,3,X),L).

   L = 5.
prolog@(prolog-user)> sumalln(10,X*X,between(1,3,X),L).

   L = 14.
prolog@(prolog-user)> sumalln(strict(3),X*X,between(1,3,X),L).

   L = 14.
prolog@(prolog-user)> sumalln(strict(2),X*X,between(1,3,X),L).

   L = 5.
prolog@(prolog-user)> sumalln(strict(4),X*X,between(1,3,X),L).

no
prolog sumalln(N,Expr,Goal,Result), the sum of all expressions. prolog prodalln(N,Expr,Goal,Result), the product of all expressions. prolog countalln(N,Goal,Result), the count of all solutions. prolog maxalln(N,Expr,Goal,Result), the maximum of all expressions. prolog minalln(N,Expr,Goal,Result), the minimum of all expressions. prolog lastalln(N,Expr,Goal,Result), the last of all expressions. prolog foldalln(N,Template,Goal,Result).

The same as previous chunk of interfaces but the stepwise version is of cause

prolog sumstpn(N,Expr,Goal,Result), the sum of all expressions. prolog prodstpn(N,Expr,Goal,Result), the product of all expressions. prolog counstpn(N,Goal,Result), the count of all solutions. prolog maxstpn(N,Expr,Goal,Result), the maximum of all expressions. prolog minstpn(N,Expr,Goal,Result), the minimum of all expressions. prolog foldstpn(N,Template,Goal,Result).

The sumof can be adjusted so that i the same solution appears twise then the solution is combined, e.g.

prolog@(prolog-user)> sumofs(X,member(X,[1,2,2,3]),L).

   X = 1,
   L = 1.
more (y/n/a/s) > y

   X = 2,
   L = 4.
more (y/n/a/s) > y

   X = 3,
   L = 3.
more (y/n/a/s) > y

no

prolog sumofs(Expr,Goal,Result), the sum of all expressions. prolog proofs(N,Expr,Goal,Result), the product of all expressions. prolog countofs(N,Goal,Result), the count of all solutions. prolog maxofs(N,Expr,Goal,Result), the maximum of all expressions. prolog minofs(N,Expr,Goal,Result), the minimum of all expressions. prolog foldofn(N,Template,Goal,Result).

The stepwise sumof are: prolog sumofn(Expr,Goal,Result), the sum of all expressions. prolog proofn(N,Expr,Goal,Result), the product of all expressions. prolog countofn(N,Goal,Result), the count of all solutions. prolog maxofn(N,Expr,Goal,Result), the maximum of all expressions. prolog minofn(N,Expr,Goal,Result), the minimum of all expressions. prolog foldofn(N,Template,Goal,Result).

And the combination of the s and n simply is

prolog sumofsn(Expr,Goal,Result), the sum of all expressions. prolog proofsn(N,Expr,Goal,Result), the product of all expressions. prolog countofsn(N,Goal,Result), the count of all solutions. prolog maxofsn(N,Expr,Goal,Result), the maximum of all expressions. prolog minofsn(N,Expr,Goal,Result), the minimum of all expressions. prolog foldofsn(N,Template,Goal,Result).

Af all examples above we also av an argument max and argument min version as well just replace sum with amax or amin bmax or bmin in the name of the predicate e.g. The return value is in the form MAX|ARGMAX with index starting at one and zero for the empty list. Example:

prolog@(prolog-user)> aminall(X,member(X,[2,4,4,1,1,3]),L).

   L = [1|4].
prolog@(prolog-user)> bminall(X,member(X,[2,4,4,1,1,3]),L).

   L = [1|5].
prolog@(prolog-user)> amaxall(X,member(X,[2,4,4,1,1,3]),L).

   L = [4|2].
prolog@(prolog-user)> bmaxall(X,member(X,[2,4,4,1,1,3]),L).

   L = [4|3].

a delay construct.
------------------

Sometimes we don't have currently all information to evaluate an expression, for example in a stream we want to use future values. So it can be nifty to record the evaluation and perform it when values are available. in (logic guile-log guile-prolog delay) we have the tools to do this. The first step is to take an expression and rewrite it for the tool. A variable will have another structure and we will need to insert a value ito this structure outside the normal mechanism for setting a value. so take a normal addition and define

    plus0(X,Y,Z) :-
      XX is val(X),
      YY is val(Y),
      ZZ is ZZ + YY,
      insert(ZZ,Z).

Now using this plus0 we can create a delayd plus with

    plus(X,Y,Z) :- delay(plus0(X,Y,X),[X,Y]).

The first argument in delay is the action that will be fired when both X and Y has been instantiated. the second argument is a list of all variables that must be nonvariable in order to fire plus0(X,Y,Z). This is how it can behave

    prolog> plus(X,Y,Z).
    X = <delay>,
    Y = <delay>,

Let's afterwards insert the value

    prolog> plus(X,Y,Z),insert(1,X),insert(1,Y).
    -->
    X = 1,
    Y = 1,
    Z = 2.

We can chain expressions however we like

    prolog> plus(Z,X,W),plus(X,Y,Z),insert(1,X),insert(1,Y).
    -->
    X = 1,
    Y = 1,
    Z = 2,
    W = 2.

Now the next development out of this is to create a trigger network that works like a spreadsheet of cells. This the variables will be translated to cell structures and keep beeing those, and we need to use the `val` operator to retrieve the value, so here we first define a cell version of `plus`,

    plusc(X,Y,Z) :- cellit(plus0(X,Y,Z),[X,Y]).

and now,

    prolog> cell(Z),plusc(X,Y,Z).
    -->
    X = <cell #>,
    Y = <cell #>,
    Z = <cell #>.

inserting values lead to

    prolog> cell(Z),plusc(X,Y,Z),insert(1,X),insert(1,Y).
    -->
    X = <cell 1>,
    Y = <cell 1>,
    Z = <cell 2>.

And it's mutable but backtrackable to put another value in `X`

@verbatim
    prolog> cell(Z),plusc(X,Y,Z),insert(1,X),insert(1,Y),insert(2,X).
    -->
    X = <cell 2>,
    Y = <cell 1>,
    Z = <cell 3>.

This means that with this little tool you have something vastly better than a spreadsheet at your prolog and guile-log fingertips. Note that to define a variable a cell variable you do, which is not mandatory in this case, Z could be left as a variable.

    cell(Z)

You can initiate it as well

    cell(Z,1)

The predicate cellit will automatically make the variable cell variables but not the depedant variable Z. When it creates a value on it it will however create a cell structured variable. We can also do this,

    prolog> cell([X,Y]),cell([A,B],[1,2]).
    --->
    X = <cell #>,
    Y = <cell #>,
    A = <cell 1>,
    B = <cell 2>.

We could prepend to plusc the following clauses,

    plusc([],[],[]).
    plusc([X|XX],[Y|YY],[Z|ZZ]) :- plusc(X,Y,Z),plusc(XX,YY,XX).

Then we can do,

    prolog > cell(X,[1,2,3]),cell(Y,[9,8,7]),plusc(X,Y,Z).
    ...

Then you will have a normal formula between collumns X,Y,Z just like in a spreadsheet. And then you can manipulate the formula just as you like, store a state, name it, and the continue and later move between them freely in  alightweight manner, because you typically will execute a kind of diff between the different states.

Note that the delay is a more lightweight environment to funcitonally update cells but you can't go backwards. If you want that use clpX in stead.

How to program prolog microkanren style
=======================================

Micro kanren teaches us that infinities can be avoided e.g. a non depth first search. Depth first searches is the base of prolog. To see the problem consider the predicate f as

    f([X|Y]) :- f(X);f(Y).
    f(X) :- X==1.

Then the following search will fail in an infinite loop,

    f([_,1]).

In micro kanren if the search has a solution it will find it in finite time. Wanting to stay with the standard prolog tool, the question is how can we implement support for microkanren like searches. The idea for a solution of this is to construct a continuation tree. E.g. each leaf is a stored state together with the continuatoin of the evaluatoin at that point. We define a new disjunction, G1 ;; G2 that will add two continuations leafs one representing G1 and the other representing G2 at the current level and then do a move. Each node in the tree has a list which containes leafs or new sub nodes that when diving down, you cycle through them. A conjuction of the new kind, G1 ,, G2 will create a new sub node and put it into the tree at current for later move down. The continuation after G1 is to first move up to the conjunction level and that try to satisfy G2 meaning that you will try the last part more often then the first part. And after adding the conjunction to the tree a move is made. A move moves up to the root of the tree and than dives down cycling all nodes down to a leaf, restore the state and continue the evaluation.

The algorithm sticking to guile-log also can create for each leaf a potential value. Then one could seach for a minimal value and execute the minimum leaf cycle between them if the minimum is the same. The tree keeps the minimum of the subtree on the node so the search for the minima is logarithmic in a balanced tree. And where the potential is equal one can cycle. The interface also supports how to decide the value of a list of subnodes / leafs at a certain node, typically the min of them but one can think of other versions.

An example of a potential would be to calculate a complexity at a certain state and try to find the solution that has the least complexity. Other possibilities are depth of the tree, just a sequence of numbers or the inverse of them.

Finally, the definition of f aka microkanren:

    f(X) :- (X=[A|B] ,, (f(A) ;; f(B))) ;; X==1.

or more effectively,

    f(X) :- (X=[A|B] , (f(A) ;; f(B))) ;; X==1.

In order to just get one solution once_i can be used and in order to mimic -> but for the "microkanren" like searches, use -i>.

For the guile-log user that want's to play with a potential, then issue (use-modules (logic guile-log iinterleave)) and use pot-machine-base like

    (pot-machine-base potential)
    ...restOfLogicalClauses

With potential like

    (define (potential s depth) ...)

With s containing potential variable bindings so that logic variable values can be probed.

To play with combiners, like minimum of all nodes / leafs use

    (machine-base* potential min-combine #f)

The interface to min-combine is

    (define (min-combine curent-pot list-of-pre list-of-tail)
      ...)

With current-pot the value of the current potential. list-of-pre is the list of the head of the list that is cycled through at each move. And list-of-tail is the end of the list in reverse order. these lists are lists of leafs or subnodes. if it is a pair, then it is a leaf and the potential is (cdr leaf). If it is a node then the potential of it is (vector-ref node 2). Typical a get function would be,

     (define (get x)
       (if (vector? x)
   	   (vector-ref x 2)
	   (cdr x)))

tabling and prolog
==================

Tabling or memoization in guile-log is revised and updated to reflect the interface found in swi prolog. The guile-log implementation uses the postpone system in order e.g. basically a use of delimited continuations, used in the swi prolog implementation as well. The idea is that at the first time we enters with a pattern, we establish a collection mechanism that collects all values resulting from the evaluation of the predicate, success as well as fail is recorded. Then at a re evaluation the memoized sequence is reused. If we happen to enter as a subgoal the same function with the same signature, then all memoized results are generated and if not all is generated the state is stored and it will delay until more results is available or all are generated. The idea is to batchwise collect continuation points and then when no more solution is available, the stored solutions are retried. In case of a fixpoint it all fails. This means that recursive definitions that in a depth first search lead to infinity loops, it resolves and the a solution is found in finite times. Note that this is another mechansim appart from the minikanren apprach that tries to do this. The difference is that minikanren is more generally in this mechanism. E.g. cases which lead to infinite recursion with tabling can be finite in minikanren, and all cases which is finite with tabling is finite with the minikanren approach. But the memoization means that the speed of the solution with tabling is much better.

So how does the interface look like? Well there is a lightweight version called `memo` and used like.

    -memo.
    fib(0,1).
    fib(1,1).
    fib(N,F) :-
      N1 is N - 1,
      N2 is N - 2,
      fib(N1,F1),
      fib(N2,F2),
      F is F1 + F2

And an example of execution is,

    fib(1000,X).
     X = 703303677114228158218352548771835497701812698363587327...
         426049050871545371181969335797422494945626117334877504...
         492417659910881863632654502236471060120533741212738673...
         39111198139373125598767690091902245245323403501.

That is executed in less than a second. Use memo whan all executions has one solution. The more advanced solution is to use `table` here one specify a set of in-out varaibles and if the result of the non ignored resto of the arguments is from a unique class of solutions we can take shortcuts, else if the classes is infinite e.g. all possible paths from a startpoint to an endpoint in a biderctional graph. The idea is to find a candidate for these remaining variables and there is a system to decide what to store in them. So we have a set of modes. + means an inout variable. min means that the minimum value is stored, 'max' means maximum values of those values are stored, sum means that the sum of the variabvles is stored, last means that the last value is stored. 'first' means that the first encountered value is stored and the predicate search ends (for the others it can happen that a new predicate appears and then the combination is taken and it backtracks. po(f), with predicate f as f(Old,New) menas take new if f is true else take the old value. Finally we have lattice(f) with f=f(Old,New,Res). Here f combines old and new value and produces res which will be used as the value. Sometimes if whatever value an argument has, it has no influence of the result can be signaled with the `ignore` modifier. A good example of ignore can be statistics and e.g. a depth value used to cut an infinite recursion.

Sometimes we want to say that for these incomming values the system has only one solution, to save space and limit the amount of recursion continuations stored. E.g. a way to specify that an + argument is ground. The + modifier will be ground if it is ground and has no unbounded variables. all means that all values can be considered ground. An argument with a modifier ground(f), where the user supplied predicate f=f(Arg) tell if the argument is ground or not.

Let's make an example, consider the minlen predicate

    minlen(X,Y,Z) :-
      length(X,NX),
      length(Y,NY),
      (
        NX < NY ->
          Z=X;
        Z=Y
      ).

Then we can define the path finder f

    -table(+,+,lattice(minlen)).

    f(a,b,[a,b]).
    f(b,a,[b,a]).
    f(b,c,[b,c]).
    f(c,b,[c,b]).
    f(b,d,[b,d]).
    f(d,b,[d,b]).
    f(d,f,[d,f]).
    f(f,d,[f,d]).
    f(c,e,[c,e]).
    f(e,f,[e,f]).

    f(X,Y,P) :-
      f(X,Z,P1),
      f(Z,Y,P2),
      append(P1,P2,P).

With solution

    > .* f(a,_,X).

    X = [a, b].
    X = [a, b, b, a].
    X = [a, b, b, c].
    X = [a, b, b, d].
    X = [a, b, b, c, c, e].
    X = [a, b, b, c, c, e, e, f].

    no.

If we don't care about the actual value of the path we can use the first encountered. Also we show of an ignored depth argument, here is f2

    -table(ignore,+,+,first).

    f2(_,a,b,[a,b]).
    f2(_,b,a,[b,a]).
    f2(_,b,c,[b,c]).
    f2(_,c,b,[c,b]).
    f2(_,b,d,[b,d]).
    f2(_,d,b,[d,b]).
    f2(_,d,f,[d,f]).
    f2(_,f,d,[f,d]).
    f2(_,c,e,[c,e]).
    f2(_,e,f,[e,f]).

    f2(N,X,Y,P) :-
      write(f(N,X,Y)),nl,
      NN is N + 1,
      f2(NN,X,Z,P1),
      f2(NN,Z,Y,P2),
      append(P1,P2,P).

with solutions,

    > .* f2(0,c,_,X).
    X = [c, b].
    X = [c, e].

      f(0, c, X0)

    X = [c, b, b, a].
    X = [c, b, b, c].
    X = [c, b, b, d].

      f(1, b, X0)
      f(2, a, X0)

    X = [c, b, b, d, d, f].

      f(2, d, X0)
      f(3, f, X0)
      f(1, e, X0)

    no.

The system works well under negation and cut's but this is experimental. To make things more efficient a postpone_frame can be issued and then all continuations below that will be managed with it. Else if there is a long path of state changes between the beginning and the actual postpones the system can spend a lot of time restoring and removing that state. The system works in batches however and because we store the tree of state changes moving from one pospone to the next whithin the batch can be lightweight altghough the path from the postpone_frame is long. So it might not be too bad. What doesn't work is if a function is not depending on it's arguments alone e.g. `setval/getval` is used below.

The next level up on this is to make tabling work with interleaving constructs that derive it's roots from kanren. Shorts story is that ,, is an interleaving conjunction and ;; is an interleaving disjunction and once_i(Goal) execute Goal with 0 or 1 success. The system introduces an interleaving frame inside the predicate f when it executes and hence f behaves like a normal predicate and you can use ! to cut it and not need once_i. if f is a recursive table it will guarranteingly execute interleaving construts but also inside the definition of f you may find the inteleaving constructs catched by the predicate and not seen outside it. The tabling interleaving constructs comes in two forms.

table_i, this as arguments just as with table but it also allows interleaving construts in the defenition. Let's see some example: first a non interleaving construct.

    -table.
    fe(a).

    fe([A,B]) :-
      fe(A),
      fe(B).

    ff([U,V]) :- fe(U),!,fe(V).

The execution is not optimal, here is the sequence found,

    > .10 ff(X).

    X = [a, a].
    X = [a, [a, a]].
    X = [a, [a, [a, a]]].
    X = [a, [a, [a, [a, a]]]].
    X = [a, [a, [a, [a, [a, a]]]]].
    X = [a, [a, [a, [a, [a, [a, a]]]]]].
    X = [a, [a, [a, [a, [a, [a, [a, a]]]]]]].
    X = [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]].
    X = [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]].
    X = [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]]].
    X = [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, [a, a]]]]]]]]]]].

The problem with this sequence is that there is finit solutions that are never found. It's with these problems interleaving constructs are well used. So let's hot this example up and define:

    -table_i.
    fe2(a).

    fe2([A,B]) :-
      fe2(A),,
      fe2(B).

    ff2([U,V]) :- fe2(U),!,fe2(V).

Note the interleaving ,, in the definition of fe2 and this function behaves just the same as any other predicate with infinit solutions and here are them,

    > .10 ff2(X).

    X = [a, a].
    X = [a, [a, a]].
    X = [a, [a, [a, a]]].
    X = [a, [[a, a], a]].
    X = [a, [a, [a, [a, a]]]].
    X = [a, [[a, a], [a, a]]].
    X = [a, [a, [[a, a], a]]].
    X = [a, [[a, [a, a]], a]].
    X = [a, [a, [a, [a, [a, a]]]]].
    X = [a, [[a, a], [a, [a, a]]]].

We see that the cut works and that we will generate any finite seqence in finite time.

table_rec, We could try find all recursive solutions to the predicate and any solution with finite number of symbols  should be found in finite time. Soo with,

    -table_rec.
    fe3(a).

    fe3([A,B]) :-
      fe3(A),,
      fe3(B).

    ff3([U,V]) :- fe3(U),!,fe3(V).

We find the solutions,

    > .rec .20 ff3(X).

    X = [a, a].
    X = [a, {0}[ref[0], ref[0]]].
    X = [a, {0}[a, ref[0]]].
    X = [a, {1}[{0}[ref[0], ref[0]], ref[1]]].
    X = [a, {0}[ref[0], a]].
    X = [a, [a, a]].
    X = [a, {0}[ref[0], {1}[ref[1], ref[1]]]].
    X = [a, [a, {0}[ref[0], ref[0]]]].
    X = [a, {1}[{0}[a, ref[0]], ref[1]]].
    X = [a, [{0}[ref[0], ref[0]], a]].
    X = [a, {0}[ref[0], {1}[a, ref[1]]]].
    X = [a, [a, {0}[a, ref[0]]]].
    X = [a, [{0}[ref[0], ref[0]], {1}[ref[1], ref[1]]]].
    X = [a, {0}[ref[0], {2}[{1}[ref[1], ref[1]], ref[2]]]].
    X = [a, [a, {1}[{0}[ref[0], ref[0]], ref[1]]]].
    X = [a, {0}[ref[0], {1}[ref[1], a]]].
    X = [a, [a, {0}[ref[0], a]]].
    X = [a, {2}[{1}[{0}[ref[0], ref[0]], ref[1]], ref[2]]].
    X = [a, {0}[ref[0], [ref[0], ref[0]]]].
    X = [a, {0}[a, [ref[0], ref[0]]]].

Let's see another example where all solutions are recursive, here it is

    -table_rec.
    fd([A|B]) :- (A=1;A=0),,fd(B).

With 20 solutions,

    > .rec .20 fd(X).

    X = {0}[1|ref[0]].
    X = {0}[0|ref[0]].
    X = [1|{0}[1|ref[0]]].
    X = [1|{0}[0|ref[0]]].
    X = [0|{0}[1|ref[0]]].
    X = [0|{0}[0|ref[0]]].
    X = [1, 1|{0}[1|ref[0]]].
    X = {0}[1, 1|ref[0]].
    X = [1, 1|{0}[0|ref[0]]].
    X = [0, 1|{0}[1|ref[0]]].
    X = {0}[0, 1|ref[0]].
    X = [1, 0|{0}[1|ref[0]]].
    X = [0, 1|{0}[0|ref[0]]].
    X = [1, 0|{0}[0|ref[0]]].
    X = [0, 0|{0}[1|ref[0]]].
    X = [1, 1, 1|{0}[1|ref[0]]].
    X = {0}[1, 0|ref[0]].
    X = [0, 0|{0}[0|ref[0]]].
    X = {0}[0, 0|ref[0]].
    X = [1|{0}[1, 1|ref[0]]].

To note, for complex construct it can be a good idea to make use of logical variable that follows like an assoc along the calculation, normal prolog variables is heavily set and unset, which is not needed if one make use of assoc variables.

Using dynwind
=============

This is a prolog construct to assign action on unwind and rewind. When you backtrack you undo all changes to a point and when you restore a state you issues rewind actions. In this undo and redo chain you can issue actions. The problem is that this will be in the middle of a unwind or a rewind and the state is not synchronized. This is a problem. Previosly this is used in fallbacks to protect changes to datastructures and also enable redoing a state at a certain point. This is in C code and call back into scheme so it is a bit slow. So it is limited in what it can do. The task now with dynwind is to enable prolog code to be executed to inform and protect datastructures within prolog itself. To note is that we have a good framework do protect datastructures allready and this should be used primarly, so the use of dynwind should be information only. Anyway in the name of letting the user drown with choices I present. You find it in the module (logic guile-log guile-prolog wind).

    dynwind(OnUnwindGoal),
    dynwind(OnRewindGoal,OnUnwindGoal),

The inner workings of this will at the rewind point or unwind point call the submitted goal and execute with the variable bindings at the point of entering the dynwind. There is a restriction however, you shouled not mix objects used to be protected by guile-log's outomatic framework, that will not work currently because we will not synchronize the state of thos to these timepoints. This is a deficciency but you compining a pure prolog program with dynwind should be safe.

so now you will have,

    > freeze(X, dynwind((write(unwind),nl))),X=1.

    X = 1.
    unwind

Types and Classes
=================

It turns out that with the set implementation together with the fact that acyclic graphs are indexed and a generalized dynamic predicate functionality, we can implement a quite interesting class system that glean on common lisps CLOS. In all we do not implement the full protocoll, but we can connect the dots and get close.

The first thing to note is that set's in guile-log can also represent key value stores or maps. We could therefore define a class as a set of keys, where the values is manipulated with the usage of generalized predicates, just as in guile schemes GOOPS and Common Lisps CLOS. Normal sets and maps are equal if the keys are equal, for attributed guarded sets, full unification on values is also done in case the other variable is a var or attributed gurded set. This means that in  cA={a,b,c} and we have defined f as

    f(cA,1).

Then we for all objects oA (keys + values) with the same keys we have

    > f(oA,X).

    X = 1.

This works even if oA is an attributed set. Name clashes could be a problem if atoms where not named spaced as they are in guile-log. Hence this definition of class and objects are quite general. But as in all guile-log the unfication of strings with atoms is true e.g. a = "a" independent on which name space a is located. So one could define short cuts for e.g. operators that have the same meaning but different implementations available in different name spaces like +,-,*,/ which has an inneficient but standard compliant implementation and a faster more native guile implementation.

Class inherritance is done via the subset relation and we can identify a set oc classes with a inherritance graph via the helper function sets_to_theory in module (logic guile-log guile-prolog set-theory) setting up the class system and issuing this function on a list of class sets we have a class system that essentially create an efficient implementation of the inherritance graph and also maps sets to type index via the lookup function in the module (logic guile-log inheritance). There is also reverse-lookup that can generate the set an index stand for. Anyway with a theory defined we can implement indexing and matching of types where A matches B if  A is a subclass of B or if B ⊆ A. The compiled graph means that if we use indeces instead we will not need to evaluate the whole set, but just do a simple eq? on it and use compiled decitions regarding subclass. Anyway for a typed argument you would typically do it like

    f(X : tA).

With a type index tA. Where the actual object is transferred as X and clause selection is via tA. Finally the order of clauses for generilized functions are peculiar. One can't generally use append or prepend via assertz or asserta. In stead on can use a -generalized. directive in source code or assertg in dynamic context to place the clause sorted for a generalized predicate. The rule is that when asserting a generalized clause, we find the first match of the prevoius clauses and insert the new one before that. This means that more specialized codes will be executed before the less specialized ones.

So now over to an examplification.

First of all we define some helper predicates,

    :- dynamic(class).

    e(X,L) :-
      texp(X,XX,true,LL),
      (
        LL=true ->
          L=XX ;
        L = (LL,XX)
      ).

    texp(X,X,L,L) :- var(X),(\\+attvar(X)),!.
    texp(cls(X),U,L,LL) :- !,
      LL = (L,(class(X,C),U=(X : C))).
    texp(cls(X,C),U,L,LL) :- !,
      get_attr(C,'Type',[A|_]),
      revlookup(A,AA),
      AA ⊆ X,
      LL = (L,(U=(X : C))).

    texp([A|B],[AA|BB],L,LL) :- texp(A,AA,L,L1),texp(B,BB,L1,LL).
    texp(A(|B),AA(|BB),L,LL) :- texp(A,AA,L,L1),texp(B,BB,L1,LL).
    texp({A},{AA},L,LL) :- texp(A,AA,L,LL).
    texp(A,A,L,L).

Here e/2 will represent a goal transformer that replaces cls(X) with   X : tX, where tX is the class index looked up from the object/set X. Or we can say that interpret X as class cA via cls(X,cA) a check for truth will be done and then the actual X : tA will be inserted in the goal.

Lets make a class graph, first prolog code,

    'init-theory' :-
       A is {a},
       B is {b},
       C is A∪B,

       sets_to_theory([A,B,C]),

       define(aS,A),
       define(bS,B),
       define(cS,C).

And run init-theory which will define sets and place the as defined in the module as aS,bS,cS.

Now evaluare the set representation for fast subclass verification, see (logic guile-log inheritance).

    (compile-sup-sub)
    (order-the-set)
    (print-theory)

with output

    (({a,b} -> ({a,b} {b} {a}))
    ({a} -> ({a}))
    ({b} -> ({b})))

Now define the type objects which essentially are special attributed variables found in (logic guile-log types) e.g. mk-type

    (<define> (mktype x y) (mk-type (lookup (<lookup> x)) y))

and prolog:

    mkclass(X,C) :-
      mktype(X,C),
      asserta(class(X,C)).

    tp :-
      mkclass(aS,AT),
      mkclass(bS,BT),
      mkclass(cS,CT),

      define(aT,AT),
      define(bT,BT),
      define(cT,CT).

So aT,bT,cT is the types associated with the set classes aS,bS,cS.

Now define a simple generalized predicate,

    -generalized.
    ftheory(X : aT) :- write(a(X)),fail.
    ftheory(X : bT) :- write(b(X)),fail.
    ftheory(X : cT) :- write(c(X)),fail.

Note that ordinary the last clause will be executed last, but in stead due to the `generalized` directive, it will be places ahead of both the others. Now lets define a simple macro expander and test code,

    t(X) :- e(X,XX),(XX -> write(true(X)) ; write(false(X))),nl.

    test :-
      t(ftheory(cls(aS))),
      t(ftheory(cls(bS))),
      t(ftheory(cls(cS))),

      X is {a-2},
      t(ftheory(cls(X))),

      Y is {a-2,b-4},
      t(ftheory(cls(Y,aT))).

Now running test will result in,

    test.

    a({a})                     false(ftheory(cls({a})))
    b({b})                     false(ftheory(cls({b})))
    c({a,b}) a({a,b}) b({a,b}) false(ftheory(cls({a,b})))
    a(({a-2}∖∅ ∪ ∅))           false(ftheory(cls(({a-2}∖∅ ∪ ∅))))
    a(({a-2,b-4}∖∅ ∪ ∅))       false(ftheory(cls(({a-2,b-4}∖∅ ∪ ∅),X0)))

To note is that the rule for types unification is that cT=aT but not the reverse. So the unification for types is not symmetric that is subs match supers.

wingos fibers wrapper for multithrreaddin green/system
======================================================

Check out wingo's wingos-fibers (https://github.com/wingo/fibers/wiki/Manual). I added support for fibers in guile-log and guile-log prolog. Fibers are an attempt to model multitasking, like in erlang, with cooperative scheduling (meaning that you need to enter a sleep now and then to allow other threads to run. Currently the interface is very simplistic. Here is the prolog interface

To enable this feature use the module logic guile-log guile-prolog fiber`. To enable code that use the scheduler we can use

    with_fibers(Goal).

This will execute Goal with a fiber scheduler enabled, when all fibers have finished this ideom will succeed, the current engine is used for variable bindings.

We can spawn a new fiber inside a `with_fiber` goal e.g.

    spawn_fiber(Goal).

Executes Goal in a new engine in a separate fiber. This engine will need to communicate via channels preferable (see below).

So we can spawn separate fibers. They will not schedule unless you specifically tell them to sleep, wait on io or a result over a channel. To do io in a way that let the io fiber sleep untill io finishes, one need to use the non blocking version of the guile io internals. Sleep and channels can be used as

    sleep(TimeImMs).

    make_channel(Channel).

    put_message(Channel, Message).

    get_message(Channel, Message).

That's it. This is the basic building block to make a quite potent web server where you spawn threads in the same process. This is prefereable multitasking when the scale is not too large and the system is not CPU bound. The reason is of cause that global data is consistant and you may share global state without lock.

It is possible to instrument code to be executed in a fiber within time-slices making sure to inject a possible check of the time alive for the time slice. Then one need to add ideoms for protecting data consistancy. So either the user cooperatively, like it is now, add sleeps. Or we automatically add sleeps, but add data protecting ideoms (e.g. prevent sleep injection).

Finally an example,

    ?- make_channel(Ch),
       with_fibers(
         (
           spawn_fiber(put_message(Ch,1)),
           get_message(Ch,X),
           write(X)
         )).

    1

    Ch = #<<channel> queue-size: 1 state: #<atomic-box 75a52f0 value: ()>>,
    X = 1.

swi prolog engines
==================

A recent addition to swi prolog is engines. These objects are self contained prolog engines with their own stack that maintaines the computation state and will generate each answer back stepwise. Guile log have implemented the same API and is reachable from the library (logic guile-log guile-prolog engine). A good introduction to these engines can be found at swi-engines (http://www.swi-prolog.org/pldoc/man?section=engine-predicates).

Let's consider the creation,

    engine_create(+Template, :Goal, -Engine, +Options)

The idea is to copy_term the Template and Goal simultaniusly and get a indipendent copy for the engine to work on and at yielding a return value a copy_term of that is returned to the enclosing environment. Else everything should be independent.

The idea of guile-log and guile-log-prolog is that it want's to take advantage of a delicate state storage and restorage mechansim. We want the user to be able to stall a calculation and later restore it essentially passing back to the repl with some user data which can be manipulated for investigation and then restore the state and continue the calculation with some user choices added. The idea is that this would be the most powerful repl for deductive machines guided by humans. This means that in guile-log you can have an engine whithin and engine whithin an engine ... and still reach the shell with the storage of the overall state. Another issue is that many variables contained mutating state that should be safe for store / restore. This means that at change of state one need to copy the box values and restore them. Manually this is tedious and the semantics is plentiful for how you would like to maintain this global state. Where guile-log shines is it's toolbox to control these mutating boxes. So in guile-log we can do this, (using engine_next to get the next value).

    ?-  engine_create
              (X,
                (
                 (X=1;X=2),
                 stall
                ),E,[alias(test)]),
        engine_next(E,T1),
        engine_next(E,T2).

    stalled engine > e<test>

    ?- .s 1                           %save current state in tag 1

    ?- .c                             %continue

    stalled engine > e<test>

    ?- .s 2                           %save current state in tag 2

    ?- .c                             %continue

    E = e<test>,
    T1 = 1,
    T2 = 2.

    ?- .l 2                           %load state stored in tag 2

    ?- .c                             % continue from tag 2

    E = e<test>,
    T1 = 1,
    T2 = 2.

    ?- .l 1                           % load tag 1

    ?- .c

    stalled engine > e<test>

    ?- .c

    E = e<test>,
    T1 = 1,
    T2 = 2.

In the next main version of guile, (2.2) there have been a lot of work to enable green threads or fibers. This means that when you get to a blocking io, you will let go for another fiber to run. This is cooparative scheduling and with scheme's delimied continuations you get some really smooth code for executing this. Guile log is enabled to work well with this and you can expect guile-log-prolog to support fibers in the near future.

Green threads or fibers or nice in that maintaining state consistancy is dead simple. If you just can make sure to yield to the scheduler and not risk freezing out other threads - this is the pay you have to do. Assume all fx below spawn an engine with potential blocking io at which time the next fiber is invoked etc.

    g :- f1(X),f2(X),,,,f100(X).

we see that they share state. An engine can be dependant and when a shared variable is unified, it can check for consistancy and add a unifying postprocessing construct knowing that all other engines in the conjunction is not running and complete each unification witout yielding to another fiber in the midle of it. It also means that each thread can fail early e.g. it can early see that X=1 fails when X have been bound to 2 in another fiber. To make this work seamlessly and effectively is difficult but it turns out that guile-log has the right infrastructure to make this work well without too much hazzle. All this is not implemented but is on the drawing board. I will blog with examples when it is implemented. I just fired up guile 2.1.4 which has supports of the right toolbox for io operations.

the art of the return value
===========================

Prolog passes all in,out,in/out values as arguments to the predicate. This has the drawback, for out variables, that the variables need to be allocated from the heap and adds complexity and overhead to the predicate. If in stead the out variables could be passed over without making a box for it first we get possible much less complexity of the predicate and hence better performance. So let's see the semantics that I plan to add to guile-log and already works today in a experimental compiler of an experimental prolog VM that is included in the guile-log sources. Guile log has the <values> ideom. In guile prolog the basic form is. It is also possible to alternatively use <=,=> instead.

    % Executing a goal with out variables
    % unicode ← is indicating a return value, (leftarrow in latex)
    [V1, ..., Vn] ← Goal.

    % Executing a goal with named out variables placed where out may be
    % referenced by executing the goal 'F(...)'

    F(V1, ..., Vn) ← Goal.

    % an alternative default symbol is <=, likewise for rightarrow we have

    Goal → [V1, ..., Vn].
    Goal → F(V1, ..., Vn).

    % lets make a predicate that outputs a pure out variable, cc(X,...)
    % exits to the prevoius `←` and return X,... to it.

    sum(X,Y) :-
       Z is X + Y,
       cc(Z).

    % and let's use it
    printsum(X,Y) :-
      [Z1] ← sum(X,Y),
      write(output(Z1)),nl.

    % we can also just inline code
    printsum(X,Y) :-
      [Z1] ← (X < Y -> (Q is X + Y, cc(Q)) ; cc(X)),
      write(output(Z1)),nl.

Now, it it is possible to compile ordinary old versions of prolog code to take advantage of this system. But I tend to like the clarity of the code where out variables are explicit.

A possible extention for this would be a Tag(V1,...) version, e.g.

    % we can also just inline code
    printsum(X,Y) :-
      A(Z1) ← (X < Y -> (Q is X + Y, cc(Q)) ; A(X)),
      write(output(Z1)),nl.

Then if we have multiple exit points then one can sellect the outer one with the correct tag. Note that this is very similar to catch/throw in prolog. The taged one only works in explicit code, if tags needs to be catched from inside an evaluation of a predicate, then use catch/throw. This system has it's value because the catch/throw is pinned down to assume a predicate can indeed make a throw, but with the cc and ccc the predicates at tail position in the goal clause is the only one that allow a cc/ccc-throw. Also a difference is that cc is a continuation, hence the name, e.g. it is not a throw or return in which the bindings are undone as with throw catch.

So to summarize, this extension is only to enable more effective code and enable more opertunity for uses of the stack, ctach/throw is more generall and don't enable this oppertunity due to this.

Some examples:

    ?- [X] ← cc(1).

    X = 1.

    ?- [X] ← cc(1,2).

    no

    ?- [X,Y] ← cc(1,2).

    X = 1,
    Y = 2.

    ?- X ← cc(1,2).

    X = [1, 2].

    ?- F(X) ← ((Y ← F(1)),(write(y(Y)),nl))

    X = 1,
    F = lam.

    ?- F(|X) ← ((Y ← F(1)),(write(y(Y)),nl))

    X = [1],
    F = lam.

    ?- F(A|X) ← ((Y ← F(1,2,3)),(write(y(Y)),nl))

    A = 1,
    X = [2, 3],
    F = lam.

iterate to e.g. speed up member
===============================

When coding my prolog VM I noticed that the overhead of a prolog call is in the order of 2M execution per second, and this is typically what I see when executing simple prolog perdicates in swi prolog as well. So all complexity that one need to care for simply means a hefty work load for the solver. I can do about 20M operations a second for simple math operations where the stack can be used, and this can be increased with the help of analyzing type flows. The goal is to go up to 100M operations per second as close to the new guile speeds on simple loops. Now, this means that inlining will have dramatic effect on speed of prolog programs and a way to do JIT compiling (still on the VM and later natively) would be helpfull. Anyway here is a simple addition to the prolog:

    % A fast member
    member(X,L) :-
      recur * lp((LL,L)),
        (
          LL=[A|LLL] ->
            (
               A=X;
               lp(LLL)
            )
        ).

    % A fast summer
    sumall(L,S) :-
     recur * lp((SS,0),(LL,L)),
       LL=[X|LLL] ->
         (
            SSS is SS + X,
            lp(SSS,LLL)
         );
         S=SS.

How to debug prolog programs
============================

There is a simple tracing framework that can be used. If one are using compile-prolog-string use syntax parameters Trace = #f/#t to make all function goals defined to be under tracing supervision and use the syntax parameter Level do define the default level. It is possible to force a single defination of a goal functions to be traced by using the prolog functor

prolog -trace.

To define the level of the traced function use prolog -trace(level).

When running the level of the run is controled by trace-level and all defined goal functions that have trace enabled will be printed if,

Level <= trace-level

The simplest way to use this feature is to just use the functor -trace on the goal functions that needs to be traced.

Garbage Collection
******************

Guile log sports full garbage collection of logical variables which makes it suitable to run server like prolog code. It is experimental but working. Unfourtunately the bdw-gc that guile uses does not allow this to work effectively and hence you need to download and replace the standard bdw-gc with a modified version of it. You may find it at

https://gitorious.org/bdw-gc-logical-mod

Now you typically build this and make sure to save the old gc.so that guile is using (you can google how to find which shared libraries guile is using) and then clobber the bdw-gc .so file with the newly created one (sic). This is of cause not a simple thing to do, but until we can get some comparable feature in bdw-gc this is what you need to do. Then finally when configureing guile log do something like

./configure --with-logical-gc

And then make, make install and you will run guile-log with garbage collection on. Then on to happy hacking!.

To note is that only variables and cons cells allocated from stacks will support garbage collecting. Knaren style variables is fundamentally broken with respect to this and one need for that style use other techniques like making use of return variables in functions and the small but potent hacks you may find in the kanren sources. Another option is to make use of guile-log's <call> that will basically only transfer the set of variables in the result essentially skiping all intermediate allocations.

Persistance
***********

It is possible to persist logical datastructures and state. It is not trivial to accomplish this and the interface must enable varying logic in order to meet different demands. One important aspect is that a named variable need to be able to be looked up and at loading new data those variables need to be updated. define-named-object enables this feature. Another feature is that you do not want to update a named objects value make-shallow enables that and will force the persister to just remember the module/name path to it and not persist the value. Finally if you do not want to change the value directly, but a substructure inside of it, associate a getter and a setter via associate-getter-setter and you will be able to maintain the integrity of variable values identity but still update the data. Guile structs, guile-log vlists and vhashes lists prolog variables and cons cells lists vectors closures primitive programs can all be persisted.

API
===

scm (make-persister #:key (file "persist.scm")), this will make a persistance object. You can add datastructures and retrieve datastructures and persist to disk. Datastructures are keyed in.

scm (persist-set! per key data), will add object data associated with key key to the persitance datastructure per.

scm (persist-ref per key), This will retrieve datastructure referenced by key  key in persistance datastructure per.

scm (load-persists per), will load the datastructure from the persistance file defined at the creation of the presistance datastructure.

scm (save-persists per), will save the datastructure from the persistance file defined at the creation of the presistance datastructure.

scm (define-named-object name obj), this is like (define name obj), but obj will, in case of an non immediate, attache a property that indecates to the persister that this object is the same as the named object meaning that in stead of creating a new object it will at loading use the named object.

scm (define-shallow-object name obj), this is like (define name obj), but obj will, in case of an non immediate, attache a property that indecates to the persister that this object is the same as the named object meaning that in stead of creating a new object it will at loading use the named object also this object is shallow meaning that the persister will not touch substructures of the object from the object reference point.

scm (make-shallow obj), This tells the persister to not grovel down the values of this datastructure. Returns the object with the association.

scm (associate-getter-setter obj set get), will add a getter get and a setter set to the non emmidiate object obj. The persister will use the setter and getter to grovel into the objects datastructure to understand what to save and what not to save. Returns the objects with the associations.

(define-fluid-object name val), this is the same as
(define-named-object name
    (associate-getter-setter o fluid-ref fluid-set!))

Index of the guile-log api
**************************