The escape of the batch curse

Consider the following problem, assume that we can generate two random sequences l1,l2 of numbers between 0 and 9, take a transform that to each number map it to the length of when it appears again modulo 10, call this map M. Max be the transform of a sequence by taking the max of the current value and the next. Let Plus be the summation of two such sequences modulo 10. we also assume that we now that the second sequence, l2 has the property that elementwize,

 Max(M(l1)) .leq. Max(M(l2)),

how do we go about to generate

 M(Plus(Max(M(l1)),Max(M(l2)))).

The idea of the solution I would like to play with is to generate a special variable, that when you create it, the value is not known, but you can place it in the right order and then when it's all it's dependants are available the result will be executed. I've played with these ideas a long time a ago here on this blog, but now there is the addition of backtracking that come into play and that we use guile-log and prolog. So what is the main trick that enables this.

Define two predicates, delay and force that is used as follows

plusz(Z,X,Y) :- delay(plusz(Z,X,Y),X,Y) ; 

               (ZZ is X + Y, force(Z,ZZ)

we want to take the addition of X and Y, if X and Y both have been forced dealy will fail, else it will delay the evaluation of plusz(Z,X,Y) and execute that function at the time when both have been forced, to put the value in Z we need to execute special code to force the value if Z as well have been blessed as a delayed value. That's it, its defined in about 50 rows of guile-log code, nothing huge.

The setup to generate sequence is to maintain state and define transforms that initiate the state and update the state, given such transforms one have enough to generate the sequence, so one need to make sense of the following ideoms

next(S,SS) :- ..

start(S)   :- ..

Lets see how it can look for our example in prolog,

next_all2([Z1,Z2,Id,S1,S2,Z],[ZZ1,ZZ2,IId,SS1,SS2,ZZ]) :- 

   next_M(Z1,[R1,P1,C1|_],ZZ1),

   next_M(Z2,[R2,P2,C2|_],ZZ2),

   moving_op(2,maxz,0,U1,C1,S1,SS1),

   moving_op(2,maxz,0,U2,C2,S2,SS2),

   fail_if(P2,(U1 .leq. U2)),

   plus10z(C,  U1 ,U2),

   next_M(Z,[_,_,CZ|_],ZZ),

   plusz(IId,Id ,C),

   writez(_,IId,C,R1,R2).

next_M(Z,X,ZZ)

next_M(Z,X,ZZ), will be the seuence M(l), e.g. it's a construct that generate state information Z->ZZ with the current value X=[l_i,M(l)_i,Redo ...], with l_i the i'th generated random value, M(l)_i the number of times it takes befor l_i appear again in the sequence modulo 10, and Redo will be the backtracking object so that everything restarts from the generation of random value l_i.

moving_op(N,Op,InitSeed,MaxRes,ValIn,S,SS)

N is the length of the window, Op is the reducing operator op(Z,X,Y), InitSeed is the initial value of the reduction. MaxRes is the current result of e.g. the max operation on the window perhaps delayed, ValIn is the value in the sequence S state in and SS is the state out.

fail_if(P,(U1 .leq. U2),U1,U2)

when U1 and U2 have been forced and U1

  plus10z(C,  U1 ,U2),

plus modulo 10 of Max(M(l1) and Max(M(l2))

plusz(IId,Id ,C),

This is a convolution of the generation of solutions C, the result IId_i will be non delayed if and only if when all C_k k

writez(_,IId,C,R1,R2).

Write out the result C and the R1 and R2 generated random valued for l1 and l2.

As you see this approach make sure the combination of values are in the right synchronization and that the solution allow to destruct the problem in reusable more abstract components that one quite easy sew together, that's the power of this idea, you want to change the algorithm, easy to do, the number of buggs will be smaller due to the composability of the approach, neat! Also this approach will be memory safe due to the neat gc that guile-log has regarding logical variables so everything would work on as long sequences that you are prepared to wait for.

Cheers!