Essentials: Functional Programming's Y Combinator - Computerphile 

'Defining factorial using Lambda Calculus has been left as an exercise for the viewer.' Yep, he's a computer scientist.

Computerphile owns all of the world's supply of line-feed dot matrix print paper.

"loop = loop" *That's enough for this sheet of paper, let's grab another one*

Because this video basically said go to wikipedia, I'll try to explain what Y Combinator is. YC is a way to name your function in a language that does not allow such pointers. It proves that function names, classes, etc. are just syntactic sugar. Let's look at the same example: function factorialFn(number){ return number == 1 ? 1: number * factorialFn(number-1) } The only thing that generates a pointer in lambda calculus is a function parameter. So let's rewrite everything to anonymous functions. // This is the mind bending part, a function takes in the factorial function, returns factorial function that takes a number (factorialFn)=> (number) => number == 1 ? 1: number * factorialFn(number-1) Let's call this our Prepared function - we know it would work, but we don't know how to run it yet. So how do we pass the internal function into itself? Looks impossible, right? We could just pass garbage(empty function) to get the internal function and use this to generate the actual function. ((factorialFn)=> (number) => number == 1 ? 1: number * factorialFn(number-1)) (((factorialFn)=> (number) => number == 1 ? 1: number * factorialFn(number-1)) (()=> console.log('garbage'))) Trying number 2 would return a correct answer, but number 3 would call the garbage function. You could just calculate how many times you will need to recurse and nest that many times, so that garbage function would never get called? :P Kinda defeats the purpose. What if we made a function that would nest functions for us? Let's look at the same example as in the video of the simplest recursion: (fn) => fn(fn) If we give this function to itself, it will repeat to no end: ((x) => x(x))((y) => y(y)) same fn, just different variable names for readability. The "y" function becomes a variable "x" after the first application, the x function repeats to infinity. This is the essence of YC. So how do we make this to call our function? Well Lambda calculus allows only way, same as before, as a function parameter: (yourPreparedFn) => (x => x(x))(y => yourPreparedFn(number => y(y)(number))) // The number function exists because I wanted this to be valid JS, and JS is not lazy - it's arguments are immediately evaluated, else the second part could have been just y=> yourPreparedFn(y(y)) If you try to run the function in your head, you will see that the "y" variable is "y" function itself. The first part (x => x(x)) makes that happen as it calls the function and passes the function to itself. And now you are thinking with portals. The second part becomes easier to understand. Because y function has a reference to itself, it has an ability to loop by simply doing y(y). And it can share this ability with your Prepared function. When your Prepared function calls factorialFn with the next number, it's not actually calling factorialFn - it calls y function that generates the next factorialFn and then calls it with the number you passed. This is it, that's Y combinator: Y = f => (x => x(x))(x => f(y => x(x)(y))) You can run this JS to and try to debug or break it for better understanding: ((yourPreparedFn) => (x => x(x))(y => yourPreparedFn(number => y(y)(number)))) ((factorialFn)=> (number) => number == 1 ? 1: number * factorialFn(number-1)) (5) Don't worry if it takes a long time to get it - took me more than a day the first time and I had better resources than a youtube comment :)

The company would only be a real y combinator if they helped out in setting up companies that help out in setting up companies that help out in setting up companies...

Teachers like this professor here are, in fact, Y combinator themselves. Thank you.

Y Combinator is a y combinator. 🤯 I have been programming since 1989, and I literally just learned this today. I feel so ashamed, yet amazed.

I love how he said "... it will loop around to 2, 1 and so on, until it eventually gets around to 1 ...". Not sure whether it was intentional but that made me really happy :D

