Crockford's Great JS lectures of this week and last

[lorlarz]

If you missed them, this will get you to one:

http://developer.yahoo.com/yui/theater/video.php?v=crockonjs-3


(the other 2 recent lectures are also more than worthwhile)


In addition to the one piece of mysterious code I asked about earlier
today
(and which I really, really really still need more explanation of),,
Crockford also showed (,but did not explain) the following:


The Y Combinator


function y(le) {
return (function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
}));



}


varfactorial = y(function (fac) {
return function (n) {
return n <= 2 ? n : n * fac(n -1);
};


});


varnumber120 = factorial(5);

While I would love to hear the full explanation I could understand of
this,
it is more important to me to here a more full explanation of
memoization --
which I asked about in an earlier thread today.


BUT, Crockford says if you can expalin The Y Combinator, then
you are truly someone who can declare himself a computer scientist.

 

[Scott Sauyet]

BUT, Crockford says if you can expalin The Y Combinator, then
you are truly someone who can declare himself a computer scientist.

There are a number of good resources on the web about fixed-point
combinators, including the Y-combinator. But if you're still finding
memoization hard to grasp, I'd suggest that you spend some more time
with first-class functions getting to this topic. Crockford is right,
and even more, there are many working computer scientists who might
mostly understand it but still can't clearly explain it.

-- Scott

 

[lorlarz]

Nobody actually uses the Y combinator. Its main purpose is to baffle
other people; other than that, it has next to no practical use.

Sure, it's a very clever piece of code, and if you like mindbenders and
riddles, you can sit down and think it through until you understand it
(been there, done that, felt great, and promptly forgot what it did ;-),
and then _please_ don't ever use it in production code. You don't want
to stumble across that thing a year later and be baffled all over again.

If you really feel you need to understand it, there are numerous
explanations on the web. This one looks useful (didn't read all of it,
though):http://blog.jcoglan.com/2008/01/10/deriving-the-y-combinator/


If the Crockford says so, it must be true.

I understand the web page you referred to qualitatively, by which
I mean: I at least see one reason why the guy bothered to build
a Y Combinator. A reason cited was: to have something you can call
that has no reliance on any global variables. Using such a function
could never be screwed up by any other javascript. When and why
you would have to have such security or protections doing it _that
way_
is not immediately
appreciable. But, in the case you did, that is a solution. But
there are seeming other extremely simple (function enclosure)
solutions
to this "problem" so the Y Combinator is NOT appreciable for that.
What else is it good for? I wonder. There is always left at least
one point at which you can overwrite something important involved
with any routine (if only the whole thing at once).

Nothing else was pointed out by the author of that web page as
to why one would want to set up that routine. If there is no
other reason, the thing seems silly (but I have not savored the
details of the entire serup in the routine, so perhaps I missed
something).

 

[Evertjan.]

lorlarz wrote on 26 feb 2010 in comp.lang.javascript:

function y(le) {
return (function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
}));
}


varfactorial = y(function (fac) {
return function (n) {
return n <= 2 ? n : n * fac(n -1);
};
});

varnumber120 = factorial(5);

Simpler, faster and more debugable:

<script type='text/javascript'>
function factorial(n) {
return (n <= 2) ? n : n * factorial(n - 1);
};

alert(factorial(5));
</script>

 

[Dr J R Stockton]

In comp.lang.javascript message <[email protected]>

Simpler, faster and more debugable:

<script type='text/javascript'>
function factorial(n) {
return (n <= 2) ? n : n * factorial(n - 1);
};

alert(factorial(5));
</script>

There, factorial(0) -> 0 . Normal usage requires it to be 1; so
good debuggability may help.

The iterative method should (but may not) be faster; but there can be no
need to do more than 170 multiplications, so that will be unimportant.
Those who want many factorials should consider initialising an array of
them all, by successive multiplication by the new index.

 

[John G Harris]

There, factorial(0) -> 0 . Normal usage requires it to be 1; so
good debuggability may help.

<snip>

It's rather stronger than "normal usage". The function on the Real
numbers that goes through all the points (n, n!) also goes through
(0, 1). It also goes to +/- infinity at all the negative integral
numbers.

To put it another way, to get (n-1)! from n! you do n!/n, so
0! = 1!/1 = 1. (And -1! = 0!/0 = BANG.)

John

 

[Scott Sauyet]

On Sun, 28 Feb 2010 at 18:26:26, in comp.lang.javascript, Dr J R


It's rather stronger than "normal usage". The function on the Real
numbers that goes through all the points (n, n!) also goes through
(0, 1). It also goes to +/- infinity at all the negative integral
numbers.

Well, it's not "the function", but a relatively simple one that is so
defined.

-- Scott

 

[Evertjan.]

Scott Sauyet wrote on 01 mrt 2010 in comp.lang.javascript:

Well, it's not "the function", but a relatively simple one that is so
defined.

All not to the point. This example was not about a userproof nterface or
even about the definition of factorial with a non-integer, zero or negative
parameter, but about simple, readable programming.

That these will not work seems obvious:

