Harry Chesley wrote:
But here's the thing that makes it hard (at least for me): twoprograms 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
