Lambda Calculus - Computerphile

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/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@illustriouschin]

"The answer is actually really easy." *Introduces an entire galaxy of new concepts in the answer.

Like me teaching.

[@ntwede]

And somehow made it include biology and history

[@vendicarkahn4860]

No new concepts were introduced.

[@ionichi]

@@vendicarkahn4860 There is nothing new under the Sun.

[@noaht2]

The answer is actually surprisingly simple. - Ceave Gaming

[@ВениаминФеафанов]

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]

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]

@@xr_xharprazoraxtra5428 a typo: f(x, y, z) instead of f(z,y,z)

[@xr_xharprazoraxtra5428]

@@ExaltedHermit oops XD

[@GkTheodore]

You mean in the context of lambda calculus only? Because logically, functions can take more than one argument.

[@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.

[@jflopezfernandez]

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]

Haha I was lucky to be his student learning Haskell in his course last year, his teaching was the best!

[@goodester6924]

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]

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]

​@@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]

@@jflopezfernandez thank you for such a thorough reply.

[@duckymomo7935]

this guy's boxes and arrows are perfect, wtf

[@obsoleteprofessor2034]

I think it was Michaelangelo who demonstrated he could draw a perfect circle.

[@malandro2023]

Giotto, actually.

[@monstercolorfunco4391]

more laughs from him would be cool

[@robbadlands9281]

yea, that's freaky. its incorrect that they are so correct. im mad about this.

[@TheRealDasluft]

I really thought I was the only one who had notice... felling better now :)

[@NoorquackerInd]

"Every computer scientist should know about this" People that only studied object-oriented programming: _shakes in fear_

[@54akhilesh]

hahahahaha

[@nam3go3sh3r3]

who cares functional programming is useless to know anyway

[@AllUpOns]

He said computer scientist, not programmer.

[@mrpedrobraga]

@@AllUpOns 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]

@@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#.

[@maartendj2724]

As a computational biology / bioinformatics major I'm delighted to hear a 'pure' computer scientist mention the similarities between biology and computer science :)

[@LSNG]

nerd

[@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]

Object Oriented Programming is way more related to biology than functional programming

[@pyb.5672]

@@phillipanselmo8540 You have no idea what you're talking about.

[@dendredi]

😂😂😂😂😂😂😂

[@von_nobody]

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]

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]

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]

@@christophescholliers5141 true was defined to take two inputs, was it not? how can it suddenly take just one function?

[@tlacmen]

ah, never mind, some gentleman actually already answered that exact question elsewhere in the comments :D

[@black_wink1649]

Christophe Scholliers hahahahaha I just came from this Chanel’s video on currying after it told me to come here

[@y__h]

Haskell Brooks Curry got his entire name as computer science terminologies. What an achievement.

[@ZonkoKongo]

I know first and last name, but what computer science terminology is "brooks"?

[@martinsaip2504]

And don't forget currying! ;-)

[@BluntForceTrauma666]

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"?

[@fernfaba]

Thats not true though. BrookGPU is completely unrelated to Haskell Brooks Curry.

[@brioche8378]

Y H I

[@lawrencedoliveiro9104]

3:37 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]

But does it still work?

[@AntonAdelson]

I didn't get that at all x.x

[@spitalhelles3380]

beautiful

[@EinstienJr]

Thanks for the info :)

[@absurdengineering]

mem reflect And here we see the trivial mapping from LISP’s s-expressions (and also RPN) to lambda calculus - and back :)

[@vedantnemane1148]

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.

[@DustinRodriguez1_0]

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]

Sounds like intellectual masturbation. Need a TRUE? Use 1. Construction finished.

[@TofuBug24]

​@@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]

@@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]

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]

requesting a video of him discussing Lambda Recursion

[@y__h]

soon

[@KorsarNek]

spj and then he will just refer back to this video...

[@Acuzzio]

Yes, please

[@dzhiurgis]

where he gives an example of him discussing Lambda Recursion

[@JamesBradford1]

please, Yes

[@jollyjack5856]

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]

pause buttons are real.

[@zelioz848]

Did you know, pause buttons are a thing?

[@w1d3r75]

XD

[@AaronHamm]

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]

Just to clarify, there wasn't any code in this video

[@andythedishwasher1117]

That bit at the end about biological systems running on something like lambda calculus was a mind exploder.

[@XDinky]

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

[@Triantalex]

false.

[@wpherigo1]

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]

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).

[@chriswilson1853]

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]

I think this all stems from the inverse relationship between comprehensibility and availability of grant money.

[@TheRastaDan]

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]

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]

it’s a shame anyone would ever return to java

[@MarcoAngelucci23]

Also worth mentioning the Curry-Howard isomorphism, generalizes the idea that lambda calculus and the turing machine are equivalent.

[@iroxudont]

Whats the deal with the camera pointed at the paper?

[@expertmax32]

Unfortunately this channel is ruined by the bad camerawork.

[@necropola]

... and bad choice of clothing for sitting in front of a camera.

[@gabbergandalf667]

golly you sure have a low bar for what constitutes "ruined"

[@wierdalien1]

gabbergandalf667 some people are never happy

[@JrIcify]

Lol first it was the audio now it's one of the cameras.

[@jucom756]

Bro i only learned object oriented programming for my maths degree but this is so much more up my alley. This is what my functional analysis mind craves

[@PeriodicLaw]

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

[@tacticaltaco7481]

The jumping from 8:20 to 8:50 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...

[@adelinghanayem2369]

Wow, I wish I had a professor like him back when I was a student, so clear explanation !

[@borislavhristov1064]

That linking of biology with lambda calculus at the end was kind of mind-blowing..

[@bartvh07]

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]

4:42

[@soundcore183]

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]

@@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]

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]

@@soundcore183 lambda calculus is more powerful than regular expressions. Lambda calculus is equivalent to a turing machine and hence is more expressive.

[@jyrikgauldurson8169]

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]

The point was to explain what the lambda operator does in a method that isn't entirely abstract.

[@gamitrooox1856]

Me: *Trying to concentrate on what he says* Guy in clip: *Winking every second he looks at the camera*

[@KingOfBlades27]

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.

[@retf054ewte3]

what I like about mathematicians and computer programmers, is that they are usually very humble. The more you know, the more humble you become.

[@msurai6054]

What is the advantage of using: (λx. x+1) 5 rather than something like: f(x)=x+1 f(5) ?

[@remedan1]

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]

not(b) = b(false, true)

[@theodorberza9933]

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]

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]

+boptillyouflop You can encode algebra in lambda calculus.

[@timh.6872]

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.

[@anonymousone6250]

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]

Well, of course! What do you think CPU architecture ultimately boils down to? It's of no coincidence.

[@sandipdas7206]

I really enjoyed this video, this instructor should appear on more Computerphile videos of related subject matter

[@samirm]

make a video on the Y comb. please

[@SJohnTrombley]

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]

Thanks, but that doesn't help.

[@SJohnTrombley]

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]

That's much better, thank you!

[@xybersurfer]

great idea. i would love to see an explanation of that thing

[@TimJSwan]

I like this guy. He explains it better and more concisely than I do.

[@unev]

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

[@cedricproper5256]

There is no logical way I can dislike this video. THANK YOU. Subscribed.

[@jezza10181]

How to turn very simple concepts into convoluted nightmares in one simple step lol

[@kaynex1039]

Designing programming languages is definitely not simple haha

[@dieteralfred8636]

From all speakers at Computerphile I can understand your explanations best.

[@4.0.4]

So this means you can simulate the sequential memory of a Turing machine using only functions and parameters?

[@ChristopherKing288]

aiklarung yep

[@Kembread]

My favourite Computerphile video in a while! Grand job, Professor Hutton!

[@probablyapproximatelyok8146]

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]

yet there's no 3

[@lastchildonearth]

First Lambda Calculus explanation I understood! I love that I didn't have to stare at a piece of paper the whole time. The history squeezed in is also a bonus

[@_aullik]

The syntax for the NOT in 8:22 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]

Is correct. In Haskell this syntax is used. For lambda is \ normally used

[@Triantalex]

false.

[@b1n]

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]

I had to watch it like 3 times and follow along in Haskell before I got it lol.

[@lawrencedoliveiro9104]

2:47 The important point is that the same inputs always produce the same outputs.

[@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]

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.

[@Ludix147]

Why the hell do the current releases match my lecture on Computer Science so closely? We just learned about the lambda calculus yesterday!

[@AndreasToth]

There's probably a lambda expression to explain it known as recursive releases.

[@andresgongoraYT]

I haven't finished this video yet, but I'm thrilled by how structured and clean your explanation is!

[@hungrycoder3148]

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]

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

[@kingjamie2]

why is it that "recursion" or "not" has to be encoded but mathematical operators like plus + do not have to be encoded?

[@sirknight4981]

Pretty sure they actually do have to and that it was just an example. One for example has to be encoded.

[@markenangel1813]

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]

They do, and by missing explaining that, the lecturer threw the baby out with the water

[@ronramsay8587]

@11:33 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.

[@sebbes333]

1:32 Claim: "The function has no internal state" Question: How can the function know that it is producing exactly: (µx . x+1)? (µ

[@ZipplyZane]

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]

it means no information can be stored or altered in the function, so you get the same value for every input

[@npexception]

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.

[@WilliamAndrea]

Here, take this: λ

[@angeldude101]

+ZipplyZane Given that true and false were defined as functions instead of constants, can't someone redefine '1'? Granted this has been seen in other languages where someone defines a value with the identifier being a keyword.

[@zerobit778]

Both the examples could be represented by normal function. f(x) = x + 1, f(x, y) = x + y. So why do we need this Lambda thing, if we already have a working tool? Any help would be appreciated.

[@cktken3336]

Because using nothing but pure functions and no provided assumptions, we can do ALL POSSIBLE COMPUTATIONS. Lambda calculus doesn’t come with numbers or even booleans, yet it is exactly as capable of a Turing machine. The functions you described can be written with nothing but λ, letters, and parentheses. No plus signs, no numbers. Now the reason we care about this so much in computer science is that since lambda calculus is turing complete, it also means that we can write code that only uses pure functions that have no dependencies on the current state of the computer and do ANYTHING that we could do when we coded in a way that functions depend on information outside of the function. This lets us make easy guarantees when coding, and lets us code safely. “This function can’t accidentally access sensitive info because it can’t affect the outside world.” “This function will never crash as long as its input is an integer.” “This function will always behave the same no matter what the program has been doing” for example.

[@dmitripogosian5084]

@@cktken3336 What 'pure' has to do with lambda being special ? Summation function '+' is pure, as well as all other mathematical functions, computationally even FORTRAN allows function to be declared pure (and check that it is). No numbers - that is an interesting point, but this was not in the video at all. Basically video managed to avoid saying what actually lambda calculus is.

[@carlostrebbau2516]

Check out Douglas Hofstadter's Goedel, Escher, Bach for a deeper exploration of the analogy made between recursion and DNA.

[@JonathanMcCormick32]

Great video! Please PLEASE show the paper he's writing on though...

[@npexception]

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]

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.

[@andrewlankford9634]

No matter how many times I read about lambda calculus, I can't help but wonder what makes lambda expressions any different from functions in any damn computer language, like C or BASIC, or just first year calculus. And what's so wonderful about the notation?

[@matthewgiallourakis7645]

Finally an episode on lambda calculus 😃

[@thesmileynoob]

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?

[@mojacodes]

yes

[@maxmanium2032]

How fitting, I've just once more finished Half-Life.

[@benverret7968]

I've been watching Half-Life videos recently and got "Lambda Calculus" recommended to me.

[@tomharris8712]

4:21: ...And this is basically all there is to the Lambda Calculus. It's only got three things: it's got variables, like x, y and z; and it's got a way of building functions - this lamda notation; and it's got a way of applying functions. This is the only three things that you have in the setting. 6:42 ....It doesn't have any built-in data types like numbers, logical values recursion and things like that.... This contradicts what was shown earlier, when the expressions "x + 1" and "x + y" was used to build functions. If you can use the symbol + (which is not mentioned above), then at least the integers must exist as a built-in type, or else it doesn't make sense to me.

[@deepshuklaofficial]

Awesome Explanation sir Thank you so much sir for some unique knowledge which you gave me about Lambda Calculus

[@xsli2876]

My understand of lamda calculus is that it does not have states: it does not retrieve the state value(variable) in the beginning, after ...., then put back the updated value in the state(variable). These fetch, store procedures are moving bits back and forth between memory and CPU, making computer bus very busy, making the computation less efficient. Now, with lamda calculus, no states involved, no state value updating(no side effects) --- no traffic on the computer bus, making the computation more efficient. This is what I understand. Correct me if I am wrong. Thank you.

[@xsli2876]

von Neumann architecture states: computer has a memory unit, a control unit, an ALU unit. All these units communicate through computer bus. General computer programming languages are based on this spirit, and can be called von Neumann programming languages. In contrast, the functional programming languages can be called non-von Neumann programming languages. Again, this is my understanding. Correct me if I am wrong. Thank you.

[@anthonynguyen2027]

that last remark, the connection to biology is beautiful. i love finding parallels between programming and nature

[@alastairleith8612]

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.

[@robertkelleher1850]

9:47... Skip a few steps did you? I'm totally lost. "You can see what's gonna happen now" ... qed. Huh? I had to rewatch that 15 seconds of video about 3 times before I figured it out. There is no explanation of the extended syntax i.e. How functions are applied exactly. Where the inputs are when the are applied and how to chain things together. What does parentheses mean???

[@roxferesr]

Yeah, I have yet to find someone that explain this and makes sense... Like, why did he decide to expand the first TRUE, and has the remaining TRUE AND FALSE as parameters.. why don't you expand all of them

[@pedrov8868]

@@roxferesr because it's all about expanding everything to do with the NOT in the simplest terms

