Recursions without names: Introduction to the Y combinator in JavaScript | Hacker News Reader

Recursions without names: Introduction to the Y combinator in JavaScript

blog.klipse.tech

77 pointsviebel32 comments

If I'm not mistaken, this isn't the full Y combinator yet. It's a partial step towards deriving the full Y combinator.

    (f => (x => x(x))(y => f(x => y(y)(x))))
    (func => n => (n === 0) ? 1 : (n * func(n - 1)))
    (19)

Notice that the ugly func(func)(n-1) recursive call with the proper Y combinator simply became func(n-1).

The full Y combinator is also vastly more mystical and less obvious than the partial step :)

> The full Y combinator is also vastly more mystical and less obvious than the partial step :)

The full Y conbinator simply binds func to func(func) as seen in `(y => f(x => y(y)(x))))`, an easy jump to make and pretty easy to understand.

The full Y combinator is presented in the sequel of the current article: http://blog.klipse.tech/lambda/2016/08/10/pure-y-combinator-...

Obligatory 'To Dissect a Mockingbird' link:

http://dkeenan.com/Lambda/index.htm

If you have never read this before, then I highly recommend it. It's a beautiful way to picture combinators.

Indeed. It's by far best explanation of the concept that I've seen, and it, along with some of Matt Might's posts, helped me gain a deeper appreciation for concepts like Church Encoding, and λ-calculus in general.

I find the Python implementation is slightly more elegant:

    (lambda f: f(f))
    (lambda fn: lambda n: 1 if n == 0 else (n * fn(fn)(n - 1)))
    (5)

Yeah. But I didn't find a way to run python code in the browser. Currently in Klipse, we support javascript, ruby, clojure and php...

I did not know there was a Ruby to JS compiler. That's __really__ fascinating! Do you have plans to support Python any time soon?

I'd love to support python.

If you find a way to evaluate python code in the browser, please let me know: viebel@gmail.com

Perhaps `skulpt`?

> Skulpt is a Javascript implementation of Python 2.x. Python that runs in your browser!

[0] https://github.com/skulpt/skulpt

Thanks a lot. Will try to integrate skulpt on klipse.

Jim Weirich had a good couple talks about building a Y combinator in a couple languages.

Here's his JavaScirpt version: https://vimeo.com/45140590

RIP

A question about the klipse plugin: Does code inside it have access to DOM elements just as javascript running on the console would? Would be a fantastic addition that could really make developing an interactive coding exercise for kids learning about the web a breeze!

Indeed, the klipse plugin has access to DOM elements.

What ideas do you have for kids?

I have tried to do something for kids here: kids.klipse.tech

The klipse plugin concept is explained in details:

1. http://blog.klipse.tech/javascript/2016/06/20/blog-javascrip...

2. https://github.com/viebel/klipse

The code samples fail in Safari. The first one prints "SyntaxError: Unexpected token '>'".

You need Safari Technology Preview for ES6 support.

Your version of Safari most likely lacks support for ES6 features like arrow functions[0], you could use babel[1] to transpile the code to ES5:

  (function (f) {
    return f(f);
  })(function (func) {
    return function (n) {
      return n === 0 ? 1 : n * func(func)(n - 1);
    };
  })(19);

[0] http://caniuse.com/#feat=arrow-functions

[1] https://babeljs.io/repl/

To be fair, the article would be more aptly titled "Recursion without function names". In any recursion you need a way to reference the original function somehow. They're using a function parameter to accomplish that via indirection.

There are no names except function arguments.

No 'x=...'

Please reread my post. The function parameter is the name.

Do you know a language without argument names?

You're missing the point. Nevermind.

Kitten -> meet laser pointer

Nerd -> meet article

For what purpose?

Quoth xkcd, "Tail recusion is its own reward."

In all seriousness, even if the y combinator is practically useless in languages that don't have proper TCO (which is specced for ES7), it's a useful learning tool, is powerfully mind expanding, and can help to demonstrate the power of the λ-calculus.

There is a practical application for recursive memoization:

http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-j...

http://xkcd.com/1270/

Is the Y-combinator any more or less dependent on TCO than regular recursion?

The Y combinator is useless in languages that already have builtin support for recursive functions.

Not useless, almost useless:

You can do elegant recursive memoization with the Y combinator as explained here http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-j...

No, Y is handy for defining nameless recursive functions, but it blows the stack even faster if you don't have TCO.

Implementing a linguistic trait when not built in. Next: continuations. Next: prolog.

https://github.com/IvanIvanov/JavaScript-Logic-Programming-S...

Reply on news.ycombinator.com