scale.bythebay.io: Rahul Chitturi, Auto code generation using AI & Scala Macros
Recording: scale.bythebay.io: Rahul Chitturi, Auto code generation using AI & Scala Macros
you so my name is Rahul and I'm a principal engineer at a hedge fund / VC firm called co2 management so today I'm really excited to share with you guys of a dream project that I worked on for the last four months so this is compiled AI and this is an AI framework to generate code based on natural language input so at a high level let's say you have a product requirement that is in English or you might have a programming contest problem that you want to solve so I want to take those problems and generate code for that automatically in Scala so I know this is a big goal but let's see how we can do it so why is Auto code generation so important because let's say like you have a you are a product manager and you want to develop something really fast you can instead of going to the developer you can as well go to the AI and I say I to develop the code for you and so yeah like about the dollar parts so when we went to school like what did we learn like we didn't do like all the problems that are out there in the wall we just learned like the pretty much the basics like how do we do backtracking how do we solve the problems with like CSP constraint satisfaction problems or or it could be like dynamic programming and things like that so like we learnt all the basics so my idea is why don't we teach the AI like how to deal with a problem and try to generalize it and let the AI code for us instead of be coding they I so so let's say like we come up with an AI to do something like this it can do a much better job at writing the code because let's say it wrote a function it can probably write like hundreds of test cases for it and you'll have like much better quality and at the same time it can do it at much faster pace because it can like much faster than any of us okay so let's talk about the state of that code generation so so the university of washington guys they came up with this tool called talena wherein you can come in your terminal with your natural language so essentially like you can say hey find the PDF in xyc so this is the query that I give it and it created something wrong but you get the idea like you can give a natural language query and it'll try to come up with a command line for it okay so Salesforce recently came up with Nai wherein you can like command your database with a natural language for example in this case this guy has a question in a natural language and like it is able to generate a sequel query pretty cool now Microsoft Microsoft has done a lot of research in this area so they already rolled out like several features like like a flash fill and flash extract so let's say like in excel sheet you have a column and you want to write another column that is like a formula on top of the first column you can give like one example and do like a special command and that'll fill out the rest of cells in the second column and so sometimes like it can you know do wrong things wherein you have to provide like more example so that it knows like what you are trying to get at so like the interpretation could be like so many things so as you give like more examples it'll try to come up with a right algorithm for you so you guys should check out this video like whenever you have free time okay so so what are the limitations with the current approach so like program generation is like a search problem so you have like millions of possibilities that you have to search across in order to generate the right program so people tend to use some kind of dsl so that like you can limit the number of possibilities for example like the state-of-the-art research done by Microsoft they have like 20 functions and so like so if the DSL box well for their program it works fine but if something like if you have to write a program that be written with the DSL it doesn't work and because of this like everything tends to be like domain-specific for example like we saw a terminal command and we saw a sequel command and we also have a limited set of DSL in most of the cases that I have seen so the problem that I'm trying to solve here is I want my DSL to be natural language so there is one primary Google and I want the bindings to a turing-complete system so in this case Scala so essentially I'm compiling natural language into Scala and the grander goal is like I should be able to compile to any language so so let's see like how we do it so this is a problem that I took from Euler problem set so this is this says hey find the sum of all the multiples of 3 or 5 below thousand and this is a solution that they I came up with so let's I'll do a live demo so that you guys know like what I'm talking about so if you go to the compiler website you'll see the same material but I have a disable the program there so that I can do the demo I learned I'm a little like once out of the demo ok so so this is the Euler problem 1 so find the sum of all the multiples of 3 or 5 below thousand okay so so what does this sentence mean so it makes like a lot of sense to you and I but like how how can you make sense to the computer right so in the natural language processing domain like we have the dependency parse trees so that will essentially capture the meaning behind the sentence so here the same sentence written out as a parse tree so here like I'm trying to find something which is some and some of what some of multiples and multiples of what 3 or 5 and given a condition that it is below thousand like all these numbers are below thousand ok so this makes sense so how do we convert this color so this is a solution the scholar solution for this where and if you generate the Scala ast tree it looks something like this like pretty much the same structure about different operations so let's take a look at this one so here the below thousand is good okay enemies so this is a natural language tree and this is a scholar tree we are essentially saying hey below Towson should be mapped to something like zero until thousand and the left hand side here the multiples of three or five should be mapped to the right hand side here okay so how do we do that so I came up with some Thai rules so just for the purpose of this demo so essentially what I'm saying here is so let's say like you see this English word plus and there is a parameter the left side of it and it is a Parham to the right sort of it how do we convert that to Scala is literally the plus sign just put a plus sign and I'm also doing some type level checking so I'm also capturing like what are the parameter types and what is return type here and I'll talk about the score as well in a little bit okay so given a grammar like this how can we generate the program so let's say you're here back to below thousand so this will be replaced with zero until thousand and but as you can see here multiples of 3 or 5 it can't be applied directly so you need to come up with some kind of solution for it so essentially like you take the left-hand side which is a sequence a collection and the right-hand side is a filter so how do you compose these two things together or we can ask our friend Scala compiler to do it for us so how do you do it so you can try to get the type of the string here for example I have let's say I have a sequence of 1 2 3 I can at using the runtime compilers I can try to get the type of weight which gives me a sequence of veins and on the right hand side I'm applying a filter which which is a into boolean for an example so how do you how can a compiler help us in this case so you literally ask the compiler hey like given this type on the left hand side for example this case a sequence of fins give me all the methods on it okay so it gives you like probably 150 methods but can all of them be used as a compose function on the with the right hand side probably not so you can so then you take the right hand side type and try to filter all the functions that are listed by the compiler and that gives you a list of ten different things so this way you can any nerd right like all the possible functions or there in the wall you can literally say hey like you can concentrate on the main pieces which is a plus multiply like you have to teach the air somehow but rest of the things like composition and stuff like that will be provided by the compiler okay so there are ten different possibilities like which one do you pick so that is the next thing that will come to your mind so I have a solution for that too using run time across again before we dive into the ran time actress I want to also give you guys like different complexities that we have with the program generation so for example like in a natural language it is inherently like really ambiguous so sometimes like a different like there could be like ten different paths trees for the same sentence and all of them could make sense and another problem is like most of the NLP tools that we have they don't generate the right right pasture you like most of the times especially for the the problems that I'm trying to solve here so what do we do like we have to take like instead of one tree we have to possibly take like 20 different trees and see like can we get generate program out of all these trees okay so that is like one level of complexity or now another level of complexity is like although you see the same world like some it might mean a plus symbol in certain cases and it might be like collection dot some in like other cases depending on like what type you are applying it on so yeah like instead of so instead of like just for a plane translation you have to look at like multiple possible translations so this is another dimension okay synonyms so so let's say you have defined a function on some and you don't probably want to define it again on a plus because like inherently they are like synonyms and you'd be you should be able to apply the same function no matter what so essentially you can go to the English dictionary and say hey like whatever my synonyms and if there is a synonym that has a function defined on it I can use it so this is like another level of complexity so as you can see like we can generate like possibly thousand different cases that we have to scan through so given this complexity like how can we use the runtime macros for it so essentially like I'm trying to evaluate the natural language tree as an expression so like when I go here so I will convert that this to like three or five and literally three or five and I have a function that is being applied which is a multiple and multiple gets converted to mod 3 equals to zero or mod 5 equals to zero ok and if that makes sense I will try to see hey like I have a so this below thousand gets mapped to zero until thousand and then I can see hey like can I apply see this function and that's so like it gets evaluated until at top but as we talked before like there are different possible combinations and sometimes the past is don't make sense in Scala so like a lot of times like I render into scenarios where I see things like this so there is two plus two and there is nine so what are we doing with this nine it doesn't make sense so the Scala compiler says hey there is something wrong with the code I don't know what you're saying and we can actually prune that possibility so this way like we can prune out like tons of possibilities so from what I have seen like most of the programs like one-line programs that I have been generating in Scala like they're like pretty fast so I will give you a demo of that right now so by the way this is all live code so all I have is a bunch of rules like this predict simple stuff and see like how it gets evaluated okay so I do ten plus two and this is the natural language tree that got generated so what are we seeing here so we see plus which is the root node and we have two children two there plus which is a which are like ten and two so how do we evaluate it so this is literally how it gets evaluated so plus can I like when I see this word plus like can i it actually ask the database hey like do we have any functions defined on it and then the database returns plus and then like I substituted with plus and see if it's a valid expression so this is a pretty normal thing and as you can see like it generated the code 10 plus 2 okay no big deal you just substitute your thing okay and you can do 10 multiply 3 it'll give you 10 times 3 and since so I just want to show you guys that I haven't hard-coded anything it's not like template-based or anything so for example I say okay so find 10 multiplied by 3 so here in this case see here the root so we started with fine and like 10 is a child of it but there is no function defined on fine so it as it is actually moving on to the next one which is 10 and now I'm at 10 and like what are the children of 10 it is multiplied and it doesn't make sense at a scholar level but it makes complete sense at natural language tree so you have to design the code in such a way that like given like any types of expressions you should be able to solve it okay I have multiplied and then what is the lemma of multiplier it is multiplied and multiplied has children called by okay what is the children of why it is three so that is how like it falls down to the leaf nodes and leaf nodes get evaluated and it trickles down to the top okay so then this comes down to ten times three and as you can see here so like when I say multiply and I give it to like two variables and it should do ten plus three but if it's a collection I have to do do this like collection dot map x equals to X dot three so this is another possibility that I'm considering here so like I try to evaluate both and see which one makes sense so this one throws a compile-time error at runtime and this one looks good so I'm returning this score okay pretty simple stuff so if you guys search for the same thing in Google Google fills right here like in the third or fourth examples okay so let's see 10 power 2 okay so this is the code mat.com okay so till now I didn't do anything intelligent I'm just substituting okay the next problem is design by equation so let's say you ask your friend hey like what is 10 plus 2 multiplied by 3 so there are two possible scenarios like we know the operator precedence and stuff but like you will actually ask your friend hey like did you mean 36 or 60 so essentially the sky so there are two possible expressions here so that's why it tells you hey like there are two possible things like you can do 10 plus 2 times 3 or 10 plus 2 times 3 so this one leaves you to 36 and this one lets you do 60 so which one do you want so here like you can also give an example and say hey AI hey this is what I meant so you can give it as a sample case like this you can say this should evaluate to 36 in this example you can say something like this and try to run it see now it gives you one example isn't this cool okay so I'm getting on to more exciting stuff now so till now we dealt with two variables three variables okay no big deal now you suggest to tease your friends you can ask you can ask them something like this what is 10 plus 2 multiplied by 20 plus 30 8 or 3 in a real life you won't ask this question but yeah I can answer like all these things you can do craziest over this ok let's see what the ASA's mm-hmm okay so it looks like it computed two different codes so you can play with it so I'll put this online like once I'm done with the demo so like whenever you have time you can just go to compile dot ai and you can play with it it is life okay so now we dealt with like basic math expressions let's go a turn two loops so it's like any programming tutorial that you guys find for any language it's just that this is a programming tutorial for the AI okay so again the same thing you found the tree and you're evaluating everything and ultimately it found two different so the below thousand can be treated as less than thousand or it can be treated as zero until thousand dot two lists so in this case this one makes sense so I need the runtime like I'm checking hey like does this expression less than hundred make sense to me and to the compiler doesn't make any sense so I'll throw it away so that is this is how like I prune like a lot of different possibilities at each and every level and that's why I like it's like super fast okay no big deal okay so now conjunction so this gets interesting at this point because add from this point of view like you have to start adding code in the air modules so for example like I added a conjunction module which will take like expressions like this so two or three and I'm like whenever I see an expression like this I convert that to an expression like two or five and I apply the like whatever is on to the left-hand side of it which is a multiple and so here like ie wrote a quotes in such a way that like whenever I see a expression and I'm applying a function on top of it it boils down to like a regal R or an and so this is conjunction so let's see like how this looks like okay Wow lot of logs okay so as you guys can notice here so like we never defined like all these functions like span drop while take while but the like we are as I told you before like the compiler is actually solving it for you okay but only some of them make sense like in this case only filter makes sense so you can say hey like I actually want the filter part you can say like hey this is the value that I need as an example and it will boil down to like one particular solution here okay then you can actually do the actual first problem Oh okay let's see what's going on so generates like a ton of possibilities so anyways like you get you guys can play with it so I'll just try to wrap it up so essentially like what we are teaching computer is a bunch of strategies on how to do things so here like I have some strategies wherein I can teach a computer like this is how we apply divide and conquer like for example like in merge sort what do we do like whenever we see a collection and we are applying a function on top of it we break it down into two chunks and then like we like sort out B merge the results together until we get to the end so this is like a template that I used and this is another divide and conquer algorithms that I taught it so essentially this is like mathematical induction like a Fibonacci series kind of thing which you can also teach the computer how to do it so like right now I'm working on codes like where I can apply the constraint satisfaction problems on like n Queens or like Sudoku puzzles and things like that so till now like I've we have limited the AI to be like to be working on specific set of rules that you have given in your database but imagine like what it can do if you let it like pull the learn from the online stuff for example it can go to github or again search on google.com and try to understand all the things I think it'll be a amazing product like sometimes down the line I think we are pretty close to a super a pretty soon ok that's about it guys [Applause]