What is Lambda Calculus and why?

I was going to make it nicer but I ran out of patience. And time. But mostly patience. But hey, production quality is not important, right?
Pencil Code demo:
yanamal.pencilcode.net/edit/fu...
Lambda Calculus visualizer repository (warning: the text is currently wrong and the code is janky):
github.com/yanamal/lambda-js

[@yanathecontrarian4863]

Hey everyone! Thanks for watching! Based on the discussions and thoughts people had in the comments, I just came up with an idea and outline for a sequel video, tentatively titled something like "Lambda Calculus 2: But where is the calculation actually happening? (two and a half semi-satisfying intuitions)". But I kind of want to make another visualization for it. and also making videos is hard. and I'm supposed to be writing a dissertation proposal. So I guess you can look forward to that, but don't hold your breath.

[@paeden5431]

Are you still planning on more content?

[@EternalSushiLover]

Yes are you still working on a sequel/serie of Lambda Calculus videos? This would be soooo useful and appreciated; Thank you!

[@dercoder015]

still holding my breath, this channel is awesome btw, love all your videos

[@veeloth]

​@@dercoder015you naughty follower

[@salomongilberto5347]

We keep waiting 🐥

[@charizardman283]

Woah, finally! A video that explains it in a way that makes sense! You hit the nail on the head with everyone plugging in existing mathematical expressions to "simplify things" which actually just made it more difficult to figure out what's going on lmao. Exactly what I was looking for.

[@mehradzeinali9703]

finally someone who explains it well

[@se7399]

Finally, some new channel in which I can barely understand words from. Subscribed.

[@itzsleazy6903]

Thanks for this video! I had to rewatch it a couple times to understand it but that wouldn't have been possible without your great visuals helping me along :)

[@uncoherentramblings2826]

Yes! I did a lambda calculus and typed lambda calculus interpreter for my bachelors thesis/project. Very cool!

[@mantacid1221]

You explained this so well! I was struggling to Understand how these get applied, and this explained it beautifully!

[@vancomchick]

Interesting video! Looking forward to more lambda calculus content from you!

[@KAZVorpal]

This is the best programming theory video ever. Never change.

[@arborinfelix]

That's a nice introduction to Lambda Calculus

[@Spark_Books]

This is better than the computerphile video. Thanks!

[@Lambdaphile]

I just absolutely love your style! ❤️_❤️ And good explanation too!

[@RayArias]

You're awesome, @yana!

[@zoefaramunga8752]

ok you're the only person who tells me things about lambda calculus anymore, thank you very kindly

[@bsummer]

after soo many years in high school to going to read Maths in College. 15 years later i am here to relearn the lambda calculus to understand the basics of computer programming . This is my journey to becoming a cloud Engineer. Thanks for explaining this. I think Companies must allow job seekers to add "College of KZbin" to their RESUME!.

[@cd7002]

great visualization, congratulations

[@Wonkyth]

Great video. Would love to see more :D

[@jojosthenewblack]

Thank you very much! I subscribed, and hope to see more from you!

[@melasonos6132]

Wow. You are really cool and good at explaining. I am learning Haskell and this helps :)

[@enriquelmx]

Really nice video, instant subscribing right now

[@ananya_sutradhar]

You are the best!!!!! finally got to understand lambda calculus (not totally but much clear now). Keep posting content

Great explanation. Plus, it's like fun with flags, but with programming.

[@ShahnawazSayyad]

Please.. more videos.. you have a very good way of explaining.

[@dorothystaniforth3599]

You are, The long lost easy to understand math teacher that I never had!🎲🎲

[@kapka6700]

this is the best video on youtube

[@AgustinBad]

Awesome explanation!!

[@mackexr]

great video i finally get it! thank you

[@kaidoxbeastgaming5512]

The video explain so well. Thank you

[@logauit]

Amazing! Thank you so much!

[@HacBe]

Hello you lovely person looking almost exactly like my highschool crush. When I first found this video 5 months ago in searching for an entry to lambda calculus, I must admit I didn't really understand the replacement system. Two months later I started learning some functional programming in haskell and I thought I was now kind of understanding this video. But now after actually learning about lambda calculus in functional programming.. I finally started to understand how to build NOT and AND and finally the whole video. Thank you Yana!

[@HacBe]

Now modelling after AND. I hope that OR means \a\b ( a TRUE b ) Praying to the KZbin gods that if my current crush won't reciprocate my feelings until August, my highschool crush will! Sorry for being greedy xD

[@david12kk5]

amazing video

[@algoboi]

FUNCTIONS DESCRIBE THE WORLD!!

[@rufus8765]

Hey good video, really made me understand it

[@paulhaworth5178]

Great video Yana, thank you! My daughters also enjoyed it, but we all wondered if you're a "Dwight in Shining Armour" fan (given your moniker)?

[@yanathecontrarian4863]

thank you! I actually hadn't heard of Dwight in Shining Armor but I just looked it up and it seems great, I'll have to watch it!

[@uirwi9142]

Yay, now i can recreate Gimp in bash. xD BTW, this was incredibly insightful, thank you.

[@SlavikKoval]

waiting for more videos

[@lame_lexem]

nice video, can I ask , what is this green //TODO curtain?

[@yanathecontrarian4863]

Thanks! the //TODO is because I meant to figure out how to green-screen in something more interesting, but then ran out of time and/or got too lazy.

[@ranam]

What I don't understand about lambda calculus is that it can reveal a pattern by its action but it's hard to imagine the rules which trigger the computation results in a pattern does this pattern have to do some thing with group theory pattern

[@yanathecontrarian4863]

yeah, it's hard to imagine where and how the actual computation is happening, maybe because we're not used to thinking of the reduction rule (i.e. substituting in parameters) as something that actually does "work" or computation, as opposed to just being a pre-requisite to the "actual" computation inside the function. And yet, that's the only thing that does the work, because that's the only thing that can happen! My intuition is that it's quite different from the way group theory works, although in math I suppose you can think of ways that anything is similar to anything! There are some similarities, in that we're talking about applying one operator to some set of *things*, and also there's an identity *thing*, but beyond that, I think the way it actually works is quite different. For one, in group theory, there's inverses. Each element necessarily has an inverse, and that's very important to what we can subsequently say about the group. That's not really so in Lambda Calculus.

[@ranam]

@@yanathecontrarian4863 thank you for your reply and one more question can lamda calculus also be an easy tool to understand pure abstract mathematics please tell their connection s thankyou 🙏🙏

[@yanathecontrarian4863]

@@ranam I'm not sure, Lambda Calculus is *a* pretty pure mathematical thing, but I feel like it's more *about* computation than math. It could be used as "gateway math", I suppose? like, you were a computer scientist and then it was relatively easy for you to learn about Lambda Calculus and now you accidentally understand more about how "pure math" works?

[@ranam]

@@yanathecontrarian4863 thank you for your explanation i will try my best to understand i am already 36 turning 37 still fighting and struggling to understand pure math it has been a long 27 years of pain only for understanding it .lets see the time will tell my progress but please post an intuitive videos on lambda calculus and pure math friend

[@ranam]

@@yanathecontrarian4863 so iam getting it slightly these can only take functions and return function ie true and false are also functions am I right and inverse is not any kind of gate like not , nand , nor and or ie they are gates act as functions they are reached to us like operators I don't no why so these can not be compared with group theory similar to Wolfram project cellular automata so every time the computers a bit value representing a digit or decimal it's just giving a function am I right slightly confused please help me

[@qedqubit]

has Lambda calculus have Units ? i don't get it : it's like the definition of Pi makes the binary digits aproximate it precise enough. why aren't all C(+++#) languages specified in ONE Lisp ? so then Borland-kernel and GNU assembly can be translated to ONE machine Language, and Linux could be compiled with a "Make world" command like in BSD ?

