How should I handle repeated updating in logical programming?

Question

In particular I am trying to determine the best approach to solve the following type of problem:

The example I am interested in is the find-s algorithm in Mitchell's Machine Learning book were it is applied to 4 training examples.

The basic idea is for each training example, x, and hypothesis h, determine h' were it incorporates x by making it more general. I need to map h to h' for each x in the training set. The problem I am having is how to best approach this in a logical programming language. I am using minikanren which is roughly prolog embedded in scheme.

After computing each h', I need to then set! it to a global variable h, and then proceed to the next training example x. The code below is the main part of the program.

(define h '(0 0 0 0 0 0))

(define seto
  (lambda (x)
    (project (x)
             (lambda (s) (set! h x) (succeed s)))))

(run* (q)
     (fresh (x h0 h1)
            (trainingo x)
            (== h h0)
            (find-so h0 x h1)
            (seto h1)
            (== h1 q)))

h is the global variable, seto mutates h with h1 which is the next computed hypothesis from h0 and x training example using the find-s algorithm (find-so).

In prolog it would be (I think) equivalent to assert('hypothesis'(H)) after each training example X (overwriting the the previous one) and calling retract('hypothesis'(H)) after all the training examples have been applied.

Again my question is whether this is the best approach (via side-effects) for solving these kind of problems?

Edit: I accepted @mat answer in conjunction with his comment. In summary I needed to treat the training examples as a list and use forward recursion on that list until I got to the empty list. Were I was getting stuck was in having the training examples as part of the backtracking along with finding the next hypothesis instead of having them in a list of which I can recur on until empty.

You need to explain why exactly you want to do this via side effects. The answer by @mat explains why you shouldn't need side effects for this. — , Oct 21 '16 at 08:44
By the way, you can find examples in Prolog library code of using side effects for efficiency reasons. See [this code in SWI-Prolog's library(aggregate)](http://eu.swi-prolog.org/pldoc/doc_for?object=aggregate_all/3). In any case, you would end up using predicates from the `nb_*` family, where "nb" stands for "non-backtrackable". — , Oct 21 '16 at 09:22
I mentioned this as a comment in @mat answer: "...problem I am having is after I get the next hypothesis and then backtrack to the next training example -- I have lost my next hypothesis. I don't want to use side-effects to resolve this if possible." — Charlie Conroy, Oct 21 '16 at 14:17
don't backtrack. chain the hypothesis updating: h1 + x1 = h2; h2 + x2 = h3; ...; hn + xn = final_h . (see also [@mat's comment](https://stackoverflow.com/questions/40167816/how-should-i-handle-repeated-updating-in-logical-programming#comment67625293_40170550)). — Will Ness, Oct 21 '16 at 14:22
To add to the other comments: you can change Prolog's default depth-first search strategy (through the proof tree) and you should, if this is what your problem requires. In "The Craft of Prolog" there is a whole chapter on different search strategies and how to implement them. — , Oct 21 '16 at 14:35
@Boris Thanks, but I did not need that approach. Minikanren has conde for depth-first and condi for breadth-first. — Charlie Conroy, Oct 21 '16 at 17:35

score 3 · Accepted Answer · edited May 23 '17 at 12:00

What you suggest may seem tempting: Simulate global updates with assertz/0 and retract/1.

However, there are major drawbacks if you do it this way:

Using global states prevents you from using and testing your predicates in isolation.
Using destructive updates prevents you from using your predicates in more directions.
The subtle and implicit dependencies of global states make changes in your predicates very error prone.

A declarative solution to simulate these state changes is to think in terms of relations between states.

For example, when you use H0 to compute the next hypothesis H1, then you can express this as a relation between H0 and H1, and possibly further parameters. Think about predicates like:

hypothesis_next(H0, H1)
algorithm_hypothesis_next(A, H0, H1)
parameters_hypothesis_next(Ps, H0, H1)
etc.

Note that such predicates can be read and—ideally—run in all directions!

In total, the entire solution will in your case be modeled as a sequence of hypotheses:

H0 &rightarrow; H1 &rightarrow; H2 &rightarrow; … &rightarrow; H

For more information and pointers, see the closely related question:

How to avoid using assert and retractall in Prolog to implement global (or state) variables

thanks! But the problem I am having is after I get the next hypothesis and then **backtrack** to the next training example -- I have lost my next hypothesis. I don't want to use side-effects to resolve this if possible. — Charlie Conroy, Oct 21 '16 at 14:13
A solution for this is to replace backtracking by **forward recursion**. Say you have training examples `Es` to refine your hypothesis `H0`. You can describe this with a predicate like: `examples_h0_h([], H, H).` (saying: if there are no examples, then the final hypothesis is the same as the initial one) and `examples_h0_h([E|Es], H0, H) :- hypothesis_next(E, H0, H1), examples_h0_h(Es, H1, H).`, gradually refining the hypothesis with each example. Since this pattern occurs rather frequently in Prolog, there is a meta-predicate called `foldl/4` for this: `foldl(hypothesis_next, Es, H0, H)` — mat, Oct 21 '16 at 14:21

How should I handle repeated updating in logical programming?

1 Answers1