|[2 earlier articles]|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (Sarath Kumar) (2001-12-15)|
|Re: Are there any tools that can compare two source files email@example.com (2001-12-19)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (Joachim Durchholz) (2001-12-20)|
|Re: Are there any tools that can compare two source files email@example.com (2001-12-20)|
|Re: Are there any tools that can compare two source files Martin.Ward@durham.ac.uk (2001-12-20)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (2001-12-20)|
|Re: Are there any tools that can compare two source files email@example.com (Ira D. Baxter) (2001-12-22)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (Tim Josling) (2001-12-22)|
|From:||"Ira D. Baxter" <email@example.com>|
|Date:||22 Dec 2001 22:56:42 -0500|
|References:||01-12-027 01-12-058 01-12-076|
|Posted-Date:||22 Dec 2001 22:56:42 EST|
"Nick Maclaren" <firstname.lastname@example.org> wrote in message
> Sarath Kumar <email@example.com> wrote:
> > Generalizing the problem refers to the problem of finding the
> >semantic equivalence of two programs. Is this possible??
> It is not possible. Not even in exponential time. It is at least as
> hard as deciding whether they will halt (for obvious reasons).
> More seriously, I believe that the canonical rearrangement problem IS
> soluble, and I am surprised that there aren't more tools to do it.
> This is because it has two important uses:
> 1) Signatures for separately compiled codes, to determine
> whether rebuilding is necessary.
> 2) Checking for the inheritance of codes, especially in a
> copyright context.
We have a tool, the Clone "Doctor" that detects "similar" code by
doing rather the sort-of-obvious syntax tree comparisons.
Its purpose is to detect "reused" (copied [stolen?]) code. It seems
to be pretty good at that, even though it has only a tiny
"understanding" of program semantics (it understands "sequences").
We've thought a bit about adding certain types of semantic
equivalences (ignoring accidental statement order in the absence of
dependencies), but for practical purposes syntax-tree compares seem
Other researchers have used dynamic programming to detect similarity
with smallest number of edits.
Ira D. Baxter, Ph.D. CTO Semantic Designs, Inc.
Return to the
Search the comp.compilers archives again.