[@yanathecontrarian4863]

Lambda calculus (the version I'm talking about here, which is the "default" version) doesn't have units, or data types, or anything except functions and binding values to function inputs. However, similar to how I defined certain functions to mean "TRUE" and "FALSE", you can find clever function definitions to mean "0", "1", "X+1", etc. and then recreate all of integer arithmetic in Lambda Calculus. One of the earlier versions of Lambda Calculus had data types, but that introduced some paradoxes ( en.wikipedia.org/wiki/Lambda_calculus#History ). In terms of actually using Lambda Calculus as the basis of computers, it's actually not super practical. Out of Lambda Calculus and Turing Machines - which have been shown to be "equivalent" in the sense that if one can compute something, the other one can compute it - Turing Machines are much closer to how computers actually work right now (they have memory and a linear sequence of instructions). Although you can write an equivalent Lambda Calculus program, it won't necessarily run *efficiently* on a computer. So, most languages, somewhere down the line, compile into *assembly* or *byte code* or some other low-level language which consists of a linear sequence of instructions that write and read from memory. I'm pretty sure the first C compiler was written in assembly of some sort. Even a Lisp program, when you actually run it on a computer, gets turned into something more assembly-like and then gets executed. But the benefit of functional programming languages (which are in some way "children" of lambda calculus) is that you as the programmer can think about the problem in a different(functional) way, and can rest assured that it will get converted into a more turing-machine-like way properly and automatically.

[@Wander4P]

What is the yellow book?

[@yanathecontrarian4863]

The Lambda Calculus. Its Syntax and Semantics by Henk Barendregt

[@michamiskiewicz4036]

4:44 (after defining an identity function which ignores one of its arguments) "And now we're finally getting somewhere useful!" That's the first video on logic that actually taught me something, thanks! [btw, is "λa.λb. a TRUE b" a valid OR function?]

[@yanathecontrarian4863]

Yep, that's an OR! nice! Did the video teach you that in logic, "useful" may mean something other than what you're used to?..

[@michamiskiewicz4036]

​@@yanathecontrarian4863 I see my comment was quite confusing. I should've written it with a horizontal line between one part and the other. - The video just taught me something about lambda calculus, which I'm grateful for. (that comment was meant to be general) - The timestamp comment simply expressed my surprise at you calling the forgetful identity useful. (although it does turn out important later)

[@yanathecontrarian4863]

@@michamiskiewicz4036 I wasn't sure whether you meant it the way I interpreted it, but I just thought it was a funny interpretation. Anyway, thanks, glad the video was useful!

[@BackToSquare1]

You’re so cool

[@SyntakticSugar]

Great video, thank you :) what book are you referring to?

[@yanathecontrarian4863]

The book I was holding is "The Lambda Calculus. Its Syntax and Semantics" by Henk Barendregt, though I don't know how much of it I actually read.

[@SyntakticSugar]

@@yanathecontrarian4863 thank you for replying Yana :) your video was very helpful!

[@waterbird2686]

Something similar came to me in a dream I described this to my friend and he pointed me to lamda calculus so turns out I didnt come up with something new

[@yanathecontrarian4863]

I always feel pretty clever when I accidentally re-invent something that "real" famous mathematicians or computer scientists invented!

[@yanathecontrarian4863]

To whoever just proposed λx.λy.xxy as OR (and then deleted their comment) - I think that works too! (alongside the other one proposed in an earlier comment).

[@bhaaz]

This is brilliant, thank you heaps. No one explains it this good on yt. Can you make a similar one on the Y combinator? Maybe a bit slower if you have the patience. You inspired me to figure out that there are two equivalent expressions for OR. Say, we follow your logic in decomposing the calculus and for all expressions Lambda is denoted as a forward slash '\'. Then, OR:= \a. \b. a TRUE b; There is also an alternative, which parses another definition: OR:= \a. \b. a a b; - This works a little differently, and it is equivalent to what you find on wikipedia: OR:= \p. \q. p p q. Wiki also gives an alternative for AND: \p. \q. p q p. Cheers

