3 ms·

If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. There's only so many ways yo

by barrkel 10y ago

If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. There's only so many ways you can write a loop and they all look loop-like, whether it's for / while / do / tail recursion. But if you have a program that doesn't contain a loop at that point at all, or loops over something different, then you've got a different program.

trendia 10y ago
You wouldn't literally mutate the AST, you would rewrite the code so that it performs the same output but using different code. Suppose there is a function y = f(x). You would write a different function g(x) such that g(x) = f(x) for every x, but such that the AST of g is different than the AST of f. You'd probably have to do this manually.
- barrkel 10y ago
  The same output with different code is what a clean room implementation would give you too. So clearly this is an insufficient specification.
noblethrasher 10y ago
> If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. If the original program was written in, say, F# and used a lot of pattern matching, then you could rewrite a straightforward moral equivalent in C# that used lots of visitors. Both the AST and IL will be substantially different, but the performance and functionality will be similar.
- barrkel 10y ago
  You're thinking at a much more concrete level than I am. When I think about an AST differ for the purpose of identifying copied code, I'd abstract out different ways of writing loops; I'd unify polymorphic calls to pattern matching; I'd break function call graphs down to a forest of basic blocks. In other words, I'd tune my AST comparison to actually look for algorithm similarity. I wouldn't be so trivially gamed. Even better, I'd work with a traced execution, and examine isomorphisms between call graphs and data structures.

by barrkel 10y ago

trendia 10y ago

You wouldn't literally mutate the AST, you would rewrite the code so that it performs the same output but using different code. Suppose there is a function y = f(x). You would write a different function g(x) such that g(x) = f(x) for every x, but such that the AST of g is different than the AST of f. You'd probably have to do this manually.

barrkel 10y ago
The same output with different code is what a clean room implementation would give you too. So clearly this is an insufficient specification.

noblethrasher 10y ago

> If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. If the original program was written in, say, F# and used a lot of pattern matching, then you could rewrite a straightforward moral equivalent in C# that used lots of visitors. Both the AST and IL will be substantially different, but the performance and functionality will be similar.

barrkel 10y ago
You're thinking at a much more concrete level than I am. When I think about an AST differ for the purpose of identifying copied code, I'd abstract out different ways of writing loops; I'd unify polymorphic calls to pattern matching; I'd break function call graphs down to a forest of basic blocks. In other words, I'd tune my AST comparison to actually look for algorithm similarity. I wouldn't be so trivially gamed. Even better, I'd work with a traced execution, and examine isomorphisms between call graphs and data structures.