Date ons 03 oktober 2018

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) :- X==1.
f([X|Y]) :- f(X);f(Y).

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

That's all folks. Happy hacking!


Comments

comments powered by Disqus

~ Follow me ~