it gives me great pleasure to introduce Ben Lin as our next keynote speaker Bennis floating all the way from the U.S to give this talk I'm really happy thank you very much [Applause] yeah so I know Ben actually from his blog where he talks about Haskell Lambda calculus git for some reason whenever I used to look on the internet for this Google always pointed me to his blogs and so I was like oh cool I was thinking it'd be nice to invite him over here yeah and then I asked him yeah can you be a speaker at Zuri hack and he told me I actually have a poor background and functional programming and would it be okay if I just talked about how I wrote my own Haskell compiler and yeah so after that sick fault in my brain I was like okay what's happening yeah so so we're here now and um and then later I understood what he meant because another colleague of mine came up to me so someone from computer security came up to me and said that Ben Lynn is giving a talk at Siri hack was he doing here and then he told me that he's actually a superstar in the cryptography world and I was like oh cool so I'm I'm really happy that people have paddled lives in this community yeah so it's cool yeah anyway uh so Ben's going to be talking about uh a Haskell compiler and how you can do it in two minutes so for those for those of you who uh who were there for the GHC Workshop where we spent three days and we even spent I don't know 20 years now so I hope this is not going to be too sad for us but but yeah yeah it's cool and so yeah I look forward to your talk and I hope one day I can also say I have a pool as poor a background in functional programming as you do thank you very much ben to see you well thanks very much farad and also thank you very much for suggesting the title of this talk um because I had no idea what to call it and um yeah I do want to say I I really don't know that much about functional programming it's my as I studied cryptography and um I just you know follow along free free stuff I find online to do what I do and um so let's uh yeah so given my background or lack of it I thought I'd I'd decision this talk more as light entertainment and I'm going to start with some magic tricks so I hope you like those um so first I'd like you to pick a Boolean expression any any Boolean expression and um was this the one you thought of uh no well that's okay this isn't a mind reading correct it's actually a Vanishing act and so I want you to watch very closely we'll get closer it isn't I should have had a broader magic wand or something and um and look the logic symbols have disappeared and yet the control of the expression has kept its meaning um and so judging by the lack of astonish grasps I can only surmise that you you all know how this trick works and that's uh um it's an end it's um I've used I've denoted Nan with juxtaposition and using some ancient rules we can rewrite any Boolean expression so that every operation is just nand excuse me and um for instance A or B you can rewrite as not a nand not b and then in turn there's not a you can write as a and then a in other words nand is functionally complete and apparently this this uh the jewel of this trick was used in the first moon landing like the Apollo guidance computer only had one type of gate on it it was a three input nor gate and I did that deliberately I guess because back then um the hardware was a bit more primitive and then to maximize reliability they wanted to standardize on one kind of gate that they could test extensively and be sure that it would work in the extremes of space um and even though this is a very simple trick that you all know uh it's it's already we already run into a very thorny issue and that's one of sharing so the formula not a it rewrites as a and a that's kind of suggests duplication but but would you take the circuit a and then rebuild the circuit a and then take both inputs and put him into a nand gate of course not you would any engineer would take the upward wire split it into and then feed it into an and gate in other words they would share the input and uh this is something that's uh we've actually I mean Simon mentioned this on on Saturday that um it's it's a it's pretty hard to to to depict the true Heap usage in an expression and and here we run into this problem so we have the nice beautiful tree on top though with plenty of duplication but that's kind of not really what happens and what really happens is we share inputs and um I've sort of used a funny notation to denote that I've got these numbers that that correspond to bits of circuits and then it's um hopefully you can follow along and see how they're shared and um and yeah I'm afraid I don't have a good solution for this throughout this talk I'm going to switch between those two depending on when it's important and you just have to bear in mind that it's not the top clean one is not always the truth I mean it's got a lot more duplication and then what's really happening and sharing is a is a it comes up everywhere in computer science and because of that it has many different names like lazy evaluation common sub-expression elimination the flyweight pattern um automatic differentiation and so on which I think is really funny because of all optimization techniques you would expect this one to have a unique name anyway moving on let's let's do another magic trick so this time we're going to do higher order logic formulas so recall these are just Boolean Expressions but this time you can have functions predicates variables and those variables can be Quantified you can put for all all there exists in front of these variables and again there's nothing on my sleeve oh yeah and just to be and this is the perhaps the most famous logic formula on Earth we have a celebrity volunteer here and it sort of represents um John Stuart Mill's famous example all men and Mortal Socrates is a man therefore Socrates is mortal and being a high school conference I don't need to put parentheses because um and and we have carrying if there were multiple arguments but we don't in this example and once again nothing up my sleeve and I'm gonna make all the logic symbols disappear once again wow tough crowd so how did I do this trick and well maybe not no one no one's impressed because it's just a variant of the previous trick it's universally Quantified then so if I write x dot a B for for all x a and then B then um there's a set of rewrite rules that show anything called um found in 1920 which can translate any higher order logic formula so that it only uses that one Construction so now that we know how this trick works let's let's do it again and our next volunteer is this uh kind of funny looking higher order function a higher order formula and yeah we can as I've just shown we can rewrite it with a universally Quantified nands but we can do more than that and again I'd like to watch very carefully and the variables have vanished and then although I haven't defined what these U S and B constants are perhaps it's a bit surprising that with just a bunch of parentheses and these three constants you can sort of represent the same information like the other one is all these funny symbols in it and variables um so let's dig into this some more um and first of all I want to there's a sort of annoying step it's this uh this U thing the U doesn't help at all it's just it's more of a notational device it instead of our funny dot notation it lets us write a logic formula in a Lambda term and as you can see it even blows up the size of the thing we're trying to represent so so U isn't really helping you it just lets us write it as a Lambda term and the real secret is in the other two S and B and these are combinators a combinator is a cleverly chosen function and in this case we've cleverly chosen S and B which are given by those equations and it turns out there's something called a bracket abstraction algorithm which can rewrite any Lambda term in terms of combinators so it gets rid of all the variables and perhaps some of you can do in your head can check in your head that this evaluates the same as that right now probably but for the rest of us we will have to use Simple examples so um likely we're prepared one right here so suppose you're in an emergency situation and you really need to build an identity function but all you have in your pocket are a bunch of S and K combinators so what do you do I mean S and K are given by those equations and as you probably recognize them in Haskell like K is just a const function and S is the reader instance of app and you want to connect them together somehow to build an identity function and maybe it doesn't look that hard I mean identity is simple you get an X return index and the K function already returns an X so we just have to figure out how to deal with the Y part of it and maybe you can like just snap together a constant const and um but if you but if you play around with this a little it's not as easy as it seems because if you try consequence but kkx evaluates the K because it drops the second argument not the first one and then if only you could somehow tell it K to to um evaluate the arguments in the opposite order you could do it but we don't I didn't give you the C combinator well AKA flip in Haskell and so it's it's um it's not that as easy as it seems and um but the solution is there is actually a pretty short solution and pretty well known and it's uh people say skk even though you could actually replace the third the second K with anything you like and uh you can check using those rules that we really do get the identity function skkx evaluates to K of X applied to K of X and then K drops its second argument and you just end up with X and and then the high school equivalent is app const const so anytime you have an ID function in your code you can replace with appcons and I'm sure your code reviewer will love it well you get style points so I don't know if it's um so so we've seen that you can it's possible that you can build functions that you've just by cleverly choosing functions you can build ones that you haven't defined so in this case we from S and K we have built the identity function and which raises the question what else can you build from S and K and the answer to that is everything so as SNK Turing complete and um just like we had rewrite rules before to transform any formula into a to just to use nand we can use these rules to transform any Lambda terms so it only uses S and K and so what I've done there is I took the um where is it this guy yeah I took this uh the Lambda term representation of the formula and I use those three rewrite rules to turn it into this monstrosity and obviously when I showed the trick I didn't do that I I uh it's a much smaller answer I use the different bracket abstraction algorithm there it's a it's a really clever one and and much better but I don't know if I'll have time to talk about it but I will if I if there's time in the end and um and I just oh and the second thing you do is uh this you business you can just get that you is only there for notational reasons is just connected to logic and we can get rid of that by simply prepending Lambda U applying bracket abstraction like using those as in case and so in other words you can uh and then that gets rid of the use so in other words you can write any logic formula with just S and K which was Shen finkel's main result in 1920 um and so the under the uh it's understood that if you give this this bunch of snks with someone they're going to apply it to you first and then try and interpret it as a logic formula oh yes I saw you know so um they find it even more complicated combinator called X it sort of combines S and K and then it turns out K is X of X and S is X of K and then you can then rewrite all your K's and s's in terms of the single coordinator X which is a bit silly but we can be even sillier and write X as a pair of parentheses and so and now your whole program is just a beautiful binary tree exactly exactly and well if you don't like lisp you can remove the parentheses and with the prefix operator and um you get the same sort of thing but now you need a the application operator and the X combinator thank you and so um in summary combinators are kind of the ultimate building blocks just as nand was functionally complete and can generate all Boolean Expressions we've just seen that S and K are Turing complete they can generate any Lambda term and um yeah for me it was actually a bit confusing learning about these things because they call this combinatory logic so I thought it was kind of related to logic and that's where they came from but you don't have to think about logic at all you just can just think of them as building blocks of Lambda calculus building blocks of computation and by chance um I'll be talking about the well the common areas I happen to use spell out the word bricks well there's a few more too which is really appropriate for building blocks because if you try and use S just the S and K combinators by themselves um you'll soon regret it and not only are they theoretically good building blocks but in practice you can see that really they're really good building blocks because it's so easy to write code for them this is an excerpt from a program I have that reduces combinators expressions and as you can see it's just uh just a like one line each for each combinator um and in some Primitives for interesting taking things and if you're curious here they're the Haskell equivalents of the brics combinators they're all very simple and seeming functions and yet they generate any Lambda term um and the culminators are also the original building blocks so as I said something called invented them in 1920 and um and Haskell Curry rediscovered them in 1926 and the other competing models of computations such as Lambda calculus and Turing machines they came later I mean they're not even a century old yet so it's kind of funny that they're more well known and the original one um I don't know I feel like it's not as well known and um I would have loved to say that what I just showing was all Sean Finkel in 1920 but the real history is way more messy but it's really fun to look at though um for instance he didn't even write his own paper someone else sort of wrote it for him and added his own ideas with one which was wrong and they didn't actually publish the bracket abstraction algorithm but he sort of hand waved his way through a demo and um and in 1925 John John Von Neumann also published something that would be like combinators and it was unclear if he knew about your phone thing called work or not and he also had a sort of theorem where he talked about he said oh you can do bracket abstraction but it's easy so I'm not going to talk about it because it wasn't his main focus which is fair enough and um so ultimately it's not Curry gets the credit for the first published bracket abstraction algorithm but he didn't use SNK and for that we there's a um I think it was kind of well known in the research Community he could do it with SNK but it wasn't actually written down on paper and published until 1950. so it's uh so it's kind of fun story um there's a great paper on all of this stuff and here's a screenshot of the original paper which is is quite readable well um well I can't read German for the one on the right for me but and as you can see it's building blocks of logic so that's um that's how they originally envisioned envisioned combinators and halfway down the page um in sort of archaic notation you might recognize the volunteer from the magic trick and at the bottom is um the same reduction that I got this except uh they did it by hand and I used an algorithm and historically um people have known this so Haskell have there's a comes from a long line of languages based on Lambda calculus and a lot of the compilers for those languages use combinators I think I got this from online so but hopefully people in the room can confirm this and uh um they use bracket abstraction algorithms to to take their Lambda terms and put them and write them into as combinators which are really easy to interpret and then for a long time um functional programming languages compilers did this uh but then um I don't know the exact dates I I'm guessing in the 90s the GHC encountered some issues with the combinators and at first they tried to Super combinators which are like tailor-made communities for each program and uh and hopefully they can still get things fast enough but eventually abandoned combinators all together and for STG um but then in 2018 I came across a paper published by Ollie because we have about a new bracket abstraction algorithm and here there it says maybe common natives deserve a second look for and um yeah so let's let's take a look um but first let me uh I don't just do magic tricks I also do death defying stunts so so I'd like to take care of a claim I made in the title uh and this is really dangerous don't try this at home um oh yeah it didn't work okay definitely don't try this I don't know why oh I know why I forgot to enable the browser extension I needed um oh no okay hang on a second I'll just have to swap Windows um I should have tested this beforehand um while that's loading maybe I'll do a let me just check this place the problem is I need to get a terminal window in the browser which I have an extension for oh yeah it works in this window okay so then we just close U and then um open this guy here and can I move this to that screen yeah okay and then okay now I'm gonna I can get a terminal here is that legible no okay let me boost the functions I don't want a new how do I get the font size bigger in this is it something like that um uh that's probably more readable all right um okay so you can follow along at home actually I I did say don't try this at home but you can it's it's uh we shouldn't blob your system and let's just uh I think a Siri hack directory um and then good clone what did I do I hope this repository works I only made it yesterday and this part of the time doesn't count this is the network speed and here we go so I'm going I have a um for silly I name my compilers really really silly scheme it's called precisely and and off we go in the meantime this will take a little while so I I only I I do death with fighting stunts but I also do them in parallel so we're going to go to the second window well I'm going to try some live coding here with combinators and um let's do a simple expression to start with so sabc how's that gonna is that legible let's zoom in a bit uh uh well that's probably too big okay and you might recall um the rule for sabc it's AC to uh B of C so let me slow down the evaluation speed this visualizes reductions uh I I built this for this talk actually and there's a sort of talked about the top that explains what's going on and um so I've I've connected the tops and bottoms of matching parentheses so they sort of form nested Bubbles and I think it's a really cute visualization um if you don't like it just go like that and then you'll cover the tops and bottoms then it'll be parentheses again and uh just to show you what they just gonna so you get a feel for how these things act I'm going to type in some random programs like I don't know um bricks bricks um hello is very hack oops that kind of spelling my coding's hard okay and then come on when my math go yeah okay that's that's good enough okay and so this is evaluating in normal order which means only in the left bubble is ever considered and when when a big bubble reaches the left it it pops and then we start evaluating the stuff on the inside and each one takes as much arguments as his needs and applies them to the rest of the stuff and uh uh and once again we run into the problem with sharing so um to keep the visualization simple simple and also because I didn't get around to implementing it uh yeah we don't do any sharing here so this is normal order evaluation and it's a bit unfair because in my compiler I do do sharing and so sometimes you'll see big bubbles get copied around and the same computation get done again when it when actually that's not the case um yeah so I I have no idea what this program does but it looks like but it is following the rules and it sort of gives you a flavor of of how the combinators work I'll put in a more serious program so this one um I oh wait a minute it's hard to see okay uh I don't know if any of you familiar with combinators but uh can anyone guess what this might do hey who said that if you know how how did you guess that less multiply yes yes very good the white okay this is foreshadowing but the wire does recursion and then there's a less than one check and the multiplication and the subtraction from one and then and then and then and yeah it's Computing four factorial I'm gonna let it play so you can see how um you can see what these things look like when they're when they're evaluating and and this is unfair they shouldn't be copying this bubble this is a shared bubble but that's uh but I I did come up with a visualization for sharing but I didn't have time to implement it um here let's make it a bit faster this will take a while because it's going to repeat some computations so let me uh that's about a good speed I think and in the meantime oh no I don't want to no I want to keep it playing it's very pretty and so even if you don't quite get the the guts of comment is you can kind of see each of them is individually very simple it's sort of like a assembling language instruction and you really can do arbitrary computations with it um okay I've had let's make it even faster because the timing will be wrong and once again it's subtracted repeatedly subtracting one from four even though with sharing you would only do that once and then save the results somewhere else where it would come back I mean Andres spoke about this stuff yesterday so um yeah so maybe it's just as well I didn't visualize it here and there we have 24. thank you there and this is finished too and it took one minute and 17 seconds and to test this compiler I'm going to build a compiler but I'm going to build a interactive a rebel version of my compiler and unfortunately this will take a bit more time um for like 30 seconds or so so I got a time for my program to you I I but I didn't have one I had one in mind but I forgot what it was oh yeah okay I just wanted to show that uh skk X does indeed um oops Zoom the other way please and then let's feed down is skkx is indeed the identity combinator so the top we have the tooltip showing what each combinator does and um yeah you get skk X is X and and uh the other thing I said before was you can replace the third argument instead of skk you can do SK anything so because the K combinator will um will kill the second argument so to speak and yeah they'll just fade away and you left with x and oh and this is finished and we can test that it's it worked um oh well uh like I don't know um but I should have thought about this one I don't know what's a cool way to test the hassle compiler anyway um the factorial okay that's a good idea factorial and equals uh if so yeah the program I had before um we're going to be sick of this example by The End by the way um else one I should do the trick right and then yeah so oh okay well thank you I didn't expect to follow us here but thank you very much [Applause] um so let's get back to some of how the the nuts and bolts of how I built this um so a compiler can be a first approximation you can think of it as a pipeline from from that takes a string then it returns an abstract syntax tree and then it type checks that syntax tree possibly adding to it because um for type classes you need to insert dictionaries here and there and then we convert that syntax tree into a Lambda term and then finally we use bracket abstraction to change the Lambda term into combinators which um as we've seen even you can run with a pretty simple VM and so the first part of this talk was about bracket abstraction and I even showed a full bracket abstraction algorithm but that's not the one I use because it's terrible and and so now I'd like to focus on the the second last step um so in this whole yeah so normally you would also care about errors and things like that but yeah not not for this talk so into lambdas how do we squeeze Haskell into these three constructions where um where so a Latin term is either a variable a land or abstraction or application which uh yeah I I guess I don't need to tell this crowd and and a lot of the Haskell is really easy to convert to Landers like um Peter Landon called his language church for that Lambda because it was just an alternative way of writing land Boonies in his mind like if you see a function definition like this all you have to do is move the arguments from the left side to the right side and put a land in front of it and then you have a Lambda term and similarly a let is just a syntax sugar for a Lambda abstraction applied to a tone but what about data data types and and case expressions and recursion and mutual recursion I mean like data is tricky because it doesn't look like anything like a function like a Lambda term and the problem with recursion and mutual recursion is that this is such a simple thing like uh with variables Landers and applications there's no it doesn't seem there's a way for them to point to things that haven't been defined yet or point to yourself so so those two I mean I guess these things I found most challenging about writing um I had to think the most about when I was writing this compiler and so let's focus on data first so how do we turn a data type into a Lambda term um so suppose we have some definition of a data type here and um and then those of you who attended addresses to talk yesterday will know the answer to this what is the only meaning meaningful thing we can do with the data value exactly case analysis and and so that's that's the only otherwise we're just passing the value from function to function and the only time we actually do something is a with it is when it encounters a case expression and it's going to look something like this um if you figure out which one of those data construction Constructors is it is and then you apply um the appropriate function and that doesn't sound like a big thing to say but in fact it uh it sort of motivates the solution really well I think because it plus you just uh well yeah let's take that case statement and then well it's not a Lambda term well let's just force it into a Lambda term somehow and then the way to do that is we delete the keywords we don't know how to handle and we don't delete the data Constructor so we don't know what those are and and then the rest of it kind of looks like a land expression and so we get this and then it is a Lambda term scrutinized value is value applied to three lambdas and then the Scot encoding of a data type is whatever you need to do to make that work and then and that's how you can go with data and case Expressions as Lambda terms um so for as an example here this unknown data type I know 42b takes three functions and runs the third function on 42 and B because it'll correspond to the the third case of the case expression and here's some more examples if um oh yeah maybe this isn't a good slide like unless you're really familiar with this technique it's not going to be obvious but the FNG x's and y's sort of correspond to the the fields of the data Constructor and FNG are the various case matches um and uh it's booleans I would prefer true and false would solved around but way back in the day Church described it in one way and that's the way we've uh people have said it ever since and I'm I I'll get confused if I let's switch it around now um and the reason I do prefer it the other way is because uh false sort of corresponds to zero and true corresponds to one so false should go first not true but anyway and and it's still SAS and it's that's the way it is for the other similar things like nothing goes first the empty list goes first and um and so on and piano is going to take zero will go first instead of the successor function and now we come to um a mutual recursion so we've handled data types of case Expressions let's look at the recursion and neutral recursion so suppose you have a two mutually recursive functions and it's it's unclear how to convert these to Lambda terms because you pick one you pick the chicken and then you start turning into lambd term then you encounter this egg thing and you can maybe say okay well I'll go look up the definition of egg and you start converting that as well and maybe inlining it and then you run into the chicken and well I haven't finished defining chicken yet and then and you end up in trouble but actually the solution is quite simple you just use uh placeholders so you sort of Define a Proto chicken which is almost like a chicken but but it has an extra argument and if that argument were to be filled with an egg then it would be a chicken so so I've somehow managed to define a sort of chicken without mentioning eggs then so once I've defined this Proto chicken and then I can now Define an egg I can say well an egg is just a protein chicken where I pass it myself and then once you have the egg now you can Define the chicken so um and so by doing that we've reduced Mutual recursion to single recursion and this is um something we actually do subconsciously every day because in natural languages we often start a sentence with the word with a word like it and we say um oh yeah it takes one to know one and then well if you if I just stopped at it takes one you have no idea what it means or one means for that matter and it's only when you hear the rest of the senders that you go back and fill in the meaning and but but interestingly in natural language they don't do that because they're trying to avoid Mutual recursion is it just sounds better I mean you can't say to no one takes one and that would just confuse people and uh that's the so in in general you made multiple may need multiple placeholders so here's a example um uh with with four mutually recursive functions and it's a weird species of the butterfly because I I had to make the various life stages interact with each other otherwise the example would be too trivial so I just had to come up with random verbs and but you can see that the solution is the same you pick you arbitrarily pick one to Define first in this case the lava and the proto-lava is given three placeholders for the other life cycles or we haven't defined them yet but it it has you can kind of access them through these uh placeholders and it's a bit more complicated because now you have sometimes you have to pass placeholders to placeholders and as you're defining these things as you define more and more things you use fewer and fewer placeholders because more stuff is now defined and um yeah it's not the sort of thing you can sort of I don't think you can learn from a slide while sitting down you just have to uh you just have to go through it but it's but but the main point is you get you need multiple placeholders and you may need to pass placeholders to placeholders to get this done um and by the way you can also this also suggests an alternative strategy for compiling lead Expressions so if you have a lead Expressions deep in some scope you can lift them all the way to the top by by treating any um variables they need as a as with play by using placeholders and and then in that way let um any let definition just becomes an ordinary function and then when you do that that's called Lambda lifting but um my compiler doesn't do that it just does that transformation we saw before where um let me show you uh there this that the second transformation over here because um because I didn't want to write Lambda lifting code and so that leaves us with just the the single recursive case so um so let's take a recursive function such as the Fibonacci numbers and then we might try what we did before which is we add a placeholder X and everywhere we normally would have needed something that was undefined we put X so we have X of n goes to if uh well the important part is the calls so x to the N of Y minus one and X of n minus two and um your first instinct well at least my first instinct was well then I then I can just Define fibonacci's numbers by placing this Proto Fibonacci function into itself right and but then if you do that you get the wrong and you get the wrong right hand side because now you get V1 of n minus one and feed one of n minus two and that's and recall these aren't people this isn't the Fibonacci function this is the proto-humanagi function it's got a plate it expects a placeholder somewhere so um you actually have to double up the placeholder so to speak you have to pass placeholders to placeholders and it's it's all kind of confusing but really it's the same as um back over here where you have to place placeholders for placeholders and for the same reason it's just somehow it's more confusing when there's only one function and so once you know this it's not too bad all you have to do is uh go on the right hand side and everywhere you see an X just replace it with two x's like that and um so the fibiaki function is this way I've done that and now you can Define the Fibonacci numbers as fibiaki passed to itself um and this works but it's actually a headache to construct because now you have to walk through an AST and find where the recursive calls are and then double them up with placeholders and that's kind of annoying and while still it duplicates XX like we're all about sharing and lazy evaluation I mean we shouldn't be Computing X of X twice so a better way to do it is to keep the original FIB one function we had before the the sort of Proto recursive function and and then do the the yucky part in in a separate function so the FIB 2 is the one that will pass the placeholder to itself and then it works there you just pass the second the yucky version to itself and and by doing so we've magically eliminated recursion each of these things doesn't need itself to uh sorry each of these things only depends on stuff that's already been fully defined if you look closely and of course I've chosen the Fibonacci numbers as an example but this technique Works in general um and you may have recognized it um some people may recognize it it's it's called the Y combinator so um the the technique for making the stuff recursive is just passing this uh placeholder doubling function to itself and when you write out in full it looks like that um and then when I first saw the white content I had no idea why it worked but then when I but when I went through Curry's papers it made more sense um and it was first published by Rosenbloom in 1950 but I would argue that Curry himself was kind of a y combinator because you could give him a almost recursive function and he would know how to turn it into recursive function by carrying out the actions of a y combinator he would he would he would Define a second function to apply placeholders to themselves and then apply that function to itself so I think if you asked him can you write down what you're doing in terms of a lamb expression he would have he would have written down a y combinator but he didn't and so Rosenbloom gets a credit um um oh yes so to recap we started with a function that's almost recursive so we can't we're not um we can't refer to itself but we can refer to a placeholder and we make it recursive by applying y to it so in other words um yeah so the Y of FIB one is a true recursive function now interestingly if we just simply make the substitution X is y FIB 1 in the first equation we get the same right hand side which which kind of means the left hand side's equal which means FIB one of y51 is y51 um and for this reason the Y combinator is known as a fixed point combinator and if you go through the details it turns out this is the only property we actually need if it's if f y of f is y of f then um then y will turn any sort of pseudo recursive function into a recursive function I'm sorry I'm just making up terms on the Fly I don't know what the real names of these things are I just say protection pseudo recursion I don't know what you're supposed to call these things um and then we we ended up with why because we went we went through a particular strategy to uh to double up the placeholders and so again history is messy and so it turns out why why in fact there was another fixed point combinator that predates Y and that's called the uh it was by Tyrion in 1937 and we can derive it right now using our techniques so we want a Theta y that satisfies this equation sorry we want a Theta combinator that satisfies this equation Theta Y is y of theta y and uh we just use introduce a placeholder and to double up the placehold on the right hand side and then pass the function to itself and then we end up with uh what Turin got and that was the first published fixed point combinator which enables a recursion so I I don't know if you caught on that but but to sum up to if you have a recursive definition the compile it um you just introduce placeholders and then apply y to it and here's here's an excerpt from my compiler of the one version of my compiler that does this it just searches through the the syntax tree to see if it's a recursive one or not and if it is then it turns the name of the function itself into a variable which is how I made it the name of the function itself becomes the placeholder and then you apply y to it and if for some reason this happens before the type checking phase uh that's okay you just tell the type Checker that y has this type and N works out and and in practice although you can write why in terms of other combinators we've seen before it's kind of a hassle to reduce all that just to do recursion so I actually special case it and um with the with the key property that you need from the from where and so it's probably a misnomer to call it why in my code but whatever and and and ultimately you can also cheat because when you when you're running compilers you have the memory addresses of the functions you're compiling and you can sort of just break out of the theory and just use memory addresses at a certain points oh yeah so he's um an example so if you which I which we went through before actually you saw uh like a father did before because um so we're here in fact and he goes oh yeah yeah um so um the the if and then our statements um as Andres mentioned yesterday I really um it's just a case match on a bullion type and we're using the Scott encoding so uh we we just that's just Scott encoding of a data type in a case expression um and then we turn it into a sort of uh pseudo recursive function which we then apply y to and then lastly we apply the bracket abstraction and that's how you end up from a recursive definition to a bunch of combinators that can be run on a um on a VM and in fact this is the program that you saw earlier on the animated VM thing and uh as a first step which is optional you can also convert what you got back into Haskell and confuse people okay foreign but um the the chicken and egg problem really is truly difficult and um because he could argue that well the GHC is just running the GHC on its source so can't we use a fixed point combinator to to magically create a GHC binary out of its source but but that's not true because although it does find a solution there is a sense in how it's it's sort of a superficial solution and so you get undefined and you don't get a git binary uh so so if you want to bootstrap a compiler you really do have to do real work you have to start from another language compile something and then improve add and write another compiling and compile that and gradually improve your compilers as you go all right okay so here we go um I forgot about this slide so as before we I mentioned that the VMS are really simple we I even showed you the except of the code if it's just a bunch of wine Liners in a case expression and um and for that reason it's easy to compile the VM towards them which also means it's really easy to run Haskell on the web so those are so the example examples from before I really could have anyone pick a formula because it was because the same person would have worked out the example on paper and then carefully typed it into their slide program to show but I didn't do that I I I have a program running in the background that actually figures out the right answer so for instance so you can give it any formula and it'll tell you how to write it with um uh without any logical symbols uh like here's a yeah just um I mean I don't know how to prove I'm not making this up but uh I don't know for all C exists the uh something oops will that work yeah well and then so it was actually I wasn't I wasn't kidding when you could have when I said pick any formula this is actually pretty cool sorry thank you thank you I'm glad you said that because because if you like that you're going to love the next slide because then um yeah so you can put uh what is this what do you call this thing get uh there's these show and Tinkles tricks into code and run them on the web but then you can also put the compiler on the web so so this is actually a live compiler right now that you can uh type code in and it'll compile and run it here I like fibs in this Bonnet as if we're zero I'll wait plus two not yet fibs tail bibs there I memorize it okay and then I don't know fields 10. and yeah I've got uh yeah and that actually I do have multiple arbitrary Precision arithmetic which I implemented myself using really just just the naive algorithms I guess but it works um and then if you're wondering well now that I have a high school compiler on the web that you can run on the browser uh you can go a tiny bit further and that's the slideshow because because if you look at this webpage what it actually does is load Haskell compiler lies in binary and then it compiles a bunch of code and then runs the slideshow written in high school which you're seeing right now and I kind of went overboard with this I I wrote some code to to do HTML markup and formula passes and then rewrite a direct abstraction and so on and and so what's the uh the VM you saw that that was actually a web page that loads of Haskell compiler and then compiles the contents of the page and just to show you here's the here's the size of the page so there's the uh that's that's the the three data structure that being that holds all the various formulas and also the HTML page format um the bracket abstraction code types of combinators um logic formula passes uh what else is there and there's there's tricks I showed and there's the first few slides and then if we go too far there'll be spoilers so I don't want to yeah don't want to scroll that much so let's uh let's get out of here I think I've made a function to do today yeah yeah oh yeah sorry that so that's the um I'll go back to more demos if we've uh we have time but but I just wanted to say that um it's actually way easier than it looks um because there's a lot of fantastic free literature out there oh the last one isn't but um the rest of it you can just find these papers online and a lot of them have just Haskell code in there or well in um a lucasio's case it was a camel code and and you can just easily translate it in Cotton copy and paste things around and I found really the only part I needed to think was um with designing the combinator reducing VM which we've already seen wasn't that complicated and and he's um just if you're curious this is what one of my compilers looks like it's a so this is fairly early in the bootstrapping stage there's no it doesn't it can't do recursion you can't do um you can't do data types really you can't do well yeah you can see uh it you can still have you have direct access to the combinators the ones with the ad sign in them um and I I sort of manually Scott and code things in my head so I know how to write these functions and and oh yeah here's another one here's a data declaration because I don't have data decorations I have to write this Scott encoding myself out and um and so there's the Prelude the syntax tree and here's the types of combinators and because at this stage there's definitely no type classes or anything um there's fmap app they only mean they they only the parts accommodated instance of them um but it's not too bad it's um well maybe I'm too used to these things but but it wasn't that much work throughout the parts are complementary Library even in such restricted with my hands tied behind my back basically and there's Alexa so the first one's the comment the next one's space I mean if you know parts of communities I think this might make some sense to you you can see um anyone is any child I don't know why I called anyone and um or any one car I guess but and a variable is let's see a space followed by something that satisfies that's something that's between a and z so you can only use lowercase because all the sorry yeah the hash symbol you know it's immediate like that's uh that's that character a and then the character Z that's the quoting mechanism and here's the parser a program is a bunch of definitions a definition is a bunch of stuff separated by equal signs and so on and lastly the rest of the compiler it um if you pass something and um convert it oh yeah um B app stands for bracket abstraction which causes which is just the SK algorithm that I showed earlier with one optimization in it and um uh Cowboy what is free for oh yeah you need it's free you know for the optimization and then and other than that it's it just prints stuff in the right order and and the output looks like this which is sort of bytecode for my um Community interpreter and I've used that polish notation trick so the the back tick here means application and you can see all the SNK and I accommodators and have sprinkled with little bits and pieces um which we refer to uh immediate values and also um yeah once again sharing rears its head so because this remember it's not really one single expression it's a it's actually it's not just a tree it's a directed a cyclic graph so there has to be some way of jumping um from place to place um oh yeah okay is there time left over oh okay yeah okay well I said if there was time left over then I'd show how that a better kind of um bracket abstraction algorithm works and here I have a um yeah pick a term any Lambda term and I'm going to make the variables disappear again but I think you'll be really disappointed this time because all I'm doing is uh the brown indexes which is just the level of nesting of a variable um hopefully you're all familiar with that but um but the reason I want to show this trick is because there's something interesting when you write lambdas with the Browning indices and that's you can you can sort of make sense of a Lambda term that doesn't have any lambdas in it like if I just write down x c if y of Z and then it's hard to know what that means because if depending on how you um add land obstructions later on depending on in closing context it can mean very different things but if you start with something like two zero one zero and no matter how and then add a bunch of lambdas to it it's always going to mean the same thing and and I think this was um the Kingsley odds Insight in in making a bracket abstraction algorithm because then um okay uh let's see yeah okay I'm not sure this is going to make sense but um oh yeah maybe I'll skip I'll skip this part these slides uh it doesn't matter so much this is the sort of the thing you do really have to read papers for but but the summary is that thanks to the brown indices um you can make sense of bits and pieces of Lambda terms that you wouldn't that you couldn't otherwise and that empowers an algorithm that that allows an algorithm that looks that can sort of paste little bits together and figure out the the final expression because all other bracket abstractions um don't do this that they actually look at the variable names and try and figure out where was this variable defined and then because of that um I think they're not as effective um and what else do I want to say about this oh yes I I did want to mention that um one really fun part of writing your own Haskell compiler is you can just you know pick the there's no religious walls you you win every time so so for example I I wanted a for multiple comments for two multiple tuples I decided that that was going to be syntax sugar for um uh nested um tears and that way you can have one instance handling all tuples at once because because one thing an annoyed me in the I'm sure you all seen that that some instances and many declarations just for lots of tubules and if you add one more it won't work and I also for another example is like I really like having a ring type class instead of a num type class like I'm kind of mathematically minded and I don't like how I don't like the how numb is ringing with just a little bit more stuff because then it doesn't make sense for certain things like gaussian images and gaussian images I think are quite practical for 2D games um because sometimes I wanna I have a title I want to rotate or something and I can never remember oh you got a take the x coordinate make it to the Y chord and I kind of I can't remember the rules but I can always remember multiply by I and and so I I find it quite useful um and I have this little really silly nitpicks like I like uh empty Lander tofu to mean Fu and I I have uh I have these turned on in fact you can't turn them off with these uh extensions and and it's also it does type checking the way I want which is I don't generalize let and uh you you can you can declare the type of a um of a lead declaration and respect it but in but when it's in info if you don't if you leave it Undeclared if you don't annotate it it won't generalize and there's no dreaded metamorphism restriction um oh yes another thing is I was I was hoping I found the process of it to be a lot like playing one of those uh games like um factorial and Minecraft where you have to uh you start it's like a survival game where you start with very little and you have to build your way up to high school 98 and I'm wondering is there a way to make this more formal could there be a game where where you could say okay everyone you start with nothing go build a high school compiler and I think that'd be really fun because it's it's a lot easier than than it seems I think um and then and then and the main reason I wanted to happen is so I can watch YouTube speedrunning videos on this so I really love watching those things and I'm sure there's a lot more a lot of cool tricks that are out there that I just haven't found yet and here are my own tips if you want to try this and that's uh for the past I just use Plaza combinators because it's really easy to get a small Library working and I guess eventually you may want to use a more theoretically sound thing but yeah I haven't got there yet and um for the tree decoration problem um I was just holding my nose and I I just held my nose and just use one tree for everything because you don't yeah it just takes too long writing different very similar tree definitions and shuttling between them and then you don't have a type system that can I can automate a lot of it for you um one thing I made a mistake was pattern matching because I I didn't have Hannah matching in my language and then I tried to add the full thing and it's very awkward to write a pretty complex code without Panda matching so it's better to write a poor pattern match at first and build your way up which is probably obvious but it wasn't to me um I also should have supported off-site the offside rule way earlier because that was that was uh that was way more helpful than I thought it would be and um uh yeah just other little things um oh fixity oh geez um yeah I originally fixed it is pretty annoying to deal with because you have to pass an expression without knowing any of the operators six cities and so I thought oh I'll still make my life simpler and assume I'll fix these declarations are at the beginning I'll make the user you know write programs that way and then I can have my partner know how to fix cities but um I found it's actually quite annoying to do that too because now you have to thread the fixity table through the parser and it's way better just to do the full General version which is you pass an expression assume the the expression operators have a certain dignity and then you have a separate phase once you know the fixies to go through and rejigger all the trees to the cracks big cities and and um yeah and modules I really should have thought about it way earlier because it's still quite wrong like in my compiler which um yeah which luckily we haven't run into yet um and my last slide is uh some of some of you may know that I uh yeah I entered the international obfuscated C code contest in 2019 with a high school compiler and that's because um and then and then and there I just uh you can look at my website for the full tricks but but basically the rules are you can have at most 4K bytes and at most 2000 tokens but they have 2053 tokens but they have interesting tokenization rules so you can encode stuff into white space characters and and braces and things like that and so basically I wrote a compiler that with no type checking very very limited syntax but but enough that it can compile your GHC and um yeah I would encode the data into using exploiting the the accounting rules and I use Huffman to compress things a bit further and base 85 to avoid hybrid characters um yeah I guess that's about all I wanted to say and I listen and you want to see more demos or something or animations of combinated [Applause] thank you uh yes one sec let me just go ahead and get the mic yeah oh that's good we can meet halfway yeah thanks so first of all I just want to say thank you for an amazing talk um that's probably one of the best talks I've seen in the last two or three years um it's a little context I'm the owner of www.cominatorylogic.com uh I'm a massive combinatory logic fan um also a huge fan of your blog so my I got two questions my first is I'm not sure if you recall the APL and J blog that you wrote I did write the J interpreter once yes yeah um so I'm I'm kind of uh Moonlighting here at a Haskell conference I'm I'm also a huge array language fan you mentioned in that blog that uh I believe the S combinator sort of maps to the reader instance which he said but are you aware that um or sorry what they call hook and fork and J yes uh are you aware that hook and Fork map to the S combinator and the Phi combinator and I just gave a talk like a week ago on Monday at Lambda days that like points out that array languages are the best programming languages in my opinion for programming with combinators because Ken Iverson in 1989 published a paper uh called phrasal forms where he basically references Curry's work and says we're going to throw all this stuff in Array languages but then he renames it all and that's the last time you ever hear of it anyways just curious because you just gave this amazing talk and you also have dabbled in the array languages did you know about that connection yes I did I did know about the S1 the the notebook yeah is it hook the one the one where you the you put three operators together um uh it's a two train so two the juxtaposition of two functions in J yeah okay okay yeah I think I was aware of that yes okay second question uh you added R So like um uh Curry published his textbook in 1958 and in chapter five he lists five of the combinators as Elementary combinators um and I think basically B I C and K uh are four of those five W is the other one and then you added s so am I correct in thinking that you added R just so that you had a nice word to spell or do you also have like a fondness because rscc and then in my VM you would have to it would have to allocate a new upsell on the stack just to undo it again because because they would I mean it's better it would it would do more work in in a loop basically so I was rather because I knew CC would pop up all the time so I just made one commentator for it and I did make up it came from another source I think it's a smallian or somebody defined it and um so that's perfect I can claim it's a basic combinator now you know okay so you borrowed it from someone else yes anyways thank you once again this talk was amazing [Applause] would anyone else like to ah so given that with binary Computer Logic we can express any Turing complete thing in binary what do you think about literally implementing this is a kind of binary Hardware thing where you stream in a bunch of binary values and a bunch of binary combinators um so I don't I don't gain that much from doing that because you would lose from the expansion I think that's my feeling but but it is striking that it the body representation does closely correspond to the structure of the program uh unlike like taking a c program and then reading it's asking binary it's very hard unclear how that Maps back to the original program yeah so there are people here who are trying to bootstrap GHC I've heard of that Yokum yeah yeah and that's your compiler help well not as yet it's um it can't do because of you can't do uh what do you call it uh recursive mutually recursive modules yet I didn't even think about that so it's it's not in my compiler but I um I think it could be done though I I don't know I I don't exactly know how much how much more syntax I need before I can understand whatever GHC is written in uh this is a um flooring I'm going to put the bubble thing back on if I can find it yeah okay uh thank you very much ben again for this great talk it was really great thank you very much thank you thank you [Applause] [Music]