Deriving the Y Combinator in JavaScript | Hacker News Reader

Deriving the Y Combinator in JavaScript

enlight.nyc

49 pointsshamdasani19 comments

Hi! Author here, and glad to see my writeup on HN.

I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript.

I hope this exploration is helpful, and feel free to leave any questions or comments you may have below!

Is it impossible to write a y-combinator with space complexity O(1)? I'm in the very early stages of a comp/sci education and have not yet learned how to prove that something is impossible.

Space complexity will depend on the computational model you choose.

Hey dude! Not sure if you remember me but I talked to you a while ago on a2c. Anyways, this is a cool article and I thought you did a good job of explaining some of the technical details. Btw, since you have a JS background I thought I'd recommend ReasonML to you. I just started using it, but I think it's a really nice mix of functional programming with JS type stuff, plus it's designed by the guy who made React.

Nice article but you can't write the Y-combinator in Haskell (or in simply typed lambda calculus). You can write it in the untyped lambda calculus.

"y = \f -> (\x -> f (x x)) (\x -> f (x x))" will fail to type check in haskell.

Also it would be cool to show that what the Y-combinator does is find a fixed point for a function. When you define fact as "function fact(f, n) {...}" you are actually defining it as "function fact(f) { n => ... }" and the Y-combinator finds a fixed point for fact. A fixed point is x such that f(x) = x. so fact(fact) = fact.

In lambda calculus _every_ function has a fixed point; In a simply typed lambda calculus it does not. This gives a way to define recursion as fixed points and not as circular references.

Best explanation i've encountered thanks

Some uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...

What similarities are you talking about? I'm not seeing it.

Jim Weirich's 2012 Ruby Conf talk is also a great introduction to the Y Combinator and Lambda Calculus.

https://www.youtube.com/watch?v=FITJMJjASUs

This is an article, not a Show HN. Please read the rules: https://news.ycombinator.com/showhn.html.

Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.

I mean, recursion is just a way of saving state on the program's call stack implicitly instead of explicitly in a stack data structure.

fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without shenanigans.

Functions are syntactic sugar on calls and calls are syntactic sugar on jumps so those dynamic shenanigans would be messing with calling conventions? That might not be too ridiculous.

> fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

That's one possible implementation of recursion on commodity hardware. Recursion itself is a mathematical method for defining a function which may not even be computable, or may be computable using other primitives.

Recursion is not defined in terms of the execution of the program (such as storing data on the call stack). For example you can have stack less languages with recursion.

Maybe a stupid question ...

Isn't passing a function to itself kind of like recursion?

no, it's more like passing a continuation in this case (which is the function itself). but the function is not defined in terms of itself.

I don't get it. I do not want to define recursion, but for me as a programmer stackoverflow is a recursion, what is happening if I call y(factorialFactory)(10000).

Also http://www.crockford.com/javascript/little.html (scroll down)

Reply on news.ycombinator.com