y-combinator: here are 10 minutes of introduction. To actually see more then the plain formula itself pls visit the wikipedia page. wtf :(

For the exercice on the fac function, I'm not sure but is it possible to write : fac = rec (λf.λn. n*(f (n-1) - 1/n) +1) So that the n*(-1/n)+1 cancel out when n is greater than 0 but as soon as n hits 0, we should compute 0*(stuff) and no matter the stuff we get 0 then add 1 so 0!=1 I'm assuming we're computing in a lazy way and when we see 0*... we immediately return 0

Dear Computerphile. The topics you cover are interesting, but you sometimes, such as in this video skip the important parts. While it is nice to know the history of an idea and the people behind it, it is really a lot better when you explain the idea through-fully, and when you first establish the grounds to complete the exercises the lecturer gives us. Like how does the Y Combinator Works, like please use it with an example, define how to use parenthesis, if the TRUE and FALSE statements are functions on themselves, please define why and how we can distinguish between functions and variables, etc.

Problem is that this series skips soooo much from basics of functional programming that it's complitely impossible to follow why stuff is done this way.

That functions all fun and games till someone puts -1 in it

This is certainly one of the coolers idears in computer science.

♬ When a grid's misaligned; with another behind; that's a moiré ♬

This might be the most important computer science video on YT

Please make a playlist of lambda calculus videos.

So the first question should be "loop = rec(λx.x)". If we look at it, we get rec(λx.x) = (λx.x)(rec(λx.x)) = rec(λx.x), which gives us our infinite recursion as desired. Not sure how to do the second one.

Muchas gracias profesor. La recursión es una gran ayuda!!

quick refresher lol last video was 7 months ago! come on computerphile!

great video; more on functional programming please

Simply awesome!

You made a video about the Y-combinator without explaining the Y-Combinator at all. Okay.

I think a possible definition of the factorial using 'rec' can be: rec (\f n -> if n = 1 => 1 else n * (f n-1)), where 'f' is going to be 'rec' after the first step. So the first call should be : rec (\f n -> if n = 1 => 1 else n * (f n-1)) n . Where n is the number whose factorial you want to calculate.

Make some videos on category theory

Can you do a video on how calculators calculate things like sine functions, and square roots?

Oh, I'm reading Prof Hutton's and Erik Meijer's paper on parser combinators from 1996. Cool to see him on computerphile.

I have almost 10 years of experience in more classical programming languages like C, Java, Javascript and Python, yet I haven't got the slightest idea of what the answer to these 2 exercises is.

Why is everything on computerphile left audio only and everything else is fine?

Very clear... i would like my teacher watched your videos...

Wait... did he give us homework?

The Y-combinator is the primal recipe for stackoverflow

i like the structure of Hutton's explanation. especially how he first introduces general recursion with rec f. but, he could have brought some extra attention to the fact that the result of rec f is a function. i think that this makes it extra difficult for people to understand (lot's of people confused in the comment section). working out the examples would have helped. on the other hand people might not really understand unless they come to the solution themselves. difficult dilema

The way I see it: The Y combinator is a function that takes a function _f_ and returns a new function _g_ that behaves exactly like _f_ except that it's implicitly passed _g_ as it's first argument.

Very good video! Now can we have a video explaining monads?

More of this!!

This is the first time I’ve ever heard the phrase “last day” in the sense of “previously.” Which branch of English says that?

How do you get the recursion to stop?

Great video

Great video! Just a question...when the author writes down the symbol "=" First he uses it as a term rewriting rule and later to give an alias to a complex lambda expression.,.former case seems to legitimate the use of recursion, latter does not. Is not this a way to use = symbol ambiguously? Does it make sense my rigorous worry? Wouldnt it be preferable yo use -> and the equivalent sumbol ≈ instead to clarify? . Somewhat pedantic, = should be used for denotational equations. Anyway, this is q wonderful video... straight and short.

How do I propagate the last case =1 up the recursion chain? Here is where I am stuck. Passing the 1 we receive at last up the chain: \f. .n*f(n-1) (1)

this video turns my brain into a rec.

