Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming in JavaScript
HTML-код
- Опубликовано: 6 авг 2024
- Fullstack Academy was recently ranked the #1 coding bootcamp in the U.S. Learn more at www.fullstackacademy.com
The Lambda Calculus is a symbol manipulation system which suffices to calculate anything calculable. This branch of pure mathematics forms the backbone of functional programming languages, and here it is presented through the concrete and familiar lens of JavaScript.
In this Lambda Calculus video you will learn:
- Lambda Calculus Syntax
- History of the foundations of mathematical logic
- The essence of functional programming
🔗 Part II: • A Flock of Functions: ... 🔗 Slides: bit.ly/2xpcPKn 🔗 Repo: github.com/glebec/lambda-talk
This was the clearest, most understandable introduction to lambda calculus I'm come across. Nicely done. Thanks for making it.
Very True. it has been so troublesome to me, but now its so clear. thank
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"!)
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
@Otis Chance instablaster ;)
@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.
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.
Top quality is not for everyone, unfortunately
Watching this video felt like unravelling the world's deepest conspiracy
This comment is almost on par with the video!
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
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. 😂
the best lambda calculus explanation ever
Just want to say, those were some of the best slides I've ever seen.
This should be a TED Talk, the preparation must have been intense. You Sir are a genius
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! :-)
Gabriel Lebec please make videos like this! I guarantee you’ll get a lot of exposure
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.
Welll, good luck!
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.
This lecture is just unbelievably good. This guy is a very talented teacher/lecturer
[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
Thanks for the timestamps!
Thanks for you work!
Good one thanks
Literally the best talk about lambda calculus on RUclips, after watching this video (and the second one), I am enthusiastic to read To Mock a Mockingbird.
This was remarkably clear, a lot of thought must have gone into preparing this talk ! Thank you so much for this excellent talk : )
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!
Beautiful talk! I love the way you tie it into javascript, the one functional language that everyone understands!
Mr. Lebec’s talk was excellent. If I had the desire to return to professional programming, I would be knocking at your door.
Best explanation on the internet
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.
This is exactly how I feel as well!
FullStack is amazing man!
Brilliant presentation. I can see why Gabriel said he spent a long time making it.
38 minutes into the talk and can't resist to appreciate. Very well explained
I'm half way through this, just wanted to praise the speaker and the talk, real quality, perfect for my entry-level FP disposition.
Best video on Lambda Calculus ever. Got to know about the combinatorial logic for the first time so clearly. Thank you. 🙏👍🏽
Such a great explanation of lambda calculus that I was so confused about -- thank you!
53:02 *that's XNOR !*
Yes ;-)
I thought the same! And then when he said "boolean equivalence" I felt both stupid/wrong and smart/correct
Right. I thought of it as 'if and only if'
first time in life that i can understand why lambda calculus are so amazing :D congratulations
Very helpful on my path to understanding functional programming. If you make any more related vid's I'd like to know.
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!
Great Work. Both the thoughts and the slide deck. Amazing!
Excellet introduction! I knew nothing, (despite watching another video by which I was more confused than enlightened) now things are much clearer, bravo!
Thank you so much, I had no luck understanding beta reduction but you made it so clear with such complex example.
Thank you so much. This is the best RUclips video on the topic. I was lost in the sauce until I watched this
thanks so much. for a newbie to understand this, is remarkable on your part.
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.
This is correct and can be verified quickly by a truth table.
XNOR / NXOR is equivalent to logical equality "=="
Thank you for this talk, insanely good and fun!
What an amazing speaker and so much content to revisit. I love this video.
This is the most amazing explanation of Lambda Calculus I have come across! Thank You !
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
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.
It is strange how simple concept is it, but yet I could not easily adjust my brain to that level of abstraction.
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! :-)
I come back to this often. Love it!
Remarkable, this is the video recommended by my professor
The prettiest slides I have ever seen.
edit: also some of the most engaging math/programming teaching I have ever been privy to!
Thanks!
This guy does everything right. Also love his use of PowerPoint
Clearly clearest explanation on YT
Well done - fantastic lecture - best explanation of lambda calculus I came across so far!
Great tutorials on functional programming. Thank you!
I am impressed. Math is so beatiful! Thanks for an awesome talk.
This presentation blew my mind. Awesome stuff!
Very helpful! Thanks for the talk.
I finally get how much you need to know and understand to start contemplating creating a start-up company.
This is so engaging! Thank you!
so clear explained and slide are just artwork
spectacular presentation
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.
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
Excellent presentation, Thank you very much
Loved the presentation. This guy really knows how! :D
Florian Wicher I absolutely agree.
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.
Amazing! It seems so simple.
You can see his passion. Great work.
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!
That was an amazing talk, thank you!
This video is very helpful and understandable!!!Thanks!
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
This is absolutely fascinating. Thanks!
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 :)
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.
@@glebec What is normal order evaluation? (leftmost outermost)?
@@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.
The best video on λcalc‼️‼️
Such a clear talk. Thank you.
This is amazing! Thanks!
This is amazingly good. I'm just blown away.
Great talk, thanks!
Wonderful talk!!! Many thanks!
Thank you for the kind feedback. Glad you enjoyed it.
phenomenal lecturer
Great explanation!
Thanks for the great presentation!
what an amazing presentation!!!
very clear ad thanks for the heads up on 'to mock a mockingbird.' It's on my x-mas list.
Amazing talk. Thank you.
What a beautiful talk....
This is just beautiful and amazing!
I was very skeptical at first but it turned out to be well worth the watch
Great and fun explanation, thank you very much
Thank you very much Sir. this inspired me to keep on studying Lambda Calculus although i'm over the hill.
Cheers! It's never too late to keep learning, right? I sometimes wish I had done more of this stuff in college, but I'm doing it now and enjoying it. :-)
Neat, thank you for your effort.
Amazing, you are a great lecturer.
Thank you for this video!
Super cool, thanks a lot!
Great video, preparation, delivery, ...
Best explanation yet from a high school student perspective thank you :)
omg~ to understand this lecture, I study hard english! worth it! Thank you.
An excelent talk!
This is an excellent talk. Thank you so much 😊😊
The bad thing about this video is that the bottom left is covered by the presenter and I can't see what he is typing.
Right? Like they couldn't have put him in the other corner?
What are you talking about? Not only does he literally narrate everything he types, the only _second_ where this is remotely relevant is 20:38, and even then you can see what he just typed a moment later when he presses [Enter] and it moves up a line.
I’m amazed anyone even noticed. Then again some ppl look for things to complain about
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!
Excellent indeed, Thank you !
A great talk fun and truly informative.
Absolutely beautiful
10/10 Would watch it again
Awesome, man! Just awesome!
It is so hard to teach this subject, excellent job