var result = factorial('Hello world!');

var result = factorial(false);

 

[Michael Haufe (\TNO\)]

Nobody actually uses the Y combinator.

Yes, they do.

Its main purpose is to baffle other people; other
than that, it has next to no practical use.

It is of great practical use in the implementation of recursion
in functional language compilers

Sure, it's a very clever piece of code, and if you like mindbenders and
riddles, you can sit down and think it through until you understand it
(been there, done that, felt great, and promptly forgot what it did ;-),
http://matt.might.net/articles/impl...t-y-combinator-in-javascript-for-memoization/

and then _please_ don't ever use it in production code. You don't want
to stumble across that thing a year later and be baffled all over again.

Especially if you don't understand what it does.

 

[Michael Haufe (\TNO\)]

What else is it good for? I wonder.  

In JavaScript, next to nothing since the language supports anonymous
recursion
which is basically what this is all about. If you're implementing a
language
though, you can use a derivative of this function as a means of
implementing
some appreciative tail calls.

Nothing else was pointed out by the author of that web page as
to why one would want to set up that routine.  

Perhaps because the author doesn't know and is just trying to sound
smart.

If there is no
other reason, the thing seems silly (but I have not savored the
details of the entire serup in the routine, so perhaps I missed
something).

There is indeed a reason, but not much utility in this context.

 

[Michael Haufe (\TNO\)]

It is of great practical use in the implementation of recursion
in functional language compilers

Maybe Peter Michaux could weigh in on that; he recently decribed the
creation of a Scheme interpreter on his blog. I haven't been following
every step, so I don't know if recursion is covered. Interestingly, Matt
Might (from the link below) was the first to comment on Peter's Scheme
From Scratch introduction page.

In strict functional programming and lambda calculus, functions don't
have state nor do they have free variables and can only refer to their
provided arguments. This being the case, the Y-Combinator can be
applied (since its a stateless function) to another stateless function
which returns a recursive form of that argument.

I should probably have been more precise in what I meant to say:
"[almost] nobody [sane] uses the Y-combinator [in JavaScript]."

I agree that its mostly pointless to use in this language.

I could be wrong. It's possible that serious real-life applications of
this construct exist (in JavaScript), but I've never seen them.

I know that it appears in the Mozilla code repository and has been
there for some time, but I can't divine to what purpose its being
used.

http://matt.might.net/articles/implementation-of-recursive-fixed-poin...

Correct me if I'm wrong, but from what I can see, the performance gains
of this article's example code are the result of memoization; they are
not directly related to the Y combinator. Of course, those examples are
factorials and the inevitable Fibonacci sequence. Both of these can be
written (with or without caching of intermediate results) in a far more
readable manner than using the Y combinator.

I meant that link more as a supplemental explanation of topic in
general.

Or if you think that you may not remember it, a year after you've
written something like this:

  function y(le) {
        return (function (f) {
                return f(f);
        }(function (f) {
                return le(function (x) {
                        return f(f)(x);
                });
        }));
  }

  varfactorial = y(function (fac) {
        return function (n) {
           return n <= 2 ? n : n * fac(n -1);
        };

  });

This seems like a very roundabout way of getting numbers from a simple
sequence. Now compare it to this equivalent function:

  function factorial (n) {
      var result = 1;
      while (n > 0) {
          result *= n;
          n--;
      }
      return result;
  }

(both examples without memoization)

There is an analogous straightforward function for Fibonacci numbers.

In pure languages though based on mathematical foundations, such
constructs may not exist. This is why combinators have value as they
can provide a more abstract foundation to build upon. "Y" for example,
is an abstraction over a significant set of other, simpler
combinators.

All of this is meaningless in the context of JavaScript though as it
is an impure language AISB, though it lends itself as some semblance
of an explanation to the OP.

 

[Lasse Reichstein Nielsen]

In strict functional programming and lambda calculus, functions don't
have state nor do they have free variables and can only refer to their
provided arguments.

That would be overly restrictive. A lambda expression can refer to
variables that are not defined inside the lambda.
However, if a lambda program is evaluated using substitution, those
variables will have been replaced by closed expressions at the time
the lambda is applied.

[Y-combinator]

I agree that its mostly pointless to use in this language.

Indeed, when you already have recursion in the language, you don't
need to build it from primitives.


/L

 

[Michael Haufe (\TNO\)]

That would be overly restrictive. A lambda expression can refer to
variables that are not defined inside the lambda.

Which would make it dependent on its environment and not just its
inputs. This I believe is impure by definition since the results for a
given constant argument can change depending on the context of the
expression.

 

[Michael Haufe (\TNO\)]

Which would make it dependent on its environment and not just its
inputs. This I believe is impure by definition since the results for a
given constant argument can change depending on the context of the
expression.

Clarification: I'm differentiating between closed expressions and free
global values when I refer to free variables (currying vs global
capturing)

 

[Lasse Reichstein Nielsen]

Clarification: I'm differentiating between closed expressions and free
global values when I refer to free variables (currying vs global
capturing)

Ah. Global variables suck. 'nuff said.
/L