[@yanathecontrarian4863]

That's very cool with the alternative expressions for AND and OR! I do theoretically want to make another video (or two) trying to parse out the Y combinator and recursion. Though step 1 would be to understand the Y combinator. (I've theoretically wanted to make another lambda calculus video for over a year now, so don't expect it too terribly soon)

[@codecleric4972]

Good explanation. Fast transitions but we can always pause the video 🙂

[@yanathecontrarian4863]

Thanks! I recently re-watched it and I totally agree about the fast part. There were also a million places where I wish I had highlighted the part I was talking about at the moment.

[@Wander4P]

@5:40 and @6:53 you click on FALSE as if you had a choice of substituting TRUE or FALSE, but by the lambda calculus convention of left association that should be a given, correct?

[@yanathecontrarian4863]

Correct - The only reason I'm clicking on them is to make the interactive visualization progress. When I built it, I imagined it as a sort of exercise where the user would have to click on the right thing (the thing that gets substituted in next), and until they do that, nothing happens.

[@TitaniumRailgun]

People challenged me to master calculus How am I going to master it if I don’t even know about this thing

[@yanathecontrarian4863]

Well technically, "calculus" just means any "method or system of calculation", so you could just master any one method of calculating *something* that you feel like. Then again, when people just say "calculus" they usually mean the specific calculus that's more properly called Infinitesimal Calculus, and it has very little to do with Lambda Calculus. If you wanted to master all of the calculuses you'd have quite a road ahead of you... ( en.wikipedia.org/wiki/Calculus_(disambiguation) )

[@haydermabood]

Which is more accurate "SOME_FUNCTION" or "SOME_LAMBDA"?

[@haydermabood]

i.e. is it "lambdas" all the way down or "functions" all the way down?

[@yanathecontrarian4863]

@@haydermabood I think they are usually called "lambda functions", so "lambda" is more of an adjective in this context. And I would say "function" is more descriptive, since lambda is just an arbitrary greek letter.

[@BillboMC]

lam a . lam b . a True (And b True) Does this work for Or?

[@yanathecontrarian4863]

I think it does! I also think the (And b True) part can be simplified a bit

[@sandpaperunderthetable6708]

"And b True" is just the same as b itself though

[@darrenzou2967]

as a applied CS guy, WTF?

[@yanathecontrarian4863]

Thank you for your thoughtful and well-considered question. As an applied math person, I have to wonder WTF is "applied CS" - since CS is basically applied math. Is "applied CS" just a euphemism for programming? If not, and it is actually supposed to involve computer science, I think you should be at least a little alarmed if this whole video went over your head.

[@joseville]

Nice! I really like the visualizer. Is there a way to input our own functions into the visualizer? Just saw the end of the video so I know the answer lol. Btw, at 3:53, if SOME_FUNCTION were λx.xx itself, we'd end up with the original expression and we'd have infinite recursion?

[@yanathecontrarian4863]

Thanks! Yep, you're right - (λx.xx) ( λx.xx) is an infinitely recursive expression which does nothing except for recursing. As I understand it, it's a step toward getting "useful" recursion, which is achieved by combining something called the "Y combinator" with a function you want to make recursive. But I haven't tried to understand it more deeply than that yet. Also, technically, there is a very limited way of putting in expressions in the visualizer - you can pass them in as part of the URL, so for example yanamal.github.io/lambda-js/expand.html?expr=AND%20TRUE%20TRUE visualizes "AND TRUE TRUE". but as far as I remember you can only put in space-separted (well, %20-separated) symbol names, not parentheses or lambdas or anything else. If you do try it, I'd like to reiterate all the disclaimers about it being unfinished and possibly limited and the text may be incorrect in places, etc.