What puzzled is that the `f(f(f(…)))` expanding never actually ends! Which to me meant that the argument of `f` will never be calculated, thus we won't ever be able to call the `f`. But that's only true if we eagerly evaluate the arguments. But we can postpone this evaluation until it's needed. E.g. in the factorial calculator we only need `f` when we call it in the "else" case: var fac_calc = f => n => n == 0 ? 1 : n * f(n -1) // < only here we need the actual function of the `f` which means that the actual unwrapping of `f` to the next step of recursion in `f(…)` can happen on demand. So `f(f(…))` turns into `f( lazy f ( lazy f(…) ) )`. For laziness we can declare functions with no arguments, that upon call will do some calculations: () => calculate_the_answer(42) Thus we redefine our `rec` and `fac_calc` to use lazy evaluation: var rec = f => f(() => rec( f ) ) Then we can define our factorial calculator as: var fac_calc = f => n => n == 0 ? 1 : n * f()(n -1) // unwrap lazy `f` and then call it And then derive factorial fn from rec + fac_calc: var fac = rec(fac_calc); And finally call it: fac(3); // = 6 Hope it helps someone else. Also see CheezyRusher's comment with great explanation of Y Combinator. P.S.: this is how we can define lazy `rec` via a Y combinator: var rec = f => (x => f(() => x(x))) (x => f(() => x(x)))

Can you make a video about assembly, compiler-omptimization or/and compiler-building, please?

This video defines y combinator in terms of itself. Watch again and again to understand.

More lambda calculus videos

Excellent.

if you delete all the parentheses in the y combinator, what does the resulting thing do?

Isn't the definition of `rec` at the end not a combinator because it has the free/unbounded variable x ???

That's a cool idear!

They need to make a video about combinator calculus

The function you apply to Y should have 2 parameters correct?

This is the first computerphile video that I didn't unserstand.. is this a bad sign

Simple types now please!

How often do you need recursion? Not often.

PS: Can confirm how the y combinator gets past step 3 here? IE: Does the input function get passed in as f again somehow or is the f on left side of the function always automatically assigned the original input value on every pass?: Step 1: (λf. (λx. f (x x))(λx. f (x x)))SomeFunction Step 2: (λx. SomeFunction (x x))(λx. f (x x)) Step 3: SomeFunction(λx. f (x x))(λx. f (x x)) Step 4 (Want to make sure this "f is automatically assigned SomeFunction as val on every pass" step is correct): SomeFunction(SomeFunction(λx. f (x x))(λx. f (x x))) If f is automatically passed the first input function on every iteration, then maybe this is a better way to show?: Step 1: (λf. (λx. f (x x))(λx. f (x x)))SomeFunction Step 2: (λx. SomeFunction (x x))(λx. f (x x)) Step 3: SomeFunction(λx. SomeFunction(x x))(λx. f (x x)) And so on SomeFunction(SomeFunction(λx. SomeFunction(x x))(λx. f (x x)))

Sound does not work anymore?

finally!

quote: "And that's basically what their company is doing..." should have been followed by: "They're a company that helps start companies which helps start companies" Just to be a real recursive company. Otherwise that company doesn't even deserve the name Y-Combinator.

Very Great！

Thank you

So the loop one is easy. loop = rec(λx.x). The factorial one, though - how do you stop? It seems to me that the definition of rec will loop infinitely no matter what you put as the argument to rec, but the factorial function obviously has to stop.

very nice video

Video on kmp algorithm plzzz

Is it possible to record your audio in a way where the pen sound is quieter? That felt tip pen on paper goes right through me worse than nails on a blackboard, it's horrible. Or some kinda pen that doesn't make that sound?

excellent

In lazily evaluated untyped languages, this works. But in strict statically typed (eager) languages like ML and F# this won’t work. The compiler will complain that the resulting type would be infinite. And if you work around that, your loop would be infinite.

Grandpa = father’s father Recursive is everywhere in universe

Very nice video, but why does Prof. Hutton pronounce Haskell like Pascal with an H?

Did anyone get to the expression of factorial?

mind blown...

recursion is the idea of having recursion Recursive definition

Love computerphile videos, but this..? Thanks for being like almost *every* maths teacher i've ever had: Teacher: 1+1=2 Me: ok Teacher: therefor, *obviously* integrating the sum of two cosines with their parameters being the derivatives of sqrt(2)/π *clearly* has to be.. Me: .. i wonder what's for lunch today..

In Python: (lambda x: x(x))(lambda x:x(x)) - although this bottoms out against Python's recursion limit instantly.

Most dope ⚡⚡⚡

Wouldn't a monitor with an editor not be a better tool to show of the examples?

Thank u sir

In a project, I had a recursive f() in the main loop, which is disastrous for performance. I took it off, using several 'goto's. However, I discovered that it got slower! o-0

Anyone else think that was Kryten in the thumbnail?

Funny video. At 9:24 he says to put in a simple function so not to over complicate the recursive function, but all this lambda calculus already seems like a massive over complication to me. Might just be me, but I'm sitting here behind my PC thinking, "yea, that's what recursive is, i do this all the time in my work", and its presented like this is quantum physics. I do have a question though. How would a functional language deal with memory overhead when stepping through a recursive function? Every function call is going to store some memory that's not released until the function completes. So a recursive function that isn't meant to end after a few calls, for example a computer game loop, will eventually crash the program.

But how do you do that in crocodiles?

varys?

One thing that can be confusing about this video is that he uses a language with lazy evaluation. So I translated the code to JavaScript and used a function to simulate lazy evaluation. i.e. () => rec(f) instead of rec(f) let rec = f => f(() => rec(f)); let loop = rec(f => loopBody => { loopBody(); f()(loopBody); }); let fac = rec(f => x => { if(x === 0) return 1; else return x * f()(x-1); }); let add = rec(f => x => y => { if(x === 0) return y; else return f()(x-1)(y+1); }); loop(() => { console.log(fac(5)); console.log(add(20)(22)); });

FP isn't hard, the problem its about industry standards that dictate production, so new programmers make the choice that gonna put then in the market faster. The most interesting, cool and exciting things happening in computer science today comes from FP concepts. FP handles parallelism and concurrency in a elegant, fun and manageable way, and everybody knows that these are the challenges of contemporary programmers to deal . The fact that most major languages are adopting FP in their architecture its at least a indication of the importance of the concept, so why so much repulse? I think programmers should always be open minded and ready to learn new stuff, only benefits can come from this attitude. A programmer that closes itself in conservatism can only condemn itself to closure, and that is not what we want, it is? I know that a programmer that worry only about his deadline is just living his life, all of us have bills to pay. But you can't go to everywhere despising others ways of thinking just because that wont fit in your deadline. The world is not just about that. ps: Thanks for the videos, i learned new stuff! I know that is not very complete, but you could consider a complete series in this topic, that would be great! I just finished the Nand to Tetris self course and was imagining a computer architecture built entirely of lambdas, that would be cool.

"This one (loop = rec(?)) is quite easy..." Um... maybe I'm just a silly imperative programmer, but I can't figure that out >_

Somebody needs to explain the explanatory comments to me. and then I also need an explanation of the resulting explanation. Ad infinitum. This is the essence of lambda calculus.

one day I'll understand it 😓

Thank you :)

That's an hard way to do factorial! I always do it the easy way !n = int_0^inf(t^n*e^-t)dt

I love how he expl

We could _try_ solving the factorial case if he at least told us how are we supposed to encode integers at all. How do I check for 1? How do I subtract? The only things we know about lambda calculus is how to do boolean logic.

I'm just a humble engineer attempting to transition to computer science. In common with all videos referring to lambda calculus, I still don't get it. I feel like the Red Dwarf Cat: "I understood everything up to simply..."

Btw, I heard that Y Combinator is usefull in call bu name reduction strategy, but useless in a call by value one.... In last case Y g can diverge for ever, despite of g

What is the Y Combinator? Computerphile: Yes

Ok so all of this makes sense, but please why would it be written as at 4:06? This seems really ambiguous

Please stop with marker on paper sounds - its screeching and makes me turn down the volume then I can't hear the speaker. Is there a way to selectively edit it out?

So hold on, WHY you made this video? Please change description to "Intro to Lambda and Y Combinator PART 1". Upload the others because am lost.

I can't stand the sound of marker on a paper, I go crazy. But still I watch and enjoy this through pain :)

Well, if fac is: fac = rec [some] , then according to the definition of rec we got: fac = rec[some]= [some] rec [some] . But rec[some] is fac due to definition of fac. So fac=[some] fac in that case [ some] = £f.£n (n==1) [ 1 n*( f n-1)]

"the way factorio works"... is that you build a factori on a alien planet using robots.. hmm .. wrong. ?