[Haskell-cafe] Comparing programs

[Jacques Carette]

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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe