[Haskell-cafe] Comparing programs
carette at mcmaster.ca
Mon Mar 6 13:45:08 EST 2006
I believe you might be able to use (commutative) anti-unification, also
known as "generalization" for this task.
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
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe