Lambda Calculus - Computerphile

  Рет қаралды 990,652

Computerphile

Computerphile

7 жыл бұрын

The basis of almost all functional programming, Professor Graham Hutton explains Lambda Calculus.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

Пікірлер: 1 200
@illustriouschin
@illustriouschin 7 жыл бұрын
"The answer is actually really easy." *Introduces an entire galaxy of new concepts in the answer.
@HectorIvanPatricioMoreno
@HectorIvanPatricioMoreno 5 жыл бұрын
Like me teaching.
@ntwede
@ntwede 4 жыл бұрын
And somehow made it include biology and history
@vendicarkahn4860
@vendicarkahn4860 4 жыл бұрын
No new concepts were introduced.
@ionichi
@ionichi 4 жыл бұрын
@@vendicarkahn4860 There is nothing new under the Sun.
@noaht2
@noaht2 4 жыл бұрын
The answer is actually surprisingly simple. - Ceave Gaming
@NoorquackerInd
@NoorquackerInd 3 жыл бұрын
"Every computer scientist should know about this" People that only studied object-oriented programming: _shakes in fear_
@54akhilesh
@54akhilesh 3 жыл бұрын
hahahahaha
@TheMaremessina
@TheMaremessina 3 жыл бұрын
who cares functional programming is useless to know anyway
@AllUpOns13
@AllUpOns13 3 жыл бұрын
He said computer scientist, not programmer.
@mrpedrobraga
@mrpedrobraga 3 жыл бұрын
@@AllUpOns13 it's true! Functional programming is rather inneficient generally if you want to get things done, but are useful for proving things, I guess
@dmitryburlakov6920
@dmitryburlakov6920 2 жыл бұрын
@@mrpedrobraga Not only for proving things really IMO. It's very useful when you need extra control of the program state, when there's a lot of inputs and outputs. That way having pure functions, higher-order functions and controlled storage makes it much easier to see what's going on in your environment. You can take a snapshot of your state or even reverse it, you can control state flow in general. Not saying that it's impossible with an imperative way, but the concept itself I think means a lot and makes a great change if used properly, even if it's completely abstract and has no connection whatsoever with what's going on in the program really. However, you'll likely will sacrifice performance, and if performance meant by "efficiency" I think that's true it's rather inefficient because computers are really Turing machines, and state and sequences means a lot. So I guess any functional language backend built with a lot of abstractions which give some performance penalty -- as with the majority of abstract structures. I don't have CS degree however, maybe I'm wrong but from my experience they were a bit slower usually. But if you need to take a control over something complex, lambdas are great too in practical programming. And sometimes it's just simpler to express something in lambda/functional way! At least any SE student should try to. At least for me, it changed mindset quite much. That's why it's so popular nowadays I think and should be deeply covered on SE programs instead of some "Best Practices" for another getter/setter in Java or C#.
@user-vf7pz2zn8t
@user-vf7pz2zn8t 7 жыл бұрын
Just to point that out: functions only take one argument. So what the "addition" function: λx. λy. x + y actually does is it takes x and then returns a function: λy. x + y where x is replaced with given input and y is expected as another input, but that's another function. And that's what is the coolest thing about the lambda-calculus: black boxes can take black boxes and return black boxes.
@xr_xharprazoraxtra5428
@xr_xharprazoraxtra5428 Жыл бұрын
so basically it is something like this ? f(z,y,z) = x+y+z would be λx.{λy.[λz. x+y+z]} or λz. { λy.[ (λx.x) + y ] + z }
@ExaltedHermit
@ExaltedHermit Жыл бұрын
@@xr_xharprazoraxtra5428 a typo: f(x, y, z) instead of f(z,y,z)
@xr_xharprazoraxtra5428
@xr_xharprazoraxtra5428 Жыл бұрын
@@ExaltedHermit oops XD
@GkTheodore
@GkTheodore Жыл бұрын
You mean in the context of lambda calculus only? Because logically, functions can take more than one argument.
@pavel3596
@pavel3596 Жыл бұрын
@@GkTheodore Nope, they can't. You only think so. f(x,y) is not really a function with two parameters. It is a tuple, hence only one parameter.
@duckymomo7935
@duckymomo7935 7 жыл бұрын
this guy's boxes and arrows are perfect, wtf
@obsoleteprofessor2034
@obsoleteprofessor2034 6 жыл бұрын
I think it was Michaelangelo who demonstrated he could draw a perfect circle.
@malandro2023
@malandro2023 5 жыл бұрын
Giotto, actually.
@monstercolorfunco4391
@monstercolorfunco4391 4 жыл бұрын
more laughs from him would be cool
@robbadlands9281
@robbadlands9281 4 жыл бұрын
yea, that's freaky. its incorrect that they are so correct. im mad about this.
@TheRealDasluft
@TheRealDasluft 4 жыл бұрын
I really thought I was the only one who had notice... felling better now :)
@jflopezfernandez
@jflopezfernandez 6 жыл бұрын
I was starting to read my copy of Programming in Haskell and I realized the author was from the University of Nottingham, so I looked his name up to see if he'd appeared in any videos and I was shocked to find out this is him! So cool to see that I already both knew and liked Professor Hutton before even starting his book!
@ghy30
@ghy30 4 жыл бұрын
Haha I was lucky to be his student learning Haskell in his course last year, his teaching was the best!
@goodester6924
@goodester6924 3 жыл бұрын
Thank you for sharing this. I'm currently reading his Haskell book as well and didn't realize it was him in this video.
@ltpetrenko
@ltpetrenko 3 жыл бұрын
is the book as verbose and confusing as the video? "Love" his choice of function names same as Boolean values. No operation precedence "helped" as well. Watched 5 times.
@jflopezfernandez
@jflopezfernandez 3 жыл бұрын
​@@ltpetrenko Remember that this introduction to functional programming is taking place in Untyped Lambda Calculus; the idea is that there is no such thing as a Boolean value until you encode it somehow, which is what he's showing here. In other words, the functions and the types aren't "sharing" a name, the functions themselves define the types, so they literally *are* the same thing, in the same way that your name and you are the same thing. The precedence in functional programming can definitely be pretty confusing at first, but it's actually really simple. Literally just start reading from left to right, taking however many arguments you need. It looks weird, but literally just apply the function: TRUE means pick the first of two things, whatever they are, so if you have TRUE FALSE TRUE, obviously the first thing is the function, and FALSE is the first of the two arguments, so that's the result of the function. Believe it or not, this idea gets even simpler. The fact that you can represent any computation by a sequence of partial function applications in which each component function takes only one argument is related to something called the Curry-Howard Isomorphism, and Haskell programmers use this pretty frequently in what's called point-free notation, if I remember correctly. The point is that the sheer simplicity of these ideas can actually be really counter-intuitive, so I definitely don't blame you for feeling frustrated. To be honest, I genuinely loved the book, but I paired it with a bunch of additional resources, like "Real World Haskell", "the Haskell Road to Logic, Maths and Programming", and Bartosz Milewski's awesome Haskell tutorials at School of Haskell. It can feel like every statement is either clearly obvious and useless or super abstract and useless at first, but if you can hang in there until it clicks, I think it's 100% worth it.
@ltpetrenko
@ltpetrenko 3 жыл бұрын
@@jflopezfernandez thank you for such a thorough reply.
@maartendj2724
@maartendj2724 4 жыл бұрын
As a computational biology / bioinformatics major I'm delighted to hear a 'pure' computer scientist mention the similarities between biology and computer science :)
@LSNG
@LSNG 2 жыл бұрын
nerd
@pyb.5672
@pyb.5672 Жыл бұрын
I've been obsessed with the correlation of recursive computation, evolutionary biology, DNA, and Godel's incompleteness theorem. Any ideas on this from your experience in bioinformatics?
@phillipanselmo8540
@phillipanselmo8540 Жыл бұрын
Object Oriented Programming is way more related to biology than functional programming
@pyb.5672
@pyb.5672 Жыл бұрын
@@phillipanselmo8540 You have no idea what you're talking about.
@Endredos
@Endredos Жыл бұрын
😂😂😂😂😂😂😂
@y__h
@y__h 7 жыл бұрын
Haskell Brooks Curry got his entire name as computer science terminologies. What an achievement.
@ZonkoKongo
@ZonkoKongo 6 жыл бұрын
I know first and last name, but what computer science terminology is "brooks"?
@ankushmenat
@ankushmenat 6 жыл бұрын
en.wikipedia.org/wiki/BrookGPU en.wikipedia.org/wiki/Haskell_(programming_language) en.wikipedia.org/wiki/Curry_(programming_language)
@martinsaip2504
@martinsaip2504 6 жыл бұрын
And don't forget currying! ;-)
@BluntForceTrauma666
@BluntForceTrauma666 6 жыл бұрын
That's one of the most bass-ackwards way of looking at things I think I've ever read. Don't you think that a MUCH better statement would be, "What an achievement, to have three computer science terms derived from your first, middle and last name"?
@felres
@felres 6 жыл бұрын
Thats not true though. BrookGPU is completely unrelated to Haskell Brooks Curry.
@von_nobody
@von_nobody 6 жыл бұрын
Probably one thing this video is lacking is emphasizing fact that as `x` you can pass not only numbers but another function too. This way `TRUE FALSE TRUE` look very strangle but have meaning. Using other syntax we could write this like that: `TRUE(FALSE, TRUE)` this look and work same as `f(5)` or `sin(Pi*2)` but instead returning number its return another function. As a approximation we could write `λ x. λ y. x + y` as `f(x,y) = x + y` and `λ b. FALSE TRUE` as `not(b) = b(FALSE, TRUE)`.
@orokushi5953
@orokushi5953 6 жыл бұрын
Thank you! I thought we take TRUE, then pass its output to FALSE, then pass its output to TRUE again, and have several undefined inputs! But now i get it. Thank you again. :)
@christophescholliers5141
@christophescholliers5141 5 жыл бұрын
Just wanted to say that you did great with making the translation to more modern syntax. However, TRUE(FALSE, TRUE) is not an entirely accurate translation. You should look at it as (TRUE(FALSE))(TRUE). The first application of TRUE(FALSE) returns a new function which you later apply to TRUE. If you are interested in these kind of things you should look up "currying".
@tlacmen
@tlacmen 5 жыл бұрын
@@christophescholliers5141 true was defined to take two inputs, was it not? how can it suddenly take just one function?
@tlacmen
@tlacmen 5 жыл бұрын
ah, never mind, some gentleman actually already answered that exact question elsewhere in the comments :D
@black_wink1649
@black_wink1649 4 жыл бұрын
Christophe Scholliers hahahahaha I just came from this Chanel’s video on currying after it told me to come here
@lawrencedoliveiro9104
@lawrencedoliveiro9104 6 жыл бұрын
<a href="#" class="seekto" data-time="217">3:37</a> Note that each λ represents a function definition: so “λx.λy.x + y” is not (directly) a function of two arguments: it is a function of one argument (x) returning a function of another single argument (y) which returns the sum!
@happyfakeboulder644
@happyfakeboulder644 4 жыл бұрын
But does it still work?
@AntonAdelson
@AntonAdelson 4 жыл бұрын
I didn't get that at all x.x
@spitalhelles3380
@spitalhelles3380 4 жыл бұрын
beautiful
@EinstienJr
@EinstienJr 4 жыл бұрын
Thanks for the info :)
@absurdengineering
@absurdengineering 4 жыл бұрын
mem reflect And here we see the trivial mapping from LISP’s s-expressions (and also RPN) to lambda calculus - and back :)
@DustinRodriguez1_0
@DustinRodriguez1_0 7 жыл бұрын
I imagine that if someone had never heard of the lambda calculus before and they watched this video, they would have a problem when they hit his claim that it can encode any computation. He says, correctly, that the lambda calculus includes functions and variables and a means of application... but he previously used an addition operator and the number '1'. Lambda calculus does not include either of those things. They have to be constructed. The ways they are constructed are pretty interesting, IMO.
@frankfahrenheit9537
@frankfahrenheit9537 6 жыл бұрын
Sounds like intellectual masturbation. Need a TRUE? Use 1. Construction finished.
@TofuBug24
@TofuBug24 4 жыл бұрын
​@@frankfahrenheit9537 That's fine if you are the one writing all the logic, what Lambda calculus allows you to do is pass around actual logic like you do with data. That's why languages like C# can have a Method called .ForEach(Action Lambda) where Action is a Lambda expression that doesn't return anything but its logical definition is provided by the programmer using the method OR in a more advanced idea since any logical idea can be represented in a lambda expression you can have a program that allows an end user to check boxes and select drop downs that collectively feed into generating logic that is converted into a lambda express and passed into the existing code base to then be executed like it was originally written into the program. pretty crazy and fun stuff to play with. To make all that work the programing framework needs to understand the FULL language of logical representation. Abstract Syntax Trees are how that happens Simple example NOT (A OR FALSE) translates to Unary Expression - Lambda Expression Takes 2 parameters The Operator [NOT], and a Value [The result of (A OR FALSE)] , it returns one value L_Operator Expression - Lambda Expression Actually does the NOT logic L_Group Expression [( )] - Lambda Expression Takes multiple parameters) returns one value L_Binary Expression [A OR B] - Lambda Expression takes 3 parameters, Left [A], Right [FALSE], Operator [OR] it returns one value L_ Value Expression [A] - Lambda Expression takes 1 parameter [Variable name], returns the in memory value of that variable L_ Constant Expression [B] - Lambda Expression holds a constant value in this case FALSE L_ Operator Expression [OR] - Lambda Expression defines how the Left and Right parameters are combined It can get pretty nuts looking into an abstract syntax tree for even the most basic algorithms but understanding that the ONLY thing the computer understands is Expressions all we do is teach it to tell the difference between common expressions by abstracting away the differences e.g. Binary Expression (can be ANYTHING that takes two inputs and gives one output, +, -, /, *, OR, AND, XOR, NOR, etc) pretty powerful stuff in a REALLY condensed code base if you actually look at the logic for how abstract syntax trees work (just a logic wood chipper that keeps breaking it down into its most basic parts and then executing or reconstructing them as needed)
@kaynex1039
@kaynex1039 3 жыл бұрын
@@frankfahrenheit9537 This is the difference between programming and computer science. Yeah, if you're making a game, just use 1. If you want to better understand the logical structures that can go into programming languages, then abstractions are necessary.
@reinux
@reinux 2 жыл бұрын
The point that's being missed is that it's a universal language the way NANDs are universal operators, By combining nothing but NAND gates or the three lambda constructs, you can compute anything.
@jgcooper
@jgcooper 7 жыл бұрын
requesting a video of him discussing Lambda Recursion
@y__h
@y__h 7 жыл бұрын
soon
@KorsarNek
@KorsarNek 7 жыл бұрын
spj and then he will just refer back to this video...
@Acuzzio
@Acuzzio 7 жыл бұрын
Yes, please
@dzhiurgis
@dzhiurgis 7 жыл бұрын
where he gives an example of him discussing Lambda Recursion
@JamesBradford1
@JamesBradford1 7 жыл бұрын
please, Yes
@1337GameDev
@1337GameDev 4 жыл бұрын
The Y Combinator. That takes me back to school. Our class was given the assignment to come up with "tying the knot" to allow recursion in lambda calculus. A few students got it (in different ways), and I was SO CLOSE to getting the Y combinator, but didn't get it to work. That class was so much fun.
@vedantnemane1148
@vedantnemane1148 3 жыл бұрын
Never delete this video. As a university comp sci student, this video is invaluable to me. The examples are on point, the explanation is succinct, history for background- I'm only halfway in, but I've understood SO MUCH. THANK YOU.
@anthonynguyen2027
@anthonynguyen2027 2 жыл бұрын
that last remark, the connection to biology is beautiful. i love finding parallels between programming and nature
@XDinky
@XDinky 4 жыл бұрын
This feels like listening to an alien explaining logic. It's so much different from the way I'm used to think about it, yet it makes perfect sense once translated
@TheRastaDan
@TheRastaDan 3 жыл бұрын
I'm really glad I took this optional class in my CS-Bachelor which was called "Alternative Programming Paradigms" where we explored both logical programming with Prolog and functional programming with a LISP dialect called Racket. Even understanding only the core concepts of this languages just opens up the mind so much and makes you think different about problems when comming back to Java or Python
@reinux
@reinux 2 жыл бұрын
I don't know why CS curriculums still treat it as alternative. You'd think both theoretically and practically, these things should be front and center.
@esobrev
@esobrev 5 ай бұрын
it’s a shame anyone would ever return to java
@adelinghanayem2369
@adelinghanayem2369 3 жыл бұрын
Wow, I wish I had a professor like him back when I was a student, so clear explanation !
@chriswilson1853
@chriswilson1853 4 жыл бұрын
I'm a computer programmer with 25 years' experience and I am totally baffled! I've never understood Haskell either. Perhaps I can't see the wood for the trees.
@jeffreywbaumann1210
@jeffreywbaumann1210 2 жыл бұрын
I think this all stems from the inverse relationship between comprehensibility and availability of grant money.
@wpherigo1
@wpherigo1 6 жыл бұрын
That was fascinating. I’ll have to watch it 5 more times and run thru the examples several times, but it is still very helpful in trying to understand what Lambdas in Java, etc., are trying to do.
@SkyyySi
@SkyyySi Жыл бұрын
For the record: In most imperative programming languages, a lambda just means a function that you can pass as if it were any other data type (like a string).
@jyrikgauldurson8169
@jyrikgauldurson8169 7 жыл бұрын
Not entirely correct; the basic untyped lambda calculus doesn't have numbers and operations like +. They have to be encoded using the three fundamental constructs, i.e., variables, lambda abstractions and applications.
@ganondorfchampin
@ganondorfchampin 5 жыл бұрын
The point was to explain what the lambda operator does in a method that isn't entirely abstract.
@4.0.4
@4.0.4 7 жыл бұрын
So this means you can simulate the sequential memory of a Turing machine using only functions and parameters?
@ChristopherKing288
@ChristopherKing288 7 жыл бұрын
aiklarung yep
@Kembread
@Kembread 7 жыл бұрын
My favourite Computerphile video in a while! Grand job, Professor Hutton!
@dieteralfred8636
@dieteralfred8636 3 жыл бұрын
From all speakers at Computerphile I can understand your explanations best.
@matthewgiallourakis7645
@matthewgiallourakis7645 7 жыл бұрын
Finally an episode on lambda calculus 😃
@hungrycoder3148
@hungrycoder3148 5 жыл бұрын
Just a little suggestion. When you say "Computerphile has videos on X", you can make that video's thumbnail appear at the right side of the screen, so that we can go directly to that video if we want. Thanks for great videos btw.
@gavintoohey6604
@gavintoohey6604 4 жыл бұрын
Thank you for this video. Learning about functional programming and the foundations of mathematics really does excite me. Love your stuff computerphile and Professor Graham Hutton's work seems really cool
@borislavhristov1064
@borislavhristov1064 7 жыл бұрын
That linking of biology with lambda calculus at the end was kind of mind-blowing..
@npexception
@npexception 7 жыл бұрын
I would love to see a video on the Y-combinator. It took me quite a while to grasp the concept when I first learned about it a while back, and it would be interesting to see it being explained in a (probably) easier to understand manner.
@herksen
@herksen Жыл бұрын
Same here. I really appreciate the video, but it is quite abstract. I didn’t have an ‘Aha Erlebnis’. Also, i cannot read the text on the paper sheets. Why not present it full screen. It’s nice to see your face, but it doesn’t help me understanding it better.
@TimJSwan
@TimJSwan 6 жыл бұрын
I like this guy. He explains it better and more concisely than I do.
@andresgongoraYT
@andresgongoraYT 4 жыл бұрын
I haven't finished this video yet, but I'm thrilled by how structured and clean your explanation is!
@anonymousone6250
@anonymousone6250 7 жыл бұрын
The true and false functions you described are like MUX gates, which are universal AND -> lambda x . lambda y . x y false OR -> lambda x . lambda y . x true y
@regmemer9198
@regmemer9198 6 жыл бұрын
Well, of course! What do you think CPU architecture ultimately boils down to? It's of no coincidence.
@andythedishwasher1117
@andythedishwasher1117 2 жыл бұрын
That bit at the end about biological systems running on something like lambda calculus was a mind exploder.
@adam7425
@adam7425 5 жыл бұрын
Super helpful! This explanation worked for me better than the last few. Thanks!
@darrusgoh
@darrusgoh Жыл бұрын
This video is so important! I've been trying to learn functional programming and trying to understand what's the whole point of it, and this one video pretty much explains it all!
@herrbonk3635
@herrbonk3635 Жыл бұрын
Does it? I didn't get anything out of it. I understand the point with having anonymous functions (which I implemented in my language's compiler), and I know they are called "lambdas" :) But that's it.
@MarcoAngelucci23
@MarcoAngelucci23 7 жыл бұрын
Also worth mentioning the Curry-Howard isomorphism, generalizes the idea that lambda calculus and the turing machine are equivalent.
@gamitrooox1856
@gamitrooox1856 4 жыл бұрын
Me: *Trying to concentrate on what he says* Guy in clip: *Winking every second he looks at the camera*
@timh.6872
@timh.6872 7 жыл бұрын
Kinda wished he would have mentioned something about how lisp is a rendering of lambda calculus, since the left hand term is expanded into a function and applied to the rest of the terms, parenthesis giving an ordering. I also hope they follow up with simply typed lambda calculus and the derivatives of it, eventually.
@alastairleith8612
@alastairleith8612 2 жыл бұрын
love the dot-matrix printer paper for notation. nice reference to an exciting period history of computing. I self-taught myself fortran when I was 10 by reading out fortran code print outs for Adventure game and Star Trek from the ND-6000 mainframe my dad did his research on in the lab. always had lots of old printouts to use for drawing on.
@cedricproper5256
@cedricproper5256 11 ай бұрын
There is no logical way I can dislike this video. THANK YOU. Subscribed.
@retf054ewte3
@retf054ewte3 6 ай бұрын
what I like about mathematicians and computer programmers, is that they are usually very humble. The more you know, the more humble you become.
@deepshuklaofficial
@deepshuklaofficial 5 жыл бұрын
Awesome Explanation sir Thank you so much sir for some unique knowledge which you gave me about Lambda Calculus
@samirm
@samirm 7 жыл бұрын
make a video on the Y comb. please
@SJohnTrombley
@SJohnTrombley 7 жыл бұрын
For a brief explanation: Y=λf.(λx.f (x x)) (λx.f (x x)) if we apply Y to some function g we get: Y g =(λf.(λx.f (x x)) (λx.f (x x))) g = (λx.g (x x)) (λx.g (x x)) (this process is called beta-reduction, btw) Applying the first λx to the second λx yields: g ((λx.g (x x)) (λx.g (x x))) now, the parentheses contain identically Y g (from the 4th line), so we have: Y g = g (Y g) The fact that that's recursive should be self-evident.
@samirm
@samirm 7 жыл бұрын
Thanks, but that doesn't help.
@SJohnTrombley
@SJohnTrombley 7 жыл бұрын
To elaborate a little, in the line beginning "Y g", I'm simply substituting g for f. In the line beginning "g ((", I'm substituting the second "(λx.g (x x))" for x in the first "(λx.g (x x))". After you do both of those things, you'll notice that the thing inside the parentheses after the g on that line is the same as the result of substituting g for f, hence Y g = g (Y g). This is recursive because you can keep substituting g (Y g) for Y g, getting g (g (g ...(Y g)...)). To be clear this is an infinite recursion, not a terminating one. Sorry if that didn't clarify anything.
@samirm
@samirm 7 жыл бұрын
That's much better, thank you!
@xybersurfer
@xybersurfer 7 жыл бұрын
great idea. i would love to see an explanation of that thing
@iroxudont
@iroxudont 7 жыл бұрын
Whats the deal with the camera pointed at the paper?
@expertmax32
@expertmax32 7 жыл бұрын
Unfortunately this channel is ruined by the bad camerawork.
@necropola
@necropola 7 жыл бұрын
... and bad choice of clothing for sitting in front of a camera.
@gabbergandalf667
@gabbergandalf667 7 жыл бұрын
golly you sure have a low bar for what constitutes "ruined"
@wierdalien1
@wierdalien1 7 жыл бұрын
gabbergandalf667 some people are never happy
@JrIcify
@JrIcify 7 жыл бұрын
Lol first it was the audio now it's one of the cameras.
@CaioPetrelliCominato
@CaioPetrelliCominato 7 жыл бұрын
From where I stand, I see that the functions will vary depending on the way you define true and false for example. Using the definition of true and false used in the video we can safely assume that: The OR expression can be written as: (λb.λb'.b b b') The AND expression can be written as: (λb.λb'.b b' b) At least using True and False as arguments that would work
@KingOfBlades27
@KingOfBlades27 4 жыл бұрын
I am pretty sure the major amount of people have the same problem that I am having with this one: I understand well for example what AND and OR mean in programming. Also when I see Lambda Calculus like on this video's paper I can easily read through it, evaluate it and confirm it works. But what I don't have is the logic on how am I supposed to figure out a lambda function for AND or OR. I have checked some of the examples others have wrote and after thinking about them for a while I can understand why they work. But still I have no clue how I am supposed to get these functions if I don't already know them.
@_aullik
@_aullik 7 жыл бұрын
The syntax for the NOT in <a href="#" class="seekto" data-time="502">8:22</a> was pretty confusing. Took me a while to figure out what you mean with how to apply your syntax correctly to higher functions. I hope i understood it or my answers for OR and AND wont make sense As i dont wanna lookup the lambda sign. im going to be using the l key OR: lb1. lb2. b1 TRUE b2 AND: lb1. lb2. b1 b2 FALSE OR2: lb1. lb2. NOT (AND (NOT b1) (NOT b2)) AND2: lb1. lb2. NOT (OR (NOT b1) (NOT b2))
@PeterAuto1
@PeterAuto1 7 жыл бұрын
Is correct. In Haskell this syntax is used. For lambda is \ normally used
@WaliSayed
@WaliSayed 9 ай бұрын
Well explained, thank you. For me as a student of MSc, this was enough to understand Lambda.
@TheThunderSpirit
@TheThunderSpirit 7 жыл бұрын
so can we encode the whole lambda calculus using lambda calculus like we do in a universal turing machine? can we also define any formal language using this lambda calculus?
@unev
@unev 7 жыл бұрын
Thanks for sharing your knowledge! But please consider the editing style, it's 10 times harder to grasp a new notation when you jump between the viewes of notation and presenter's head all the time. Take care
@msurai6054
@msurai6054 7 жыл бұрын
What is the advantage of using: (λx. x+1) 5 rather than something like: f(x)=x+1 f(5) ?
@remedan1
@remedan1 7 жыл бұрын
With your example there really isn't one. But lambda calculus is all about functions. It allows you to apply functions to other functions nicely. Look at the example with NOT in the video. You couldn't really do that (efficiently) with the conventional f(x) = y
@Wafflical
@Wafflical 7 жыл бұрын
not(b) = b(false, true)
@theodorberza9933
@theodorberza9933 7 жыл бұрын
The second is syntactic sugar for the first. ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/
@boptillyouflop
@boptillyouflop 7 жыл бұрын
f(x)=x+1 f(5) is classical Mathematics: x is a real number and you can apply algebra and you can have numbers like 1.2435278567... heck, you can even have numbers with infinite never-repeating digits that would take infinite amounts of information to describe and it still holds. (λx. x+1) 5 is lambda calculus, which is really a programming language and not a math system, you can't really do algebra on it and fundamentally it doesn't even really have numbers: +, 1 and 5 are actually functions in this example - ex: 5 is a function that takes its input and turns it into a function that's the same but applied 5 times. Lambda Calculus can't really have infinitely random numbers, with infinite digits and requiring infinite amount of information to express. Lambda Calculus ONLY has functions. Logically, your functions take a function as an input and return a function as a result (since there are no other manipulatable objects). The insight is that even just having functions that take a function and turns it into a new function is actually so powerful as a mechanism that you don't need anything else.
@davidwuhrer6704
@davidwuhrer6704 7 жыл бұрын
+boptillyouflop You can encode algebra in lambda calculus.
@NinaTheLudaca
@NinaTheLudaca 7 жыл бұрын
such a great explanation. please, more videos with Prof Hutton!
@johanandersson8464
@johanandersson8464 7 жыл бұрын
The Y-combinator is mind blowing. It gets me ever time. I learned about it through the excellent book The Little Schemer. It will expand your mind if you let it.
@maxmanium2032
@maxmanium2032 7 жыл бұрын
How fitting, I've just once more finished Half-Life.
@benverret7968
@benverret7968 3 жыл бұрын
I've been watching Half-Life videos recently and got "Lambda Calculus" recommended to me.
@bartvh07
@bartvh07 6 жыл бұрын
Interesting, but "why is it useful" is never addressed. Famous researchers, lambda calculus is compact so probably elegant, and an example of basic logic. But *why* is lambda calculus useful? What insights has it produced apart from being a simple & effective computing model? In my opinion this should go at the start of the video, before history and details!
@bernardonunes128
@bernardonunes128 4 жыл бұрын
4:42
@soundcore183
@soundcore183 4 жыл бұрын
It all translates to final state automata. which uses a regular language, which means you can express every line of code with that logic. Maybe useful if building minimal models which means your code running the best way possible?
@fnors2
@fnors2 4 жыл бұрын
@@soundcore183 Applied lambda calculus is basically functional programing. The main feature of which is that there are no side effects from using any function. You generally have to go out of your way in functional languages to get side effects (i.e. actual data being written/modified). This can become extremely useful in situations like multi-threading or server connections. It also offers a lot more consistency to the code, since the outputs don't depend on anything other than the actual inputs given to a function.
@agreencat3484
@agreencat3484 4 жыл бұрын
If I'm not mistaken, it also bridge mathematics and computers. In the beggining computer were made to do maths calculation. The mathematical notion behind calculation is functions, which is formalised in set theory. Those functions themselves formalise equation in physics I guess. The thing is that set theory doesn't mean anything in terms of digital electronic circuits. That is why Church wanted to formalise mathematical functions in a way that means anything for electronics. He came up with Lambda calculus. Then the Churh-Turing hypothesis say that lambda calculus and turing machine are equivalent, or something like that. Then the Turing machine concept, implemented with von Neumann architecture were used to make working general purpose computers.
@maheshprabhu
@maheshprabhu 3 жыл бұрын
@@soundcore183 lambda calculus is more powerful than regular expressions. Lambda calculus is equivalent to a turing machine and hence is more expressive.
@cameronramsay5063
@cameronramsay5063 6 жыл бұрын
I'm trying to use my bubsort lambda function but I keep getting an index out of range exception. Do u have any suggestions?
@leo386386
@leo386386 4 жыл бұрын
Awesome video. Congratulations you demystified all questions that I had.
@Ricocossa1
@Ricocossa1 7 жыл бұрын
Truly a beautiful isomorphism (lambda calculus/turing machine)
@carlostrebbau2516
@carlostrebbau2516 7 жыл бұрын
Check out Douglas Hofstadter's Goedel, Escher, Bach for a deeper exploration of the analogy made between recursion and DNA.
@alexanderdavidsonbryan7264
@alexanderdavidsonbryan7264 6 жыл бұрын
I have one question about the order of operations, is it defined so that the expression to the far left is evaluated as a function and then applied to the expression on the far right?
@kinxofsepluv
@kinxofsepluv 7 жыл бұрын
Looking forward to any covering of SKI Calculus if we are continuing down this FP line. Been hoping for these to be covered for a long time.
@marcthatcher
@marcthatcher 6 жыл бұрын
love these theoretical CS videos
@jezza10181
@jezza10181 6 жыл бұрын
How to turn very simple concepts into convoluted nightmares in one simple step lol
@kaynex1039
@kaynex1039 3 жыл бұрын
Designing programming languages is definitely not simple haha
@blakef.8566
@blakef.8566 4 жыл бұрын
<a href="#" class="seekto" data-time="310">5:10</a> how would you encode programs with side effects, programs with methods that return void, or programs that take no inputs? I don't have a very strong understanding of this yet, but I can't see how these types of things would be accounted for in the lambda calculus.
@artoheino7315
@artoheino7315 Жыл бұрын
I am working on Trical/Trigol/Trilogic with Troolean logic, I wonder if Lambda Calculus can be applied to a Ternary system?
@lawrencedoliveiro9104
@lawrencedoliveiro9104 6 жыл бұрын
<a href="#" class="seekto" data-time="167">2:47</a> The important point is that the same inputs always produce the same outputs.
@probablyapproximatelyok8146
@probablyapproximatelyok8146 5 жыл бұрын
Just as a reminder: true chooses the 1st input. false chooses the 2nd. AND: λb1. λb2. b1(b2, False) OR: λb1. λb2. b1(True, b2) XOR: λb1. λb2. b1(b2(False, True), b2)
@KidNamedKewlHam
@KidNamedKewlHam 4 жыл бұрын
yet there's no 3
@b1n
@b1n 5 жыл бұрын
I think that why a lot of people get confused is because you pass a 'true' or 'false' *function* into the not function and the passed in function is applied to a true and a false *value* .
@andrewthompson9714
@andrewthompson9714 10 ай бұрын
I had to watch it like 3 times and follow along in Haskell before I got it lol.
@tacticaltaco7481
@tacticaltaco7481 4 жыл бұрын
The jumping from <a href="#" class="seekto" data-time="500">8:20</a> to <a href="#" class="seekto" data-time="530">8:50</a> was very confusing. I don't even get to see the previous step while he's writing out the current step... I have no idea which definition got expanded using what part of what other definition...
@kyleburge923
@kyleburge923 7 жыл бұрын
This channel should discuss Lisp someday!
@ntwede
@ntwede 4 жыл бұрын
Whatth lithp?
@kingjamie2
@kingjamie2 7 жыл бұрын
why is it that "recursion" or "not" has to be encoded but mathematical operators like plus + do not have to be encoded?
@sirknight4981
@sirknight4981 5 жыл бұрын
Pretty sure they actually do have to and that it was just an example. One for example has to be encoded.
@markenangel1813
@markenangel1813 5 жыл бұрын
They do have to be encoded, but since this was an example, it had to be simple, and was therefore dumbed down to a level that needed no prior knowledge to understand. The number 1 needs to be encoded, as well, BTW.
@dmitripogosian5084
@dmitripogosian5084 11 ай бұрын
They do, and by missing explaining that, the lecturer threw the baby out with the water
@JonathanMcCormick32
@JonathanMcCormick32 4 жыл бұрын
Great video! Please PLEASE show the paper he's writing on though...
@pjnoonan1423
@pjnoonan1423 3 жыл бұрын
Does Lambda calculus use parenthesis, or does it use another method? For example, if I wanted to first multiply x and y, but then divide them by z, would it be written: Lambda x. Lambda y. Lambda z. (x*y)/c Please excuse the poor notation, I don't know how to print the Lambda character on my mobile keyboard.
@Ludix147
@Ludix147 7 жыл бұрын
Why the hell do the current releases match my lecture on Computer Science so closely? We just learned about the lambda calculus yesterday!
@AndreasToth
@AndreasToth 5 жыл бұрын
There's probably a lambda expression to explain it known as recursive releases.
@zacharytack6932
@zacharytack6932 5 жыл бұрын
Is this similar to Ligma calculus? I’ve heard of it but I’m not too sure how it works.
@MadocComadrin
@MadocComadrin 4 жыл бұрын
The ligma calculus is closer to the updog calculus.
@eldaneuron4183
@eldaneuron4183 4 жыл бұрын
What’s updog calculus
@pianochannel100
@pianochannel100 4 жыл бұрын
@@eldaneuron4183 You'd need to know the sugon identity to understand that.
@Economically.
@Economically. 3 жыл бұрын
What's Ligma?
@MrPoutsesMple
@MrPoutsesMple 7 жыл бұрын
Very cool video, as always. I've looked and it seems that you haven't done a video yet on Logic programming and Prolog. It'd be great if you could interview R. Kowalski, or someone else very close to the subject (e.g. E. Shapiro, I. Bratko, R. O' Keefe, A. Nerode).
@yaelmartincalzada1357
@yaelmartincalzada1357 3 жыл бұрын
I love you haha, you saved me from a task in the faculty, I hope my teachers will explain how you
@jollyjack5856
@jollyjack5856 7 жыл бұрын
please show less of the person's face and more of the paper with actual code written on it. it is easier to follow the stuff if it is seen on screen for longer.
@MrMentholSlim
@MrMentholSlim 4 жыл бұрын
pause buttons are real.
@zelioz848
@zelioz848 4 жыл бұрын
Did you know, pause buttons are a thing?
@w1d3r75
@w1d3r75 4 жыл бұрын
XD
@AaronHamm
@AaronHamm 4 жыл бұрын
Buncha smart asses think you want to just stare at the equation in silence and ponder it for a bit rather than hear the related dialog concurrently, apparently...
@unclesam997
@unclesam997 4 жыл бұрын
Just to clarify, there wasn't any code in this video
@-XArchLinuxEnjoyerX-
@-XArchLinuxEnjoyerX- 6 жыл бұрын
why do almost all guests to this channel use that specific type of paper...? weird question
@d-rex7043
@d-rex7043 3 жыл бұрын
Back in the days, that's what a printer printed on
@-XArchLinuxEnjoyerX-
@-XArchLinuxEnjoyerX- 3 жыл бұрын
@@d-rex7043 i actually like it, weirdly
@peterzsurka2703
@peterzsurka2703 7 жыл бұрын
That was really interesting, I'd be very interested in seeing a video on the y-combinator.
@daryoushmehrtash7601
@daryoushmehrtash7601 7 жыл бұрын
Thanks to this the light bulb went on for me in understanding the significance of the notion of "encoding the computation".
@milankovacs4259
@milankovacs4259 2 жыл бұрын
My Professor told me "if you understand Lambda calculus, you will understand everything" I am afraid I will not understand anything
@juancuadra3697
@juancuadra3697 7 жыл бұрын
I went into sleep mode.
@vendicarkahn4860
@vendicarkahn4860 4 жыл бұрын
You didn't miss anything but nonsense.
@ronramsay8587
@ronramsay8587 3 жыл бұрын
@<a href="#" class="seekto" data-time="693">11:33</a> No, the DNA helices of a strand are not "two copies of the same thing". They are the complements of each other, therefore from one you can deduce the other, but they are not the same thing.
@thesmileynoob
@thesmileynoob 6 жыл бұрын
Great explanation. I have a question though. Didn't you also include the "+" operator in the function? How do you then represent something as fundamental as addition using lambdas? Do you literally define ALL possible numbers as lambdas?
@proloycodes
@proloycodes 2 жыл бұрын
yes
@nicholas1460
@nicholas1460 7 жыл бұрын
Well, now I guess I know where the ycombinator website got it's name. Sometime I'm going to have to listen to this video while λb.b FALSE TRUE multitasking.
@frankfahrenheit9537
@frankfahrenheit9537 6 жыл бұрын
You better forget this video ASAP
@ferna2294
@ferna2294 7 жыл бұрын
The logical part of the video almost kills me. I think I need a doctor.
@DragonofStorm
@DragonofStorm 5 жыл бұрын
Why is lambda stateless and turing maschine is not? The invocation process of a lambda term (which result returned by which sub lambda function) are also "states" in the process of evaulating a lambda term like there are states in the turing maschine which store the interim status of the transit function of the turing maschine?
@sumdumbmick
@sumdumbmick 7 жыл бұрын
I find it more interesting that Heidegger's Dasein captures the same thing at very nearly the same time (several years earlier, really), since he wasn't involved with either Church or Turing, and he wasn't interested in its mathematical properties at all. So while you find it wondrous that there are these two approaches, between Turing and Church, you're missing out on noticing that it can be approached in more, quite different still, ways.
@mariank.2210
@mariank.2210 7 жыл бұрын
this is very interesting, I wish more of these 'lambda calculus' or 'lambda expressions' videos... though I don't quite get the explanation of NOT function... is there any link to some further sources?
@Ganonink
@Ganonink 7 жыл бұрын
1. Put the quality to 144p 2. Look at the guy's shirt 3. ???? 4. Profit
@sSunbeamM
@sSunbeamM 7 жыл бұрын
Benefit
@zokalyx
@zokalyx 6 жыл бұрын
5. Receive likes
@Xgil2Play
@Xgil2Play 6 жыл бұрын
It becomes polka dots
@DragonofStorm
@DragonofStorm 5 жыл бұрын
But a turing maschine can also be interpreted as a blackbox? Or does he mean that you can see the "insides" if you want (e.g. see the state transform function)? But with a lambda function, you can also see how it works with other lamba functions? I don't understand why he stresses the blackbox on lambda vs not on turing machine. Why?
@Temo990
@Temo990 5 ай бұрын
Those 'pure functions' do not really exist (like the turing machine with infinite memory), right? If you break down a function call to assembly it always does store some state (at least the return address possibly the saved registers, parameters and return value).
@shahinmodaresenshayi3576
@shahinmodaresenshayi3576 5 жыл бұрын
In my opinion (as a C programmer) Turing's understanding of computation and the way he modeled the notion using his machine is far superior to this approach. This approach is really counter intuitive, at least for me...
@adamleblanc5294
@adamleblanc5294 4 жыл бұрын
The lambda calculus has a big advantage for modern computing. It can more easily take advantage of multicore machines as it does not rely on state, and proper implementations of it in languages like haskell make it very easy to work with. Worth at least learning Haskell and building a few things with IMO.
@sebbes333
@sebbes333 7 жыл бұрын
<a href="#" class="seekto" data-time="92">1:32</a> Claim: "The function has no internal state" Question: How can the function know that it is producing exactly: (µx . x+1)? (µ
@ZipplyZane
@ZipplyZane 7 жыл бұрын
My understanding is that state is something that is mutable. The 1 is a constant, and thus is allowed, merely being a part of the definition. Just like the +.
@slevvio
@slevvio 7 жыл бұрын
it means no information can be stored or altered in the function, so you get the same value for every input
@npexception
@npexception 7 жыл бұрын
State is something that can change and is not inherently constant. The function would be having state if the value that is added to the input would increase with each call of the function, for example. So as long as the only things that the function consists of are unchanging constant values and the input arguments, it does not have state. I hope that makes sense somehow.
@alalize
@alalize 7 жыл бұрын
Think of a function as a huge look up table of values. For example, for the function x mapsto x + 1, you regard it as the table "1 -> 2 ; 2 -> 3; 3 -> 4; ..." etc. Of course, this is impossible to do in real life, but who cares about that ? Conceptually, it's true, and that's what's interesting here. You can see from this view how the function doesn't have a state : it's not "thinking", it's just looking at the input and returning the right value, and there's no state in that.
@WilliamAndrea
@WilliamAndrea 7 жыл бұрын
Here, take this: λ
@WilliamBombardellidaSilva
@WilliamBombardellidaSilva 3 жыл бұрын
Computerphile, would you make a video on partial recursive/ mu-recursive functions? I would love that
@WilliamBombardellidaSilva
@WilliamBombardellidaSilva 3 жыл бұрын
By the way, your videos are awesome
@stIncMale
@stIncMale 7 жыл бұрын
This video is very interesting! I'm looking to watching the next part
@frknklcsln
@frknklcsln 7 жыл бұрын
Double helix is not made of two copies of the same thing.They are complementary not identical.
@davidwuhrer6704
@davidwuhrer6704 7 жыл бұрын
More interesting is the question whether DNA is recursive.
@frknklcsln
@frknklcsln 7 жыл бұрын
David Wührer Recursive on terms of what ?
@davidwuhrer6704
@davidwuhrer6704 7 жыл бұрын
Furkan Kılıçaslan​​​ From the Devil's Data Processing Dictionary: recursion: n. _see: recursion_ Another way to put it is to ask if it can do loops. Again from the Devil's DP Dictionary: endless loop: _see: loop, endless_ loop, endless: _see: endless loop_
@frknklcsln
@frknklcsln 7 жыл бұрын
David Wührer I know what recursive is and there are some repeating sequences in DNA but i am not sure if DNA can be called recursive
@davidwuhrer6704
@davidwuhrer6704 7 жыл бұрын
Furkan Kılıçaslan Neither am I, which is why I think it is an interesting question. We know it is code, and it involves programs for proteins as well as code about how to process them, and even about turning parts of the code on and off, as well as error correction and redundancy. But do the processors process the programs purely sequentially, or can the code refer them to other parts of the code? More topically: Does DNA encode instructions on how to decode instructions in the DNA or derived from instructions in the DNA? In some sense it has to, because it replicates itself by following the instructions it replicates via processors built from these instructions. But is the encoding itself recursive? Does it maybe have an equivalent of the Y-combinator? Or is the self-replication the only recursive aspect of it (which is more a phenotypical property, depending on how you look at it). The double helix structure is more about the re-assembly of the code after use, as far as I understand, and the similarity of it to function definitions more or less co-incidental. How deeply the code can be mapped to purely mathematical concepts however, or if it can at all, is the interesting question hinted at here.
@Slackwise
@Slackwise 7 жыл бұрын
I would love to see a video on Lambda Calculus and its philosophical relationship to Biology, and really, anything else. Oh, and thanks for the great video!
@user-in4xz9dk4g
@user-in4xz9dk4g 2 жыл бұрын
Can someone explain this syntax... I'm having a hard time understanding the "flow" what's going where
@SevenDeMagnus
@SevenDeMagnus 3 жыл бұрын
Thanks sir Newstn for calculus. Lambda Calculus was tested to compete with binary for computation.
Essentials: Functional Programming's Y Combinator - Computerphile
13:26
What is a Monad? - Computerphile
21:50
Computerphile
Рет қаралды 583 М.
Sigma Girl Past #sigmagirl #funny #viral
00:22
CRAZY GREAPA
Рет қаралды 15 МЛН
Cracking Enigma in 2021 - Computerphile
21:20
Computerphile
Рет қаралды 2,3 МЛН
Von Neumann Architecture - Computerphile
16:20
Computerphile
Рет қаралды 621 М.
Bug in Binary Search - Computerphile
11:31
Computerphile
Рет қаралды 277 М.
Lambda Calculus!
9:51
Truttle1
Рет қаралды 45 М.
Functional Parsing - Computerphile
22:46
Computerphile
Рет қаралды 131 М.
Programming Loops vs Recursion - Computerphile
12:32
Computerphile
Рет қаралды 1,4 МЛН
The Man Who Revolutionized Computer Science With Math
7:50
Quanta Magazine
Рет қаралды 2,7 МЛН
Lambda (λ) Calculus Primer
34:26
LigerLearn
Рет қаралды 5 М.
Floating Point Numbers - Computerphile
9:16
Computerphile
Рет қаралды 2,3 МЛН