Toward Efficiency Trough Generality

TOWARD EFFICIENCY TROUGH GENERALITY.

Jean Louis LAURIERE Groupe Structures de 1' Information Institut de Programmation 4 Place Jussieu 75230 Paris Cedex OS FRANCE

ABSTRACT: In the following lines we shall adduce new elements to a controversy which lies at the heart of current discussions about programming activities. The question is: must we write speci­ fic programs or general systems ?We shall contrast the two approaches to this methodological problem by means of a case in point. Their respective interest will be compared andasurprising conclusion will eventually be reached which is crucial to the core of AI and justifies many researches in the field : efficiency can only·be attained trough generality.

II - INTRODUCTION.! Work in computer aided programming has two closely related aims: one is program verifying the other is program genera­ ting. Since the pioneering results [3 ] , [9] before the seventies, the two basic doma ins have been extensively studied. Computer aided ve r i f~cations of programs, assertion-basedproofs of programs wherein assertions are both produced and proved automaticaly, syntactic and semantic transformations of programs, program syntheses f rom examples, high level languages are the present common t opics f2 ],[8],[10].

In this context, our purpose is on the contrary t o show, however strange it might seem, that a spec ific algorithm, tailored by hand or by program for a particular problem, can be less eff ec tive than a general system, the essential nature of which is to be non-deterministic and which is able to deal with quite a large family of different problems.

