One Shot Prolog

We are going to play with an idea how to implement prolog programs using one shot continuation or simply where we allow a stack-code unit to be attached and detached to the active stack at will.

So the building blocks are that each predicate, \(f\), is defined as a vector or struct contains the elements

$$ f = [UnitsCache,Constr] $$

The idea is that we cache the used stack spaces and reuse them in stead of tearing up and tearing down stacks all the time.

Now getting a unit is done with the 'get-unit' function and the semantics are

(define (get-unit f)
   (let ((l (unit-cache-ref f)))     
     (when (null? l)
       (set! l (list ((get-unit-constructor f)))))

     (let ((unit (car l)))
       ;; Add an item on the stack so that at unwinding the constructed
       ;; unit will be cached
       (register unit f)


Now to start a unit from the beginning it will use the unit's stack and start the code at the code starting point sending the arguments to the unit e.g.

(start cc-unit arg ...)

For predicates, minimally the arguments are \(p,cc,a \ldots\), where \(p\) is the fail unit e.g. we return to it as it located on the chain of stack and is a return point. \(cc\) is the continuation of the algorithm and is a unit that needs to established.

Now in order to start a unit we have the "start" function and in order to return we have the "return" function e.g.

(return p-unit)

This will return to the start of the unit. Finally we have the "self" command it will make a unit that is using the self stack on both sides. Then the "goto-forward-point" command will initiate the self command so that it will return directly with false and later with a non false value. we use it in a "and" construct as

(let ((cc* (self)))
  ;; when one calls (start s pp) this will return pp else at init false
  (aif pp (goto-forward-point cc*)
       ;; Second clause
       (let ((ug (get-unit g)))
         (start ug pp cc))

       ;; First clause
       (let ((uf (get-unit f)))
         (start uf p cc*))))

And similar for "or" we have

(let ((fr (newframe)))
  (let ((uf (get-unit f)))
     (start uf uf cc))
  (unwind fr)
  (let ((ug (get-unit g)))
     (start ug p cc))))

The frame is a stack point in the prolog control stack that enables one to undo variable bindings and other constructs like "dynamic wind" operations and put a used unit on the cache.

It is possible to create the same logic with lambdas and this is done in guile-log but a problem with that is that the compilation time is huge. Also a complexity are that to make the units concept working one need to modify guile itself.