Lambda Calculus Explained: History, Semantics, and Programming Applications

[00:00:04]still here honestly I talk on lambdas last thing on a Friday you're hardcore you have my respect you will have my slides in a minute you have my respect to begin with me okay so let's talk about Landers um this is a phrase that's been used a lot by programmers language designers so I know I'm really what I want to do is I want to get inside this and say well okay so what is this thing people keep talking about let's talk white origin stories okay this is this is basically the way that Hollywood works you've had all the lambda features released in your languages now it's the origin story okay that we've released that how do we monetize more lambdas okay this is what we're going to talk about and to understand a little bit more about what's going on here it's a nice letter it's it's one of the most pleasing letters to write actually and but there's this thing it has a number of associations the Amazon completely completely jumped on some crazy van right so we're gonna call this thing that's nothing to do or even remotely like functions and lambdas we're going to call it lambda that'll confuse everybody because it's kind of like function sort of yeah our PCs done differently right so yes nothing to do with that no it's not to do with half-life which borrowed it from the idea of the decay constant in physics where it's also used as a wavelength physicists like to recycle their letters quite a lot they don't use name spaces and then there's calculus and that's the one that we're kind of interested in now this all came out of the work of Alonzo Church and he published this paper in 1936 so that's kind of the moment of Inception except actually it isn't he published a previous paper in 1932 which I have not been able to get my hands on even via the interwebs but this is the kind of the basic reference point he did some fixes in 1935 to some stuff and he wasn't interested in what we are interested in he was interested in computability but in the same way that cheering was is something computable as opposed to how do I actually write a program and he was exploring this an unsolvable problem of element number theory this was really just the exploration of the insurance problem which is related to the halting problem and in the same year Turing came out with similar proof that was shown to be compatible but using Turing machines and these was shown to be actually equivalent and so there's so but as a buyer by in this paper which I am not trained as a mathematician so I kind of I kind of reached a sort of a sort of sheer g-force acceleration after a couple of pages got really totally sure I'm with you here on this one there's a lot of assumed context but he just tosses in learned calculus it's just a very casual thing but it's also interesting this is the 1930s and there was this is a period at which it's worth understanding where a number of certainties about the future was starting to be torn down and I'm not making political references just yet but I could easily do that it's there was this idea at the end of the nineteenth century that we had everything was everything was knowable knowability everything could be complete maths could be consistent and complete and all of this started tumbling down in the 1920s the end of the 1920s thanks to Kirk girdle and the incompleteness theorem we discovered halting problem as a whole series of things by the way relativity came along to just say oh yes black holes that was a nice side effect of relativity which was 1915 when Einstein first presented it properly published in 1916 and then other people started working through the know working through the equations going wait a minute you know there's a really weird thing here what we now call a black hole a boundary of no ability and it turns out that the 1920's 1930's came along and tore down this edifice of like everything is knowable oh by the way quantum mechanics it's just like so that was that that was that was the stage which ultimately gives us this idea of what we have is rigidly defined areas of doubt and uncertainty that certain things cannot be known and are no but it turns out that lambdas are they are knowable they were they were left as a kind of theoretical thing something of interest pretty much until the end of the 1950s when McCarthy and others started designing lists the first implementation of the list was 1960 and it was pretty much based on lambda calculus and lambdas were a feature in the language and this was kind of like the first time this is just like right made its way in to computing and these days it's kind of like you know I just did some googling around the other day and there's this Ruby Ruby tutorial you may have heard of Landers before perhaps you've used them in other languages it's just what it's now got to that point where we kind of assume that people have heard of them there's a strong assumption despite the fancy name I don't know picking a letter is not particularly fancy I mean you know dominant programming languages through history see what that's a fancy name no it's just just because it chooses a letter from a different alphabet it's like that a lambda is just a function peculiarly without a name and you know what this actually means in terms of solving deep significant problems it means that this classic quote from Phil Carlton okay it turns out too hard things and computer science cache invalidation and naming things we're done you know we've just reduced it if land does mean you you never have to worry about naming things and cache of validation if you've doing functional programming it turns out there's no such thing as invalidation because that's a process with a side-effect nothing happens in functional programming it's so purely even if you unplug your computer your functional programs will still run wait a minute doesn't work yeah they're riddled with side-effects that's all that makes it all of this stuff is an illusion okay functional programming is an illusion every paradigm is an illusion but yeah we can do that and basically say right we've done if we can go home you know there are no more problems because it's also caching validation is not relevant to this talk either so what was Church what's Church saying I said right okay so we select a particular list of symbols consisting of the symbols open close curly open close parenthesis lambda square brackets and an innumerably infinite set of symbols ABC etcetera to be called variables and we define the wave formula to mean any finite sequence of symbols out of this list now this is a shift from the way that people have and here within the paper he also uses traditional function notation from a mathematical perspective and there's this very simple but subtle idea that a function is a name and there is a formula and the function begins with a name and what we're doing is we're basically saying you know what if you do have a name it's just kind of like on the side and that's an associate that's a convenience but it's not a fundamental idea and we're going to shift this and we're going to treat these things as first class that there are only values and that's the thing in lambda calculus there are only values that are lambdas that will turn out to be interesting a little bit later and so here we have a very simple lambda expression and I'm gonna use this to demonstrate the basically the the three rules of what makes a lambda a lambda the first thing is variable that seems trivial we we take these for granted but this is the basic idea that you have something that can hold a value that value must be a lambda in pure lambda calculus but you have a variable we'll see in a moment has two kinds of variables the next thing is you have abstraction function abstraction where what you're doing is saying that this variable is bound within this context over an expression Y of X and the y and to be precise it's Y applied to x and y is a lambda being applied to a value so application so it turns out these are the three things if you've got these this is fundamental you have variables you have function abstraction you have application you've got that that's e it now a couple of other things that thing F that I had before that's an abbreviation it's not formally par of lambda calculus but it turns out it gets quite boring when you have to write everything out longhand yeah although he wasn't saying don't repeat yourself that's what he meant these are convenience but this is really important because it means just as an aside I'm not a topic I'm going to cover here it means that that is simply a stand-in for that because it's not a definition because it is an abbreviation it basically means that you cannot refer to F on the right-hand side which means that lambda calculus does not support recursion which is going to upset a lot of people who've just thought whoa wait a minute isn't that all the functional programming there's this there's a whole bunch of things called fixpoint Combinator's that get kind of interesting and maybe an extended version of this talk I'll explore that but these are just abbreviations they turn out to be surprisingly convenient the next thing is to look at the kinds of variable we have bound variables that comes in as a parameter that's your classic parameter and free variables that means that as defined somewhere else and then that somewhere else is kind of an interesting thing we'll come to that in a moment so let's just look at something fairly simple and what I'm going to do is I'm going to introduce something beyond lambda calculus that little x symbols strictly speaking the purest well the purest form of lambda calculus has nothing else to it I just showed you the whole thing and it got a few reduction rules and that's it but for convenience obviously we just like yeah this is through some mathematical stuff and let's make life a little bit easier so we take our standard definition of what is Square and we do something like this so therefore this is an abbreviation I apply that guess what innumerably infinite symbols I'm not saying Alonzo Church invented emoji but he accommodated it he didn't say there's a bound set he said no and that means that that's a cross-product I know I know that's terrible it does not get better than that in fact we can do the whole thing this is great so I can now get square and he said he knew a reemployment I'm gonna take him at his word and so we comply that to seven or we can do that or we can write the whole format so there we see in its purest form we've used simple types and we've got a simple application we're very strict about things like parentheses as programmers about where they go that's not the case of mathematicians it's just like yeah feeling that he actually switches through the page how he does function application f parens of X or f space X it says parentheses are just there to make things a little bit more visible I just love to see I just love to see compilers do that it's just that yeah I think I understood that you know I feel I understood that I'm gonna go with this you know so that's the kind of thing you can get away with in a paper now let's make this real javascript doesn't get more real than that so traditional JavaScript we we have we are we are brought up with the idea of thinking we named functions a function has a name that is your starting point but actually we could do it like this now there's an interesting point about and one of the reasons I've chosen JavaScript here it's not simply that it is broad accessible but Brendan Eich when he developed it in the mid-90s we kind of the tale goes that it took him two weeks to do a lot and then there's half a dozen jokes that hinge around the fact we're not quite sure what he was doing in the second week but actually what he wanted to do was implemented version of scheme I will come to scheme in a moment but people said nobody's gonna buy that syntax you've got to use familiar syntax so basically it's it's kind of an interesting mashup he said ok right I'm gonna use C style syntax I'm going to use I'm gonna use Landers I'm going to use ideas from scheme so it's a list based language I'm gonna use ideas from there and I don't really want any of that complex objects I'm gonna use a really simple prototypical model of objects and go with that but from the very beginning it was always in there now strictly speaking some people would some people get very fussy and say well I know that's not really a lambda because it's just a function without a name it turns out that these are not necessarily equivalent but some computer scientists get get very upset about them being regarded as equivalent so I'm gonna treat them as equivalent so anyway what we get is X script 6 comes along and says you know we got this arrow form we're gonna make life even easier and we can they we've gotten more abbreviations and actually if you've only got a single expression then yeah black very easy so this is all good this works out really well let's go back to that Ruby tutorial they're anonymous little functional spires sneaking into the rest of your code I don't like the sound of that I mean I've already got Facebook to worry about and now you're telling me my lambdas are gonna gang up on me but we have a point here about the way that people perceive them not the spy but the functional bear people immediately associate lambdas I say all right lambdas that must be in function program so 2014 Java gets lambdas lots of people going like I am now functional programming its Java mate you're not functional programming really yeah but I'm using Landers and they're like totally functional it's just like oh okay let's let's take things down a bit let's let's reduce our excitement here Excel interesting enough which does not have lambdas although it's been suggested I don't know I think spreadsheets already have enough bugs in them I'm not quite sure that the public is ready for the ladders but assignment page Jones mr. Haskell basically med Association Excel is the world's most popular function language functional means a number of different things to different people at different times they start from different positions some people say write functional programming is rooted in this for me it is lambda calculus for other people on and I know it's to do with hindley-milner type systems that is functional programming to me it's kind of like everybody has their own personal version of this but I wanna go back to list because this is the one that was kind of interesting this just want to trigger a number of ideas and there's a certain beauty and elegance to the original Lisp this is the manual for the original Lisp as I have a copy of it at home you can find a PDF online it's quite it's quite brilliantly written as she was written in the early 60s Lisp 1.5 there was supposed to be a list to than ever was the syntax they were going to tidy up the syntax and make it less list oriented but actually it turns out the syntax they're merging between data and code treating them as the same was not a it was not a stepping stone idea it was actually a really big idea and they were kind of thought we're going to change the sin two accents just like now you know what this is this something really good here but we use Lisp generally to mean anything that coming - looks like Lisp there's a there's a monster called Common Lisp which I've had to grapple with in the past a couple of times number of people are familiar with the Emacs Lisp earless there's lots of different flavors they're not all of them were significantly larger than this but this is sent elegance to it and I've described to people you need to get infatuated with this I don't think I've ever been commit pay commercially to write this code although I think I managed to sneak some stuff that was Lisp ish a couple of places but there is an elegance to the thinking there's something really clean and simple Alan Kay of small talk Fame when he saw part of some some of the ideas in this book said basically that this page this is the laws of physics or Maxwell's equations to be precise for programming of all languages in particular is really aspired and that inspired a lot of small talk come back to that a little bit later and so we can always get carried away with this and xkcd last night I drifted off while reading a list book suddenly I was baited as a fusion of blue I noticed the coincidence that actually I don't think Randall Munroe intended it but that is the blue of the original book and there it is nice coincidence suddenly I was bathed in this effusion blue once just like they said I felt a great in light when I saw naked structure of Lister code I'm fall before me the patterns and meta patterns dance syntax fade and I swam the purity of quantified conception of ideas manifest 2001 referenced there which if you know Lisp is hilarious if you don't don't worry about it truly this was the language from which that gods wrote the universe no it's not it's not I mean its density yes honestly we hang most of it together with Perl there is a certain pragmatism to the way that things come out and as for those red X's for quantum mechanics you're on your own kid but that does bring a rather interesting point um lambdas really have got everywhere to try and claim them for your paradigm is it's not really gonna work out I'm not no I'm not gonna do anything with Perl I have a kind of a there's a bit of me that won't let me do Perl you know it's it's kind of like Sethe speech I just can't do it it's not I'm not allowed to do it Perl is executable line noise it's one of my least favorite languages no like languages but PowerShell let's use a scripting language he's partial here's a lambda that's the square it's quite nice actually POW sure there's a surprisingly good and well well for to our language if I want to give it a name like oh yeah I can just I can bind it to a name I can apply up a really simple application syntax there it is it's very direct and that's it so I've got I've got these options I can even do it this is prop now you know it's a proper lamb because you can just take that and you don't need the name with which to execute it that's that substitutability that freedom the idea is that the name is simply an abbreviation for something else if you've got that this is a really good thing then that's also while we well you know let's go back to the 60s again Algol 68 possibly the most influential language you've never used if you were all of those those are you using languages where there's in a keyword int yes that came from Al Gore prior to that all language design involved using the word integer int character char that's where it all comes void that came from Algol there's a load of stuff it really is at the time it was seen as this monstrously huge language that would nobody would ever be able to implement honestly the I've got a copy of the language report it's it's kind of really quite small compared to modern languages this is not complex but you know guess what one things I love about Algol is it is unforgivingly procedural it does the procedural paradigm properly algorithmic language there it is it does the procedural paradigm it's committed to the procedural paradigm so committed that you can have unnamed procedures that's how committed it is yeah they were a standard feature it's a standard concept okay so I can go ahead and I can you know bind this simple anonymous procedure square so I just want to remind you 1968 okay Gouri because you all the other languages going around is like yeah Java's going like 2014 we got lambdas and everybody else behind it's going like hi c++ here that was 2011 for us and c-sharp sitting going like come on we're in the 2000s javascript in the background going like yeah mid 90s Lisp was going like yeah 1960 but somewhere in there in the 1960s this was kind of a normal feature of language design COBOL did not have it but a lot of other languages had this ability to have this kind of procedural abstraction freely available so I've got a declare it as I you know it's it's a language that has a concept of types doesn't do type deduction so I do have to go ahead and declare these things but you know I can apply it I can also as we expect with an application I can just apply it freely I can just take that expression and apply it to seven and it will give me the square of that so it's a little bit much to try and claim I am being pretty I've just shown you scripting and procedural I mean that's yeah it's not oh my goodness lambdas and Ruby are also objects just like everything else okay we are not done with this paradigm apparently so pick this one up from a discussion group on which years ago there was a discussion I dug out with guy Steele and a number of other people guy Steele was his kind of languages expert had a hand in a number of languages worthless son but prior to that it's been involved in variety of languages most notably scheme in the 1970s really nice bloke very very knowledgeable but this was kind of a response and somebody was kind of describing it the pheromone Master croc now I was walking with his student Anton hoping to prompt the master into discussion Anton said master I've heard that objects are a very good thing is this true quick nah looks pityingly at his student and replied foolish people objects am merely a poor man's closures so closure is a term that gets thrown around a bit and actually wikipedia has one of the best definitions oh god I dug around I don't know you know I don't always like to rely on Wikipedia except for the fact that sometimes they absolutely Nayla and it's a really good condensed tour of it the concept of closures was developed in the 1960s that's a hell of a decade for the mechanical evaluation expressions in the lambda calculus they were invented to solve this problem how do we take lift this stuff off the page and use things that we are familiar with now scope binding variables things like that how we do this piece of land in defines term closure in 1964 is having an environment part on a control part now what is interesting is I encountered closures there are things called closures in a number of languages and I encountered closures at one point in Borland's Pascal had Delfy stuff and I thought these are not closures they're just bound methods you can't actually I can't give you a chunk of code I can simply say here's an object dot here's and here's a method and that's I'm going to pass you that bind that bound thing and that's not really that's happen yeah that's a that's re poor version of closure but strictly speaking these kind does kind of fit it's having an environment partner control part it's just that you can't do much about it it's just that you have a very restricted idea of what environment is and what control is a a pointer to a method but it must be a named method that already exists so that's very different to the lambda idea which is it doesn't have to have a name in fact we're not going to assume names the environment parties the binding of the names now importantly these ideas become a little more popular for a number of reasons John Moses creates landing with introducing the term closure to refer to a lambda expression whose open bindings the free variables have been closed while bound in the lexical environment resulting in a closed expressional closure in other words those free variables we now have a regular concept like that free-standing Y that refers to this it's not totally free standing we have an idea of scope if you like that gets passed through this turns out to be quite an important idea one that again we take very much for granted but this does also allow you to if you find yourself one is absolutely fascinating the pointless debates you know is a lambda closure or a closure or lambda there is now an answer a closure is a lambda that had free variables if it has no free variables in fact so Square for example is not a closure because it is fully self-contained all of its variables are bound it takes X it only uses X we're done okay um now the bit of history that is more important and interesting this usage was subsequently adopted by Jared Sussman and guy Steele when they defined scheme in 1975 a lexical scope variant of this variant of Lisp and from that point on it became widespread that was the kind of like the inception point for the popularity of the term it started taking it out to other people now that becomes interesting let us go back to Anton chastise Anton took his lead from his master and returned to his cell intent on studying closures he carefully read the entire land of the ultimate series this is a series of papers by guy Steele and colleagues that kind of showed how powerful lambdas were written primarily in the 1970s but that name has been taken and is used for a site that dedicated function prone land to the alternate ultimate series babe and it's cousins and implemented a small scheme interpreter with a closure based object system now this book is sort of computer science classic structure interpretation in computer programs one of those books that it's kind of everybody eventually refers to few people have read has one of the dullest titles but there's a lot of really interesting stuff in there that was by Gerald Sussman and partner and Herald Abelson interesting thing in here actually as an aside is the Maxwell's equations as it were for programming languages this is the scheme interpreter written in scheme or the heart of the scheme interpreter written in scheme this is a that's demonstrating a something we would sometimes refer to as Homo iconicity the idea of a language representing itself and this is part of the same mind-bending stuff when you first hear about cross compilers you know I'm coming across that's like how can you write a C compiler in C that doesn't make sense yeah there's a couple of extra tricks you have to get in there but the idea is let us write this one out and let us do this let us describe the language in terms of itself and translate that and then you've got the kernel and you can kind of bootstrap everything from there but it's a very profound idea because it you can see it's very simple it's a favorable font it fits on once it fits on one slide and that is kind of everything that you need to make this stuff work what is interesting is that Alan Kay did the same for small talk he wrote the basic idea of small talk in small talk his he did this kind exact Lisp ish type of thing and small talk is all about closures and this idea however whenever people sort of always talk about purity I've just done it I just did it with Excel and functional programming it turns out this thing I discovered a few years ago Dan Ingalls was some of you work with Alan Kay at Xerox PARC Dan Ingalls implemented the first version of small talk 72 now small talk is a language often touted as a very pure object-oriented language for a few people use it now very few people have had hands-on with it but its influence is is quite quite marked in fact if you go and look at Ruby a lot of that Matz was inspired very heavily by ideas that he found in small talk but what is interesting is that Darin Ingalls took the small talk version of this and implemented it at home using basic it's kind of like it's beautiful elegant object because it was a time this is the 1970s time sharing systems had just come in and what else do you have available to you on a time sharing system you didn't really have high pact and pilots he was busy working at home and it turns out that it basic was the only language available so you know you make do with what you've got now this is kind of interesting because you can actually see there's a little bit here that says lambda and that's kind of that's one of the more interesting bits there we go lambda make procedure bind the environment and do all the rest of it that's all good that turns out to be quite an important bit in a paper published in the mid-70s Sussman still point out they say well here's why we did this we weren't just inventing languages for kicks this worked fell out of an initial attempt to understand the activeness of actus Carl Hewitt that come out in the early seventies with this idea of computation the actor model and Carl Hewitt has written some crazy ideas I've read some of the original papers I ended up doing my master's degree thesis was on actors and I have to admit the call here at stuff was the least accessible and since I understand the motivation what is what is an actor is it is it an object is it oh what actually is it so they they did what a number of people did in academia at that time is if you don't understand something let's build a language to understand it yeah and this was a part of a series of languages there was a kind of a culture in the AI community back then of naming your Lisp variants after something like well one of them is called planner and other was called mapper this was supposed to be called schema you get the idea of what's going on problem is there was a six six character limit on file names so schema-less one that trim down becomes scheme hence the name scheme this interpreter attempting to mix the use of actors and list lambda expressions in a clean manner now I saw a talk by guy Steele 2005-2006 what was interesting is he talked about this when it was completed we discovered that actors and the land of expressions were identical and implementation in other words it turns out that that bit there that says lambda it turns out they had another bit and they call them alpha expressions for actor it turns out it was syntactically identical this is the joy of having code that fits on one page and they said wait a minute it's exactly the same except the names are different but other than that it's structurally similar wait a minute both mind-blown actors are Landis Wow cool so that's where it all comes from but that was the motivation so we've now just unified another paradigm with Landis at this point crook na has another walk with Anton who tends to impress his master by saying master I had diligently studied the matter now understand that objects are truly a poor man's closures quick now I responded by hitting Anton with his stick saying when will you learn closures are a poor man's object at that moment Anton became enlightened this is kind of duality here and it's one that we kind of pick up it's a rather nice paper from 2009 will you cook it's based on revisiting a paper on data abstraction and polymorphism that was a very influential in the night in 1984 Lukic art daily peter Wagner published it and William Kirk goes back to it a number points he makes but one of my favorite is lambda calculus was the first object oriented language by looking at a number of things related to polymorphism and and and so on and we can actually see this if we look at so this is seven mountains just outside Las Vegas as you can see the data structure in use here is the stack I'm going to be traditional with this so you know here we have the quote this is this is if you like this is a kind of a functions as objects sometimes called modules but and that's not that that terminology is falling out of favor but this is the purest object model that lives inside of JavaScript there's quite a few object models that live inside of JavaScript and lots of different ways of getting them but if you like this is the one that most directly represents this idea of closure and pure data abstraction and so what we see here is simply I've got the outer thing I'm basically saying I've got a name that I'm going to associate it's just the abbreviation there's no cycles here it's a lambda you call it and then you will get a new thing a new record or a new object that happens to have names accessible depth top push and pop and each one of these is bound to a lambda each one of which is indeed a closure because it's referring to a local variable items that items list is about as private as you can get it's an array that is a local variable and it's it's truly local that's bound in with the scope so it's not it's not in the sense it's not a there's not a keyword thing going on here it's it's hidden because it's hidden it's not hidden because it's inaccessible that's a difference in languages like C sharp and Java if you say oh yes we've hidden this now you haven't I can see right there on the page I can do reflection and I can see it right there that field it's there you just said you can't access it I can perfectly well see it but you just can't access it whereas here it's just like no there is nothing this is the bottom of the iceberg so this takes us to to another paradigm and a lot of people associate structured programming with the idea of go to free programming so this book was published in 72 based on work in the late 60s and early 70s and in it they make a really important point well the most powerful mechanisms of program structuring is the block and procedure concept so I'm gonna give you some code here that is based on a language based on Algol 60 predecessor of Algol 68 and what we're going to do is going to have an array of items one to capacity you couldn't have dynamically sized arrays so one to capacity or other you could not have dynamically allocated is it you can capacity as long as that's in an outer scope we can allocate that on the stack and it's got a reference to Rox and we're going to keep a count of how much of that capacity we've used just as a general point you have a nil there isn't there is then there is a null reference here this is the null reference that was borrowed from another language in the algal family algal W and Tony Hoare kind of feels he is responsible for inventing null which he calls a billion dollar mistake but this is where it comes from and then we can actually be we can we can go ahead and initialize that and because it's a proper block structured language and this is the thing I think we've also forgotten what block structured originally meant it meant that you could put anything in a block that means if you want to put a procedure in a block you can put a procedure in a block it's as simple as that there's no idea of there's a top level and you can't define nested things it turns out curiously that a number of languages are kind of caught up with this one a little bit late so c-sharp said you know what we're gonna have these kind of like you know you can have these kind of methods nested inside your methods this idea is a very very old one but that idea being able to offer operations desktop push and pop on that is interesting so that's a block of code that's your begin and end that's your open and closing curly a procedure which is capable of giving rise to block instances now that's kind of interesting because given the specialist we're talking about stacks the whole point here is that normally when you think about blocks its stack discipline you enter a block you get your variables you do you work you leave the block and that's all gone okay it's gone there are no more variables that's it that some of those objects may live on thanks to the garbage collector but they're on there that's done there is a very simple idea here what if it doesn't go away what if the block is itself a thing huh what if what have you returned the block and say look I've got a block and it's got procedures in it and it's got variables it's got state here have this you can use it and that was the beginning of object orientation the language in question so here we go which survive it's called be known as claw clasp and the instances will be known as objects of that class and classes did not have to be named they could be anonymous just like lambdas you could have unnamed classes but I'll show you the named version what I do is we take that and then we just simply add that at the top and we're done and that's where so this is this is similar 67 the first object-oriented language it's based on Algol 60 and it follows exactly that idea of why don't we take a block and then add the idea that the block doesn't go away when you've left it it can become a thing that you can refer to wow you can create a whole paradigm out of that and again the land earnest of that is it's pretty cool we could of course use any notation we want to not laugh at notations invent them they are powerful so Nobel laureate Richard Feynman made this observation in fact mathematics is to a large extent invention of better notations so let's talk about that Alonzo Church was asked why do you why did you choose lambda and there are a number of different origin stories the one that is the most rational it goes like this you've got an abstraction you basically want to say I've got a a is a bound variable I want to show I want to show an abstraction with respect to that and his original form was this it was a carat okay it's good put it don't by the way this also means something I haven't said so far and I'll state it lambdas can only take one parameter because if you forgot that notation does make sense to have two parameters you can't do lands can only take one thing and return another and that was that problem is and trust me you get a lot of trouble trying to find an a circumflex don't worry about your infinitely innumerable symbols it's quite tough if you're a typesetter in the 1930s you go like come on mate really give us a break what about that there we go that's the story that makes the most sense later in his life Church gave other stories which is I liked it yeah whim that was it you know why not yeah but I like that story because it also helps demonstrate some of the aspects of what lambda is so what are the other languages do well they took lambda and you know some of them imaginative Lee called their lambda abstraction lambda okay so this is what Lisp did this is what scheme did if you work in Python this is what Python does Haskell kind of said dude that's so verbose there we go everything you need to know that is one of the most minimal notations out there clearly you've got stuff like JavaScript came along and said we have to call it function and then you get blank just like closure so a kind of a lisp variant running on the JVM it decided to call it FN because clearly you know vowels they're bad so in some languages you get func in other language you get fun here hmm now what I consider this to be profoundly ironic it basically means that closure has anonymous functions but it has there is nothing in the language that is called a lambda what is the logo for the language a language that does not have anything called lambda there you go it's either ironic or deep or quite possibly both we get C++ is a great one this is actually you get choice of whether you want to catch a closure or not so we get square brackets now this get some great syntax this is a valid token sequence in C++ okay what it is is this is a lambda that captures nothing takes no arguments and does nothing and here's how you execute it so this is kind of so this doesn't this is silence of the Landers if you like I told you they weren't going to get any better so then we get all the language we've got JavaScript we've got c-sharp we say you know we're gonna go for this arrow notation and then you've got some other folks you know groovy and Javas like now we're gonna be more we're gonna be much more lightweight see that's much more lightweight it's just like yeah but it's kind of interesting because here it isn't Java here's the thing that does nothing well I have an interesting question how do i execute that that's a language brush in java well how do i excuse me thing but how do i execute it and we have exact the same problem in c-sharp how do i execute that it here's the thing that does nothing how do i execute that now it's kind of an interesting one cuz it actually opens up a number of issues because what is the type of the return well in the original and calculus there was only one type there are only lambdas that's it but we have grown used to languages that have a very particular vocabulary and set of concepts the languages most names that I've described so far are C based languages which have their origins in Algol you know the syntax has shifted but all of the ideas are there and there's a fundamental idea in all of these languages you have expressions and all expressions have a type clearly that's we can kind of say well you know the original lambda can't care but what is the type of that expression in c-sharp what is the type of that expression in Java these are C related languages in terms of their concepts of a category but it turns out that we cannot name weak well I just don't even case we can't name it it turns out that they don't actually have a type they're not expressions in the conventional sense the original lambda calculus is often referred to as untyped there's been a move recently people have described unit types which is kind of cool if you want to you know confuse your colleagues if you're having one of those dynamic versus static like debates and you think it's getting away from you just throwing new terminology you know this is on type oh I think you'll find it's you know typed you know it's like the type of the web is in the string yeah the type of the enterprise is the core dump you know this is there's lots of different ideas of what there is one true type but yeah shell scripts are historically you know typed around string they are streaming typed but there is only lambdas so this is kind of interesting what do we do now clearly having just untyped lambda calculus is annoying and in fact Church later developed a simple typed calculus and a number of other people kind of assume that it's just like yeah I want my convenience I want to use lambdas as a vehicle in the context of other things I don't want to have to build everything up from scratch that's a little bit yeah Baima ones and zeros together I haven't really moved to a very high level so we normally assume that there is a type system but we let's go have a look at what languages do if we go to Haskell that is our square in the shell I can go ahead and ask what's your type I don't tell me and it has a well-defined type this works with classes of numbers and gives you a result that is of the same type there you go it has a type the type is determined in c-sharp oh nope so it's C++ it has a type you cannot name the type the type is anonymous but it has a type that can be deduced and you can use it it has a type that has certain syntax associated with it if I go to python i can sit there and wrap that expression in type and i will get an answer yeah it'll tell me hey this is a function this is an object of class function but if I go to c-sharp and try and get type this does not work out quite so well for me operator dot cannot be applied to operator type language question that's it no explanation I'm sorry do not pass go but why you just can't do that's been frustrating well tell you what maybe I'll just put it into a variable yeah same dealer again no explanation you just can't do it yeah but why no I'm telling you why it turns out that you can that's one of the kind of the key distinction so this is the interesting thing it turns out that's not a lambda I mean it's called the lambda but it's not a lambda you know you can call it with what you call it fret you know I'm not going to argue is your choice of names there but that is not a language question because I cannot it doesn't support application to get it to do anything I have to do that now technically speaking based on everything I've just said this is a lambda expression that bit away from the type is not a lambda expression so there are lambdas the dart lambdas and there are other things that we don't call the Landers that our lambdas and you know what about Java yeah what about Java it's slightly well at least we got to use normal function call or method call syntax here you only hit Java it gets a bit Messier because Java doesn't have this idea it basically says you can't do any kind of there's no abstractions for operator overloading or being able to hook into that in the language that simply doesn't exist and so for yeah there's a bit of a compatibility issue here in fact there's a bit of a consistency issue that is not a lambda but if I execute it I can't just put her ends around it like a method so it doesn't behave like a functional abstraction the other function abstractions in the language it turns out there's a whole library of interfaces that I can use to wrap lambdas and I can also apply my own but those are not the type of the thing they are things you know there was the JIT LAN just used to generate something but I can then give it a type and it's a big it's a big old mess it's a big old mess and that's just the basic variants that's one and two parameters and deals with the fact that generics aren't rarified in the language there's a lot of duplication here so did they choose a consistent name given I'm not you given that we understand that normally how you call a functional abstraction is to use open parens closed parens that's one that is the one syntax to rule them all so surely they must have chosen one name one consistent name and now they didn't some of them are called apply some of them are called test some call the sect and someone will get so there are four different names actually turns out this five because if we want to do this one there's run now sometimes people said well yeah we don't we don't have enough information to deduce the types and that's quite reasonable because these expressions tend to be very light a lot of deduction needs to go on what's the return type well that's how we have to have a look what's the you know what what are the parameter types well we're going to have to look at context but I've just given you an expression that has no context it's bound to nothing it takes no arguments returns nothing it really is if you're looking for the type it's void void so there's no deduction to be done here but we have to jump through the hoops here so yeah it turns out the c-sharp and java do not support the third of the three things so they are very useful but they are not really strictly lambdas now it may come as no surprise that Alonzo Church doesn't care about any of this not simply because he is yea long since deceased but this was not the problem he was trying to solve it turns out the lambdas came out to be useful for other reasons but his original motivation was something well it was to do with numbers countable numbers innumerably infinite sequences of numbers and do they have well can we find an end to things yeah is there a finiteness to certain sequences of execution or not this is a very simple question turns out has ridiculously hard answers so this observation I've got must have forward slumped against the bulkhead and started to count to 10 he was desperately worried one day sentient life-forms would forget how to do this only by counting could humans demonstrate their independence of computers so of course remember I just said right back at the beginning and I've kind of none cheated it every now and then if you do pure lambdas there's no numbers because there are only lambdas can you go do arithmetic when you've got no numbers well the answer is obvious you invent them you know you create your own numbers so we're gonna start with nothing and this is in fact the curiously enough Church did not you need a zero in his original paper but here's a zero and I here is a lambda that takes two parameters effort an X X is itself actually a function but I'm just choosing names that look a little more obvious and here we're not going to apply F to X we're just going to return X with one we're going to apply it once to X with two we're going to apply F to the result of F to the result of X with three we're going to so you see what's going on here is what we've done is we defined our numbers as the application of a functional thing an application of a lambda to something else and the number of times we apply it repeatedly is the number that is the thing that is how we distinguish it so four is equivalent to that five and so on I won't go in numeral infinite on you there are a couple of observations we could write it like that there are some shorthands in fact to be consistent we could write it like that I'm not going to do that here I want the full form also I told you that lambda is strictly speaking only take one parameter but it's a shorthand and it's in the original paper that you can basically go oh lambda FX that's understood as being lambda F got lambda X and notationally that's convenient it just means that everything is curried if you've done highschool or looked at all this kind of stuff all that's for free that was built in but I can use this long form cuz it makes it a lot easier to turn this into JavaScript now I know if those of you who work JavaScript already know that JavaScript has a really weird idea of numbers so we're not missing anything by skipping it so here we go I'm going to have underscore 0 a so the thing things nice about JavaScript choice of notation is this is actually one of the lightest I've done this in a number of languages because I have a certain masochistic streak and honestly JavaScript is one of the easiest to do this it's syntactically light and you can really see when you've gone wrong but yeah so basically we've now recreated the number system awesome but how do we know that it works well what is that this is a thing that does stuff we aren't actually defining or we are defining numbers by and/or as it were application this is the thing that doesn't apply a thing what's it not going to apply well I'm gonna plug in some good old-fashioned JavaScript I'm gonna take an increment you receive an argument and you add one to it and that's your result so we're not going to apply that because it's 0 and what is it that we're not going to apply it to well I'm going to use the original 0 in the language so we're not going to do that and what's the result of doing this 0 it's a JavaScript 0 what happens when we do it once one applies F n becomes n plus 1 once which gives us that and then we see so in other words the numbers these are this is called the church encoding these are church numerals which of you here if you read that out of context it makes you think since I talking Roman Catholics here what are we worried over here Church numerals so these are church numerals this is a really cool idea it's moderately insane why don't have curacy enough one of the best best explanations of it i came across was in shadows of the mind no no emperor's new mind by roger penrose which is a book about why it is that we will have create consciousness and a bunch of quantum mechanics and stuff but and ultimately you tend to think he's got a very he has a great mind but he's gone wrong but it has one of the best explanations of this and i think this is one of the first places i encountered it's just ok so numbers can be considered to be the act of applying something to repeat a number of times that's really cool ok um let's go back to our friend square so here's a really simple way of implementing it we take a thing if 2 2 is is the tunis of something i'm going to take em and I'm gonna apply it to em huh so that's squared I'm gonna apply em to em how many times well that's twice it's no I'm gonna do that what happens if I put seven in well seven is a thing that's a counting thing so I'm gonna apply seven seven times and seven does seven things so huh this is really cool because we can now apply this straight to start with zero and the answer you've been waiting for since the opening minutes of this talk yes it is 49 okay but we've just recreated numbers now why stop there why stop there 19th century let's go back to the 19th century when we thought we could solve and know everything was knowable everything was logical Victorian engineering it reaches Peaks like yes the world can be understood through engineering through mass we will you know everything will be understood and the optimism is apparent in this gentleman's book title very very these days people just refer to it as the laws of thought but clearly this is Victorian era people still in too long book titles and investigation of the laws of thought which are on which I found the mathematical c et cetera so there's beautiful optimism that actually we think logically come the late 20th century that that edifice was torn down hugely it turns out that logic is the thing that you learn we are a mess logic is a tidiness that can only be acquired through education by our default state is to be messy and irrational I refer you to the activities outside was evening so what did he do for us well he basically formalized propositional calculus and you know we live in a post truth era so I thought I'd just show you this just so yeah before you lose sight of what it is and false you know what you can church and code this I can apply it so lambda a B truth is a falsehood is B so I'm now got shrim Fosters pretty cool if you look carefully although I've used different names you may recognize this if I did this as f and X you may recognize this as zero so for all those of you wondered is false zero is that is that just a programmer thing no it's actually built into the foundations of lambda calculus that zero is false so next time you have one of those debates depending on where you stand on it but if you ever need to justify your gratuitous abuse of a language feature and this happens to have been what you've done you have a justification for it just refer them to the paper they'll never get through it it's our friend small talk and what it's small talk well this is the whole thing small talks idea of what is truth and falsehood is not there is a symbol called true and there is a symbol called false truth and falsehood do different things so truth does one thing this is polymorphic if I give a and B to a thing that is true I will get a back I'll get the a part so I'm basically created the basically if-else here which is kind of neat so we can take this a bit further it turns out you can get really carried away with this pair was originally introduced so pair is you take an ax and a Y and then you bind them together with an F and you kind of glue that together you can pass it around you can pass it around to an operation first which will return you the X well I'll pressure second which will return you the Y if you look very closely at those you realize that first is basically pair true second is pair of false this is quite nice all you need to do now is add nil and you just reinvented Lisp so it's ridiculously powerful for words I'm not suggesting that you got to go out and just like just say look don't worry about the optimize will take care of it I'm go I am NOT going to use these mere mortal numbers and integers that you you've been talking about using you that domain-driven design thing of yours we are going to build things from the purest of the pure you know oh you mean you're gonna use zeros and ones serious once do we're gonna use landis we're gonna make our own zeros and once this is the craftsmanship movement we make our own zeros and ones finely-crafted so I'm going to end with a exploration of one of the most teasing challenges fizzbuzz what was interesting as a number of years ago I guess it was about ten years ago I was reading a piece by Tom Stewart and it's called programming with nothing and I suddenly realized I know what you're doing it was a ruby piece and Tom solved it like this now this is not a language you're familiar with and I just said Ruby well what did he do well what he did is he basically programmed with nothing he had those three properties I can have a name of a thing a variable I can have lambdas and I can apply a lambda that is it and he built up and these are all the abbreviations so he built up all of these concepts he built the numbers 3 5 50 100 he built logic he built iteration he did the whole thing and you can find that on blog programming with nothing but he also included it in his book understanding computation he also included the full form if you expand it from the abbreviations that's what it looks like you know it is one of the crazier versions of fizzbuzz I have ever encountered yeah yeah this is it yeah this is the kind of stuff you give to somebody could you just work this one out for me you know I I need some more detail here yeah good luck debugging that by the way so we found is this idea of lambda it was in one sense of mathematical curiosity it helped solve a problem it was shown and it was to do it the fact it was such a simple formalism that even numbers could be encoded in it and it had rules of reduction and therefore you had very simple operations it turns out integers on their own are surprisingly hard we tend to think it was quite easy there's a whole load of stuff it's the idea of what I want to understand certain sequences if I can encode everything in the simplest form then I can provide proofs about it and this turned out to be incredibly convenient but this idea of an abstraction that was not about things but about doing if you like it's about functions that's not the usual candidate for this stuff we normally mass was always phrased in terms of of objects or things not objects in the arrow sense but of things of entities here we are talking about something that is much more intangible a much more first class idea a function rather than function being a convenience it was actually a thing and we can reduce everything down to that so there is nothing else and this proved to be surprisingly powerful so powerful in fact that when people started thinking about well what how do you build up simple languages how do we do this this idea freestanding functions whether we take it at its rawest level or start saying you know if I know how to just pass a piece of doing stuff to us around rather than having to name everything you only I could just create everything and just pass it around and we discover that that's actually been infused in a number of different paradigms obviously there is a natural home in functional programming for this but what we first see is that that is not restricted to that that every paradigm has ultimately ended up claiming it as its own because of that convenience so I hope that has been thought-provoking and that you managed to stay awake and that is provoked some thoughts in you maybe you can just gonna go home and drink that away or maybe you're gonna go home and say alright ok let's just try this I can do this let's try a little bit church encoding COBOL yeah yeah but yeah good good luck with that thank you very much [Applause]