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!
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.
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.
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.
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.
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.
> 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.
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.
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).
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!