6 ms·
An intriguing discovery of Computer Science: The Y combinator [video]
- lgm__ 4y agoIt requires some thinking, but the video gives a complete explanation, and is accessible to anybody with a strong programming background.
- edgecasestdio 4y agoHere are a few additional written articles on what a Y-combinator is. -Stack Overflow, "What is a Y-combinator?": https://stackoverflow.com/questions/93526/what-is-a-y-combinator/94056#94056 https://stackoverflow.com/questions/93526/what-is-a-y-combin... -Wikipedia, "Fixed-point combinator," at the Y combinator sub-section: https://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator https://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combi... -For a more academic source, an article from a Johns Hopkins computer science professor is at: https://www.cs.jhu.edu/~jason/465/readings/lambdacalc.html https://www.cs.jhu.edu/~jason/465/readings/lambdacalc.html
- cercatrova 4y agoHence the name Y Combinator, a startup that generates other startups.
- systemvoltage 4y agoI'll be honest, I didn't know what Y-Combinator is. It was one of those things I just took as granted. Mind blown.
- quickthrower2 4y agoAnd never stops. (Which would be the Z-Combinator!)
- EddySchauHai 4y agoWhich is apparently a thing! https://www.zcombinator.org/ https://www.zcombinator.org/
- a1371 4y agoI admit I hadn't thought this is YC's name origin. I didn't research it, just thought maybe "Y" is actually supposed to be "why" and "combinator" had to do something with _combining synergies_ or something. You know, something cryptic that sv people think is cool. This, on the other hand, is pretty clever with the recursion reference. Sometimes I forget that YC was a wild idea at its time too, aiming to realize other wild ideas. Thanks for sharing.
- vishnugupta 4y agoIn case you didn't know, PG is a big proponent of Lisp and I believe he had a big role in naming YC as YC. His well known (I guess not for the current generation) work is in creating the very first (kinda) ML automated based spam filter. I believe he implemented it in Lisp. It's a beautiful piece of work. http://www.paulgraham.com/spam.html http://www.paulgraham.com/spam.html
- Bayart 4y agoHN is also built with Arc, Paul Graham's Lisp dialect.
- quickthrower2 4y agoThat is quite the first video of a channel!
- ncmncm 4y agoA Y-combinator was proposed to be added to the ISO C++ Standard Library. It was not adopted, as everyone agreed it would not be useful. If anyone ever did find a use, they could copy its proposed implementation into their own code. But everybody knows that will not happen.
- texaslonghorn5 4y agoFor a fun introduction to this field, check out Raymond Smullyan's To Mock a Mockingbird. If you have kids, this and his other books are a great way to let them get interested in puzzle solving and math without realizing that they're doing math (he cites such an anecdote in another book).
- lgm__ 4y agoThank you, I never heard about Smullyan, I'll check that out.
- sn41 4y agoGreat suggestion, thanks!!! I'm about to teach simply-typed lambda calculus and fixed-point combinators in my class. This book is a great suggestion (as are all books by Smullyan). Shame that the pace of courses today and bite-size youtubization has killed the joy of sitting around with a single puzzle in a cozy nook or a bus.
- Breza 4y agoLately I've really gotten into reading Dover math books. They're written with such a love of the underlying topic without much concern for practical applications (most predate modern computers). For example, I read a book about graph theory before delving into the Neo4j documentation, and the code makes so much more sense.
- dullcrisp 4y agoThat’s easy though: Mockingbird mockMockingbird = Mockito.mock(Mockingbird.class); MockingbirdMocker mockingbirdMocker = new MockingbirdMocker(); mockingbirdMocker.mock(mockMockingbird); verify(mockMockingbird).mock();
- tantalor 4y agowhen(mockingBird).dontSing(thenReturn(diamondRing));
- math-dev 4y agoThis piqued my interest so I had a read of the below which explained things very well, although I’m only about 70% fully comprehending it: https://lucasfcosta.com/2018/05/20/Y-The-Most-Beautiful-Idea-in-Computer-Science.html https://lucasfcosta.com/2018/05/20/Y-The-Most-Beautiful-Idea...
- NoMoFascyDos 4y ago[flagged]
- innagadadavida 4y agoI never understood this obsession with lambda calculus or ycombinator. If most of the computers have an instruction set that is rich and has support for loops and types and other things, what use is it to waste your time to understand this? It’s like reading poetry perhaps? There is no goal but just to come up with puzzles so you can show a cool solution? Why? Why?
- chii 4y agoit's part of theoretical computer science. You asking this is the same as someone in the 15th century asking why bother with square root of negative 1, and what it could possibly be used for. lambda calculus can be considered fundamental to how computations can be represented via simple building blocks - it's in the same category as a turing machine. if a problem could be represented as a lambda calculus expression, you know that it is theoretically solvable - or if you proved that it isn't, then you know the problem is unsolvable (like the halting problem).
- tlb 4y agoThose computers with rich instruction sets are built up of smaller units made of smaller units, down to individual transistors (typically 2 kinds). It's pretty cool that you can build something so complex from a couple types of components and wires. Lambda calculus is the analogous building block for algorithms. With just a few primitives (including the Y combinator) you can have a powerful system upon which you can build any (no-quantum) algorithm at all. I find it deeply pleasing that all our fancy systems can be broken down to such simple components, and I'm glad to belong to the profession of people who are good at this task.
- lou1306 4y agoBut the cool part is that the YC is not actually a primitive. Primitives in lambda calculus are essentially just variables, function definition, and application. At a first glance, you wouldn't tell that you could express infinite computation from such rudimentary tools, but the YC shows that you actually can.
- vishnugupta 4y ago
- albert_e 4y agoin all the recursion explanation..there is a minor edit I noticed at timestamp 10:16 the presenter originally said "g" but then edited the video later to overlay the audio of him saying "f" a second later :)
- lgm__ 4y agoI am amazed you noticed this. It is correct. I noticed my mistake, didn't want to spend an hour putting back my camera and light at the same location, and proceeded to clumsily edit the audio :)
- bluepnume 4y agoThis was my attempt to understand and implement the Y combinator a while back: https://gist.github.com/bluepnume/6973b6efb7d48edcbf19 https://gist.github.com/bluepnume/6973b6efb7d48edcbf19
- tromp 4y agoThe author skips the (standard) construction of numbers in lambda calculus, the so-called Church numerals C0,C1,C2,... which iterate a given function a certain number of times on a given argument. So C0 f x => x C1 f x => f x C2 f x => f (f x) Curiously, for these numbers, you can define the factorial function without any use of recursion, instead using their built-in iterative behaviour. Written in the standard notation for lambda calculus, it is factorial = λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x)
- daniel-cussen 4y agoWhat I don't get is when it decrements and checks if we're at the base case?
- tromp 4y agoThe definition of factorial (fac for short) can be broken down as succ = \n\f\x. n f (f x) -- the successor function for Church numerals F = \c\n. n (c (succ n)) fac = \n\f. n F (\x.f) id As you can see there is no use of a decrement function. Instead, numbers 1..n are recreated by the iterated successor function. We can follow the reduction of fac 3 as 0 = \f\x. x 1 = \f\x. f x 2 = \f\x. f(f x) 3 = \f\x. f(f(f x)) fac 3 = \f. F (F (F (\x.f))) 1 = \f. 1 (F (F (\x.f)) 2) = \f. 1 (2 (F (\x.f) 3)) = \f. 1 (2 (3 ((\x.f) 4))) = \f. 1 (2 (3 f))
- teddyh 4y agoAn explanation by Gerald Sussman himself: https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s
- sva_ 4y agoA good video that made it click for me is the following, which derives the ycombinator from 1st principles: https://m.youtube.com/watch?v=FITJMJjASUs https://m.youtube.com/watch?v=FITJMJjASUs
- maxiepoo 4y agoI have to plug my favorite "explanation" of the Y combinator, which is called "Lawvere's fixed point theorem". In a cartesian closed category, if there is a function p : A -> (A -> B) that has a left-inverse, i.e., e : (A -> B) -> A with p o e = id_(A -> B) then B has a fixed point combinator Y : (B -> B) -> B, i.e., every function from B to itself has a fixed point: Y(f) = f(Y(f)). The proof is like the Y combinator in untyped lambda calculus, but with extra ps and es. This is because one way to understand untyped lambda calculus is that you are working with a single type D that satisfies D = (D -> D) (so p,e are identities). I like this because it makes the connection between the Y combinator and diagonalization arguments like Cantor's theorem explicit. For instance, Cantor's theorem says that the powerset of a set always has higher cardinality. We can reformulate this as saying that there is no onto function p : X -> (X -> 2) because a subset of X is the same as a function from X to booleans (2 = {true, false}). An onto function has a left inverse (using axiom of choice) and so if we have an onto function X -> (X -> 2) then every function (2 -> 2) has a fixed point, but this isn't true! If we took Y(not) we would construct a boolean b : 2 such that b = not(b), which is impossible so we have a contradiction. I found this helpful in understanding why the "not" appears in just the right place in the classical proof.
- 3PS 4y ago> if there is a function p : A -> (A -> B) that has a left-inverse, i.e., e : (A -> B) -> A with p o e = id_(A -> B) then B has a fixed point combinator I think you meant to write "right inverse" here. Agreed that Lawvere's theorem is very cool. It helps that Cartesian closed categories are basically just categories where you can do typed lambda calculus, so the underlying link is already very close.