karthikbalaguru said:
Agreed !
Interesting approach ! I think, this is better than the earlier
approach. But, Need to know the kind of programmer style
problems that will not get covered by this second approach.
Any ideas ?
It's not just a question or programming style. You're at the semantics
of the programs. The question is to compare the semantics of two
programs. So you first have to represent the semantics of a program.
One way to do that would be to have a formal semantic definition of
the programming language, and to translate the programs into that
formalism, and then compare thetheir formal semantics.
Unfortunately, not a lot of languages have a formal semantic
definition, and for most of the programming languages which have been
developed without such in mind, when one is developed for them, if it
is complete, then it is rather complex, giving formal semantic forms
that are not really more obvious than the original program (for
example, in the case of C). In conclusion, for these kind of
programming language, the best way to express their semantics in a
formal way is to consider their compilation to some simplier
processor code, and then compare these codes.
Now of course when you compile these two programs:
(defun s1 (v)
(loop for e across v sum e))
(defun s2 (v)
(do ((s 0)
(i (1- (length v)) (1- i)))
((< i 0) s)
(incf s (aref v i))))
you get two different listings, but you have to find a way to conclude
that they do exactly the same thing:
C/LISP[215]> (disassemble 's1)
Disassembly of function S1
(CONST 0) = 0
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
19 byte-code instructions:
0 (CONST&PUSH 0) ; 0
1 (NIL&PUSH)
2 (CONST&PUSH 0) ; 0
3 (JMP L19)
5 L5
5 (LOAD&PUSH 4)
6 (LOAD&PUSH 3)
7 (CALLSR&STORE 1 1 1) ; AREF
11 (LOAD&PUSH 0)
12 (LOAD&PUSH 2)
13 (CALLSR&STORE 2 53 0) ; +
17 (LOAD&INC&STORE 2)
19 L19
19 (LOAD&PUSH 2)
20 (LOAD&PUSH 5)
21 (CALLS2&PUSH 72) ; LENGTH
23 (CALLSR&JMPIFNOT 1 50 L5) ; >=
27 (POP)
28 (SKIP&RET 4)
NIL
C/LISP[216]> (disassemble 's2)
Disassembly of function S2
(CONST 0) = 0
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
17 byte-code instructions:
0 (CONST&PUSH 0) ; 0
1 (LOAD&PUSH 2)
2 (CALLS2&PUSH 72) ; LENGTH
4 (CALLS2&PUSH 152) ; 1-
6 (JMP L20)
8 L8
8 (LOAD&PUSH 1)
9 (LOAD&PUSH 4)
10 (LOAD&PUSH 2)
11 (CALLSR&PUSH 1 1) ; AREF
14 (CALLSR&STORE 2 53 1) ; +
18 (LOAD&DEC&STORE 0)
20 L20
20 (LOAD&PUSH 0)
21 (CALLS2&JMPIFNOT 148 L8) ; MINUSP
24 (LOAD 1)
25 (SKIP&RET 4)
NIL
The semantics of assembly is not more obvious than the semantics of
high level programming languages. The reason why you will work with
assembly is not that (otherwise we would keep programming in
assembly!). The point of assembly, is that the instructions are
simplier: their semantics is simplier. Therefore it is easier for
programs to work with it. You want to compare semantics, then it's
simplier to compare the semantics of simplier instructions. However,
you still have a lot of work to do, even if each step of this work
will be simplier. But it is possible to infer mechanically from both
these assembly codes that each element of the vector is read, and
summed, and that the sum is returned by the function. Therefore that
these two functions are equivalent semantically.