The most intriguing discovery of Computer Science: the Y combinator demystified.

A compact explanation of what's considered one of the most profound constructs of Computer Science - the Y combinator.
This @Computerphile video is an excellent introduction: • Essentials: Functional...
Cut scene attributions:
Video: www.pexels.com... (Nicky Pe) and Jess Loiterton from Pexels
Music: www.bensound.c... and pixabay.com/us...

[@szymonbaranowski8184]

Early in functional thinking so it seem confusing. Less if presented less abstract adding: True(a,b) == a False(a,b) == b and F instead of b: NOT(f) = f(False, True) and NOT(False) -> False(False, True) -> True That b in example confuses as its used as argument not function first then true/false function becomes argument & b a function 🤯 Putting "true", "false" instead of a and b in first declaration of true and false would make it less complex to grasp, more to the hard Earth ground. Practical instance really helps sequential minds get the abstract ideas ;-)

[@isleepinadatacenter3951]

This is correct! Indeed choosing the name "b" for the parameter of NOT was not the greatest idea (I chose "b" for "boolean"). If you're interested in this kind of things, the classical next step is to look at how integers are typically defined (search for "Church numerals"), it is very satisfying.

[@berlincount]

I did NOT expect the goat.

[@isleepinadatacenter3951]

Some say it's the best part. :)

[@JPalermo]

Greatest of all time

[@AByteofCode]

Welcome to KZbin! Although I'm a bit salty this video removes the need for both videos I'm currently working on, you did a great job, especially for your first upload! Good luck with your journey, if you work a bit on titles, thumbnails and production quality, I can see you going far!

[@isleepinadatacenter3951]

Thank you, it's very kind of you! It's my first and last video, I have nothing more to say :) It's such an interesting construct, I'm actually surprised this isn't covered by more people. Don't you think a video explaining just the Y combinator proper (i.e. without explaining lambda calculus or the Z combinator) would fit very well your short format? The world needs to know about this! :)

[@AByteofCode]

@@isleepinadatacenter3951 Aw, sad to see you go, but fair enough! My plan was one video just about lambda calculus, then one video just about the y combinator (with a quick refresher of syntax for newcomers of course). Agreed, the world needs content about this which does a slightly better job than computerphile's "and i leave figuring out how it works as an exercise to the viewer" lol

[@zenlanfleek6580]

@@isleepinadatacenter3951 Why your last video?!

[@isleepinadatacenter3951]

@@zenlanfleek6580 I made this video because I was interested in the Y combinator and couldn't find a video clearly explaining it, so I thought this content was missing. So far I haven't found any other subject I'm interested in that's not nicely covered elsewhere. Also making this takes time, I now have a great respect for youtubers :)

[@Bobbias]

@@isleepinadatacenter3951 well here's to hoping you find something else you feel isn't adequately explained elsewhere :)

[@PunmasterSTP]

These concepts still blew my mind, though you expertly explained them, and I really appreciated the transitions as much-needed mini-breaks!

[@floral5371]

very good video. the Javascript visualization helped a lot too! Cheers!!!

[@JustinZymbaluk]

Thanks for the goat, very cute

[@isleepinadatacenter3951]

An adorable Y combinator AND a goat in the same video? Cuteness overload! Thanks to Nicky Pe: www.pexels.com/video/a-meerkat-standing-8268897/

[@Danaugrs]

Awesome explanation, thanks!

[@sandipdas7206]

Extremely helpful and understandable video The name of your channel though...

[@BleachWizz]

7:40 - this is one of those things that feels so stupid that it's brilliant. of course, it's the fact you did a good job explaining a context for it that if feels stupidly brilliant. nice video.

[@isleepinadatacenter3951]

Yes nowadays it looks like a fun academic exercise, but when it was discovered it gave a profound insight into what constitute what we'd call today a Turing-complete language (i.e. one that can represent any computable function).

[@camefromsirius6985]

This is intriguing.

[@isleepinadatacenter3951]

I agree, it is mind boggling. Before seeing (g => g(g))(g => g(g)) I really though this was not possible.

[@exquisite7416]

Great explanation!

[@AgnaktoreX]

