Mary had a little lambda
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 160 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/33679 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Computer virusBucklingComputer programmingLink (knot theory)Neuroinformatik
00:59
Computer programmingSoftwareLambda calculusChurch, AlonzoData modelSound effectoutputWordFunction (mathematics)CountingNumberCheat <Computerspiel>Numeral (linguistics)Loop (music)Universe (mathematics)MathematicsComputer programConditional probabilityBoolean algebraLogicNetwork topologyPredicate (grammar)Data structureElectronic mailing listDisk read-and-write headEmpennageHand fanMaizeSoftware testingCodierung <Programmierung>Functional programmingLaptopSlide ruleMultiplication signCartesian coordinate systemParameter (computer programming)ResultantLambda calculusProgrammschleifeRight angleNumberBitOrder (biology)Zoom lensPredicate (grammar)Poisson-KlammerMassSpacetimePower (physics)Phase transitionMathematical analysisFunction (mathematics)Pattern languageWordComputer configurationoutputReading (process)Web 2.0Row (database)Pulse (signal processing)Set (mathematics)Instance (computer science)Musical ensembleSession Initiation ProtocolCondition numberStatement (computer science)Water vaporEvent horizonMetropolitan area networkInheritance (object-oriented programming)Block (periodic table)Type theoryArmFreewareMereologySystem callSequenceBranch (computer science)Direction (geometry)WhiteboardValue-added networkLine (geometry)ExistenceElement (mathematics)Electronic mailing listContent (media)Video gameMathematicsFunctional programmingBookmark (World Wide Web)Endliche ModelltheorieSound effectOnline helpBoolean algebraCheat <Computerspiel>CASE <Informatik>Computer programmingQuantumSoftwareCivil engineeringNatural numberOpen sourceTuring-MaschineProgrammer (hardware)Observational studyUniverse (mathematics)Software design patternTruth tableBulletin board systemObject-oriented programmingData structureComputer scienceLoop (music)Numeral (linguistics)Uniform resource locatorProblemorientierte ProgrammierspracheNeuroinformatikWeb-DesignerSeries (mathematics)Logic programmingQuicksortGoogolVariable (mathematics)Slide ruleSymbol tableLaptopDisk read-and-write headGroup actionTupleError messageMultiplicationInterpreter (computing)View (database)ExplosionDifferent (Kate Ryan album)Variety (linguistics)TouchscreenCodeIntegerData conversionGreatest elementState of matterProof theoryTheoryService (economics)Formal grammarSystem programmingCountingForm (programming)Wave packetArithmetic meanOpen setDataflowCodeRemote procedure callSelf-organizationDifferenz <Mathematik>Process (computing)Moment (mathematics)Game theoryAdditionPotenz <Mathematik>Codierung <Programmierung>Turing testSurfaceComplete metric spaceExpected valueArtificial lifeRecursionSinc function2 (number)Goodness of fitPointer (computer programming)Interior (topology)Operator (mathematics)Letterpress printingEquivalence relationSimilarity (geometry)Term (mathematics)Game controllerXML
Transcript: English(auto-generated)
00:05
Hi, everybody. I'm Anjana Vakil. Hello. You can find me on Twitter, at AnjanaVakil. That has links to my various other online presences. And today we're going to talk about Lambdas.
00:21
We're going to get into why this is not going to be a programming talk, really. And it's definitely not an AWS talk. It's kind of a talk about a really, I think, really fun and really interesting and really beautiful theoretical construct,
00:41
that allows us to simulate computation. And yeah, it's going to be kind of fun, kind of silly, not practical at all. So, buckle up. Really quickly, I'm Anjana. Hello. I work for a company called Uber Research. No affiliation.
01:04
And we work with data on science research funding, so kind of where the money goes in the process of science. And I work on building a domain-specific language to query that data. And we do lots of other cool stuff. And we're actually hiring right now, especially for a web developer.
01:23
If you like working with Pyramid, come talk to me. I'm also an alum of a couple really great organizations that have helped me wrap my head around both things like the Lambda Calculus and things like Python. One is the Recurse Center. It's a programming retreat, like a writer's retreat, but for coders.
01:41
In New York City, absolutely fantastic, self-directed program. And another is Outreachy, which is a really incredible initiative to get more women and underrepresented folks involved in open source, by offering paid remote internships at open source organizations like Mozilla.
02:01
Which is where I did my internship and I'm still involved with Mozilla as a volunteer with the Mozilla tech speakers. So I'm more than happy to chat about any of those things. If you're curious about any of the stuff I just mentioned, come grab me afterwards. One other important thing to know about me, I like emoji and I like writing silly code poems about the Lambda Calculus.
02:23
I wrote you a poem. It goes, Mary had a little Lambda, a function pure as snow. For every program that Mary wrote, the Lambda was all she needed to know. Where's my thunderous applause?
02:41
I'm just kidding, I'm just kidding. I know, it's not a very good poem. That's why I write software for a living. But this is what's cool about the Lambda. And we're going to see in a minute how it works. But basically the Lambda Calculus gives us a way of representing pretty much all computation. Anything that like a Turing machine could do.
03:03
With just a tiny little pure function. So the Lambda Calculus, let me zoom out so you can see that. The Lambda Calculus and if you've seen Lambda represented as this Greek symbol,
03:20
that's because that's what the name of that Greek symbol is called. You might recognize it from the logo of every functional programming language ever. It's basically a kind of mathematical or perhaps logical formalism. It's kind of a system that this guy, who looks super fun to hang out with, Alonzo Church is his name, and starting in the early 1930s,
03:42
he started developing this system as a way of trying to understand the theoretical foundations of logic and math. And he fell down a crazy big wormhole with it, and we're only going to scratch the very, very surface of that wormhole. But there's like, you could spend your entire life playing with this stuff.
04:03
So we're going to spend about 40 more minutes doing it. As I said, it can serve as a universal model of computation, meaning that it's Turing complete. So no big deal, whatever. We can just model pretty much anything computable with a tiny little Lambda,
04:22
which we're going to explain what that is in a minute. And just as a side note, it comes in some varieties. You have options. There's the untyped variety and simply the typed variety. We're only going to be talking about untyped Lambda calculus today. Okay, so that's tiny.
04:45
Can we see that better? Okay. So a quick note on the difference between Lambda in the Greek symbol, Lambda calculus sense of the word, and Lambda in the Python keyword that you probably all know and love, sense of the word.
05:00
So the Python keyword is great. It's really practical. We can use it in our Python to write programs. The Lambda calculus is not for writing programs. This is why this is not actually a programming talk. It's for thinking. It's for reasoning and trying to understand and get to the bottom of things and trying to make proofs and assertions about what we know about logic and math.
05:23
And those are two very different things. So let's just keep that in mind. As I said, not a practical talk. You're not going to learn anything today that you can go use in your job tomorrow. Let's talk about pure functions. So a pure function is a function that has no side effects.
05:40
In the Lambda calculus, there is like no way, no how, are you going to have a side effect in your function. A side effect is something that the function does that is other than just returning its return value. So for example, in Lambdas in Python, you can do things like you could say Lambda x print x.
06:02
You could print it out to your screen. That's not returning anything useful. It's just returning none. That's a side effect. And we cannot have that in the Lambda calculus. But it's fine with Lambdas in Python. So we're going to ignore that feature of Lambdas. Another thing is that Lambdas in the Lambda calculus
06:20
have exactly one input. It's like a pure function that takes exactly one input and returns exactly one output. Whereas, as we know in Python, we can use Lambda with multiple variables. We can return a tuple of multiple outputs. So we have a lot more flexibility there. When we make a function
06:43
in both the Lambda calculus and in Python, it looks kind of similar. It's just that the syntax is different. So in the Lambda calculus, we call function abstraction the act of sort of what we would in Python say declaring a function. In the Lambda calculus, if you see on the left-hand side,
07:02
that's represented by the Lambda symbol and then a symbol that stands for the input variable. In this case, X. Then you have a dot, and that's kind of like the colon in Python between Lambda X and the body of the function. And the body of the function comes to the right of the dot. So Lambda symbol X dot X is equivalent to,
07:22
in Python, Lambda space X colon X. On board so far? Cool. Okay. As we said, the Lambda calculus functions can only take one input. So if we want a function that we want to pretend takes more than one input, we have to basically take the first input,
07:43
let's say X, and then return a new function, because everything is functions, return a new function that takes the second input, Y, and then does something with both of them. So the second row after making one abstraction there on the left-hand side,
08:01
this would be a way of representing kind of a two-parameter function in the Lambda calculus. It would be Lambda X dot Lambda Y dot body, so X plus Y, for example. And in Python, remember we have options. We can actually create a single Lambda that takes two arguments and does something with them. But here we're going to be restricting ourselves
08:20
to just one argument per Lambda. So we're going to be writing functions like this, Lambda X colon Lambda Y colon body. Yeah, and then once we've got a function, we've made one by abstraction or by definition in Python, and then use it by application,
08:40
which is what we would call in programming like calling the function. And this looks pretty similar. It's just got an extra pair of parentheses on the Python side of things. In the Lambda calculus, function application is just the function that you want to apply and then the argument you want to apply it to with a space between them. In Python, we use brackets to indicate that we're calling something on arguments.
09:01
Sorry, parentheses to indicate that we're calling something on arguments. Ah, yes, and I guess I didn't mention that the Lambda in Python is just an anonymous function. It just doesn't have a name. But we're going to be cheating a little bit. We're going to be naming some of our Lambdas just for sanity.
09:20
All right, so the game that we're going to be playing here, I'm going to zoom back out, is if we were to pretend that Python's Lambda was like Lambda calculus Lambda, what could we do with it? And as I said, this is going to be an experimental, fun, silly, learning-oriented talk,
09:42
not a programming, practical, let's do useful things talk. So please take this opportunity to get off the train if you want to go learn something practical. There's a bajillion other talks on right now that I'm sure are way more useful than this one, but this one hopefully will be fun. All righty, don't worry, I won't feel bad.
10:04
So what can we make? How about some numbers? Numbers are cool, we like numbers. Numbers help us do things like count. One thing, two things, three things, but what could we count if we're in a world where all we have is a Lambda? All we have is a tiny, little, pure,
10:20
one argument in, one result out function. So all we know how to do is create functions and then call them, apply them. What could we do with that? Well, we could think of applying a function
10:41
as like counting one and applying it again as like counting another one and applying it again as counting more. So we could think of counting as like counting calls to a function or counting function applications. So if we wanted a couple of numbers,
11:01
zero and one, can everybody read this okay? Awesome. What would those look like? Well, okay. Bear with me here. We're gonna get a little freaky with our definition of numbers, but if we need to count things by applying functions, then a number is gonna need to be something
11:21
that takes a function as an input. And it's gonna return something that is another function because everything is a function and that function is gonna take some argument. Okay, so if you'll allow me here, we're gonna think of all numbers as being something that like takes a function
11:42
and returns a function that takes an argument and does something. And the thing that it's gonna do is apply the function f n times for whatever number it's supposed to represent. So like one would apply the function once and zero would apply the function
12:02
zero times exactly, which would mean we would just return Cool. Okay, let's see if live coding works. Probably not. Let's find out. I think I also forgot to clear all the inputs in this thing, so that'll be interesting.
12:22
So two then would be, oh, come on, y'all, help me out. We're calling f twice, right? So we'd be like applying f to f of x. And three, similarly, would be f of f of f of x, I think.
12:45
Look good? Okay, let's see what happens. Now, so far I've been asking you to just trust me, but you probably want some kind of proof. So we're gonna cheat just to do some sanity checks here.
13:00
We're gonna make an int converter that'll take a lambda number and convert it to a Python int. So what we're gonna do is we're gonna take the number n and we're gonna pass it a function that adds one to some integer, i, and we're gonna start it off with the integer zero. So zero should call this function here zero times, right?
13:21
So that should give us zero. And one should call it once, which should add one to zero, which is one, and so on and so forth. You with me? Is this acceptable? All right, let's see what happens. Oh no, I forgot to clear the inputs. Okay, so do it to zero. It works, it was zero. And similarly, one, if you believe me,
13:41
I'll do it live here. It's one. I think you see where I'm going with this. Yeah? Convinced? You look so convinced. I have never seen a more convinced-looking group of people in my life. Okay. M3, yeah, whatever. Same difference.
14:00
Okay, so now how do we get a higher number given a particular number? This would be what's called a successor function. We're gonna need to be able to take a number and see what the next one is. And in order to do that, whoa, hi, okay. In order to do that, we need a function that takes what as input?
14:22
N, a number, cool, and gives us another number, right? And a number is a thing that takes a function, oh, that's not how you spell that, and then that returns a function that takes an x.
14:40
And so if I wanted just n, like the original number that I gave it, I would call it like this, right? I apply n to f, and then I apply that to x. But I want one more loop. I want one more application of f. So if I'm not super duper tired, I should be able to wrap that whole thing
15:01
and apply f to it one extra time. I see skeptical, puzzled, and completely uninterested faces. Okay, so let's see what happens. If you believe me here, okay, so four would be the successor of three, right?
15:21
And that should be and is four. And similarly, five should be the successor of four. And I should be able to get seven by applying successor to the successor to the successor of four, right? Three extra successors. That gives me seven.
15:40
I see how excited you are by this. It is really exciting, I know. Okay, but where can we go from here? So just a note, these numbers that we have, they're called church numerals. Can you guess who they're named after? That dude from the beginning, Alonso, he's my BFF.
16:03
No, not really, but I wish. Anyway, so just if you want something to Google, you can Google that. Okay, what about arithmetic? Can we like add two numbers? So if we have an n loops and an m loops and we want to add them together, we could just loop n times and then loop m more times, right?
16:23
So if I had like n is two and m is three, I could do like one, two, and then one, two, three, and then that would give me five, right? Cool. So how do we represent that? So add is going to take an n and an m,
16:44
and it's going to loop n times, first of all. So that means we apply n to f, oh sorry, it's going to return a number, which looks like that, as we've seen a couple of times. It's going to apply n to f and then to x. But then we're going to add on a couple of extra loops,
17:03
so we're going to apply f again m times to the result that we got from looping n times. I think this is right. Everybody on board? Maybe? We'll find out.
17:21
Okay, let's see, I don't know. Maybe I'm just super tired. Okay, so I should be able to get this. I should be able to add eight and two and I should get a thing called 10, and it should convert to this. All right, it worked, yay, nothing exploded. And I should then be able to, oh, let me zoom out a little.
17:43
Can you still read that? Okay, I should then be able to add them in the opposite order, and it should work. And I should be able to mess with this, right? Like, this should give me, yay, yay! Good job, everybody. Okay, so subtraction is way harder,
18:05
but multiplication, multiplication is not so hard. So what about multiplying n and m? How do we do that? So basically, if we're multiplying like two times three, we're gonna do like one, two, that's counter one, then we're gonna do another one, two,
18:21
and then we're gonna do another one, two, and that should give me two, two, two, six, right? So we're basically gonna loop n times, m times over. Okay, oh, jeez, that's what it looks like when you don't enter anything in. Oh, we're gonna fix it. So multiply is gonna take an n and an m, and it's gonna give us another number, which looks like this.
18:44
Okay, so first we're gonna loop n times, and if applied to f gives us a function that applies f n times, then if we apply m to that,
19:03
that should apply that function m times. So we have like a loop within our loop. I see your faces all look like my face looked the first time I played with this. Feel free to follow along if you've got your laptop in front of you, open up an interpreter.
19:20
Okay, so if I apply m to a function that loops n times, then I should get a function that loops n times m times is how I'm trying to think about this thing. Let's see what happens. All right, it didn't explode. Does it give us the right thing? This is what I'm expecting.
19:40
I should be able to multiply four and three and get 12. Let's see what happens. Yay! Okay, and I should be able to, oops, I should be able to do something else like to int multiply, I don't know, two and three.
20:02
Okay, let's see if it works in the other direction. And again, dividing is super hard, no more dividing, no more dividing. Okay, so what about powers? What about raising n to the power of m?
20:21
Huh, I'm gonna take a sip of water while you think about that one. Yeah, everyone looks at the ceiling like the answer's gonna be written there. Okay, this one's gonna get a little weird. Let's see what happens. Okay, I want a power function that takes an n and an m,
20:42
and it's gonna give me a number. Right? Okay, let's imagine, let's take like a simple example. Let's imagine n is like two. So if I wanted to apply, and this would be like two,
21:03
n is two, if I wanted n squared, I could multiply two by two, right? And we saw in the last example that that means calling this part, this one was our m before, so imagine n was two, and now we've got like two squared.
21:24
Okay, and then for like three, it would be like calling that again, two to the power of three. So this would be like two times two times two. Imagine n is two. Okay, so what we're doing is we're applying n m times to f, right?
21:45
Now if only we had a way of telling the computer to apply a function a certain number of times. Oh wait, that's what numbers do. So, I should be able to take this n,
22:02
get rid of these extra things, and apply m to it, and this would give me a function that calls n m times on this function, which should then give me like the power that I want. Maybe. Let's find out.
22:24
Okay, so this is what I would expect, right? If I raise two to the power of three, I should get eight, perhaps. Moment of truth. Yay! Okay, wait, but I don't know. Maybe I could have just faked that. What if I raise it to four?
22:40
We did it! We did it! Okay, but actually we can even simplify this, because this is getting ugly. Now we've got like four things in here. A number is just a thing that takes a function and takes an argument and like applies to both of those. We can then just consider that if we clear all this out,
23:02
since that's what a number does anyway, and clear all this out, we should still have a valid definition of the power function. So let's see if that still works. Okay, so that's even more elegant than like adding and multiplication.
23:20
So, this is some arithmetic. This is pretty fun. People are looking at me like, you said this was going to be interesting. But we did really, really basic math with something super complicated. Isn't that what all programmers love to do? Okay, meanwhile, I'm like,
23:42
hey, BFF Alonzo, Mr. Church, sir. He's like, yeah, Amjuna, I'm speaking to you from beyond the grave. What do you want? Could you tell me the answer to life, the universe and everything, please?
24:03
Computation. No, just kidding. But I don't know. I thought this was pretty cool because if you think about it, the way we've been taught to think about like addition, multiplication, exponentials, it's completely different than all of this and yet it totally works out in this lambda formalism. So I think that's pretty fun.
24:20
Feel free to disagree. Okay, so we've done math. That's cool, but that's not all of this. Oh, somebody said conditionals because I planted them there in the audience beforehand. No, I didn't. But yes, we do need conditionals and in order to do conditionals,
24:41
we need Boolean values, right? Because these sort of go hand in hand. So, oh good, okay, this is what happens. Just ignore that. When we work with a conditional, it has some kind of form like this, right? We say if a condition is true and where the condition is a Boolean
25:02
then it's false. If it's true, then we do some stuff in the then block and if the condition is false, then we do some stuff in the else block. Yes? On board? Okay, so we kind of need to define all of these things together so that they work out,
25:20
so that we can do things like this. We can test if a condition is true and then do the then thing and if it's not true, do the else thing. So if then else is gonna be a function because everything is a function, it's gonna take a few different things. Well, it's always gonna take one thing but we're gonna line up a bunch of arguments in sequence so that it looks like
25:41
it takes multiple things. So it's gonna take a condition, first of all, and then we're gonna need to tell it like a then do, like a then block and then we're gonna need to tell it like an else do, else block and then something. Okay, let's forget about what the something is for now
26:00
and go back to Booleans. So Booleans, and I'm just naming them true and false here so as not to like mess with our Python words even though the lower case shouldn't mess with it but anyway, it's also more fun to spell things wrong. Okay, so true should be a thing that when it sits here,
26:21
it should pick this branch, right? And false should be a thing that when it sits here, it should pick this branch. So true is gonna be a thing function because everything is a function that we're gonna give it a then
26:40
and an else block and it's gonna pick the then block, right? Just like that's how we wanna be able to use Booleans so let's just define it in terms of how we wanna be able to use it and similarly, if we give a then and an else to false,
27:01
then we should get the else thing out. Okay, on board so far? I see like one or two nods. I'll assume that applies to everyone. Now, what about the rest of our if statement? We didn't finish it. What we're gonna do,
27:21
if true and false are like choosers here and they take a then and an else, then we can just take our condition which is gonna be a Boolean and apply it to the then and the else and it should choose the right one for us if we've done everything right. So I'm gonna call the condition on the then,
27:41
oops, apply it to the then. Typing is so hard and then the else and if it's true, it should pick the then and if it's false, it should pick the else. Maybe, let's see. Okay, at least our little ugly thing went away because clearing Python notebooks is hard.
28:01
Let's see what happens. Okay, so I am tired. That is true and the number of coffees that I'm gonna drink today depends on whether or not I'm tired. So if I'm tired, I'm gonna drink three coffees and if I'm not tired, I'm gonna just drink one coffee
28:20
because I'm in Italy and I have to drink coffee. Okay, so this is what we would expect, right? If I'm tired, then coffees today should give me three. Yes? Okay, let's see what happens. Run. Okay, okay, all right, all right but I don't entirely believe this because again, I could have rigged this so what if I'm not tired?
28:44
We did it! We programmed! We programmed! Look at that. We have conditionals now. I see you're all so excited like me. Okay, moving on. So with truth values, we can do logic.
29:02
That's fun. Okay, we're just gonna power through these kind of logic things so in the interest of time. So if I wanna not function, and again, I'm just gonna use a different word so as not to override Python words, I'm gonna call it opposite because that's, I don't know, longer. Anyway, it's gonna take a Boolean
29:22
and a Boolean is a thing that takes a then and an else, right? And a Boolean that's true is gonna choose the then and a Boolean that's false is gonna choose the else. So if we wanted to do like opposite day, and apply the Boolean to it, and it would pick the wrong one
29:41
because we switched them because we're sneaky that way. Do you believe me? You're like, yeah. So we should expect this, right? If I make a little cheating function that just applies a Boolean to Python's true and false just so that we can see
30:00
what Python thinks it is instead of having to do something complicated. And again, this is cheating because we can't do side effects of false in any other way except these functions that we created. If I convert true to a Boolean, I should get true. Okay. And if I convert the opposite
30:21
of true to a Boolean, I should get false. Ooh, that worked, but let's make sure if I convert the opposite of false, I should get, yay! Okay, logic, step one. But we need more logic. Oh, no, we'll get to more logic in a second. First we need predicates. So we want to be able to apply
30:40
a function to a thing and get a Boolean out. That's like a predicate function, yeah? Where we test that something is or is not conforming to some high standard we're holding it to, like for example, being zero. So if I wanted an is zero function that would take a number and give me a Boolean
31:00
that tells me whether that number is zero or not, I could do it like this. I could apply that number, which again takes a function and applies that function n times to a value, and I could pass it a function that takes whatever we give it and returns false, always. Then if I pass that whole,
31:22
that n times application of this function to true, the only time that we're gonna get true out is if we don't call this function on true at all, zero times. Whereas if we call it once, true will get turned into false. If we call it twice,
31:41
false will still say false and so on and so forth. So I should be able to do this and get false for two and I should be able to try it with zero and get true. On board? So we have to be a little tricky now that we're in Lambda World on how we think about
32:01
functions like predicates. We have to start thinking in a totally different way where we're thinking about the number of times we would have to apply a function to things to understand something about the number of times that we have applied that function to the thing. This is why you could spend
32:20
your whole career thinking about this stuff. We're not going to. Similarly, as another example, we could have an isEven function that starts off with true because zero we'll call even and applies opposite n times so we alternate back and forth. One is the opposite of true, it's false.
32:41
Two is the opposite of the opposite of true, which is true, et cetera. So I should be able to get eight is even, seven is not even, one is not even, four is even. Programmers.
33:00
Ha ha ha. Don't clap for me. Clap for Alonso. We're running out of time here. Let's see if we can power through this logic part. This is where things get a little crazy. I'm just going to show this to you and let you think about it for a second while I take a sip of water and then we're going to talk about it.
33:20
First I have to open the water. Okay, so this is like our and function. I'm calling it both because and is a special word in Python. Okay, so an operator like and, or both in my case,
33:42
is going to take two Booleans, right? Bula and Bulb. No, Bula and Bulb. How do we get to a place where we can use the fact that Booleans choose
34:00
either a first thing or a second thing to tell us whether both of them are true or one or more of them is false? Okay, this is the answer, but let's try to figure out why. So, if Bula is true, then I can sort of continue
34:24
and check Bula B. If Bula is not true, then I already know that the whole thing is going to be false, right? Bula is false. So if I were to set up two things where the first thing is I don't know what and the second thing is false because we've hypothesized that Bula is false,
34:42
then false chooses the second thing, right? So it will choose false. So already just by knowing that Bula is false, I know that this whole thing is going to be false. I see faces like, feel free to play with this on your own time. I think that's the only way to wrap your head around it.
35:01
If Bula is true though, then we'll pick Bula B and see what Bula B does. And if Bula B is also true, then whatever comes here will be like the second thing that it would have chosen. But if Bula B is true, then it'll choose the first thing.
35:20
It won't choose this second part. It'll choose the first thing, which is Bula A, but we already said that Bula A is true, so this means we'll get true. I see like one nod and a couple of like amused chuckles. Okay. I don't know. Let's try it out. Maybe we can convince ourselves by like actually applying it to stuff. So I should be able to do both true, true
35:42
and that should be true, right? Let's see what happens. Okay. All right. What if I change it? This should give me, oh, one more to check.
36:03
Okay. Are we convinced? All right. These are just more examples. And similarly, we could do like or, which I'm just gonna call inclusive or,
36:21
where if Bula A is true, it doesn't really matter what Bula B is. So Bula A is gonna choose the first thing and we already know that Bula A is true, so we're just gonna make it choose true. If Bula A is false, then it's gonna choose the second thing, which is Bula B, and then the value of the whole thing just depends on whether Bula B is true or false.
36:42
Right? This is how truth tables work. Okay. Let's see what happens. So I should be able to get true for this and true for this and this should be false. Haha. And this should be true, right?
37:01
Yay. Okay. Only one person thinks this is cool, so if you don't understand why it's cool, you can go talk to him later. All right. Yeah, this is just more examples. Okay. I have like three minutes left. Don't know how much we'll be able to get through this, but let's try. Oh, oh, oh. We're being flexible with me.
37:21
Nice. All right. So we've got some data. The answer is we love lists,
37:45
especially in functional programming land. We love lists, right? What is a list? It's a thing that contains stuff. What kind of stuff could it contain? So it could contain nothing. It could be empty,
38:00
which is often called nil, the empty list. It could contain one thing or it could contain more than one thing. Yes? Have I forgotten any possibilities? Hopefully not. So we're going to try to represent these things by building lists out of pairs of two things.
38:25
It's going to get a little weird, but we're going to try to get through it. Okay. We're going to have a make pair function that takes a left thing and a right thing and returns a pair of those two. Now, what is a pair of those two? We're just going to represent a pair
38:40
as being some thing, some function that takes a function and then calls that function, whatever function you pass into it, on the left and then the right. It applies some function to the left thing and the right thing. Okay. Then we need a function to get the left thing and get the right thing.
39:01
And we already have a really nice function for choosing either the first thing or the second thing. It's called a Boolean. So we're going to take the get left function and it's going to take a pair and then pass the true function to that pair, which is going to call true on the left and the right,
39:20
and true chooses the first thing, so it's going to choose left. Yeah? And similarly for right. So if I make a pair of one and two and I choose the left thing, then I should get one. And if this were different... Okay. And if this were right...
39:41
Okay. With me? Cool. All right. Now, an empty list we're just going to, like by convention, represent as a pair of true and true. And we'll see why that's helpful for lists because we're going to represent lists not as a pair of just two things, but as a kind of special pair
40:01
where the first thing in a list is going to tell us whether or not the list is empty. And then the right thing in that pair is going to be the actual content of a non-empty list. And if the list is empty, then we don't care about what's on the right-hand side because it's empty, there's nothing in it. So we could just put whatever we want there,
40:20
like true. It's a little bit more complicated than that, but close enough. So the only type of list that will have true as the left element will be the empty list. So we can use, for our isEmpty predicate function, isEmpty nil should be true.
40:41
Okay, cool. Then, just powering through, we can create a prepend function which takes an existing list, L, takes an item and prepends it to an existing list, L, which is non-empty, sorry, and gives us a list which is non-empty,
41:00
so isEmpty is going to be false, the left item is going to be false. So we're going to make a pair where the first thing, the left thing, is false, and then the right-hand side is going to be a pair itself of the new item and the old contents of the list. I see people doing like this, which I think means my chin
41:20
really gets this. Yeah, your chin does get it. Okay, so what we can do then is undo that with a head and tail function that get us the stuff in the right-hand of the list where head is like the first thing in the list and tail is like everything else. So just take my word for this because we're almost out of time.
41:42
So, okay. On the first day of EuroPython, I had had like two coffees. So I'm going to prepend two to an empty list, and this is how we get a list that just has one thing in it. So we already have the empty list. We needed a list with one thing in it. This is how we could do it.
42:04
So if I were to get the head of, let's say, coffees. I don't know if this is going to work. Let's see. This should be. Nope, nope. Sorry? Ah, thank you.
42:23
Haha, great. Okay, and then if I were to prepend more stuff to that, I could get a more complicated list that had other things. So if I had coffees per day the head of that I should get. The first thing is I took the coffees on day one, which is two,
42:40
I prepended one, and then I prepended three. So the first thing should be three, which it is. And if I were to take the first thing of the rest of the list, that should be the head of the tail of the list, which should be.
43:00
Ah, okay. So we got all this stuff. We got data. Numbers, booleans, lists. We got arithmetic. We got logic and control hole. And representing the data that we did here is called church encoding. So you can go Google that. And I know we're like super out of time, so I'm not going to go through these slides, but it turns out that this,
43:22
what we've been doing representing data this way, is kind of like object oriented programming. Unfortunately we don't have time to talk about why that is, but I'm going to post the rest of this and there's like explanation and I just want to say these are some cool places
43:41
to go read more about these things. Again, I will tweet out the location of this Python notebook. And I just want to say thank you to the research, to your Python, and to all the people who helped me and inspired me to do this. Yeah, and I would say we thank you. Awesome talk, really. Great. I learned a lot. Maybe I would not have dropped out
44:01
of my computer science studies when I had such an introduction to the science of things. I didn't understand it. So thank you and yeah, unfortunately no time for questions, but I think she's over there. You can come grab me afterwards. Thank you. Okay, thank you again.