Using and Abusing Ruby for Computer Science Great Good

Brice Fernandes speaking at Sheffield Ruby User Group in March, 2017
148Views
 
Great talks, fired to your inbox 👌
No junk, no spam, just great talks. Unsubscribe any time.

About this talk

A live demo talk, where we will playfully take a tiny subset of Ruby and explore how far it can be taken and what can be built by exploiting a single language feature. In the process, we'll learn about (or revise) some interesting computer science and explore a less common paradigm of programming.


Transcript


So the idea's that we're going to take Ruby and things are going to be happening to the language and we're going to be left with something else, something inside Ruby, and then we're going to do some stuff with that little bit of inside Ruby. And so the reason I'm giving this talk is really because it's one of the things that introduced me to kind of the more interesting aspects of computer science. I didn't do a computer science degree, I went into programming from a science degree, so I didn't know any of this before, and I found it really interesting and really fascinating. And what I want to do is share that with you guys, share that moment of kind of this bit really interested me and got me to learn a lot more. And also I'm kind of paying my dues. I learned a lot on this topic from other people and I'm kind of sharing the good word, so to speak. I'm kind of being an evangelist for those ideas that I don't think have enough of a foothold in kind of everyday programming. So it's a fairly abstract talk. Don't ever try any of this stuff that we're going to try tonight in Production Systems otherwise, you will be fired. But besides that, you should have some fun. So while this is happening I just got to ask some questions. Out of you, how many of you did kind of computer science, studied computer science formally at university? Cool. How many of you have heard of lambda calculus? That's good. Church numerals? Okay, that's even better, that's great. So this is basically what we're doing today and it's out of chapter six of this book called, "Understanding Computation." I highly recommend it. It's all in Ruby which is kind of why it's relevant to us for the [inaudible]. But it's kind of not really about Ruby, it's about other things. And if you've seen that talk you probably did a better job that I'm going to do so I'll put a bunch of references at the end of the talk where you can find kind of other people's take on the same ideas and other resources that I'm going to mention. So that's kind of why I'm doing this talk. So I'm going to start with a story, right? The first thing is the state of the world that it is today. We live in this tower of abstraction, these beautiful gardens, and we have our objects and our methods, and we're very proud of what we do and we can do lots of things with them and we're very productive and we build websites and applications and mobile apps. And this is great, life is good, and we're very proud of what we've accomplished, kind of tamed the gods within the machine. However, we kind of started flying too close to the sun and the god of programming decided that we were too proud and our hubris, he is going to cast us down, he's going to throw is down and salt the earth behind us so that we can never use our tools again. And so we find ourselves in this weird and wonderful dimension where there is nothing for us to program with. And we are cast down in this darkness, the place where people who talk at the theater are. And so we're here and we look around and the only thing we can see is this weird construct out of Ruby. So everything else in Ruby's basically disappeared. The only thing we're left with is the proc or the lambda. There's a differenve between the two in the language, but it doesn't matter too much for this talk. So that's the only thing we have. So out of you, how many of you have actually seen something like this in your code somewhere? Okay, one. There's many different ways of kind of saying a proc, you can expressively say proc instead of using the square bracket to pass in arguments. So this is basically just a function call, this is the argument that's passed in. You do some stuff with it and you pass some value into the proc. So you can do proc.new to create one instead, and you can do .call to call the function, but its basically just a function, right? There's nothing else there. And not only is it just a function but in his wisdom, the god who cast us down has decided we can only have one argument in our function. So this is what we're left with, we're left with a function. And what I mean we're left with a function, that's everything we have. So our arguments must be procs and our output must be procs as well, so that's the only thing we have. So what can we do and what's going to happen if we only have procs to play with, right? What can we do? So let's take a look at procs occurring as a couple of examples before we get started properly. So let's take a look, right? We have only the proc and so let's say we have some proc, we can do X. So this is an imperative X. And let's say we want to create a square function, right, we square something. And this is our proc, so it returns itself, it's a proc. We can name things, we can give things a name, right, this is allowed. We can just say this bit of code over there is called Bob and then we can use Bob somewhere else, that's not kind of cheating. So we can call this square, and again, so we've got our square function and I'm just going to call square with some argument, let's say square[4]. Now, of course, we're not allowed to do this, right? we're going to be kind of chastised for doing this because we don't have times right now, we don't have multiply, multiply doesn't exist. The only thing we have is a proc. So there's another kind of twist to it is we can't do this, right? Usually, in Ruby, you might be allowed to do x, y and then you can do x*y and then you can call it with say [2,3] and you get six, right? We're not allowed to do this. We're only allowed one argument. So what we can do is actually wrap a proc up so that every proc takes one argument and we change it so that we've got a proc that returns a proc that does the actual multiplication. Close the first one and then we call the first proc with the first value of X and we call the second one which is wrapped up with three and we should get six. So this is basically currying with turning multiple argument functions into single argument functions. And you've got this in Ruby, there's a bunch of operators that let you use occurring and stuff in the language. So that's what we're kind of left with. So once we've got those two things, right, what do we do now? That's all we've got. We're not even allowed to use multiply yet. We're kind of lost in the woods. Where do we go from just those two procs? And so, where I'm going to go now, the direction I'm going to head is towards basically these constructs, right? So the first one is IF, that allows us to make decisions, it's kind of basic. Lists we can kind of collect things into a list that's useful. First and rest that's kind of manipulating a list so we can grab the first thing in the list or the rest of the list. Boolean TRUE and FALSE. If we can make choices based on boolean, we have to kind of have a boolean thing to make a choice on. Equality we need to be able to compare numbers in particular. Pairs, which are kind of how we're going to build lists up, it's kind of the basic construct of lists. And then some boolean kind of operators OR, AND, NOT. And finally, integers and math, right? We need some integers and we need to be able to do some math with them. Now, we obviously don't have any of this yet. Ruby does but we're not allowed to us them. So why did I choose this set? And the reason is, you can actually build an object oriented language out of this. I've shown it in another talk and you can kind of find the references. You can take it as given but these constructs are sufficient to build an object oriented language. So we can get back to Ruby eventually by just these constructs. There's kind of one that's not quite there but mostly, that's all we need to build an object oriented language. So the first thing we're going to do is Truth & Logic. We want procs that are TRUE and FALSE. We want to create something that represents truth and something that represents false. And I'm not going to tell you how. You're going to have to figure it out. A proc that takes A and B or two procs, one wrapped inside the other. When the proc is called TRUE, it'll return the first thing. When it's FALSE, it'll do the second bit, that's it. And now that's the first thing you have to implement and then once you're done in 5 or 10 minutes I'll come back and show you kind of an example. So that's it. Any questions about how this done? You have to create a proc, so just to remind you, the proc syntax is this, and you have to name it TRUE and FALSE. Okay, how did everybody get on? Did you manage to get a proc that kind of does this thing? - [Male] I got a proc. - You got a proc? Okay. - [inaudible] two components. So I've got proc T equals proc that accepts A and then [inaudible] B inside and returns B or A. - Yeah, really this one is quite straightforward, it's just to get us started. It's fundamental. The truth bit is quite, yeah, the truth is pretty straightforward. This bit is basically what we're looking at. And I'm going to hide IF. So if you can't see this bit, right, TRUE takes A and B and returns A, FALSE takes A and B and returns B. So this is really just exactly what you'd expect from the description just translated into procs, basically. Can you see that bit? Cool. Definitely not, yeah. So literally just this bit. Don't worry about this. This is just a helper. Cool. So I'm going to paste this stuff into my interpreter and we can try it. Pretty straightforward. Right? SomethingElse. Don't worry about what Something and SomethingElse are, it doesn't really matter right now. Okay, cool. So we've got our truth, right? We've gone TRUE and FALSE, I've just shown you this. So we have our boolean kind of values, we have TRUE and FALSE in our code. We've defined them in a really strange way, which is like they're procs that take two arguments and return one or the other. But we'll see kind of why that makes sense later, and I think that's the only thing we can do with procs, right, it's the simplest thing we can do is return an argument. So what's next, right? Now, we have Booleans. The next step is kind of actually logic, making decisions. So we have NOT, OR, AND, and IF that we need to use. So the first thing I think I'd like you to try is to build IF, right, the IF function. And IF will be given a boolean, the condition, and then we'll return either A or B depending on where the boolean is. So we're kind of wrapping our boolean around something else that will kind of do the same job but it will be important to kind of get us to start thinking about how procs are going to be used inside of procs. So we have an IF, that's going to be proc IF and let me jump in the shell to show you. So we'll take some proc IF is going to be equal to...and it'll take a condition. And then inside of that will have a proc that's going to be a...so this is consequence and then inside of that we'll wrap a proc that's going to be the alternative, and then make sure I've got everything balanced. And the alternative something inside of there and that's what you have to write, you have to write what's to replace the three dots here. So we've got an IF, the condition, consequence, alternative. And if the condition is TRUE, you want the consequence to return, if the condition is FALSE, you want the alternative to be returned. Cool, so that's kind of the first task and then move onto like the boolean operators. AND, OR, and NOT are the ones you want to hit once you've done IF. Your turn. Start with IF, AND, OR, NOT. Use numbers for the two others if you've got the true and false that you've created, you can cheat and use numbers. Okay, so we're kind of working with IF right now, we've tried to build IF from scratch, right? We want a function that does IF. Now I'm going to jump into... I'm going to do this in the interpreter. So the first thing that you should know about IF is it's a proc and it takes an argument, and the argument is a condition. And we've only allowed procs, so condition must be proc as well, right? So it takes a condition, that's the first thing it takes. Then we've got... It also takes a consequence so I'm going to shorten this to c, consequence, and alternative, right? So most of you got to the point where you had the idea that you would have a consequence and an alternative with something here, right, something blank before the consequence and alternative. You get the idea that something would be called with the consequence and the alternative and that would kind of return the right thing. And some of you tried to put TRUE in there and it didn't give the right behavior because the condition no longer mattered. And some of you tried to use FALSE in there and it didn't matter because the condition was not taken into consideration again. So the idea here is that you're going to use your condition, the condition itself is going to be used as a proc with two arguments. So here in that call when it goes c, cs, alt. So condition, consequence, alternative. The condition is a proc, the consequence is a proc and the alternative is a proc. And you're passing consequence on the alternative into the condition just like you were doing above, right, when we were trying TRUE and FALSE. But we just don't know which one to...told, it's told which one to use when it gets given the... So the idea is IF, condition, consequence, alternative. We call the condition on the consequence on the alternative and that gives us the right thing. And I kind of unexpected tSTRING_DEND, that's not quite what we wanted. Yeah, that's better. And then if I do IF let's say TRUE. And here I can put anything I want but I'm going to do Something and SomethingElse. We don't have anything else, right? It's Something and SomethingElse are things I've created just so we can have a nice response on the interpreter. And we get Something. And if I do it again but this time with FALSE, we get SomethingElse. So I'm just going to jump into a nicer kind of format that syntax highlighted. Now we're in IF. Right, so this is IF kind of nicely laid out and syntax highlighted. So you've got IF now and I'm keeping this fairly quick because we've got some ground to cover before we can cover everything else, right? So now it's your turn to do the boolean operators: NOT, AND, and, OR. And you'll need to think about kind of what it means for the value TRUE and how you would change that and how you would kind of combine two TRUE values together or two FALSE values. And kind of how do you do AND, OR, and, NOT? Right, your turn. You can get an IF solution working that is perfect because the IF solution is guaranteed to reduce down to the same thing. So whatever happens, no matter how you solve the problem, it'll reduce down to the same function in the end because they have the same meaning, so it doesn't matter how you solve it if that makes sense, which is not a property of other programs. Nice, yeah. So for the interest of time, I'm going to go through them now because we've got a lot of ground to cover. We're only kind of on booleans but there's no magic, I will show all of the stuff that I'm building and you'll always be able to go back and take more time to understand these functions. It takes a while. I think it took me kind of multiple years to eventually get this stuff so I can kind of recall it easily. So don't worry too much because we're going through a lot of ground very quickly. So let's start with NOT. NOT is you get a condition, which is a boolean, and you just inverse its inputs and that's it, and then you'll get the right thing out. So A could be FALSE or TRUE and then you're going to call A with FALSE and TRUE reversed to the usual position and NOT will work as you expect it. So let's try it. So let me copy and paste this stuff into my console. So if NOT FALSE, that would be TRUE. I'm expecting the first thing to come back out. And we get Something, right? If I used FALSE directly without inverting it I get SomethingElse. So what you'll notice is actually a lot of the kind of the end product is quite a lot simpler than you were going for. Those kind of boolean functions can be quite straightforward in the code. I know a lot of you tried to nest conditional, IF conditions and stuff like that. The actual function is quite short. So let's jump back into...so we've got NOTs, let's do AND. So AND will take A and B and if A is itself, a condition, it can do stuff, it's a proc but you can pass stuff to it. B is also TRUE or FALSE, so that's good, that's a good sign. So you can... - [Male] The only difference I've got I put IF on A and IF on B, like that was square. So could you see the same result? - If you've got the same result, it's the same function so don't worry about it. Behavior is the same, it's the same thing. - I used the IF function on IF on A and IF on B but it still produces the same stuff. - Yeah, exactly. So you've wrapped an IF here and an IF here, right? Yeah, just remember that these things are both values and procs, right? So B itself is either TRUE or FALSE as a value, and A is also TRUE or FALSE but it also procs. You can do stuff with values, which is great, right? Value and function kind of disappear, it's all the same thing which is one of the kind of key point to take away here is that's the value but it's also the proc, it's also a function. Cool, so that's AND. OR is basically the reverse. So if A is TRUE then it's guaranteed to be TRUE no matter what B is, and then if it's FALSE then it's going to be whatever B is. So you don't need to wrap it in all those IF statements. You can use them as procs themselves directly. And if you want XOR, XOR gets a bit fancier but it's still the same idea, it's still kind of...you're still... XOR will look very like OR, the oly difference is that instead of just returning TRUE no matter what, whether it's TRUE will also depend on kind of B. So you can have A and B being TRUE because it's exclusive. So that's kind of the more complex boolean function. Okay, cool. So we've just demoed that. So now we have Booleans, AND, NOTs, and OR... IF Booleans, AND, NOT, OR, etc. So the next step are Data Structures, right? We want to build stuff, we want to put these booleans lists. Let's say I want to represent A binary stream of ones and zeros. I want to be able to do that with this PAIR language I'm building. So I want to be able to have a structure that keeps ones and zeroes or TRUEs and FALSE in a list, in a collection. And we start by building pairs. So pairs you can think of it as just left and right, it's just a pair of things. So we need to construct a pair of things. Now, we only have procs, right? So we need the PAIR, the proc to take in LEFT and RIGHT and then return a proc. So this one is kind of...what's the right word? A cognitive leap into how you're going to be building this. If you've heard of closures, a pair is a closure if that helps. Otherwise, try and create those three functions. PAIR, LEFT and RIGHT they will work together and the output of PAIR will be taken in by LEFT or RIGHT as procs if that makes sense. So it'll be quite familiar to the boolean functions actually. You'll see the similarities for the Boolean functions when you kind of run through this. So that's kind of your next exercise, think about pairs. And what I'll do is I'll put the code up of the boolean functions back up so you can have a look. You can also if you aren't sure of anything, want to reference, come here and have a look on the computer for the entire thing. So next exercise, creating pairs left and right. There is no spoon, right? You're going to have to return a proc because you don't have anything else to return. So you're going to return a proc that kind of needs to remember A and B and then the proc that you're returning will give kind of A or B depending on something. - [Male] It's almost like, or it feels like you want to return...[inaudible]. So what pair do you have to return worth value? - So PAIR doesn't return worth value, PAIR returns a proc because you can only return procs. And the proc you're returning will then somehow either return the LEFT or the RIGHT value. This one is a bit of a kind of twist and it's annoying because I don't want to take away that moment when you realize how it's put together which is kind of why I'm not showing you, I'm asking you to figure it out because that's quite a nice...when you realize how you can build stuff out of complete thin air, that's quite nice. Okay, cool. I think everybody's either there or getting there so let's go through it, right? So we have our PAIR, A, and B. And what we're actually going to return has to be a proc, right? The three dots we're going to be returning there's no other choice, we only have procs to work with. So we're going to take some procs and we're going to take the choice which is LEFT and RIGHT, and then we're going to... So inside that proc then we're going to use that choice to select which element we want. So that's going to be choice[A]...let me get my case right. Or [B] What's it complaining about? Formal argument cannot be a constant. I just need to lowercase my A's and B's probably. Right, so now I've got my PAIR I can do PAIR say Something and SomethingElse I know a lot of you are using numbers which makes sense, right, it's a lot shorter. I'm using Something and SomethingElse. - [Male] One character. - Yeah, but just to kind of give you an idea, you could be anything, you could be choosing between two functions, right? Do I kind of brew coffee, do I brew tea? It doesn't really matter. And so we've got our PAIR and now the PAIR, right, is going to be a proc and we pass in the choice. So I could do it manually. So let's say I want Something, Let me just go up. I could pass TRUE to my PAIR, right, and get Something and then I could pass FALSE to my PAIR and get SomethingElse. Now, the idea is that this is not the LEFT and RIGHT function, right, it's not what we're doing. The LEFT and RIGHT function need to be called like this. LEFT of PAIR of Something and SomethingElse, right? That's how we're going to be calling the LEFT and RIGHT function. So the LEFT function is really going to be taking a pair and we're going to pass TRUE to the pair, right? So now I can do...if I give it a name. Right, we've got our LEFT function. I can now do LEFT of a PAIR and I get one. Right is basically the same except I pass FALSE. RIGHT, and as you'd expect, if we call it, we actually get two. And I'm going through the actual motions of going through and showing how it's all working just so you know I'm not kind of just pretending, this is kind of all built from scratch in the console. So now we've got pairs, we've got LEFT, RIGHT. We've done LEFT, RIGHT. We have IF's so we can make choices, we have Booleans so we can represent TRUE and FALSE, we have Boolean operators, AND, NOT, and, OR so we can kind of combine both values. We have pairs, we can create a data structure that has just two things in it. And right now, those two things can only be TRUE or FALSE. But actually, what we're going to do next is we're going to move to using pairs to represent something more complex because instead of having a pair of TRUE and FALSE, I could have a pair of pairs. So we can create a tree, or we could have a pair of a value and another pair, which builds a link list which is what we're going to do now. So the idea is now we're going to create the representation of a link list, and a link list is constructed by having multiple pairs. Now, this shouldn't say CONS, that's my bad. That's just a lispism. [SP] That should say nested PAIRS, right? So we have lists and nested PAIRS and the end on EMPTY. And EMPTY is a pair where both are TRUE. So we want functions to be able to manipulate this data structure. We want HEAD which kind of gives us the first element, and REST which gives us the list that remains after you've taken HEAD away. And finally, we want IS_EMPTY which checks whether something we give it is empty or not. Cool, it's your turn. - [Male] Woo-hoo! - So EMPTY is a pair with TRUE and TRUE. Lists are nested PAIRS, and I'll show you an example of a nested PAIR. So I have a PAIR where the first element is say, [1] and the second is a PAIR where the first element is [2]. And the third is a PAIR where the third element is [3] and then I finish my list with an empty PAIR, which is a PAIR with TRUE and TRUE. And I close that parenthesis, I close that bracket, that bracket, right? So this is kind of a representation of a list with 1, 2 and 3 in it. So it's kind of nesting the pairs within each other. I'll come round and I'll kind of draw a quick diagram to show you this in a visual way, it's a lot easier to understand this visually. Cool, so now you've got to...once you've got this thing, and you can give this thing a name. My_awesome_list is this thing, then you want to be able to call HEAD on it and get one and TAIL on it and two, three, and the EMPTY and the... - [Female] REST. - That's right. So REST/TAIL I don't care how you call it as long as it does the right job. Your turn. But we've got a link list, right? What we're talking about here is a straight link list. We've got the first kind of item is a PAIR where the LEFT element is the item in the list and the second element is another PAIR which has the other item in the list and so on until the EMPTY, the end, the EMPTY list which determinates us kind of how you close a list which is a PAIR with TRUE and TRUE. So if you've done computer science, you've probably seen a link list represented like that before. Cool. And note, this is just an example of how to use pairs. We're building lists but we could be building trees instead. So that's what I meant. It's basically what we're dealing with is just a link list. You've probably seen something like that before. A list with two elements, Something, and SomethingeElse and at the end we've got a determinator which is a PAIR with TRUE and TRUE in there. And that's it. So you have to figure out how to tell whether something's empty or not, basically. Okay, I think we're going to bring you back. We've got about 20 minutes left and we've got a couple of things to cover. So we've got a bunch of examples, it's kind of reusing what you've got before. So let's jump into our interpreter. So you've got it here. LEFT[PAIR[1][2]]. You've gone through the LEFT and RIGHT. Let's create a list. So my_list is a PAIR of [1] with a PAIR of [2] and this is the original list we had. PAIR of [3] and a PAIR of EMPTY or PAIR of TRUE and TRUE. No, I could just define TRUE, TRUE to be EMPTY or NIL or the EMPTY list or something. Let me make sure I've got the right... [1], [2], [3] And if I want to create the HEAD function, that's just going to be the first element of my list. So HEAD is kind of the LEFT of the list, so HEAD will take a list. L which always has to be a proc. And we're going to be returning the LEFT of the list. That's right. And if I do HEAD[my_list] I'm expecting one. What have I done wrong here? - [Male] I think my_list expected an extra square bracket. - Open, close. - That's what I'm doing. I don't like lists. - [Male] One, two, three. - Yes, you're quite right. I think that was it. Still not. - [Together] [inaudible] bracket. - Oh, sorry. That's better. Yeah, I've not defined it. Thanks. The joys of live coding, right? And TAIL is going to be basically kind of the LEFT side of my lists so we can just do that. And then I should be able to do TAIL of my_list and if I do the HEAD of the TAIL I should get two. I'm really hoping... Proc into Integer, where is it complaining? - [Male] Is it not TAIL on the RIGHT - Yes, thank you. Yeah, that would make sense. Right. Yeah, here we go. Great, brilliant. Awesome, thank you for doing that for me. So now we've got the IS_EMPTY and most of you figured out you can do IS_EMPTY by checking that and the LEFT and the RIGHT are TRUE. And then we can do IS_EMPTY is a proc that takes a list. And we'll return AND [LEFT] of the list and the RIGHT of the list. So IS... - [Male] Something to do with bracket. - Is that... - [Male] It's the bracket on the other end. - After the RIGHT. - CTRL+C. - Yeah. - Yep, that's right. Just testing you're paying attention, honest. - Of course. - So IS_EMPTY of an EMPTY list, so. And I've not got AND defined for some reason. Let me grab that from here. - [Female] You want the one above first. - Nope, that's right. And then if I do say [1][2] I'm expecting one because the IS_EMPTY's going to be returning a boolean and I can do that, I can kind of prove it so to speak by using a little utility function. So I've got a utility function at the top somewhere in my code. There we go, to_boolean. To_boolean will take what we're creating and kind of give the value in Ruby, in Ruby terms. And then I can pass IS_EMPTY to my to_boolean and I'll get the actual boolean value in Ruby language. Great, and that's what we expect. Good, it's all working according to plan, honest. So let me jump back into my presentation. So now we have...we have IF, we have Bool, we have AND, we have PAIR, we have OR and NOT and we have the list, first and rest. We've built all this stuff. Now comes kind of...we are going to jump up again into kind of the complexity we're dealing with. And I think what I'll do is I'll probably go through them rather than give you the exercise because we don't actually have that much time left. So the first thing we want to do is actually integers. And this is kind of the interesting bit is how we represent integers using procs only. So the idea here is that we are representing just the kind of zero, one, two, three. We're not doing negative, we're not doing floating points. It's an interesting exercise to figure out how you can build those things from the base integers, from the natural integers. But I think that would take way too long. So not for an hour talk but it's something that's quite interesting to look at as well. So the idea here is that we're going to represent numbers and we're going to represent a number has the number of time a function is applied to some value. So let's say we have the number three. What the number three really means is we're doing something three times, right? So the number three is going to be a function applied to a value and then the same function applied to the result and then the same function applied to the results. So you're applying the function three times repeatably on a given value, and that's represented here. So ZERO...given a value, will just return the value, right? It's given a function and a value and it'll just return the value without any change. ONE will kind of return the value transformed once, TWO transformed twice, etc, etc. So let's...into our console and show this. So we've got ZERO and we can define that as a function. So it'll take a function and a value and it'll apply the function ZERO times. So the first thing we take is a function, the second thing we take is some value, going to call it X for some number. And we just return X, right? We're not applying F to X at all here. - [Male] Equals. - Thank you. I'm glad somebody's watching this code, right? So we expect zero if we're giving say the function prints something. If we pass F as print something and X as any value, we'll just get the value back and nothing will be printed, right? We're never applying F ever to our X. Then we have ONE and ONE can be defined as a same idea, right? We take a function and a value and we're going to apply the function once. So we take a function, we take a value, and we apply the function once and so on. But I don't want to define all the integers like this, this would kind of get really tedious so I want to create ADDONE, right? I want to create the function ADDONE. And because I'm getting tired I'm going to jump straight to the... Cool. So ADDONE is here and I'll copy and paste this into my console. So the idea here is we're getting a number N, that's what we're passing in, and we're returning a number. And we've come to find that API for numbers to be something that takes a function, and a value, and applies the function a certain number of times. So here ADDONE we've got the function, we've got the X, we've got the N, so N could be 44 times, right? So this [n[f][x]] could be F applied to X 44 times. And then we're just applying F once again. So ADDONE just applies F once again, right? So just based on this definition, can one of you tell me what would ADDTWO numbers look like? If you're using ADDONE and your number is doing something repeatedly, how would you build ADD number A and number B? So I'll prove that ADDONE works right, while you're thinking. I've got a little helper function here as well that turns my integers into Ruby integers. So I can do to_integer of ZERO. Wrong number of arguments to_integer, yeah. ZERO, and if I put ONE I've got 1. And if I do ADDONE to ONE I get two, right? This is what we're expecting. Now the question becomes kind of how do you add A and B? Has anybody kind of figured that out? Okay. The idea is a number is a proc, right? The number is a proc that takes a function as its argument. And it'll apply the function N number of times. So how about we give number A the proc, ADDONE and we apply ADDONE to number B? So number A will do the work of actually adding one to a number, it'll actually do all the work for us. So I'll try it from memory, if it doesn't, I'll just jump into the crib sheets. So ADD is a proc that takes a number A and in number B. And the idea here is that we're going to apply ADDONE to B, A times. So we can do A. So let's say take A, apply ADDONE to B, A times. And fingers crossed this is going to work. Yeah, there we go. Cool. Right, so we've got addition, we can add numbers together, A and B. And this relies on the fact that numbers aren't just values, they're also able to do stuff, right? So the work of actually doing something A times is actually done by the number A. We cannot delegate. The ADD function delegates all its work to the numbers themselves because numbers know how to kind of carry out an operation a number of time. So we've got ADD. The next one we want is MULT, so like...subtraction, right? We can add number, we want to be able to subtract numbers. Note here, if we subtract five from four we're going to get zero, right? Our kind of number range stops at zero, we can't go below zero in our number system. That's a massive limitation but using that you can build other things afterwards. So to subtract two numbers, and I'm definitely going to use the crib for that. This is actually probably the most complex function we're going to be dealing with, and we use it the same way we use ADD. We are going to create MINUSONE that decrements a number and then going to apply it N number of times. So the same way we did ADDONE N number of times, we're going to do the same with MINUSONE. So the logic for MINUS is actually quite straightforward, but decrement is quite difficult to get your heads around. I will say that this takes time and I don't think we have kind of a lot, and this is the most kind of complex dense bit of code we've got here. If you want a great definition of this that's a lot more user- friendly, "Understanding computation" go through the steps to derive this. But basically, there's nothing up my sleeve. This is what I want you to walk away with. I've not taken some stuff from Ruby and added it sneakily in the back. This is pure procs, right? There's nothing here that comes from Ruby, it's pure procs. So let's try MINUSONE and let's try and see whether that works. So to_integer and we've got to. So we're going to do TWO and MINUSONE and we're expecting one and we get one. Once again, like once we've got MINUSONE it's not really easy to build two numbers minus the other, you just take the number you're minusing and you do MINUSONE N number of times. So let's grab MINUS and it's the same construction that we have before, right? That's it. And just to kind of give you that MINUS actually works. So say MINUS TW and ONE. I'm expecting that to_integer to be one. All working. So we've got numbers, we've built numbers, we've shown numbers. Now we're starting to move onto the math bits. So we've got ADDONE, we've got ADD, we've got MINUSONE, we've got MINUS. MULT and EXP are interesting kind of to see that they can be built quite simply as well. EXP, in particular, is really straightforward. So let's do MULT first. So let's grab MULT. So MULT takes two numbers, A and B and returns a number. And remember, the number API is I take a function I apply N number of times. And what the N number of times is B so instead of just applying F, A times on X, we're going to repeat F, B number of times. And that's basically what multiplication is. You're just kind of doing something. You're adding a number N times so this is what this is representing. We're adding B kind of multiple times. A times B. As I said, not too worried. The kind of key takeaway here is nothing's there, it's pure procs again. So we've got MULT and if I do to_integer of say MULT[TWO] and [TWO] we get four, right? So this is quite an exciting four considering all the things we've put into it at this point. - [Male] Two hours later. - Right, yeah. Exactly. So now we've got multiplication and EXP is quite neat because it kind of takes the idea of numbers doing N number of times. And it's the simplest one you can kind of use and I'm just going to copy and paste it here. And let's raise say three to the two, so. [inaudible] I've got three defined right? So we should be able to do EXP of [THREE][TWO]. Right, this is... - Woo hoo! - ...what we're hoping to get. Good, good. Thank you. So we've got a nine, this is also quite an exciting nine. So the idea here is we've done the math operators and now we're left with equality, right? So we're kind of left to compare our values. And the equality I kind of want to share is really the number equality. How do we compare two numbers to be equal? And I'm going to kind of break the problem down and I'm going to start by checking whether a number IS_ZERO, right? That's the first thing we want to do is check whether our number IS_ZERO. So to check whether a number IS_ZERO... This'll take a number N and the idea is that if the number is zero when we pass a function to N, when we pass anything to N the function should never be called. We should get kind of the other side of N. So let me type that in. So we have N and we pass in a proc as the function we want to apply N number of times. And the proc X is actually going to return FALSE always, right? Because if we ever call that proc which failed, right? Because that proc should never ever be called because we're applying it zero times. And otherwise, we return TRUE. So I've forgotten something again, haven't I? Yeah. - [Female] Small F? - That's a proc that returns X, returns FALSE. Right, so the proc that's the proc that I'm passing in and this small T as well. Cool. And so if I do IS_ZERO of [ZERO], we should get true. True, this is good, right? Zero is zero and one isn't, right? So we have IS_ZERO. And then I'm going to define less than or equal to. So less than or equal to means that if we subtract one number from the other we get zero. It's not equal yet because if one's bigger than the other you could get zero but that doesn't prove the two numbers are equal. So less than and equal to takes two numbers, right? It's getting tedious to write all of these kind of nested and it's not pretty, right? It's lengthy and verbose. But the idea is it's still...we're still dealing with pure function at this point. And if I do IS_ZERO of say [MINUS][A][B], is that the right way round? A's less than equal to B so if A minus B...yes, that's right. And so LEQ to say [ONE] TWO] should be true. - [Male] I don't think it's going to work unless you have A and B defined. - Oh, right. Thank you. Yeah, I've got the wrong case. So LEQ[ONE] and [TWO]. Good, and if we do it the other way around we should get false. Right, so we're able compare to do less than or equal to, and we're doing that by kind of subtracting them by checking if they're zero. And now equal. Well, if you've got less than or equal to, you should expect that it's less than or equal to both ways around, right, if they're equal numbers. So what you can do now is you can do EQ and that's going to be a proc that takes A and B and it's going to return AND of [LEQ][A][B]. - [Male] Small cases, man. - Thanks. Thank you. And we should now be able to do EQ[ONE][ONE]. True. And if we do [ONE] TWO]. False. And just to check that we're not doing something stupid, if we reverse that, that should also be false. And we get false. So that's basically we have now got equality and it essentially completes our feature set, right? All the features we've talked about at the very beginning we have implemented from nothing but pure procs, right? Pure procs I take one argument, we've created all this in about an hour. Well, maybe two. So we've created all this from literally nothing, right? We've kind of built our entire ecosystem from the basic proc. And you need to take it on trust at this point that we can build a language out of these things, but we can. And if you're interested you can kind of go check it out. So the idea is now we're kind of back to our original story. We've now been cast down by this kind of god of programming and we found a different god, the god the proc or the lambda. And the god of the proc or the lambda has kind of enlightened us into how we can build entire systems without all these kind of beautiful features we're used to, all the comforts we're used to. We can still program in kind of that lower circle of hell we've been sent down to because that's what's on your mind you know when you're burning in eternity, it's programming. So that's the idea. The idea is that we can rebuild our entire ecosystem, everything we know from just a single idea, a core concept of the procedure. Cool, now there are some kind of caveats. None of these things are implemented, right? I kind of skipped over all of this so there's no IO. We don't have strings although it would be kind of sensible to represent them but as lists of integers. So that integer as in coding so we can encode it in ASCII for example, which is basically where this is. We don't have kind of interesting list operations like map and reduce. It's quite simple, like reduce doesn't take a lot to build out of the few primitives, but what we need to do that is recursion, and that's the one we're kind of missing, that's the big one we don't have. We don't have loops and we don't have recursion in our kind of what we've constructed yet. And that's been omitted because it's more complex and it takes more time. Once again, the book, go through the stuff. I highly recommend it. And what you end up having to use is those things called Z or Y combinators. They're kind of special function with a property that they let you recurse without being able to refer to yourself, right? Because if we implemented a recursive function with say function that calls function, we'd actually be relying on Ruby's implementation of all the mechanics of recursion to do that, right? Ruby understands recursion but we've not been allowed to use recursion and so we need this kind of trick, and the trick is encoded into the Y or the Z combinator depending on the family of your language. And obviously we don't have floats and the question is kind of, ìSo what?î What's the kind of the walkaway point here? Why do we care about this stuff? And one is expressive power,î right? we need to understand that the single function has this amazing expressive power to rebuild our entire program existence from scratch. The other one is, never ever do this in production, right? I've said it before, I'll say it again. This is probably the worst possible implementation of actual numbers you'll ever find, but it's the idea that matters. And if you want to kind of learn more about this stuff, I recommend these three books. I highly recommend these three books. So "Understand Computation" is this one, and that's really chapter six is what I've just been presenting. He actually describes how to implement recursion but he literally says, "Take this function from previous programmers who have thought it up." And that's the Z combinator. Then you have "SICP" which is this one, and this one will kind of go into it from scratch and teach you about the recursion, how to build recursion, teach you how to build kind of the data structures from scratch as well. And the final one is "On Lisp." Now, "On Lisp" is out of print and you literally have to get a bootleg fake copy to get hold of a print book these days because they're so expensive, but those three are highly recommended. And if you want to take a photo of the links, I will also send a PDF to Eve and James so that they can kind of share it with all this stuff. The first two are Tom Stuart who wrote this book, that's his take on this idea, on introducing lambda calculus. And these two are how I prove that using those basic building blocks you can build a full language, an object-oriented language. I take kind of the list of things we've built and I built an OL language out of it. So that's it. Thank you very much, I hope you've enjoyed it. - Woo-hoo! Woo!