[@Temo990]

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).

[@Singularity7425]

Super helpful! This explanation worked for me better than the last few. Thanks!

[@sumdumbmick]

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.

[@shahinmodaresenshayi3576]

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]

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.

[@WilliamBombardellidaSilva]

Computerphile, would you make a video on partial recursive/ mu-recursive functions? I would love that

[@WilliamBombardellidaSilva]

By the way, your videos are awesome

[@zacharytack6932]

Is this similar to Ligma calculus? I’ve heard of it but I’m not too sure how it works.

[@MadocComadrin]

The ligma calculus is closer to the updog calculus.

[@eldaneuron4183]

What’s updog calculus

[@pianochannel100]

@@eldaneuron4183 You'd need to know the sugon identity to understand that.

[@Economically.]

What's Ligma?

[@41570]

What's the purpose of the "TRUE" after the "FALSE" in the NOT function?

[@Ricocossa1]

Truly a beautiful isomorphism (lambda calculus/turing machine)

[@williamtfinnegan1359]

Actually, the DNA helix is composed of complimentary strands, not identical strands. Further, the DNA does not recurse, but is a linear calculation as it builds the resultant proteins piece by piece.

[@marcthatcher]

love these theoretical CS videos

[@WaliSayed]

Well explained, thank you. For me as a student of MSc, this was enough to understand Lambda.

[@-XArchLinuxEnjoyerX-]

why do almost all guests to this channel use that specific type of paper...? weird question

[@d-rex7043]

Back in the days, that's what a printer printed on

[@-XArchLinuxEnjoyerX-]

@@d-rex7043 i actually like it, weirdly

[@TheThunderSpirit]

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?

[@kyleburge923]

This channel should discuss Lisp someday!

[@ntwede]

Whatth lithp?

[@Triantalex]

false.

[@modolief]

7:57 -- prof Hutton poses quiz question 1: How do you write the NOT function using the lambda calculus

[@seayellow5834]

I am just confused but maybe later I'll understand

[@TJ-hs1qm]

So what was their motivation to cook up this entire new notation? Is good old f(x)=... missing any properties?

[@ArvinTR-tx1ew]

That's Formalism for you.

[@biledemon85]

To the person who edited & shot this video: spend more time with the screen on the maths, this is pretty abstract stuff and the viewer needs time to process what he's being told about the funny squiggles on the page. Second, the shot of the page was of poor quality... it really didn't help.

[@gnagyusa]

Pause button. ;)

[@RichardBronosky]

Also, spacebar, arrow left, and < are your friends.

[@無神論無政府無金錢]

agreed

[@supremepancakes4388]

i wonder which potato this was shot with

[@akshaymathur2225]

Please make a playlist of lambda calculus videos.

[@mariank.2210]

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?

[@bsummer]

How i got here >> Cloud Engineering (lamda Function in AWS) >> Programming language >>Python >> had to learn Function programming to understanding a few concepts >> Then curiosity brought me here. Every Computer Scientist should Know this.

[@christopherellis2663]

I am none the wiser. it seems to be a translation of modes of notation, without any substantial elements to grasp

[@bigbox8992]

Interesting

[@yardgrid]

I know this thing had gone right over my head but it looks more to me like an observation than an actual tool that can be used to create anything.

[@morpheus6749]

You've got it right. It is entirely useless in creating anything useful.

[@milankovacs4259]

My Professor told me "if you understand Lambda calculus, you will understand everything" I am afraid I will not understand anything

[@daryoushmehrtash7601]

Thanks to this the light bulb went on for me in understanding the significance of the notion of "encoding the computation".

[@DragonofStorm]

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?

[@frknklcsln]

Double helix is not made of two copies of the same thing.They are complementary not identical.

[@davidwuhrer6704]

More interesting is the question whether DNA is recursive.

[@frknklcsln]

David Wührer Recursive on terms of what ?

[@davidwuhrer6704]

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]

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]

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.

[@OjasMaheshwari-sn3sw]

Note:- Its important to mention the meaning of SPACE in lambda calculus syntax, a space means that the second value is being applied to the first value. So NOT TRUE means that TRUE is being fed as an input to the NOT function. Similarly, it means that in TRUE FALSE TRUE, First FALSE is being applied to TRUE and then TRUE is being applied to the output of the formal function.

[@PaulaJBean]

In Python: >>> (lambda x: x + 1)(8) 9 >>> (lambda x, y: x + y)(6, 4) 10

[@SevenDeMagnus]

Thanks sir Newstn for calculus. Lambda Calculus was tested to compete with binary for computation.

[@juancuadra3697]

I went into sleep mode.

[@vendicarkahn4860]

You didn't miss anything but nonsense.