This is a continuation of the paralell conjunction ideom i've been working on. Previously the system could not handle variables that is located in many branches at the same time e.g. if you set X=1 in one branch and X=2 in another you would get into troubles. The solution is that internal to guile-log a variable creation is associated with a level and if a variable have been created before the level we collect the binding in an effective assoc datastructure and at the join of the branches we simply say that all bindings should unify else we backtrack. Currently we have a paralell zip aka pzip that are generating solutions in paralell and if there is a conflict all paralell branches will backtrack e.g.
% pzip(Goal1,...,Goaln)
?- pzip((X=1;X=2),(X=1;Y=2)).
X=1.
more? y
X=2,Y=2.
?- pzip((X=1;X=2),(X=2;Y=2)).
X=2,Y=2.
?-
Now a true paralell construct you want to control the backtracking in a more refined way. So what do we need? Well we assume that we probe the Goals in the paralell zip in such a way that we get a control of what to do at the failure of a goal, what to do when a goal succeeeds and together with this probes into faulure thunks that can be gotten through fail(Fail). The paralell construct could be written as
paralell(D1~Goal1~Fail1,...,Dn~Goaln~Failn).
The idea for a framwork is to generate a way to combine Di,Fi to get some kind of composition. So the first one is to do a zip e.g.
(D1,F1) zip (D2,F2) => (D,F)
The idea here is that first we fail via F1, then the continuation of D1 is chained to a fail of F2 where the continuation of D2 yields the continuation of the whole expression. If any of D1 or D2 fails we would then fail totally. This descrive a composition.
We have another compostion that is natural
(D1,F1) , (D2,F2) => (D,F)
Here first failure F2 is executed and in case D2 succeeds the whole expression succeeds else if D2 fails failure F1 would be executed and if D1 succeeds then D2 would be tried from the beginnning and if then D2 succeeds then the whole expression succeeds else if D1 fails we fail. This would generate teh same solutions as `(Goal1,Goal2) under a pure prolog.
We would like to make some dynamism e.g. the actual operation should change from time to time so the API would look something like
?- paralell(P(...),D1~Goal1~F1,...)
% P((D1,F1),(D2,F2),(D,F),Next) :-
(,(D,F),Next) will be added to the predicate and the rest is user supplied. Typically you would then code this as e.g.
p((D1,F1),(D2,F2),(D,F),Next) :-
eval([(D1,F1) , (D2,F2) => (D,F)]),
Next = p2((D2,F2),(D1,F1)).
p2((D1,F1),(D2,F2),(D1,F1),p2((D2,F2),(D1,F1))).
And we see how we can chain the needed abstraction. Not sure what toolbox of low level combining operators we need. Currently we have zip,"," what else? any suggestions?
Let's move over to defining the language for expressing different backtracking patterns given a paralell construct. We need to probe the state and insert alternative ways the code path can take in a fairly abstract and dynamic way. Consider a goal Goal let's probe it (we are now working in scheme):
(<define-guile-log-rule> (paralell chk ((data fail) goal ...) ... body ...)
(let* ((exit (make-variable P)) ...
(code (make-variable #f)) ...
(cc (make-variable #f)) ...
(data (vector exit cc goal)) ...)
(<with-fail> (lambda () ((variable-ref exit)))
(<code> (variable-set! code CC))
goal ...
(<code> set! fail P)
((lambda (s p cont)
(if (variable-ref cc)
((variable-ref cc) s p)
(cont s p)))))
...
body ...))
The ideom of paralell is that it is gathering information and injection points for: 1) what will be executed if the goal fail (exit). 2) the goal itself in case it needs to be redone e.g. (code). 3) What will be executed after the goal e.g. (cc). The technique is to box values that are mutated when probed in the code. Probes are P which will always be bound to the current fail object e.g. when executed it will backtrack from this point to the next disjunction. and CC which probes tha continuation. The idea is to execute all goals after each other and then decide if we are in conflict e.g. we need to backtrack (think that bracnh 1 set X to 1 and branch 2 set X to 2 which results in a backtrack). IThe first thing in the body we need to execute chk with the argument of a backtracking thunk and also instate the fail tunk e.g. if we succeed but later a new solution is requested and we need to backtrack (those two thunks are typically the same. Also note that we could probe for various differnt fail thunks inside the code and this is why we separated data and fail. A paralell zip would then be coded acording to:
(<define-guile-log> <pzip>
(lambda (x)
(syntax-case x ()
((_ (code ...) ...)
(with-syntax (((p ...) (generate-temporaries #'((code ...) ...)))
((d ...) (generate-temporaries #'((code ...) ...)))
((pd ...) (generate-temporaries #'((code ...) ...))))
(with-syntax (((zarg ...)
(fold (lambda (a b seed) (cons* a b seed))
'() #'(d ...) #'(pd ...))))
#'(<paralell> check exit cc
(((d pd) code ...)
...)
(let ((fail (call-with-values
(lambda ()
(jack-the-zipper zarg ...))
(lambda (d dp)
(lambda ()
(do-the-twist-and-fail
exit cc d dp))))))
(check fail)
(<with-fail> fail <cc>)))))))))
We have added the global exit object and the global continuation cc that is used when we sew all things together. The design is to construct a backtracking object and this is done in the code (slightly modified):
(call-with-values
(lambda ()
(jack-the-zipper d pd ...))
(lambda (d dp)
(lambda ()
(do-the-twist-and-fail exit cc d dp))))))
So we have a composer jack-the-zipper it will take a set of pairs d,pd and compse them for a zip pattern. When all compostion is done we can simply add the global fail and cc and issue the backtracker in do-the-twist-and-fail Here is the code for jackie:
(define jack-the-zipper
(case-lambda
((d1 p1)
(values d1 p1))
((d1 p1 d2 p2)
(let* ((exit (make-variable (lambda ()
(error "not hooked in"))))
(exit-1 (vector-ref d1 0))
(exit-2 (vector-ref d2 0))
(cc-1 (vector-ref d1 1))
(cc-2 (vector-ref d2 1))
(start-1 (vector-ref d1 2))
(start-2 (vector-ref d2 2))
(start (lambda (s p)
(variable-set! cc-1 (variable-ref start-2))
((variable-ref start-1) s p)))
(d (vector exit cc-2 (make-variable start))))
(variable-set! exit-1
(lambda () ((variable-ref exit))))
(variable-set! exit-2
(lambda () ((variable-ref exit))))
(variable-set! cc-1
(lambda (s p) (p2)))
(values d p1)))
((d1 p1 d2 p2 . l)
(call-with-values (lambda () (apply jack-the-zipper d2 p2 l))
(lambda (d2 p2)
(jack-the-zipper d1 p1 d2 p2))))))
We have one more composer and that is the conjunctioneur e.g. simulating a normal conjunction and in deed it can yield the same solutions as a normal nonparalell conjunction in it's simplest form and under the assumption that pure prolog is used.
(define conjunctioneur
(case-lambda
((d1 p1)
(values d1 p1))
((d1 p1 d2 p2)
(let ((exit-1 (vector-ref d1 0))
(exit-2 (vector-ref d2 0))
(cc-1 (vector-ref d1 1))
(cc-2 (vector-ref d2 1))
(start-1 (vector-ref d1 2))
(start-2 (vector-ref d2 2))
(start (lambda (s p)
(vector-set! cc-1 (vector-ref start-2))
((vector-ref start-1) s p)))
(d (vector exit-1 cc-2 (make-variable start))))
(variable-set! exit-2
(lambda ()
(vector-set! exit-2 exit-1)
(vector-set! cc-1 start-2)
(p1)))
(values d p2)))
((d1 p1 d2 p2 . l)
(call-with-values (lambda () (apply conjunctioneur d2 p2 l))
(lambda (d2 p2)
(conjunctioneur d1 p1 d2 p2))))))
This shows that we get some nice composable tools to build differnet backtrackers but we need another tool consider
(letrec ((f1 (lambda (exit cc d1 p1 d2 p2)
(set! iter f2)
(do-the-twist-and-fail exit cc d1 dp1)))
(f2 (lambda (exit cc d1 p1 d2 p2)
(set! iter f1)
(do-the-twist-and-fail exit cc d2 dp2)))
(iter f1))
(<paralell> ...
(let ((fail (iter exit cc d1 pd1 d2 pd2)))
(check fail)
(<with-fail> fail <cc>))))
This will alternatively backtrack in the first and second. Let's us finally return to the prolog version of the iterator this kind of iterating pattern is well captured by using prolog variable identities. The rest is to wrap the composition tools exposed in the prolog section as well and connect to the scheme ones. As said in an earlier version of this document any more suggestions of composers?