Help! How can factorial_gen know n although n is no input parameter? Edit, ah i overlooked the "n =>" part. alright for me now 8)

[@isleepinadatacenter3951]

Yup, you got it: there's no magic there, the value of factorial_gen(fac) is just the good old factorial function that takes a parameter 'n'.

[@fanir33]

Best explanation on yt!

[@isleepinadatacenter3951]

Thank you! I was surprised to see that I couldn't find a complete, to the point explanation of such a famous construct.

[@idiomaxiom]

Instead of realising Y were evaluate it to Z :/

[@aaronbcj]

Me getting there i think🙂 you made g(g) as f(g(g)) What do this arbitary "f" function have? can we think of it as a placeholder function containing exit condition for recursive calls ? or the exit condition is contained within g itself as you shown in factorial_gen

[@isleepinadatacenter3951]

Thank you for thinking: that's the only reason why I made this video, i.e. getting a few people to think and discover this wonderful construct. The Y combinator applied to any arbitrary function (call it "f") computes f(f(f(...))). If you use factorial_gen for "f" (i.e. compute Y(factorial_gen)), then you get factorial_gen(factorial_gen(...)) which is the factorial function. To answer your question, "f" (i.e. factorial_gen in this example) contains the exit condition (as you've seen in the definition of factorial_gen). Note that I didn't talk about "g": this function is just used to define Y. Let's see what its value is. Here's the Y combinator (it normally uses a parameter named "g" twice; I've renamed those g1 and g2 for clarity): "Y = (g1 => f(g1(g1))) (g2 => f(g2(g2)))". You can see that it contains 2 main expressions: the left one is a function with a parameter named g1, the right one is the same function with a parameter named g2. The left function will be called with the right function as its argument, i.e. g1 will have the value "g2 => f(g2(g2))": you can see there's no exit condition there.

[@RafaelMartinez-ih9hd]

EXCELLENT! To my knowledge, Y combinator is usefull for call by name reduction strategies. Since js is call by value, we need to introduce Z combinator, forcing some lazyness in a strict language Am I right? (I never thought such a pragmatic language like js (for web programming) could enlight me the very fundamentals of computer sicence)

[@isleepinadatacenter3951]

You're right that the Y combinator can be used directly with languages that evaluate function arguments lazily. There are such languages (e.g. Racket), but Javascript is not one of them, hence the need for the Z combinator. (Note that I would not use the adjective "useful" in the same sentence as the Y combinator, be certain that it's as useless as it is beautiful, and it is very beautiful.)

[@RafaelMartinez-ih9hd]

@@isleepinadatacenter3951Totally agree. "useful" is the most hated word in Computer Science. Beauty is what matters.😀

[@yomguioim]

Where can one find the lambda calculus interpreter you are using ?

[@Honken]

Developer tools > Console. It's just JavaScript without const/let/var.

[@isleepinadatacenter3951]

Exactly, it's just a javascript interpreter. As Honken said you can use the one embedded in your browser. In the video I use jsconsole.com/

[@JulianaRodrigues-ze5xd]

can't measure how much I liked this video, but it was a lot

[@isleepinadatacenter3951]

This comment brings me more joy than you'd think!

[@Oi-mj6dv]

Fixed point combinator and combinatory logic combinators are mindblowingly powerful.

[@undefBehav]

How about something along the lines of the following: Y = facgen => (x => x(x))(x => facgen(n => x(x)(n))) Y(x => n => n == 1 ? 1 : n * x(n - 1))(5) // 120 It slightly differs syntactically from what's presented in the video, but produces the same result in practice.

[@isleepinadatacenter3951]

Indeed, well done, this is equivalent (one can write a derivation similar to the one at 10:55 with your version). I suspect that the classic way to write this (i.e. the version in the video) has been chosen because it uses the same expression twice, i.e. there's one less expression to understand.

[@halohaalo2583]

Why a datacenter

[@isleepinadatacenter3951]

Because 1. I work for a very large company that has data centers 2. I don't have imagination 3. I thought it sounded funny :)

[@PunmasterSTP]

Thank you for asking that question; I had the same thought as well.

[@Dragonfree97]

The goat looks like a friend

[@isleepinadatacenter3951]

The goat *is* a friend.