On Tue, 1 Mar 2005 16:02:08 -0500, Adam Turoff <[EMAIL PROTECTED]> wrote:
> On Mon, Feb 28, 2005 at 03:39:30PM -0500, Gyepi SAM wrote:
> > It must be: I am using LISP, after a long hiatus, and really liking it. I
> > simply did not appreciate its power upon introduction six years ago.
> 
> Yep.  I never fully understood closures until I used them in Perl.
> After that, Lisp and Scheme were no big deal.  [Except for the
> Y-Combinator, and ((call/cc call/cc) (call/cc call/cc)); those still
> make my brain hurt].

The Y-Combinator made my brain hurt until I figured it out.
Heavy use of continuations still make my brain hurt, and I'm
favourable to the opinion that a continuation is like a goto,
only worse.

Here's an explanation of the Y-Combinator.  It won't work in
Perl because Perl doesn't do lexical binding of input
parameters.  JavaScript does and most should know that, so
I'll do it in JavaScript.

Our goal is to be able to write a recursive function of 1
variable using only functions of 1 variables and no
assignments, defining things by name, etc.  (Why this is our
goal is another question, let's just take this as the
challenge that we're given.)  Seems impossible, huh?  As
an example, let's implement factorial.

Well step 1 is to say that we could do this easily if we
cheated a little.  Using functions of 2 variables and
assignment we can at least avoid having to use
assignment to set up the recursion.

  // Here's the function that we want to recurse.
  X = function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  };

  // This will get X to recurse.
  Y = function (builder, n) {
    return builder(builder, n);
  };

  // Here it is in action.
  Y(
    X,
    5
  );

Now let's see if we can cheat less.  Well firstly we're using
assignment, but we don't need to.  We can just write X and
Y inline.

  // No assignment this time.
  function (builder, n) {
    return builder(builder, n);
  }(
    function (recurse, n) {
      if (0 == n)
        return 1;
      else
        return n * recurse(recurse, n - 1);
    },
    5
  );

But we're using functiions of 2 variables to get a function of 1
variable.  Can we fix that?  Well a smart guy by the name of
Haskell Curry has a neat trick, if you have good higher order
functions then you only need functions of 1 variable.  The
proof is that you can get from functions of 2 (or more in the
general case) variables to 1 variable with a purely
mechanical text transformation like this:

  // Original
  F = function (i, j) {
    ...
  };
  F(i,j);

  // Transformed
  F = function (i) { return function (j) {
    ...
  }};
  F(i)(j);

where ... remains exactly the same.  (This trick is called
"currying" after its inventor.  The language Haskell is also
named for Haskell Curry.  File that under useless trivial.)
Now just apply this transformation everywhere and we get
our final version.

  // The dreaded Y-combinator in action!
  function (builder) { return function (n) {
    return builder(builder)(n);
  }}(
    function (recurse) { return function (n) {
      if (0 == n)
        return 1;
      else
        return n * recurse(recurse)(n - 1);
    }})(
    5
  );

Feel free to try it.  alert() that return, tie it to a button, whatever.
That code calculates factorials, recursively, without using
assignment, declarations, or functions of 2 variables.  (But
trying to trace how it works is likely to make your head spin.
And handing it, without the derivation, just slightly reformatted
will result in code that is sure to baffle and confuse.)

You can replace the 4 lines that recursively define factorial with
any other recursive function that you want.

> /me wonders how different the world would be if EvilLarry didn't let map
> and filter^Wgrep slip into Perl...

I'm rather more thankful for closures.  After all, being list-oriented,
I can define map/grep quite easily.  But closures I need to be in
the language...

Cheers,
Ben
 
_______________________________________________
Boston-pm mailing list
Boston-pm@mail.pm.org
http://mail.pm.org/mailman/listinfo/boston-pm

Reply via email to