[Haskell-cafe] Comparing programs
Brian Hulley
brianh at metamilk.com
Mon Mar 6 13:46:30 EST 2006
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.
More information about the Haskell-Cafe
mailing list