Why Y? Deriving the Y Combinator in JavaScript
raganwald.com
raganwald.com
A Y-combinator is a "functional" (a function that
operates on other functions) that enables recursion,
when you can't refer to the function from within
itself. In computer-science theory, it generalizes
recursion, abstracting its implementation, and
thereby separating it from the actual work of the
function in question. The benefit of not needing a
compile-time name for the recursive function is
sort of a bonus. =)
(though I get that it can be a useful intermediate construct inside a compiler)
I'm unaware of compilers using the Y combinator. Perhaps you were thinking of continuation passing style
[1] http://www.viksit.com/tags/clojure/practical-applications-y-...
fix f = let x = f x in x
So it allows you to abstract away the memoization, write it once and then use it on any recursive function. That way you can write quite natural recursive functions and just memoize them in one wrapper call.
https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-... looks similar to what I ended up with
I used this in competitive programming for a while, it was nice for certain types of dynamic programming problems where the interesting part is the recursive definition, so once I found that there wasn't any more to write. Quite satisfying when it applied.
The CS term is "higher-order function": https://en.wikipedia.org/wiki/Higher-order_function
That said, as always raganwald's stuff is a pleasant and informative read.
But you could imagine this being part of, say, a "big integer" library. (Which C, C++, PHP, JS all lack.)
The fact that you then define this in terms of amazingly simple functions like the S and K combinators just, in my opinion, adds to how wonderful it is.
I used the mockingbird version for a very specific purpose in production a while back, although that was more like corecursion than recursion.
What my encounter with the fundamentals of Computer Science did give me (apart from the necessity of implementing things like garbage collectors) - was an abiding interest and love of the mathematical foundations of computation and with maths as something interesting rather than something to be endured.
That interest did lead to me doing postgrad research in a control engineering group, which did lead to me co-founding a startup.
So did I ever apply S & K in a practical circumstance - no. Am I glad I took a turn down the more mathematical side of CS - absolutely.
The Y combinator isn't there and can't be defined trivially since Haskell only allows non-recursive data types. However, there's a nice solution using non-monotonic data types[1]:
newtype Mu a = Mu (Mu a -> a)
y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
It's clear, minimalist, insightful, and even has an in-page live code demo. Bonus points for including fixed-points as a key concept, and memoization as an extremely useful technique.
That being said, I'm a big fan of decorators, so I expressed the memoization using a decorator, rather than baking it into Ymem.
On the other hand, trampolining is the perfect application for a special-purpose Y combinator, and thus the decoupled Trampoline.
I very much doubt anybody needs to have SICP at their fingertips, but it seems like many techniques that we deride as being "too far out there" turn out to be quite manageable by all sorts of programmers, it's just a matter of there being enough resources to learn and a little motivation.
This article definitely does not prescribe hurling combinators at every problem, but I will go on record and say that if there's somebody on your team you think cannot understand this code, perhaps you should be a little more optimistic and give them a chance.
Anybody who can figure WebPack, Gulp, Babel, closures, promises, async/await, generators, &c. out can figure this out.
My point is that today, when developers encounter this code while debugging something that needs to be done yesterday, will not spend the time educating themselves and will just ignore it or (even worse) assume they understand it, which is even worse. I don't think that I'm better than them - I just acknowledge my own stupidity. And in my stupidity, in the heat of working on a real project I want to encounter familiar technologies and abstractions that by themselves are almost boring, rather than research new things.
At least when it's out of scope of our technology focus, the core of the project that actually helps it be unique and earn a profit.
Edit: unless you are specifically talking about the use case of this article.
I tested the theory myself. I went to Boston recently and followed my GPS. It took me over the Tobin bridge through solid bumper-to-bumper gridlock. When I arrived at the gridlock my GPS said 30 minutes left. 45 minutes later I had travelled about .5 miles and it still said 25 minutes left. Google was completely wrong, but I swear it had me right where it wanted me the entire time.
After getting fed up with traffic, I eventually turned my GPS off and got into the right lane to head towards Cambridge. My logic was that GPS could navigate from anywhere, to anywhere. I would simply go somewhere with less traffic and try the GPS again.
Sure enough I made it to Edward Land blvd and turned my GPS back on. I had a clear 15 minute drive with average traffic for the rest of my trip.
Google saw the traffic I was dealing with, and queued me right in behind it all. It could have recalculated around it, but it legitimately "thought" I only had 30 minutes to go. I guarantee it told all 500 other cars in front of me the same thing.
So we were all following our GPS's, and our GPS's were taking all of us the fastest route. It created a traffic jam and then optimistically pretended there was no traffic jam.
If street lights were truly "smart", with cameras and machine learning to maximize throughput, and GPS's programmed to load balance their own congestion, this problem wouldn't be a problem anymore.
Which means that in around 14 days I’ll suddenly need to revisit this article and learn all about it because it’s suddenly useful.
Life is strange like that. I do like the term “why bird” though.
I like the mockingbird better since it's less magical. Passing "self" as the first argument seems idiomatic from an object-oriented point of view; this is sort like how Python has an explicit "self" parameter. We can take the next step and pass "self" explicitly as well.
The ability to change how a self-call is handled seems quite like overriding a method.
Joking aside, I thought this was a very approachable article. Thank you for sharing.
For someone who never had contact with functional programming, the concept of the Y combinator can seem a bit... strange. But trying to figure out what it is and does can be a real eye opener.
Edit: ah, you fixed the typo ;)
Not everything is meant to be deployed to production.
...hm.
abstract class FooImpl<Self extends FooImpl<Self>> { Self doIt() { .... } }
As a class with a self type, analogous to an open recursive function, and then:
class FooFinal extends FooImpl<FooFinal> {...}
As it’s call.
I followed it entirely with one exception: I can see that `maker(maker)` has the right type, but why is it the right value? How do we know, as we fill in the blanks, that this is the implementation that yields the right result?
I wondered this myself. I mean, I can test it and see that it appears to give the correct result, but how do I prove that it gives the correct result?
I didn't include it, but you can do reductions, successively replacing the names with their expansions, and you see that it works out was we want.
And in Combinatory Logic, there really is nothing else. If an expression has the correct "type," then it works. There's nothing except rearranging terms, duplicating terms, and erasing terms.
But that being said, I don't know if that's a "proof," and I especially don't claim that a proof about Combinatory Logic would say anything at all about JavaScript.
You know, if you want to use Haskell, use Haskell. Trying to shoehorn this stuff into languages designed for loops instead of recursion just means impressionable JS developers are going to see this and rush out to implement it in some project to prove how smart they are. Then everyone suffers. The implementation is slower because it goes to heap. The memory usage explodes because it goes to heap.
Purely for illustration of a Y combinator, this is great. But there should be a big red warning somewhere on the page as a reminder of the downsides of this approach.
That is the goal of the Y Combinator in the Lambda Calculus and Combinatory Logic, but here the initial goal was to decouple an anonymous function from itself so that we could decorate it.
Like I said, I have no problem with this article as an illustration of a ycombinator for JS devs. The problem is it does not warn them sufficiently of the very major drawbacks in using it. This is why we have Gate's law; Developers using inefficient constructs because they're neato.
Instead, I outsource that to people like you. You voice your concerns here, and people can read them and make up their own minds.
Speaking of making up their own minds, please explain in more detail how the trampoline’s memory consumption grows unboundedly, to the point where it could cause an out-of-memory error. That would be most interesting for the community to ponder.
https://jsfiddle.net/q59Ljeu7/
A loop is not just fewer LoC and easier, it is orders of magnitude faster than the ycombinator decoupled trampoline. The first alert is nearly instant. The second one takes almost a minute. My chrome dev tools are hard locked waiting for the ycombinator to finish.
This is not something I would encourage JS devs to use in practice.
I wrote an entire article about refactoring tail-recursion to iteration and linked to it in TFA. I've also written a Scheme interpreter that can perform this optimization for certain functions on-the-fly. But arguing that the code is slow is missing the point by a country mile, and then some. The article is not arguing that the code is fast, or that you should always do this. I find it amazing that every time a programming technique is discussed, people want to worry about whether it belongs in production.
Is there no recreational programming any more? Or is it all about shipping the next app to deliver food by electric scooter? My world would be depressingly boring if the only things I thought about were the things I use at PagerDuty every day.
Now as to what I asked you about:
What you said was that this implementation leaks memory in such a way that using the trampoline it trades a stack overflow for an out-of-memory error.
I wish to understand that problem. Specifically, how does the decoupled trampoline leak memory?