Comparing programs

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Comparing programs

Harry Chesley
This is more of an algorithm question than a language question, but any
insights would be much appreciated.

The problem is to input a series of programs and find previous
occurrences of the same algorithm.

The programs consist of a set of input parameters (a, b, c, ...), and a
set of side-effect-free functions (f, g, h, ...). Since the functions
are side-effect-free, they can be reordered without changing the
algorithm ("f(a), g(b)" is the same as "g(b), f(a)"). Subsequent calls
of the same function with the same parameters have no effect ("f(a),
f(a)" is the same as "f(a)"); in fact, you can assume duplicates have
been removed in earlier processing.

But here's the thing that makes it hard (at least for me): two programs
are considered the same if they can be made to match by rearranging the
order of the input parameters. I.e., "f(a), g(b)" is the same as "f(b),
g(a)". Although parameters can be reordered, they cannot be substituted
("f(a), g(b)" is _not_ the same as "f(a), g(a)").

Example: "f(a), g(b), h(a, b)" is the same as "f(b), g(a), h(b, a)" but
_not_ the same as "f(a), g(b), h(b, a)".

I need a way to compare the input programs, and preferably to order them.

In Haskell terms, given the programs are represented by a type Prog, I
want Prog to be a member of class Ord, letting me use tools like
Data.Map to look up information about previous instances.

I can do a brute-force compare by trying all the parameter permutations,
but that only gives me Eq, not Ord, and seems terribly inelegant as well.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Comparing programs

Bugzilla from robdockins@fastmail.fm

On Mar 6, 2006, at 1:05 PM, Harry Chesley wrote:

> This is more of an algorithm question than a language question, but  
> any insights would be much appreciated.
>
> The problem is to input a series of programs and find previous  
> occurrences of the same algorithm.
>
> The programs consist of a set of input parameters (a, b, c, ...),  
> and a set of side-effect-free functions (f, g, h, ...). Since the  
> functions are side-effect-free, they can be reordered without  
> changing the algorithm ("f(a), g(b)" is the same as "g(b), f(a)").  
> Subsequent calls of the same function with the same parameters have  
> no effect ("f(a), f(a)" is the same as "f(a)"); in fact, you can  
> assume duplicates have been removed in earlier processing.
>
> But here's the thing that makes it hard (at least for me): two  
> programs are considered the same if they can be made to match by  
> rearranging the order of the input parameters. I.e., "f(a), g(b)"  
> is the same as "f(b), g(a)". Although parameters can be reordered,  
> they cannot be substituted ("f(a), g(b)" is _not_ the same as "f
> (a), g(a)").
>
> Example: "f(a), g(b), h(a, b)" is the same as "f(b), g(a), h(b, a)"  
> but _not_ the same as "f(a), g(b), h(b, a)".
>
> I need a way to compare the input programs, and preferably to order  
> them.
> In Haskell terms, given the programs are represented by a type  
> Prog, I want Prog to be a member of class Ord, letting me use tools  
> like Data.Map to look up information about previous instances.

One thing you could try is to develop a "canonical representation",  
ie, an exemplar from the equivalence class which can be calculated  
from any member of that class.  You could define a lexicographical  
order for variables and define the canonical representation such that  
the first occurrence of each variable occurs in lexicographical  
order.  Then you define an ordering based on the canonical  
representation.  If your representation of programs is simple enough,  
you can probably just use the derived Ord instance and just make sure  
to always use the canonical representation.

> I can do a brute-force compare by trying all the parameter  
> permutations, but that only gives me Eq, not Ord, and seems  
> terribly inelegant as well.


It's hard to be more specific without more details about the language  
and the problem.  Your comments make it sound like you are dealing  
with an imperative language, but it's hard to tell.  In some cases,  
language analysis is easier if you do a dataflow analysis first and  
then do your manipulations on the resulting graphs; you might try  
taking that tack.


Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Comparing programs

Jacques Carette
In reply to this post by Harry Chesley
I believe you might be able to use (commutative) anti-unification, also
known as "generalization" for this task.
Jacques

Harry Chesley wrote:

> This is more of an algorithm question than a language question, but
> any insights would be much appreciated.
>
> The problem is to input a series of programs and find previous
> occurrences of the same algorithm.
>
> The programs consist of a set of input parameters (a, b, c, ...), and
> a set of side-effect-free functions (f, g, h, ...). Since the
> functions are side-effect-free, they can be reordered without changing
> the algorithm ("f(a), g(b)" is the same as "g(b), f(a)"). Subsequent
> calls of the same function with the same parameters have no effect
> ("f(a), f(a)" is the same as "f(a)"); in fact, you can assume
> duplicates have been removed in earlier processing.
>
> But here's the thing that makes it hard (at least for me): two
> programs are considered the same if they can be made to match by
> rearranging the order of the input parameters. I.e., "f(a), g(b)" is
> the same as "f(b), g(a)". Although parameters can be reordered, they
> cannot be substituted ("f(a), g(b)" is _not_ the same as "f(a), g(a)").
>
> Example: "f(a), g(b), h(a, b)" is the same as "f(b), g(a), h(b, a)"
> but _not_ the same as "f(a), g(b), h(b, a)".
>
> I need a way to compare the input programs, and preferably to order them.
>
> In Haskell terms, given the programs are represented by a type Prog, I
> want Prog to be a member of class Ord, letting me use tools like
> Data.Map to look up information about previous instances.
>
> I can do a brute-force compare by trying all the parameter
> permutations, but that only gives me Eq, not Ord, and seems terribly
> inelegant as well.
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Comparing programs

Brian Hulley
In reply to this post by Harry Chesley
Harry Chesley wrote:
>> But here's the thing that makes it hard (at least for me): two
> programs are considered the same if they can be made to match by
> rearranging the order of the input parameters. I.e., "f(a), g(b)" is
> the same as "f(b), g(a)". Although parameters can be reordered, they
> cannot be substituted ("f(a), g(b)" is _not_ the same as "f(a),
> g(a)").

Are you sure you've got this right? I'd have thought that "rearranging the
order of input parameters" just means that if you have h(a,b) == h'(b,a) for
some h and h' then you are allowed to substitute h' for h as long as you
also swap the params around.

f(b),g(a) can only be obtained from f(a),g(b) by substituting the params for
f and g respectively, which is not the same as rearranging the order of f
and g's params, and which as you've said, is not allowed.

Also, what is the meaning of "f(a), g(b)"? If f and g are just side
effect-free functions, is this not equivalent to just g(b)?

I'd suggest the first step is to define a formal semantics for the meaning
of the programs to help illuminate what is/isn't equivalent, then think
about rewrite rules/ search strategies/heuristics etc, and only at the very
end try to work out how to code it in Haskell. (Of course the problem of
comparing two functions in a TM-complete language is undecidable so unless
your functional language is very restricted no such algorithm will work for
every input)

Regards, Brian.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe