Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming in JavaScript

[@tashburn]

This was the clearest, most understandable introduction to lambda calculus I'm come across. Nicely done. Thanks for making it.

[@chumeh9886]

Very True. it has been so troublesome to me, but now its so clear. thank

[@john7556]

Agreed: I'm only 2m21s into the video, and he has clarified so much of the syntax that I'm very impressed (and regretful at all the time I lost to other "explanations"!)

[@otischance9144]

Sorry to be so offtopic but does someone know of a trick to log back into an Instagram account?? I somehow lost my account password. I appreciate any tips you can offer me

[@otischance9144]

@Fabian Jax thanks for your reply. I found the site on google and Im waiting for the hacking stuff now. I see it takes a while so I will reply here later when my account password hopefully is recovered.

[@otischance9144]

@Fabian Jax it worked and I now got access to my account again. I'm so happy:D Thanks so much you saved my ass :D

[@alinisar87]

This is hands down the best intro to functional programming/lambda calculus out there. The fact that it only has 38k views at the time of writing is a crime of untold magnitude.

[@gustavorino]

Top quality is not for everyone, unfortunately

[@itskshitij]

Just want to say, those were some of the best slides I've ever seen.

[@ziggy6698]

I used to teach at a fullstack bootcamp and I'm completely blown away by the quality of this lecture. Feel like an absolute jabroni. Amazing my dude.

[@ivandrofly]

Best explanation on the internet

[@ninichanglife]

the best lambda calculus explanation ever

[@psychedel0c]

This probably just saved my midterm grade, 10000x more clear than anything my professor has ever said. Also, this dude looks like the Jeff Winger of logical mathematics

[@glebec]

Hahah, you are the third person to tell me I look like Joel McHale. I don't really see it but I'll take it. 😂

[@SeverityOne]

Less than seven minutes in and I can already see that this is great: clearly explained, well articulated, the works. But now I have to rush off to work, writing lambda expressions in Java.

[@yannick6927]

Welll, good luck!

[@seyikareem8052]

This should be a TED Talk, the preparation must have been intense. You Sir are a genius

[@glebec]

Not a genius, just had a lot of fun reading up on what other people figured out before me! What you DON'T see here is all the time and effort it took to untangle those ideas, practice them, and examine them from different angles before it made sense to ME. Once I did that, I really wanted to make the subject easier to understand for people like me… by coming up with explanations which I think might have helped. Thanks for the kind words regardless! :-)

[@hocky-ham324-zg8zc]

Gabriel Lebec please make videos like this! I guarantee you’ll get a lot of exposure

[@charliegarrett5993]

This lecture is just unbelievably good. This guy is a very talented teacher/lecturer

[@mfrdbigolin]

Literally the best talk about lambda calculus on KZbin, after watching this video (and the second one), I am enthusiastic to read To Mock a Mockingbird.

[@olivierbegassat851]

This was remarkably clear, a lot of thought must have gone into preparing this talk ! Thank you so much for this excellent talk : )

[@codegeek98]

[0:00:00] Intro [0:00:48] I = a => a [0:01:48] Notation [0:06:39] Functions [0:09:15] Beta-reduction [0:11:49] M = f => f(f) [0:15:04] "n-ary" shorthand [0:17:00] K = a => b => a [0:18:44] KI = a => b => b [0:20:49] History [0:29:30] Combinators? [0:31:00] C = f => a => b => f(b)(a) [0:33:46] T = K; F = KI [0:39:53] not = p => p(F)(T) [0:42:21] not == C && not !== C [0:45:30] and = p => q => p(q)(p) [0:48:39] or = p => q => p(p)(q) [0:49:29] or == M [0:51:41] beq = p => q => p(q)(not(q)) [0:54:19] ¬(P ∧ Q) === (¬P) ∨ (¬Q) [0:55:01] Closing [0:56:48] Basis [0:58:15] WHY? [1:00:37] Y- and Z-Combinators [1:01:58] Outro

[@glebec]

Thanks for the timestamps!

[@florianvanbondoc3539]

Thanks for you work!

[@ivandrofly]

Good one thanks

[@tauruscolvin]

I’m a long time software engineer. Have been focusing on functional javascript the last couple years. Have been trying to put my finger on why functional feels so much better than other methods. This video and others like it get at it. Functional programming connects to underlying fundamentals such as the lambda calculus and category theory. Fundamentals which transcend a particular language. Functional programming feels like performed art. It’s satisfying again. Symmetrical, elegant, mathematical. I can tell the presenter *feels* the beauty of the lambda calculus too. Thanks for sharing!

[@patrikhagne9204]

Beautiful talk! I love the way you tie it into javascript, the one functional language that everyone understands!

[@pjnoonan1423]

This just opened a whole new world to my mind. I can't thank you enough for making and posting this. You can't possibly know how deep my thanks are to the presenter, the staff, and all other associated people. Keep doing what your doing, and you'll find someone will change the world because of your work. Thank you, and bless you all.

[@rboes208]

This is exactly how I feel as well!

[@theblackunderflow1842]

FullStack is amazing man!

[@wingsonthebus]

The prettiest slides I have ever seen. edit: also some of the most engaging math/programming teaching I have ever been privy to!

[@glebec]

Thanks!

[@joriskbos1115]

Watching this video felt like unravelling the world's deepest conspiracy

[@Yetipfote]

This comment is almost on par with the video!

[@aMulliganStew]

Mr. Lebec’s talk was excellent. If I had the desire to return to professional programming, I would be knocking at your door.

[@thomasononano9208]

I'm half way through this, just wanted to praise the speaker and the talk, real quality, perfect for my entry-level FP disposition.

[@vineboomsoundeffect5395]

The best video on λcalc‼️‼️

[@pawandesh]

Best video on Lambda Calculus ever. Got to know about the combinatorial logic for the first time so clearly. Thank you. 🙏👍🏽

[@gokk99]

spectacular presentation

[@SaisBlade]

Thanks for the great talk! I've been fascinated by this subject for a long time and this really helped cement the concepts better in my mind. One thing I'd like to understand better though, about the M* function (50:52): You say "The Mockingbird once removed is extensionally equal to the Mockingbird". If I understand correctly, these are the definitions we're working with: (0) M := λx. x x (0*) M* := λxy. x x y Applied to another function a: (1) M a = a a (1*) M* a = λy. a a y Applied a 2nd time (2) M a b = a a b (2*) M* a b = a a b It's clear to see that (2/2*) are intentionally (and extensionally) equivalent. (1/1*) appear to extensionally equivalent, since their applications yield intentionally equivalent functions But of (1/1*) - one of them (M*) is a lambda statement, while the other is an expression (no bound variable) Couple questions about this: A. does lambda calculus draw a line between these two concepts? or are they irrelevant distinctions? B. Since (0/0*) yield extensionally equivalent functions (1/1*), and thus any sequential applications of them will yield the same (extensional) results - is it fair to say that extensional equivalence is "backwards propagatable" in general? P.P.S.- To any non-JS programmers- I have no background in Javascript and had no issue following, the code use here is minimal and basic :)

[@glebec]

Thanks for this excellent question! Looking back on this talk, I feel I probably spoke too cavalierly about the M* function, especially as I think I may have subsequently seen definitions for "once removed" functions which differ from my example. Jargon aside, however, we can still talk about the logic. You asked: A) does LC draw a line between lambda statements vs expressions? B) Since (0/0*) yield extensionally equivalent functions (1/1*), and thus any sequential applications of them will yield the same (extensional) results - is it fair to say that extensional equivalence is "backwards propagatable" in general? Hm, interesting question. Certainly LC distinguishes between these at the level of the *grammar* (formal definition of the symbols in the language and how they may be arranged). In the LC grammar, an Expression is either a Value, Application, or Lambda abstraction. Clearly, (1) is an application whereas (1*) is an abstraction. And yet, as we can demonstrate via 2/2*, they are extensionally equal from the perspective of _application behavior_. I think what this comes down to is the notion of "equality" is contextual; we can define extensional equality in terms of application results (which 1/1* uphold), or we can talk about equality in terms of sentences in the grammar (which 1/1* obviously fail to pass). More practically, this sort of thing DOES have profound implications from the perspective of e.g. laziness or evaluation strategies. "Wrapping" some expression E in a "useless" abstraction like `λx.E x` is called "eta expansion". In an eager language like JavaScript, if E is itself an application like `a(a)`, then what you've done is prevented the evaluation of that expression by putting it inside a function body. The evaluation will therefore never be attempted if the function isn't invoked. This technique (eta expansion) is key to representing the Y combinator in JS; the Y combinator unfortunately cannot be used directly in JS because it would trigger infinite recursion. However, the Z combinator uses eta expansion to make part of the evaluation "thunked" or delayed. From LC we know that eta-expanding an expression is extensionally equal to the original expression, so we haven't changed the meaning of the combinator, but we HAVE changed its use case in the context of an engine which evaluates functions "eagerly". (BTW, eager evaluation means arguments to functions are evaluated before being substituted into the function body.) I didn't go much into this in the presentation, but it's a fact that "normal order" evaluation (leftmost outermost) will always find an answer if the expression doesn't diverge; JS doesn't use "normal order" however. Eta expansion can be carried out ad infinitum: `E` becomes `λa.E a` becomes `λb. (λa.E a) b` which becomes `λc. (λb. (λa.E a) b) c` and so on. All are extensionally equal as we have determined, but different evaluation strategies could result in different intensional representations, and some evaluation strategies could in theory fail to terminate. I suppose this implies that our definition of extensional equality only *really* holds for normal order evaluation! I have to think on this more. Thanks again for the stimulating thoughts, -G.

[@joseville]

@@glebec What is normal order evaluation? (leftmost outermost)?

[@glebec]

@@joseville Normal order evaluation is as follows: when multiple parts of an expression could be beta-reduced (i.e. simplified), choose to beta-reduce the leftmost, outermost expression first. For example, in `foo (bar 8) (qux 9)`, the definition for `foo _ _` will be substituted in before `bar 8` is computed and before `qux 9` is computed.

[@yathi]

This is the most amazing explanation of Lambda Calculus I have come across! Thank You !

[@waltermelo1033]

first time in life that i can understand why lambda calculus are so amazing :D congratulations

[@MCLooyverse]

On the bit about XOR or equality (@52:35): On booleans, *not*-equal is the same as XOR. We have && and || operators for AND and OR, but nothing for XOR... except you can use != for that. I also thought it was XOR at first, because I noticed the functions behavior was to return either q or !q, depending on p, it's just that XOR returns !q when p is true, and q when p is false, while equality does the opposite.

[@Kallebas]

This is correct and can be verified quickly by a truth table.

[@deepjyotisarmah8995]

XNOR / NXOR is equivalent to logical equality "=="

[@cashmoneyhustler]

Thank you so much. This is the best KZbin video on the topic. I was lost in the sauce until I watched this

[@usamakhawaja8571]

38 minutes into the talk and can't resist to appreciate. Very well explained

[@trblyoo823]

Hands down one of the most clear and concise videos I've seen introducing basic concepts of Lambda Calculus. Gabrial's excitement pretty much forced me to crack open a REPL and follow along. I'll now be locked away composing combinators for a very long time. It's also so painfully obvious how this subject can help to write more clean, readable, and declarative code. Great Job on this one. Part two blew my mind! The more I try to "play" with these combinators, the more I see the need for FP data structures. If anyone has any recommendations for similar talks, specifically on Lambda Calc within Javascript, I'd really like to see more on the subject! :D

[@AK-vx4dy]

Clearly clearest explanation on YT

[@amir650]

What an amazing speaker and so much content to revisit. I love this video.

[@JulianTontiFilippini]

Brilliant presentation. I can see why Gabriel said he spent a long time making it.

[@ilkero1067]

Excellet introduction! I knew nothing, (despite watching another video by which I was more confused than enlightened) now things are much clearer, bravo!

[@yuanyeo6926]

Remarkable, this is the video recommended by my professor

[@azurewang]

so clear explained and slide are just artwork

[@syrix5914]

I come back to this often. Love it!

[@aziz0x00]

Please i want a medal for this dude for this amazing and well done presentation! Really its hard work! Thanks!!!!

[@seahorsebyte]

what an amazing presentation!!!

[@sab611]

Very helpful on my path to understanding functional programming. If you make any more related vid's I'd like to know.

[@odiseezall]

I finally get how much you need to know and understand to start contemplating creating a start-up company.

[@Rachel-zw8sy]

Such a great explanation of lambda calculus that I was so confused about -- thank you!

[@florianwicher]

Loved the presentation. This guy really knows how! :D

[@lennyvsguitar]

Florian Wicher I absolutely agree.

[@myhumblebeginnings]

Mr. Lebec, thank you very much for this material of yours. I will do my best to digest this to the best of my intellectual ability.

[@jakeaustria5445]

Thank you! This is the best introductory lecture for lambda calculus!

[@profdre]

Great video. Easy to understand, the idea to translate lambda into fat arrow functions works perfectly for me... I'm going to spend the rest of the evening playing around with the nodejs prompt. Great video!

[@chrissxMedia]

This talk is essential. Seriously. I've spent the last 9 months implementing λ-calculus, inspired by this, and every now and then I come back to it, just because it is so awesome.

[@kenho811]

This is an excellent talk. Thank you so much 😊😊

[@monkeytrollhunter]

Thank you so much, I had no luck understanding beta reduction but you made it so clear with such complex example.

[@glaurung78]

Cool video, but my question is, whose idea was it to show the camera layer above the layer where the code is shown?

[@simongarcia5648]

Thank you for this talk, insanely good and fun!

[@VladTrishch]

I am impressed. Math is so beatiful! Thanks for an awesome talk.

[@alexlindgren1]

This was a really good presentation, informative, easy to listen to and with some humor. You did a really good job at helping me understand this stuff, thanks for that.

[@SatyajitGhana7]

53:02 *that's XNOR !*

[@theogiani8562]

Yes ;-)

[@omrishavit8843]

I thought the same! And then when he said "boolean equivalence" I felt both stupid/wrong and smart/correct

[@gumfun2]

Right. I thought of it as 'if and only if'

[@florianwicher]

This guy does everything right. Also love his use of PowerPoint

[@RohitWason]

This is simply beautiful. As beautiful as the concept of Lambda Calculus is, you have done an equally elegant job at explaining it, along with a hint of some JS genius. Thank you!

[@rbettsx]

What a communicator! The first completely lucid explanation of lc I've seen. The beautiful graphics really help, as does the parallel code. Fan...tastic.

[@gustavodelgadillo7758]

Doing so much Bizz related stuff over the last couple of years had me down during this pandemic, I felt like there's no science in the day to day computer tech industry, but FP is raising and so is lambda calculus, this talk is a gem got my interest back in the math behind computers and inspired me again, just for the beauty of math itself and the art just like You mentioned. I can't thank You enough. My best wishes in this hard times for everyone, be strong.

[@joseville]

Notes (this might confuse more than elucidate, so apologies if it confuses - it makes sense to me right now and hopefully in the future as well): 5:40 Application is left-associative -- MNP is interpreted as (MN)P -- If we want to represent the alternative parsing, i.e. M(NP), we must use parentheses. There is an implied application operator between (infix) consecutive terms -- e.g. in MN there is an implied application operator between M and N. when using infix operators in notation, the parsing can be ambiguous -- `a ~ b ~ c` can be parsed as `(a ~ b) ~ c` or `a ~ (b ~ c)`. We define that application is left-associative, by which we mean that `a ~ b ~ c` should always be parsed as `(a ~ b) ~ c` and if we want to express the alternative parsing, `a ~ (b ~ c)`, then we must use parentheses. [1] 6:58 The dot (.) is followed by a term which is the abstraction body. The abstraction body extends to the right as far as possible. 7:58 If we consider λ as being the abstraction operator, then it is a prefix operator in this notation. When using prefix operators/notation, there is no ambiguity w.r.t. parsing -- there is only one way to parse expressions containing prefix operators. [1] In notation, λ, as a prefix operator, is always followed by its first operand, an identifier (e.g. x) representing the variable, followed by a dot (.) followed by its second operand, a term, the term being the abstraction body. This lambda calculus notation mixes prefix and infix notation, if that makes sense. It notates abstraction (λ) as a prefix operator and application as an implied infix operator. More about prefix vs infix notation/operator and ambiguity in parsing: [1] math.stackexchange.com/questions/4283525/in-polish-prefix-notation-of-binary-operations-are-all-expression-unambiguous-w

[@고래-f8k]

omg~ to understand this lecture, I study hard english! worth it! Thank you.

[@bestieboots]

This is amazingly good. I'm just blown away.

[@samueleagostinelli5346]

This is absolutely fascinating. Thanks!

[@maNIKLAS2012]

Thanks for the great presentation!

[@aiohto7884]

Best explanation yet from a high school student perspective thank you :)

[@jjjjjenkins460]

This was the best video on lambda calculus online. Such a knowledgeable person, who gives perfectly clear examples, and walks us through it. Thank you!

[@joseville]

