!-- Using MathJax, with the delimiters $ -->
Date lör 03 september 2016

Having had a taste for executing things in paralell in kanren let's move over to guile-log. Executing stuff in paralell is similar but we can take advantage of variable binding beeing done directly on the variable and not bound in a binding data structure. The idea is for each engine keep a path EnginePath=[ek,...,e0] that tracks the state of the engine ek being constructed in engine ek-1 etc. When we store a junction point we make sure that the path is stored with it. This is not dramatic addition of data to the logic engine.

So what happens at backtracking to a state is that one finds the common path both in current EnginePath and the stored path. Then we clear all stacks in EnginePath up to where things are similar and execute the backtracker with the rest of the stored path that differes e.g. FindPath=[fl,...,f0] So initially we had

StoredPath = [a,...,f0,...fl]
EnginePath = [a,...,e0,...ek]
Path       = [f0,...fl]

Now the backtracker has to unwind the stack and undo bindings and dynamic winds etc. At each paralell junction we store a record of the paralell engines created. when unwinding over such a record either there is an angine in the first element of Path, if so we will install that engine and continue unwinding (adding the engine to the global EnginePath) And making sure that we will still keep the record on the old engines stack. If it is not match, all sub engines will be recursivly cleared and then the unwinding of the stack would continue. This describes the unwinding.

API, we have the following API

;; Push an new engine and add it to state, return the engine object
(gp-push-engine state-in engine) => state-out

;; Pop an engine and return new state with this information added
(gp-pop-engine)                  => state-out

;; Yield the current engine
(gp_peek_engine)                 => yield current engine object

;; l is a list of prolog variables which bound should be an engine object
(gp_combine_engines l)           => unspecified

Now engines is just a datastructure consisting of the stack and the object containes extra information that is needed in order for backtracking to work properly.

With this we can design a paralell construct

;; This executes all paralell construct to success in order and then
;; at the later successes in case of an individual arm is back tracking
;; it will not continue with the other parallell branches but continue
;; with the continuation of teh construct
(<define-guile-log-rule> (<pit> cc code ...)
  (<let> ((cc-internal
             (lambda (s p)
               (set! cc-internal cc)
               (CC s p))))
     (<with-cc> cc-internal code ...)))

(<define-guile-log-rule> (<pand> (v engine code ...) ...)
  (<var> (v ...)
    (<let> ((data   (list v ...))
            (frame  (<newframe>))
            (s      s)
            (p      P)
            (cc     CC))
       (<code> (gp-combine-engines data)  ;; record on stack
       (<pit> cc                          ;; cc makes sure the future
                                          ;; is used at back tracking         
         (<with-p> p                      ;; if any angine fails, the whole 
                                          ;; fails
           (<with-s> (gp-push-engine frame engine) ;; push the new engine
             (<=> v ,(gp-peek-engine))             ;; store the engine
                code ...                           ;; execute the branch 
                                                   ;; code
             (<with-s> (gp-pop-engine S) <cc>))))  ;; at the enf pop back 
                                                   ;; the engine
        ...
        (<with-fail> p <cc>)))))          ;; if we fail back we will skip
                                          ;; the whole paralell construct
                                          ;; make sure to prope fail thunks
                                          ;; inside the branches and use
                                          ;; them to backtrack to a specific
                                          ;; branch.

This should as said int the comments be used by probing fail thunks in the specific brances and when executing those the code backtracks to a specific branch and and leave the siblings untouched. See Dependent Kanren for an example.

How would we do about a zip then? here is the code.

(<define-guile-log-rule> (<pzip> (v pp engine code ...) ...)
  (<var> (v ...)
    (<letrec> ((data   (list v ...))
               (frame  (<newframe>))
               (pp     #f)
               (s      s)
               (p      P)
               (cc     CC) 
               (pp     #f) ...
               (pl     '())
               (p0     (lambda ()
                          (set! pl (list pp ...))
                          (f)))                                       
               (f      (lambda ()
                         (if (pair? pl)
                             (let ((p (car pl)))
                               (set! pl (cdr pl))
                               (p))
                             (ccc s p))))

               (ccc    (lambda (s_ p_) (cc s p0))))

       (<code> (gp-combine-engines data) 
       (<pit> ccc                         
         (<with-p> p
           (<with-s> (gp-push-engine frame engine)
             (<=> v ,(gp-peek-engine))            
                code ...                          
             (<code> (set! pp P))
             (<with-s> (gp-pop-engine S) <cc>))))

        ...
        (<with-fail> p0 <cc>)))))

These examples does not work well if one store and restore due to that we mutate varibales. But basically the exact code survives using mutating safe boxes.


Comments

comments powered by Disqus

~ Follow me ~