Dan Sugalski <[EMAIL PROTECTED]> writes:
> At 09:26 AM 3/27/2001 -0800, Peter Buckingham wrote:
> >Dan Sugalski wrote:
> > >
> > > At 09:50 PM 3/26/2001 -0500, James Mastros wrote:
> >
> >[..]
> >
> > > >I'd think /perl/ should complain if your comparison function isn't
> > > >idempotent (if warnings on, of course). If nothing else, it's probably an
> > > >indicator that you should be using that schwartz thang.
> > >
> > > If you figure out how, tell me. I'd like to make arrangements to be there
> > > for your Nobel acceptance speech. :) (This is, alas, a variant on the
> > > halting problem, unless you're proposing perl do the memoizing *and* still
> > > call the functions, and complain if one doesn't match the other)
> >
> >not wanting to collect my nobel prize just yet, but...
> >
> >could you not try a simple test (not guaranteed to be 100% accurate though),
> >by copying the first data element and apply it twice and then check to see
> >that the result of applying it once is the same as applying it twice.
>
> Feels a little too magic to me, and awfully fragile. I'm not
> comfortable doing that, though arguments to the contrary are
> welcome.
There are 3 separate notions of idempotency at work here; I'm making
up their names.
1. THE MATHEMATICAL NOTION:
f(f(x)) == f(x) for all x
We don't care about that *at all* when we're sorting (we're sorting
the x's in order of their f(x)'s, with not an f(f(x)) in sight!).
I'm not going to talk about this idempotency, I just mention it
because of the incorrect analogy from linear algebra that has been
floating around.
2. "STRONG" IDEMPOTENCY: (PURE FUNCTIONS)
Saying C<$a=f(x); $a=f(x)> leaves the program in the same state as
just C<$a=f(x)>. This is achieved by avoiding assignment, not
using any routines with state (I/O, PRNGs, ...) and the like.
3. "WEAK" IDEMPOTENCY: ("PURE RESULT"?)
After C<$a=f(x); more_stuff(); $b=f(x)> we have C<$a==$b>. But the
state of the program may have been changed.
Examples include any f() that does caching (or I/O for other
purposes), logging, or profiling.
If f() is memoized then it is weakly idempotent but not strongly
idempotent, since calling f(x) for the first time may change the
memoized data.
If f() is strongly idempotent then it is of course weakly
idempotent also.
(3) is enough for the sorting examples, I think. Unfortunately it's
also a lot harder to test syntactically than is (2).
So I'd like to suggest a cop-out, similar to the "let a module do the
work" argument. MJD has a module Memoize, which is very easy to use.
You can only memoize a pure function (in one of the above 2 senses;
you can always memoize (2), and you can do (3) if the semantics of it
are "good enough" for what you want to do).
So you can say
use Memoize;
# ...
memoize 'f';
@sorted = sort { my_compare(f($a),f($b)) } @unsorted
to get a lot of the effect of the S word.
Yes, I know it's not the transform (never better and often worse),
since Memoize was designed with other things in mind. But it's
probably a "good enough" solution, and has very low brain overhead.
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | [EMAIL PROTECTED]
Compugen Ltd. |Tel: +972-2-5713025 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
