Need for a new pure construct?

[dcnorris]

In our collaborations toward executable specifications for dose-escalation trial designs, @triska and I have encountered a situation that may indicate the need for a new, pure construct for Prolog. (Compare Markus's Preparing Prolog video.) In this post, I'll try to strip away distracting detail specific to oncology dose-finding methods, while retaining enough of the original problem to motivate the code and exhibit our difficulty.

Let's suppose you are constrained to walk along the positive integers, and you do this in an alternating 2-player 'game' where your turn involves deciding whether to move ahead or back, and your nondeterministic opponent decides whether your stride will be 1 or 2.

:- use_module(library(lists)).
:- use_module(library(dcgs)).
:- use_module(library(clpz)).
:- use_module(library(reif)).

:- initialization(assertz(clpz:monotonic)).

state0_decision_state(S0, ahead, S) :-
    #S0 #> 0,
    Stride in 1..2,
    #S #= #S0 + Stride.

state0_decision_state(S0, back, S) :-
    Stride in 1..2,
    #S #= #S0 - Stride,
    #S #> 0.

As you make your decision, consider that you will regret/1 stepping on a prime number:

regret(S) :- is_prime(S).

% I'll include my code for a trial division sieve to make this example complete.
% But this code is merely incidental to the question I'm asking!
indivisible(N, P) :- #N rem #P #> 0.

maplist_maxn(_, [], _) :- !.
maplist_maxn(_, _, 0) :- !.
maplist_maxn(Cont1, [E1|E1s], N) :-
    call(Cont1, E1),
    #Nminus1 #= #N - 1,
    maplist_maxn(Cont1, E1s, Nminus1).

tdsieve(K, Primes, Rest, J, N, PK) :-
    #J #>= 3,
    #J #< #N,
    #J1 #= #J + 2, % TODO: Add 2 instead, skipping evens
    #PK * #PK #=< #J #<==> B, % has current J hit or exceeded PK^2?
    #K1 #= #K + B,
    nth0(K1, Primes, PK1),
    (   maplist_maxn(indivisible(J), Primes, K1) ->
        Rest = [J|Rest1], % O(1) 'append' of N to known Primes
        tdsieve(K1, Primes, Rest1, J1, N, PK1)
    ;   tdsieve(K1, Primes, Rest, J1, N, PK1)
    ).
tdsieve(_, _, [], J, N, _) :- #J #>= #N.

%?- tdsieve(1, [2|OddPrimes], OddPrimes, 3, 10, 2).
%@    OddPrimes = [3,5,7]
%@ ;  false.

primes_below(Primes, N) :-
    #N #> 2,
    Primes = [2|OddPrimes],
    tdsieve(1, Primes, OddPrimes, 3, N, 2), !.

is_prime(N) :-
    #Nplus1 #= #N + 1,
    primes_below(PrimesUpToN, Nplus1),
    member(N, PrimesUpToN), !.

The predicate state0_decision_noregrets/3 reifies our evaluation of decision D made while standing on integer S0:

state0_decision_noregrets(S0, D, Truth) :-
    #S0 #> 0,
    member(D, [ahead, back]),
    (   state0_decision_state(S0, D, S),
        regret(S) -> Truth = false % a single witness suffices
    ;   Truth = true
    ).

Here is where the need lies. It is of the essence of 'regret', that regretting any single possible outcome of a decision causes us to avoid the decision altogether. ("A single witness suffices," one would say.) There is no need to catalogue all possible ways we might regret a decision; indeed if our program were to do so not only would it be inefficient but also (worse!) it would misrepresent essential logic of our problem.

But clearly the (->)/2 used above is an impure construct. Using it safely requires that we ensure S0, D and S are all ground. It would be so much nicer to have a pure construct that allowed us to 'not care' about multiple solutions for S while still allowing S0 and D to be variables over which backtracking would occur with no lost solutions. Is there already a construct or idiom that would achieve this?

To complete the code, here is a DCG describing the paths that may occur in this game. It implements one final bit of core problem logic: ahead is preferred to back:

:- op(900, xfx, ~>).

path(0) --> [].
path(S0) --> { #S0 #> 0,
               indomain(S0), % (see below for the effect of omitting this)
               if_(state0_decision_noregrets(S0, ahead), % prefer forward motion
                   (   D = ahead,
                       state0_decision_state(S0, D, S)
                   ),
                   if_(state0_decision_noregrets(S0, back), % second-best
                       (   D = back,
                           state0_decision_state(S0, D, S)
                       ),
                       (   D = stop, % last resort
                           S #= 0
                       )
                      )
                  ) },
             [D ~> S], path(S).

%?- length(Path, L), phrase(path(8), Path).
%@    Path = [ahead~>9,stop~>0], L = 2
%@ ;  Path = [ahead~>10,back~>9,stop~>0], L = 3
%@ ;  Path = [ahead~>10,back~>8,ahead~>9,stop~>0], L = 4
%@ ;  Path = [ahead~>10,back~>8,ahead~>10,back~>9,stop~>0], L = 5
%@ ;  ... .

%?- phrase(path(21), Path).
%@    Path = [stop~>0]
%@ ;  false.

%?- L in 1..10, indomain(L), length(Path, L), phrase(path(23), Path).
%@ false.

[UWN]

Did you have a look at treememberd_t/3? At least so far, I did not see similar uses.

In your code there is some implicit modedness I am quite unsure about. Some must_be/2s or similar would help. Like in maplist_maxn/3 which

?- Es="a", maplist_maxn(=(a),Es,1).
   Es = "a".
?-         maplist_maxn(=(a),Es,1), Es="a".
false. % unexpected

[UWN]

In other words, the new constructs you need may very well be (;)/3 and call/2.

[dcnorris]

That's a helpful way to put it. Re-reading 'Indexing dif/2' I am struck by how close the spirit of the problem is. Maybe mapping regret to a reified B in 0..1 allows the question of regret to be asked using dif/2, and this achieves a mapping between the problems? I need to think more.

[UWN]

treememberd_t/3 was chosen as a final example because it includes the generality of a search tree and shows how to stop once one desirable node is found.

[dcnorris]

I believe that indeed (;)/3 and call/2 turn out to be the constructs I was seeking:

state0_decision_noregrets2(S0, D, NoRegrets) :-
    #S0 #> 0,
    member(D, [ahead, back]),
    call(
        (   state0_decision_state_regretted(S0, D, S)
        ;   nope
        ),
        Regretted),
    reif:non(Regretted, NoRegrets).

state0_decision_state_regretted(S0, D, S, Regretted) :-
    state0_decision_state(S0, D, S),
    regret(S, Regretted).

regret(S, true) :- regret(S).
regret(S, false) :- \+ regret(S). % Negation of is_prime/1 : ℤ -> {true,false} seems safe.

nope(false).

I will now have to try translating this back to the motivating application...

[UWN]

+ regret(S). % Negation of is_prime/1 : ℤ -> {true,false} seems safe.

Why don't you test this to be sure? With e.g. iwhen/2. %-comments are ignored by Prolog.

[dcnorris]

Sure enough, my comment pointed to a wrong assumption. Starting to think Prolog should reject comments as syntax errors.

regret(S, true) :- indomain(S), regret(S).
regret(S, false) :- indomain(S), \+ regret(S).

%?- S in 1..20, regret(S,true).
%@    S = 2
%@ ;  S = 3
%@ ;  S = 5
%@ ;  S = 7
%@ ;  S = 11
%@ ;  S = 13
%@ ;  S = 17
%@ ;  S = 19
%@ ;  false.

%?- S in 1..20, regret(S,false).
%@    S = 1
%@ ;  S = 4
%@ ;  S = 6
%@ ;  S = 8
%@ ;  S = 9
%@ ;  S = 10
%@ ;  S = 12
%@ ;  S = 14
%@ ;  S = 15
%@ ;  S = 16
%@ ;  S = 18
%@ ;  S = 20.

Now that I have corrected this mistake, I find that (;)/3 & call/2 do not solve my problem, after all:

%?- state0_decision_noregrets(27, D, NoRegrets).
%@    D = ahead, NoRegrets = false
%@ ;  D = back, NoRegrets = true
%@ ;  false.

%?- state0_decision_noregrets2(27, D, NoRegrets).
%@    D = ahead, NoRegrets = false
%@ ;  D = ahead, NoRegrets = true % 27+1=28 case; see below
%@ ;  D = back, NoRegrets = true
%@ ;  D = back, NoRegrets = true
%@ ;  false.

%?- state0_decision_state_regretted(27, D, S, Regretted).
%@    D = ahead, S = 29, Regretted = true
%@ ;  D = ahead, S = 28, Regretted = false
%@ ;  D = back, S = 25, Regretted = false
%@ ;  D = back, S = 26, Regretted = false.

In a separate reply, I will reorganize my code to illustrate what I believe to be the most faithful translation of treememberd_t/3 to this application, showing how it doesn't achieve the elegance desired.

[dcnorris]

Here's a new version of selected parts of the above code:

% 'Laws of motion' are that we are constrained to walk in the
% positive integers. After we have committed to the direction
% of our step, the size of our stride is 'chosen for us' to be
% either 1 or 2 steps.

state0_direction_stride_state(S0, ahead, Stride, S) :-
    #S0 #> 0,
    Stride in 1..2,
    #S #= #S0 + Stride.

state0_direction_stride_state(S0, back, Stride, S) :-
    Stride in 1..2,
    #S #= #S0 - Stride,
    #S #> 0.

% Note the subtle collapse of "direction_stride" to "decision",
% implying that the 'decision' now means choosing a *direction*
% on the understanding that the *stride* is nondeterministic.
% (It's also interesting to me that nondeterminism corresponds
% to the don't-care variable '_'.)
state0_decision_state(S0, D, S) :-
    state0_direction_stride_state(S0, D, _, S).

% Walking according to these rules of motion, we have the further
% consideration that we would regret/1 stepping on a prime number.

regret(S) :- is_prime(S).

state0_decision_noregrets(S0, D, Truth) :-
    #S0 #> 0,
    member(D, [ahead, back]),
    (   state0_decision_state(S0, D, S),
        regret(S) -> Truth = false % a single witness suffices
    ;   Truth = true
    ).

%% What would this look like, if I reworked it along lines of `treememberd_t/3`?
state0_decision_noregrets3(S0, D, NoRegrets) :-
    #S0 #> 0,
    member(D, [ahead, back]),
    call(
        (   state0_direction_stride_state_regretted(S0, D, 1, _) % NB: Here it's crucial to avoid
        ;   state0_direction_stride_state_regretted(S0, D, 2, _) %     repeating a singleton var S!
        ;   nope
        ),
        Regretted),
    reif:non(Regretted, NoRegrets).

state0_direction_stride_state_regretted(S0, D, Stride, S, Regretted) :-
    state0_direction_stride_state(S0, D, Stride, S),
    regret(S, Regretted).

regret(S, true) :- indomain(S), regret(S).
regret(S, false) :- indomain(S), \+ regret(S).

nope(false).

%?- state0_decision_noregrets(27, D, NoRegrets).
%@    D = ahead, NoRegrets = false
%@ ;  D = back, NoRegrets = true
%@ ;  false.

%?- state0_decision_noregrets3(27, D, NoRegrets).
%@    D = ahead, NoRegrets = false
%@ ;  D = back, NoRegrets = true
%@ ;  false.

In treememberd_t/3, there are 3 alternatives subject to short-circuit evaluation: checking the current node, the left branch, and the right branch:

treememberd_t(_, nil, false).
treememberd_t(E, t(F,L,R), T) :-
   call(
     (  E = F
     ;  treememberd_t(E, L)
     ;  treememberd_t(E, R)
     ),
   T).

In my toy example, there are just 2 alternatives: Stride = 1 and Stride = 2. But this presents a problem for our motivating application in dose-finding. There, the options might be (e.g.) that there are T in 0..3 dose-limiting toxicities in a cohort of 3 patients who are enrolled and receive the same dose together. Whereas it may be quite desirable for the structure of the tree to get represented directly in a syntactical structure such as that of treememberd_t/3, it would be extremely inelegant to have to represent 4 separate tests for T in 0..3 syntactically in the program.

Admittedly, it's quite likely that valid expressions of regret in our application ought to obey some 'convexity' requirement such that only the extremities of the range (e.g., T=0 and T=3) should need to be checked. And in that case, we could get away with hard-coding these 2 alternatives as in state0_decision_noregrets3/3 above. But that would feel like letting a drive for purity impose too great a constraint on our representation and solution of our problem.

[UWN]

It helps to suffix _t for all reified predicates. Also, the nope/1 is not necessary at all. "cohort", "together" etc. this all sounds after many more quantors.

[dcnorris]

This observation that I'm after quantification seems correct, a realization I have come to by pursuing this question from a fresh (and more general) perspective.

Specifically, the need I have felt in our application has been to existentially quantify (say) the 2nd argument of a 2-ary predicate. For example,

:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(reif)).
:- initialization(assertz(clpz:monotonic)).

divides(C, D) :- #C rem #D #= 0.

divides_t(C, D, T) :-
    #C rem #D #=0 #<==> #B,
    clpz:zo_t(B, T).

:- meta_predicate any_t(2, ?, ?).

any_t(_, [], false).
any_t(Pred_2, [X|Xs], T) :-
    if_(call(Pred_2, X),
        T = true,
        any_t(Pred_2, Xs, T)
       ).

%?- any_t(divides_t(12), [4,5,6,7], T).
%@    T = true.

%?- any_t(divides_t(12), [5,7], T).
%@    T = false.

In order to do this sort of thing while preserving the non-deterministic formulation of our state0_decision_state/3 predicate, however, we would need to generalize any_t/3 over goals that generate the solutions that are explicitly listed in arg 2:

:- meta_predicate any_that_t(2, 2, ?).

any_that_t(Pred_2, Gen_2, T) :-
    (   (   call(Gen_2, X, true),
            call(Pred_2, X, true)
        ) -> T = true % see discussion below...
    ;   T = false
    ).

% Transpose memberd_t/3 for ease of use
from_t(Xs, X, T) :- memberd_t(X, Xs, T).

%?- from_t([1,2,3], X, T).
%@    X = 1, T = true
%@ ;  X = 2, T = true
%@ ;  X = 3, T = true
%@ ;  T = false, dif:dif(1,X), dif:dif(2,X), dif:dif(3,X).

%?- any_that_t(divides_t(12), from_t([4,5,6,7]), T).
%@    T = true.

%?- any_that_t(divides_t(12), from_t([5,7]), T).
%@    T = false.

I conjecture that it is in general not possible to write any_that_t/3 without recourse to (->)/2 or equivalent impure construct that yields negation-as-failure.

What can be done, however, is to replace arg 2 of any_that_t/3 with a function F_2 together with a list Ls containing elements from the domain of that function:

:- meta_predicate any_map_t(2, 2, ?, ?).

any_map_t(_Pred_2, _F_2, [], false).
any_map_t(Pred_2, F_2, [X|Xs], T) :-
    call(F_2, X, FX), % Note how a MULTIVALUED 'function' F_2 would undermine existential quantification
    if_(call(Pred_2, FX),
        T = true,
        any_map_t(Pred_2, F_2, Xs, T)
       ).

half(D, H) :- #H #= #D / 2.
%?- maplist(half, [2,4,6], H).
%@    H = [1,2,3].

%?- maplist(half, [1,2,3,4,5,6], H).
%@    false. % correct!

%?- any_map_t(divides_t(15), half, [10,20], T).
%@    T = true.

%?- any_map_t(divides_t(15), half, [1,10,20], T).
%@    false. % correct answer to a bad query (1 is not in domain of half/2)

If my conjecture above is correct, then to avoid impure constructs in our application we must explicitly list the possible outcomes (as in arg 2 of any_t/3 or arg 3 of any_map_t/4. Interestingly, this conclusion would corroborate the above suggestion that (e.g.) "cohort" needs further elaboration as a concept: perhaps this elaboration is precisely the listing of the possible toxicity counts.

[UWN]

Just a general remark. Prolog's original pure base is first order logic only. Extensions to something higher-order took some time. In fact, higher-order programing via call/N was invented 1985 or 1986 only. But it took much longer being accepted. And note that this is just higher-order programming. Not higher-order logic.