Thus there is no need for provers or syntheti­ s ers but rather for general problem solvers. This paradoxical proposition will be stud1ed through the enlargment of an example belonging to the field of discrete mathematics. We shall argue over an a priori NP-c6mplete [" 11 l problem:

"Build all the permutations over the first n inte gers whi ch verify the following constraints, where m and a ar e two boolean 1X(n-1) given vectors and a is whatever solution looked for :

"'i f r 1 In -1 I : m ( i )= 1 ~ a ( i) < a ( i + 1 ) I a(i)=O ~ Yjf[i+1,n] a(j)la(i)+1, a ( i) = 1 ~ "'j f [ 1 , i -1] ((a ( j) I a ( i) + 1) " a ( i )Ill) ".

For example if n=4, m=(IOI) , a=-(110) , the permutations a.=(l324) and a2=(2314) are the only two to meet the above requirements.

In -FIRST APPROACH : "the natural one".

The possible solutions must be gradually generated and tested; the classical backtrac­ king scheme is therefore called up and the folloliing "script" is immediately set up in our brain

• Point a: place the elements one at a time.
• Point S: test the feasibility of the thus obtained partial a .
• Pointy: carry on if it works;backtrack if part failure or if solution.

This general script must now be made more precise and refined in order to take into account the particulars of our problem. In all cases point a will correspond to something like i=i+l together with a(i)= a(i)+l and with the convenient initializations. As often, point @ will now prove a delicate one. Three tests -say tl, t2 and t3- must be applied here :

tl: a is a permutation,i.e. i+j · a(i)+a(j).

t2: m imposes some monotony constraints.

t3: a imposes less handy constraints.

{

As in any backtrack approach, the manual optimization task will. now consist in setting up these tests early enough and in the right order so as to avoid the generation of useless part solutions. Here,the first test is easy to handle and is certainly the most binding; it will thereforereasonably be undergone first. The monotony test is binding too,and it is much easier to deal with this test than with the conditions derived from a. Indeed this last conditions must be translated by a DO-loop instead of a single IF-statement as with the former ones. Eventually we keep the order tl, t2,t3 to obtain our program wich is thus nearly completed izO ; a :: 0 ; ----------., · n: i=i+l ; IF i>n THEN GOTO y ; [By hypothesis the first (i-1) elements of a are known; a convenient value for a(i) is looked for] * : a ( i) =a ( i) + I IF o ( i) > n THEN GOTO y IF ill THEN GOTO n ;

• B tl [test on a]: DO j=l, i-1 ; IF a(i)=a(j) THEN GOTO * ; END;
• t2 test on m : IF m(i-1)=1 THEN IF a(i)<a(i-1) THEN GOTO *ELSE GOTO t3; IF m(i-1)=0 THEN IF a(i) >a(i-1) THEN GOTOy ELSE GOTO t3;

t3 [test on a]: ie=a(i)+l;

IF a(i)=l THEN DO; IF ie > n THEN GOTO-y;

DO j = I , i- I ; IF a ( j ) = i e THEN GOTO * ; END ;

GOTO n ; END ;

IF a(i)=O THEN DO; IF ie > n THEN GOTO)'j DO j=l,i-1; IF a(j)=ie THEN GOTOn ;END; GOTO * ; END ;

· y: [Backtrack] a(i)=O ; i=i-1 ;

IF i10 THEN GOTO n ELSE STOP·

This program has two important virtues: first it· was very rapidly written and secondly it works correctly and can easily be proved. However this program can of course be strongly improved. The first way is to find out some good lemmas for the formal problem, the second way is to undertake 4irect syntactic transformations of the program ~· The article by KNUTH in 1974 [5) 9riginated many researches in such program manipulations. STANDISH et al [11] made up a general catalogue of such accepted transforma­ tions. ARSAC (1] programmed a nicely interactive system as an aid to program optimization. We give in (7] a more sophisticated version of the program which takes into account other mathemati­ cal properties, which avoids the use of any GOTO statement, and which keeps in memory all the useful information on vector a. The backtrack work will therefore be largely reduced. But we are concerned with a space the size of which is n! and it is likely that any such specialized program cannot work effectively for each couple of m and a. HOwever it seems impossible to achieve much better along this line!

lin - SECOND APPROACH : "the general one" J

In this section we want to introduce and discuss a quite different way of solving this kind of combinatorial problems. It is in fact clear that all the previous work will prove useless if one should change if only a little the constraints attached to our problem: we can therefore have a mind to write a much more powerful system which will solve this whole family of problems invol­ ving discrete finite sets. A great deal of mathematical knowledge and a language to state the different problems are required for achieving this goal.

ALICE already described in [5] is such a code . The p~rmutation generation probiem is given to ALICE rocedural manner as follows:

n

El=l l,n I

m ON E2

SETS

COEFFICIENTS

E2=EI-n.

a ON E2.

FIND BIJECTION a ON El

WITH Vie E2 m(i)=l ~ o(i+l) > o(i) AND

a(i)=o~Vj e [i+l,n] a(j)#a(i)+l AND

a(i)=I~v·e [I,i-1] a(j)1o(i)+l AND a(i) 1n.

Then the system asks for the missing data : value of n, vectors of coeff icients m and a Alice solves the problem quite in the same manner as we solve it by hand. So the main difference with the previous program is the ability of formal manipulations of mathematical expressions. This allows the system to derive implications, to stick to the numerical charac­ teristics of each problem, therefore t o work differently as soon as the data change, to set up good hypotheses and finally to use backtrac­ king in intelligent fashion and non predeter­

mined order. Let us see how ALICE works through some examples of this permutation problem. So if n=9,m=(IIOIOIDI) and a=( III 10110), the system interprets first the constraints deriving from vector m: (A) :a(2) > a( I) and (B) :a(3) > a(2). Now a zero value, namely m(3) is encountered; so m(i)=l is false, the program produces :

[a(i+l) > a(i)] id est a(i+l) ,.; a(i). But as a is by hypothesis a bijection it obtains finally a(i+l) < a(i); so here with i=3 : a(4) < a(3) and likewise a(5) > a(4), a (5) > a(6), a(l) > a(6). a(l) > a(8). a(9) > a(8). The constraints derived from vector a give birth to 22 new expressions from a(I)1a(2)+1 to a(9)1a(8)+1 and besides the system knows that a(l),a(2),a(3),a(4),a(6) and a(7) cannot be equal to 9. By using an ordinal function the sys tern examines now the constraints a 11 t ogether ; a( I) ,.; 6 and a(2) ~ 2 are for instance obtained from (A) and (B). Other values are eliminated in ehismanner until no other information can be obtained. Now comes the time to choose; th~ choice will bear on the element which has the fewest possibilities; in this case, our system notices that only two elements can take value 9, these are a(5) and a(9); the tie is broken by considering the element which appears mostoften in the "1" constraints. So setting a(5)=9 allows new implications and in particular 0(7)18,~6)17, 0(8)17. The next choice is a(3)=8 and the first solution the system gets to is (678193425). In this case 42 solutions altogether are exhibited. Taking another case with m=(OOOOI II I) and a=( I 0000111) the program obtains 48 constraints,but here it is made obvious from vector m that : a(l) ~a(2) ~o(3) ~o(4) ~a(5) and therefore as the lowest value of a(5) is one: 0(1) ~ 5, o (2) ~ 4, a(3) ~ 3, a(4) ~ 2; in the same manner the program shows that 0(9)~5, 0(8)~4, o(7) ~3, and o(6)~2 · Now only one element for 5 and one for 9 are convenient: o(5)=1 and 0(9)=9 are made necessary. As a(5) equals O,o(6) ,0(7) and 0(8) are not equal to 2 and therefore the system comes to o(4)=2; in the same way the system deduces 0(7)#3 and the only convenient antecedent for 3 is 3 : 0(3)=3; then o(8)#4 implies 0(2)=4which produces 0(6)#5. Substitutions give:o(l)=5,o(6)=6,o(7)=7, o(8)=8 in that order the unique solution has been reached directly. We notice that the problem solver uses, by decovering it implicity, the fact that o(j)=n can only occur for a j such that m(j-1 )=I, m(j)=O and a(j)=O; such a lenuna is very useful as an aid for fruitful choices. Many other result s are in fact found by the 'SY'Stem as it rocceds throu h formal mani ulation of cons­ traints. This permutation problem can be viewed too as a El onto itself matching problem and some convenient graph procedures allow the sys­ tem to derive other implications through graphi­ cal arguments [6]).

