4 ms·
Deriving the Y Combinator in JavaScript
- anothergoogler 8y agoAlso http://www.crockford.com/javascript/little.html http://www.crockford.com/javascript/little.html (scroll down)
- dang 8y agoThis is an article, not a Show HN. Please read the rules: https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html.
- deleted 8y ago[deleted]
- 18nleung 8y agoHi! 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!
- jacobwilliamroy 8y agoIs 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.
- rs86 8y agoSpace complexity will depend on the computational model you choose.
- nv-vn 8y agoHey 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.
- rs86 8y agoNice 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.
- dustingetz 8y agoBest explanation i've encountered thanks
- aappleby 8y agoSome uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-99427d483186 https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...
- anothergoogler 8y agoWhat similarities are you talking about? I'm not seeing it.
- Retra 8y agoOf 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.
- lsiebert 8y agoI 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.
- pitched 8y agoFunctions 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.
- rustler 8y ago> 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.
- rs86 8y agoRecursion 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.
- dnsco 8y agoJim 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 https://www.youtube.com/watch?v=FITJMJjASUs
- mchahn 8y agoMaybe a stupid question ... Isn't passing a function to itself kind of like recursion?
- rs86 8y agono, 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.
- azatom 8y agoI 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).
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]