50:45 M* is called the Mockingbird once removed. It takes two arguments and applies the first argument to itself and ignores the second? or does it apply the first argument to itself and then applies the result to the second argument?

[@NStripleseven]

It takes two arguments, applies the first to itself, then applies the result to the second argument. So a(a)(b)

[@korvstenius]

This presentation blew my mind. Awesome stuff!

[@ivandrofly]

Beta reduction 10:53 0:47 - Identity "I" 14:35 omega combinator 16:03 nested lambda

[@JoopWilkens]

Excellent presentation. By the way, at 52:40, it's not the XOR(=exclusive-or)-function, but the negation of the XOR.

[@Shnugs]

I stumbled across this a couple years ago and struggled to find it again for the longest time. I ended up randomly stumbling across To Mock A Mockingbird and managed to find my way back to this again. Genuinely recommend this as the beginning point for lambda calculus/function programming. Does anyone have any recommendations for what to learn after this

[@Silkerdax]

Very helpful! Thanks for the talk.

[@MinhLe-xk5rm]

Great tutorials on functional programming. Thank you!

[@wasifzaman1399]

This is so engaging! Thank you!

[@Kunleskeleton3332]

thanks so much. for a newbie to understand this, is remarkable on your part.

[@callumvanheerden1530]

You can see his passion. Great work.

[@viglioni]

When I started this video I wasnt expecting it to go that further. I loved it! One of the best videos I've ever watched in this subject!

[@AndersJackson]

Beta-normal form are shown not to be calculated in general form already in the 30:th by Entscheidungsproblem presented as one of many problems by D. Hilbert in 1928. In 1936 A. Church and A Turing showed independently with Lambda Calculus and Turing Machine that it was not possible to make a program that could decide if a program was decidable. It is called Church-Turing thesis. This is fun reading: en.wikipedia.org/wiki/Entscheidungsproblem

[@qaisahm8144]

This was honestly a very amazing talk, fun and educational at the same time, I've just had fun learning while preparing for my exams, again great work and many thanks mister Gabriel!

[@rboes208]

That was an amazing talk, thank you!

[@schoo9256]

Note, 29:30 is where the history finishes. (Well worth watching at least twice, but depending on how often you want to reference this video you might not want to see it every time!)

[@yingkui]

Great Work. Both the thoughts and the slide deck. Amazing!

[@rob6129]

I was very skeptical at first but it turned out to be well worth the watch

[@lc11s]

Well done - fantastic lecture - best explanation of lambda calculus I came across so far!

[@R2r_1337]

This is the best video on Computer Science ever

[@glebec]

Flattering! Untrue IMHO, but flattering anyway. ;-)

[@myhandlehasbeenmishandled]

Thank you for placing the video of the speaker over what he types. It really helps. /s

[@paxdriver]

It is so hard to teach this subject, excellent job

[@aldricazucena5471]

If this guy was my teacher, I would LOVE this class and sign up for every. single. one. of his classes lol.

[@stephenjames2951]

A great talk fun and truly informative.

[@gumfun2]

Great video, preparation, delivery, ...

[@adumont]

An excelent talk!

[@ycombinator765]

I am very happy I could come up with AND myself by thinking through it. It might be error prone but it passed all possible tests. AND ab := λab. ab NOT b Or more simplified version be AND ab := (λab. ab λp.p λab.b λab.b b) ab I know its not related but I am happy that as a 17 yr old, I could understand it well enough. Credit goes to genius instructor.

[@DamjanPavlica]

It is strange how simple concept is it, but yet I could not easily adjust my brain to that level of abstraction.

[@glebec]

It honestly took me a lot of reading, thinking, and practicing, and I have a degree in math. But like everything in math, with enough time it becomes much easier. I tried to make it easier than when I learned it! :-)

53:03 equality = xnor, xor is the other way around

[@riebeck1986]

Thank you for making this !!

[@glebec]

Thanks for watching!

[@codecleric4972]

I watched several videos about this topic and felt I kind of grasped it but this talk just made it crystal clear. Seriously can't say anything that hasn't already been said, but this talk is amazing and mind expanding!

[@levanroinishvili1]

Wonderful talk!!! Many thanks!

[@glebec]

Thank you for the kind feedback. Glad you enjoyed it.

[@alexanderhorstkotter2910]

Great and fun explanation, thank you very much

[@amanutkarsh724]

Thankyou so much for the lecture.

[@jags4all]

What a beautiful talk....