[Haskell-cafe] Comparing programs

[Brian Hulley]

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.