Let us take a last example to see an obviously polynomial with n behaviour of ALICE together with a catastrophic execution of the specific program first written.

Suppose for n=50 or greater we set: m(l)=a(l)=l and for any i > I : m(i)=a(i)=O. In ALICE the constraints are interpreted and produce o(l)<o(2) with o(2)>o(3)>o(4)> ... >a(n) ; thus o(2)=n and (n-1) values remain for a( I) ; since none contradicts the hypotheses on vector a, (n-1) solutions are inunediately printed : (n-1 ,n,n-2,n-3, ... , I), ... , (I ,n,n-1 ,n-2, ... ,2). On the contrary, the execution of the first written program is not good at all; it will generate the partial permutations 12, 132, ... ,8 9 4 I , ... ,8 9 4 3 2 1, ... with many and many useless attemps. Furthernore, in all of the previous cases, addi­ tional constraints like: o(l)=n/2, a(n/2)=1--or others, w1ll but make the task of our general problem solver easier,as proved on machine,while in the first approach,one is forced to buildnew and new lenunas again and to design in each case a new specialized program.

IIV - CONCLUSION.)

My aim was not to claim that it is impossible to write a specific. program which can work correct­ ly on specific examples; but, there are always new particular cases to take into account and therefore some new adequate statements to add into thi~ program. So, little by little, one is induced to write a quite large code; at this point, if we try a bit harder, we can deal with many other combinatorial problems,say for instance the eight queens, cryptarithmetic, integer mathematical progranuning, optimization problems and so on: such is indeed the scope of a general program. It has been actually shown by ALICE, in all these cases, that generality does

• not contradict efficiency: numerical and graphi­ cal analysis, supported by good heuristics adjusted to each particular case, allows the system to foresee quickly constraint violation even with large size problems.

·Why can a specific program work badly? The first reason is that it lacks one indispensable tool : formal manipulation; although we use this tool very conunonly by hand, too few specialized pro­ grams are able to do so. The second, perhaps more import t reason has to do with the trivial statement i=i+l "ust at the be inin of our specific bac track programs; this means that we construct the objects we are looking for in a predetermined order. But this is unfortunately not the right way to proceed: one element may have an imposed value or another may have significantly fewer possibilities than the others. In one word when we write a specific program we make implicit choices : we have to decide without correct elements of decision because the missing information lies in the data. In that way, to each specific algorithm will correspond a worst case. On the opposite this can hardly be said of a general system with good mathematical knowledge together with heuristics based on rich and varied representations of objects in the univer­ se dealt with : it discovers facts about the problem at the problem statement level not at the code level.

· REFERENCES

[1] Arsac J.:"Syntactic source to source trans­ forms and program manipulation".CACM22,1(1979) 43-54.

[2] Burstall R.and Darlington J."A system which automatically improves programs" Acta Informa­ tica 6, (1976), 41-60. [3] Hoare C.:"An axiomatic basis for computer progranuning" CACM 12,10(1969),576-583. [4] Karp R.: "On the computational complexity of combinatorial problems" Networks 5,(1975),45-68. [5] Knuth D.:"Structured progranuning with GOTO statements" ACM.Comp.sur. 6,4(1974), 261-301. [6] Lauriere J.L.:"A language and a program for stating and solving combinatorial problems" Art. Int. 10, I (1978), 29-127.

[7] Lauriere J.L.:"Specific algorithms versus general programs", GR 22, A.I. (1979). L8] Lee et al :"An improved program synthesis and its correctness" CACM 17,4(1974),211-217. [9 ] Manna Z.:"The correctness of programs". J. Comp. Sys. Sciences 3,2(1969),142-156. [10]Manna Z,Waldinger R :"A deductive approach to program synthesis" SRI Tech. R.l77 (1978). [11]Standish et al: "Improving and refining programs by program manipulation". ACM Nat. C. (1976), 509-516.