Kernel Equivalence of Programs and Proving Kernel Equivalence and Correctness by Test Cases
Proceedings of the Second International Joint Conference on Artificial Intelligence. Pages 474-479.
© 1971 International Joint Conferences on Artificial Intelligence
Abstract
The statements in a program may be classified as "kernel statements" if they participate directly in the computation of some output and as "control statements" if they participate directly in deciding the control path at branch points. Two programs are kernel equivalent if they always execute identical sequences of kernel statements given the same inputs. Kernel equivalence is defined formally and is shown to be practically decidable in many cases by a procedure of trying test cases. The concept of program kernel may also be used as a basis for proving correctness of programs.
- Lu ckham , D. C., Park, M. R. and Paterson, H. S. "On formalized computer programs," Jour. Comp. and System Scien ces, 4,3, June 1970.
- Kaplan, D. H. "Regular expressions and the equivalence of programs," Jour. Comp. and System Sciences, 3,4, Nov. 1969.
- Orgass, R. J, "Some results concerning proofs of statements about programs," Jour. Comp. and System Sciences 4,1, Feb. 1970.
- London, R. L., "Computer programs can be proved correct," in Banerji and Hesaro,•ic (eds) Theoretical Appr oaches to Non-nuneri- cal Prob. Solving, Springer-Verlag, 1970.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
I. Introduction.
The most general definition of the equiva lence of programs is the purely functional -- a program represents a mapping from input data sets to output data sets and two programs are equivalent if they represent the same function on the same domain of inputs. The other extreme of equivalence is the purely structural. One assumes a particular representation of programs, e.g. as Algol programs, Turing machines, abstract flowchart graphs, or lambda-calculus expressions. Two programs are then equivalent if they have identical representations, i.e. identical struc tures. Unfortunately, for any fairly general representation of programs, structural identity is too restricted a form of equivalence. On the other hand, determining functional equivalence is usually undecidable in general, and at best requires a detailed knowledge of the properties of the primitive operations and predicates involved.
In this paper, we develop an intermediate definition of equivalence based on program "kernels" which requires only fairly superficial knowledge of the flow of control and data between statements in a program yet which may be used to prove functional equivalence of programs whose structures are quite different. Proving the kernel equivalence of two programs may often be done by observing the results of executing each program on a finite number of test cases.
*This work supported in part by NSF Grant GJ-778
The definition of "kernel equivalence" is developed formally within the framework of the common directed graph representation of programs presented in the next section, (although the use of this particular representation is not essen tial). Following sections develop the defini tion of kernel equivalence in terms of a dis tinction between kernel and control statements and between kernel and control variables. Some examples of equivalence proofs are given. In the concluding section we also argue the rela tionship of kernel equivalence to proofs of pro gram "correctness".
ll. Programs.
As the basic formal model of a program we shall adopt a representation which has been widely used (see e.g. Luckham, Park and Paterson (1), Kaplan (2)). A program is repre sented by a finite directed graph (flowchart) with labeled nodes. Nodes may have zero (exit nodes), one (assignment nodes) or two (branch nodes) exiting arrows. · There is a unique entry node with no entering arrow and every node lies on a path from the entry node to an exit node. The arrows leaving a branch node are labeled ~ and false. Assignment nodes are labeled with assignment statements, branch nodes with branch statements. The entry node is labeled
"ENTER" and each exit node is labeled "EXIT".
Assignment and branch statements are con structed from a set of variables1f=[v 1 ,v 2 ,. ··},
-1. ( nl n2
a set of single-valued functions~= tFl ,F 2 ···l
(where ni specifies the number of arguments of
. [ ml m2 ( Fi) and a set of pred1cates C?= P 1 , P 2 , ··· 5 (where each mi specifies the number of arguments of Pi. A branch statement has the form:
and an assignment statement has the form :
Figure 1 is an example of a program. Execution of a program proceeds according to the usual rules. One begins at the entry node and follows a path through the graph executing assignment statements as they are encountered and choosing the appropriate branch at branch nodes on the basis of the value of the predicate.
The particular representation as a directed graph is not important. Alternatively, we could have used, e.g., an Algol-like program represen tation. The key items of information needed are:
- The possible sequences of statements which may be executed by the program and (2) the flow of data information given by inspecting the variables occurring in the possible sequence of statements.
Some auxiliary definitions are needed.
Let R be the range of possible values for the variables of 'V.
Definition (1.1) If His a program, then the variable set of H,~H' is
Y= tV/VE~ and V occurs as an argument H in some branch or assignment state ment or on the left of ":=" in an assignment statement in H. ]
- (1.2) A value assignment for a program H is a mapping o~into R, which assigns a value from R to each variable of the program. We shall refer to the range of such a function as
a value ~·
- (1.3 ) The initial~ assignments of Hare the value assignments which represent valid initial assignments of values to the variables of H.
- (1.4 ) The execution sequence JI of H for a given initial value assignment I is the sequence s 1 s 2 ... sn of statements executed when His executed with its variables initialized to the values specified by the initial value assi~n ment. If H does not terminate for I then .~I may be infinite.
- (1.5) The result assignment Q 1 of H for a given initial value assignment I is the value assign ment resulting from execution of the program with variables initialized to the values in I. QI is undefined if H does not terminate for I. We assume that the functions and predicates are properly defined so as to always give a value, so that QI is always defined if H does terminate fo r I.
III. Approaches !£ Program Equivalence.
The foregoing definitions give us two v iews of a program H as a function: (1) As a function from initial value assignments to result assignments, Hf(I)=QI (if H terminates on I ) and (2) as a function from initial value assignments to execution sequences Hs (I)= .8 I" Both views in fact may be used as a basis for de finitions of program equivalence, as follows:
- functional equivalence. If H and H 1 are programs th~n H! H 1 (H is functionally equiva l ent to H' ) iff H and H 1 have the same variable sets and the same initial value assignments, and for ev~ ry initial value assignment I, either
both Hf(I) and H 1 f(I) are undefined (do not terminate) or if Hf(I)=Q 1 and H 1 f(I)zQ 1 I' then Q(Q' I (similar to the "strong equivalence" of Luckham, Park, and Paterson (1)).
- Structural equivalence. If H and H 1 are programs then H ! H 1 (H is structurally equiva lent to H 1 ) iff H and H 1 have the same variable sets and initial value assignments, and for every initial value assignment I, Hs(I) z H 1 s(I),
- (i.e. each program executes exactly the same sequence of statements given input values I), and at each branch node the branch statement returns the same value in each program (similar to the "strict equivalence" of Orgass (3)). Structural equivalence does not in fact imply that the graphs for H and H 1 are isomorphic. However, it is clearly a very narrow view of equivalence, requiring that each program execute the same sequence of statements and branches for each input assignment. Functional equivalence, on the other hand, is perhaps the broadest defini tion of equivalence, requiring only that each program produce the same output (or be undefined) for each input assignment. The following result
- follows immediately:
Theorem 1. If H ~ H 1 then H ! H 1 ·
It is fairly clear that any general scheme for proving functional equivalence immediately runs into basic undecidability results (see Luckham, Park, and Paterson (1)) due to the fact that programs may not terminate for some inputs. For the study of practical programs however, it is of interest to press past this roadblock and ask: Suppose we assume termination, can we prove equivalence? This seems not unreasonable since for actual programs we can often use specialized arguments to show that particular programs terminate for the initial value assign ments of interest. Thus we now assume that the initial value assignments for each program H are
restricted to those for which H terminates.
Is functional equivalence decidable given termination? If the set R of possible initial values for variables is infinite, then it is not clear. Suppose that R is finite? Then immedi ately the brute force algorithm will suffice theoretically: execute each program on each possible initial value assignment; the programs are equivalent iff they have the same result in each case. But is such a brute force approach ever practical? (Clearly actual programs always have only a finite range of values possible for each variable.) Unfortunately very seldom, for although theoretically the set of input value sets may be finite, it is ordinarily so large as to preclude exhaustive testing. We are unlikely to find testing equivalence by looking at the outputs of the programs for given inputs a practical possibility even when theoretically feasible. We may fall back on the standard d~bugging tool - try a small set of test cases to gain some partial evidence for equivalence, but no proof.
What other possibilities besides this "black box" approach of matching inputs and outputs is feasible? Clearly, some analysis of program in ternal structure is indicated. At the extreme, isomorphism of programs is a clearly decidable but uninterestingly narrow definition of equiva lence. On the other end of the scale, we might go into the properties of the functions and pre dicates in each program, requiring a set of axioms which allow proving certain functions or sequences of statements to be equivalent. Figure 1 is such a case in point. The program in l(a) computes SUM :z ((((0+1)+2)+3)+4)+5 while that of l(b) computes SUM:=((((0+5)+4)+3)+2)+1. We can only prove they are equivalent if we know that "+" is commutative and associative.
1 (a)

Two Functionally Equivalent Programs.
Proving equivalence in cases where detailed know ledge is needed of the functions and predicates requires a substantial theorem-proving apparatus.
Are there any reasonable definitions of pro gram equivalence which are fairly broad yet re quire only the sort of information found in the abstract programs of the preceding section, name ly information about flow of control and data , but no detailed information about the functions and predicates involved? In the next section, we propose one such definition and then argue that not only is it decidable theoreticaliy but in many cases practically.
IV. Program Kernels and~ Equivalence
The proposed approach to equivalence may be briefly outlined:
- Assume that only certain variables contain significant "output values" on termination. Call these the kernel output variables.
- By backtracing control paths through the program from exit nodes, identify and tag (as ~ statements) all program statements which participate in the computation of the final values of the kernel output variables. At the same time identify the kernel input variables, those variables which are used as arguments in some kernel statement but have no prior assign ment made to them.
- By a similar backtracing from branch node s, identify and tag (as control statements) all branch statements and all statements which parti cipate in the computation of the arguments to branch statements. At the same time identify control input variables, those variables which are used as arguments in some control statement but have no prior assignment made to them.
It should be clear that given complete in formation about flow of control and data in a program, the sets of kernel statements, kernel input variables, kernel output variables, control statements and control input variables may be readily determined (algorithms are given belo~ for the model of the preceding section.) Note that neither the sets of statements nor the sets of variables need be disjoint.
Two programs are said to be kernel equivalent iff (a) they have the same kernel input, kernel output and control input variables sets and the same set of kernel statements, and (b) for each initial value assignment I to kernel and control variables they execute the same sequence of ker nel statements (the kernel execution sequence for I). ---
We shall show that kernel equivalence implies functional equivalence relative to the kernel output variables. Moreover, the kernel execution sequence for a given initial value assignment is dependent only on the values assigned to the ~ trol variables. Thus to determine kernel equiva ~e of two programs we need only try as test cases each possible assignment of initial values to the control variables and compare the kernel execution sequences in each case. Finally we sha ll argue that this technique has a certain pract i cal int e r es t , for ordinaril y control input variabl e s in actual programs have only a small range of values, and there are relatively few contro l input variables at that. It is the ker nel input variables which will contain the real da t a which the progcam manipulates, and thus wh i ch will have a large range of possible values. We may expect often to find only a small number o f possible i nitial assignments to control input variables, thus i ndicating only a small number of test cases to be tried to determine kernel equi val ence which then in turn implies functional equivalence for the variables of interest . Kernel equivalence also has some implications for prov i ng correctness of programs ( see the conclusion) .
We will now show the rigorous development of t hese concepts in the model of the preceding sec t ion :
Ke rne l Output Variab l e s . We may assume that the se t of ke rne l output variables (the variable s whose f inal values are of interest ) is given . Alt e rnative l y, we may identify such a set by t r ac ing forward from nodes containing assignment s tat ements. If the assignment statement has the form U:=F(V 1 , .·. , Vn) and there is a path from the
node t o an exit node which contains no statement i n whi ch U is an argument, then U is a ke rnel ~ ~ va r i ab l e (since U is assigned a value which i n some cases is never later used ) .
Ke rne l Statements and Kerne l Input Variables. Fir s t t ag as a ke r ne l statement each statement in the s t ep above wh i ch comput es a kernel output. Now beg in to itera te: Pick an argument variabl e V in some ke rnel s tat ement U:= F( .·. , V, .·· ) . Trace back a long each pa t h from t he node containing that ke rnel stat ement until an assignment node con ta in ing the assignment V:= ·.· is reached. Tag tha t s t a t emen t as a kernel statement. If the en try node i s r eached and no such assignment ha s been f ound , t hen V is a ~ input variabl e . Repea t t he process until all argument variables in all kernel statements have been tested.
Contro l Statemen ts and Control Input Variables. First tag a s cont rol statements a ll branch state men t s contained in branch node s. Now iterat e exac t l y a s for ke rne l statements: Pick an argu ment va riable in a control stat ement and trace back a l ong each path t o a s t a tement whi ch assigns a va l ue to that variabl e and tag that stat ement as a con tro l s tat ement. I f the entry node i s rea ched then t he va r iabl e is a contro l i nput variabl e . . Cl ea rl y all the se procedure s t e rmina te in a f init e number o f steps.
Kerne l Executi on Sequence. Given an initial va lue a ss ignment I fo r the variable s of a program H, t he ke rne l execution sequence KI of H for 1 is the or dinary execut ion sequence ~I with all but
k~ rne l 3 t a t em~ n t s d ~ l e t e d .
Ke rne l Equi va l ence. Two programs H and H' are k kerne l eguival ent , H = H', i ff
(1 ) H and H' have identical sets of kernel state ments, kernel input variables, kernel output variables and control input variables, and (2) for every initial value assignment I, H and H' have the same kernel execution sequence.
Kernel Equivalence Implies Functional Equivalence. The following theorem follows easily:
Theorem 2. If Hand H' are programs and H ~ H' then H! H' considered as a function only from the control and kernel input variables to the kernel output variables.
Proof Outline: Since the control statements are the only statements which participate in deter mining the execution sequence followed for a particular initial value assignment, the initial values for the control input variables uniquely
determine a kernel execution sequence. H! H' implies, for a given initial value assigrunent I, that KI = s 1 s 2 .·. Sn = K' I " But these kernel statements s 1 .·· Snare the only statements
which participate in determining the values of the kernel outputs , and the initial values of the kernel input variables completely determine the results of executing the statement sequence s 1 .·· Sn. Thus for the same i nitial values of kernel and control input variables, H ~ H' implies that execution of H and H' will produce the same result values in the kernel output
variables. H ~ H' also implies that H terminates on a given initial value set I iff H' terminates on I also. I I
Now the fo llowing r e sult justi f i e s the use of a set of test cas e s for deciding kerne l equivalence.
Theorem 3. If H and H' are programs wi th cal sets of kernel statement s and contro l kernel input and ke rnel output variables , identi input, then
H ~ H' iff H and H' have ident ical kernel
exe cu - tion sequences for each initial va l ue as s i gnment to the control input variabl es.
Proof Outline : The control statements are the only statements which affect the path taken t hrough the program graph during execution . A g iven in i tial value a s signment t o the control input variables de t ermines a unique execut i on sequence and t hus a unique kerne l execution
sequence . Therefore, if I 0 and I 1 are two distinct initial value assignments with ident i ca l a ss ignment s t o t he control variables t hen KI KI r egardles s of t he val ues a ssigned t he 0 1
othe r variables . //
By the preceding theorem i f we r estr ict t he possible in i tial value s of the control input variable s to be finite se ts , then ke rne l equiva l ence is decidable by simply trying each poss ible combination of i nitial value ass i gnment s and l ooking at t he ke rne l execution se quences which r esu lt; The set of poss i ble va lue ass i gnmen ts t o kerne l input variabl e s may be i nf i ni t e or very large without increasing the number of test cases to be tried.
Example 1.
Consider the three programs of Figure 2. Each has a single kernel output variable, OUTPUT, a single kernel input variable, INPUT, no control input variables, and kernel statements:
OUTPUT SUM ·z .. Print(SUM) 0
SUM ·= SUM+ X
X .. Read (INPUT)
In Figure 2, nodes containing kernel statements are tagged with a "K" and those containing con trol statements with a "C".
Are the programs kernel equivalent? By Theorem 3, we need only look at the kernel execu tion sequence for each possible initial assign ment of values to the control input variables. Since that set is empty, there is only one execu tion sequence, and thus only one kernel execution sequence for each program. Figure 3 shows the execution sequence for each program, with non kernel statements in parentheses. Since the ker nel execution sequences for each program are identical, the programs are kernel equivalent. Thus by Theorem 2 they are also functionally equivalent with respect to the input variable INPUT and the output variable OUTPUT. The impor tant point of this proof is that we have used only the simplest arguments to prove functional equivalence of three structurally quite dissimi lar programs.

K

2 (c)
Three Kernel Equivalent Programs.
SUM := 0
(I := 0)
(I ·= I + 1)
X := Read(INPUT
SUM ·= SUM+ X
X .. Read(INPUT)
(I ?; 4?) (I .. I + 1)
(I ?; 4 ?) (I .. I + 1)
SUM .. SUM+ X
X ·= Read(INPUT)
SUM ·= SUM+ X
(I ?; 4 ?)
(I := I + 1) X .. Read(INPUT)
SUM ·= SUM+ X
(I ?; 4 ?)
OUTPUT ·= Print(SUM)
3 (a)
SUM := 0
X := Read(INPUT)
SUM := SUM+ X
X := Read (INPUT)
SUM := SUM+ X
X := Read(INPUT)
SUM := SUM+ X
X := Read (IN PUT)
SUM ·= SUM+ X
OUTPL'T := Print(SUM)
3 (b)
(K := 4)
SUM := 0
X := Read(INPUT)
SUM := SUM+ X
(K 1?)
(K := K - 1)
X := Read (INPUT)
SUM := SUM.+ X
(K 1?)
(K := K - 1)
X := Read(INPUT)
SUM := SUM+ X
(K 1?)
(K := K - 1)
X := Read (INPUT)
SUM := SUM+ X
(K 1?)
OUTPUT := Print (SUM)
3 (c)
Figure l· Execution Sequences for Programs of Figure ~. with Non-kernel Statements in Parentheses, ----
Example 2.
In Figure 4 two programs are given, It is readil y verified that each has a single kernel output variable, OUTPUT, a single kernel input
variable, INPUT, the single control input vari able MODE, and the kernel statements:
OUTPUT .. Print(RES) RES .. RES+ X
RES .. RES*X RES .. 0
RES :· 1
X .. Read(INPUT)
If we assume the range of values for MODE to be the set ('ADD', 'MULT'), then we have two possible initial assignments of a value to the control variable MODE. Looking at the kernel execution sequences of each program for each assignment to MODE, it is readily verified that they are identi cal in both cases, Thus the programs are kernel equivalent and also functionally equivalent with respect to the input variables INPUT and MODE and the output variable OUTPUT.
Kernels and Proving Correctness of Programs. Studies of program equivalence are closely relat ed to studies of program correctness, How does the concept of kernel equivalence aid in proving a program correct? We may readily observe the similarity between the "test case" approach to proving kernel equivalence and the "case analy sis" approach to proving correctness discussed by London in his survey of techniques for proving correctness (4), If we look at the kernel execu tion sequence for each case of initial value assignments to the control input variables in a program, then we might reasonably argue that the program is "correct" if it has the "correct" kernel execution sequence in each case, Since each kernel execution sequence is a simple linear sequence of statements, it appears likely that one could more readily prove the "correctness" of such a statement sequence than the "correct ness" of the original program taken as a whole, and that thus this technique of proving correct ness by "case analysis" would often be useful (and might quite conceivably be mechanized). As a useful debugging tool also, one might envision a "kernel analysis system" which, given a program and a list of its control input variables wi.th their ranges, would simply list the kernel execu tion sequence for each combination of input assignments to the control variables, Inspection of the kernel execution sequences should often suffice to show the "correctness" of the program control structure, and thus the correctness of the program as a whole if one were convinced that the kernel execution sequences were correct,
Conclusion
Kernel equivalence is a rather elementary yet not uninteresting form of program equivalence, Because determination of kernel equivalence re quires only a superficial analysis of flow of control and data in a program, it has some poten tial practical value for application to actual programs,
The analysis of programs in terms of "kernel" versus "control" statements and variables which is used here in an elementary way seems a powerful tool for studying programs.
Clearly there are many other aspects of programs which are also primarily concerned with control, such as subprograms, argument transmission, iteration statements, and block structure, which often may be radically different between two programs which make the same "kernel" computation. An extension of kernel equivalence to encompass these other structures seems feasi ble without greatly increasing the depth of pro gram analysis needed.


@inproceedings{ijcai1971p49,
title = {Kernel Equivalence of Programs and Proving Kernel Equivalence and Correctness by Test Cases},
author = {Pratt, Terrence W.},
booktitle = {Proceedings of the Second International Joint Conference on
Artificial Intelligence, {IJCAI-71}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {D.C. Cooper},
pages = {474--479},
year = {1971},
url = {https://ijcai.org/proceedings/1971/49},
}
TY - CPAPER TI - Kernel Equivalence of Programs and Proving Kernel Equivalence and Correctness by Test Cases AU - Pratt, Terrence W. T2 - Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71 PB - International Joint Conferences on Artificial Intelligence PY - 1971 SP - 474 EP - 479 UR - https://ijcai.org/proceedings/1971/49 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: