Code completion is part of every programmer’s working environment, but to plenty of people, it still feels like magic. On this episode, Meredydd Lyff, founder and CEO of Anvil, joins the home team to discuss code completion: what it is and how it works, from first principles to best practices. Plus: Is 90% of biology attributable to magic gremlins?
Anvil is an open-source web framework for building full-stack applications entirely in Python.
Ready to dig deeper into code completion? Check out Meredydd’s talk at PyCon 2022 (he even built a code completion engine live on stage).
ICYMI: Listen to our previous episode with Meredydd about countering the complexity of web programming: Full-stack web programming with nothing but Python.
Connect with Meredydd on LinkedIn or Twitter.
The Lifeboat badge shoutout is back. Today’s badge goes to user Tomasz Nurkiewicz for their answer to Best performance for string-to-Boolean conversion.
Meredydd Luff Oh, this is cheating, but the point is that everything's cheating. You're always cheating. Cheating works, so you're allowed.
[intro music plays]
Ben Popper Gatsby is the fastest front end for the headless web. If your goal is building highly-performant, content-rich websites, you need to build with Gatsby. Go to gatsby.dev/stackoverflow to launch your first Gatsby site in minutes and experience the speed. That’s gatsby.dev/stackoverflow. Head on over, use that link, let them know we sent you and help out the show.
BP Hello and welcome everybody to the Stack Overflow Podcast, a place to talk all things software and technology. I am Ben Popper, Director of Content here at Stack Overflow, joined as I often am by my wonderful co-hosts, Matt and Ryan. What's going on, y'all?
Ryan Donovan Hey!
Matt Kiernander Hello everyone.
BP We have a returning guest today, Meredydd Luff, who is the co-founder, CEO, and jack of all trades at Anvil. Welcome back.
ML Hello. Great to be back.
BP Apologies for butchering your name, but I do what I can. You reached out with a pitch about code completion. I want to hear it. Apparently you gave a presentation so let's start there. Actually, no. Just for a refresher for folks, who are you and what is Anvil?
ML All right. So my name is Meredydd. I'm one of the original creators of Anvil. Anvil is a web framework for building full stack applications entirely in Python. So the idea is that you don't need to have that sort of full stack JavaScript, HTML, CSS, Python, SQL, React, Redux, Webpack, Bootstrap, all that stuff, just to make a button that does something when you click it. So instead we built something where you can drag and drop build your user interface, then double-click one of the buttons there, and you’re writing Python that drives that user interface, and that runs in the web browser, and then you write the Python that runs on the server, and then you click a button and it's live on the internet and again, hosted for you. And it's an open source framework, you can pull it apart and edit it in VM and host it locally and so on, but the point is that just to reach that basic point of, “I would like a button that does something when I click it,” you do not need to know five different programming languages and six different frameworks. You can do it just in Python. So yeah, that's who I am. That's what I do.
BP Yes, and you came on once before and we had a good discussion about this, but you were working on a project and now have done a presentation on it. So give us the thesis and then I'm going to step aside for a minute and let Matt and Ryan respond.
ML So the talk you are referring to was one I gave at PyCon a couple of months ago about code completion and I think code completion is a really interesting topic. It's one of those things that's part of every programmer’s toolbox. Almost everybody listening to this uses an editor, which as they are typing in their code, is popping up a little suggestion box offering to complete your identifiers, variable names, all sorts. And this is really great stuff and I can go on at length about why it is great from a sort of human factor's perspective, but everybody uses it every day and yet it feels like magic. And so I got interested in this because we ended up having to build our own code completion for Anvil for reasons I will absolutely go into in a moment, which meant that I actually had to crack open the magic box and find out how it works. And it is this marvelous combination of something that feels like magic when you are using it and is actually incredibly simple and is really satisfying because learning how it works teaches you so much more about how your program is running in the first place.
MK I watched your talk yesterday, going over your story, how you got to code completion and everything else, and I was kind of blown away by the fact that I've been using these tools for the last however many years and completely taking for granted and just not wanting to peek behind the curtain, because I was like, “That's going to be far too complicated. All I know is that it works. I'm not going to touch it. I'm going to let the little magical elves run around and do their thing in the background and then just out of sight, out of mind.” But the way that you explained it was very accessible I think for people to understand, “Oh, this is actually not as complex, at least initially, as a lot of people would think it is.”
ML Yeah. So this was a talk stunt at the talk. I'm not going to try and do it here, but I actually built a code completer live on stage in about five minutes just to show how simple it was, because the fundamental principles are simple. This is one of the things I really like about working with computers. My undergraduate degree was in biology, and when you're working in biology, 90% of what happens is the magic gremlins and you just don't know exactly what's happening. Maybe someone has an idea of what gene is involved, maybe someone doesn't. It just happens and you have to sort of keep your focus tight if you want to make any progress at all. But with computers it's fundamentally all a knowable system and so whenever you see a little box with the magic elves, it's just worth thinking about cracking it open because sometimes the answer inside is delightful.
RD I'm curious more about the answer because I would see something like that and think that this is sort of the same as a search box that does autocomplete.
ML Uh-huh. And it really isn't.
RD And it really isn't. I think that's fascinating. So why isn't it like that search box?
ML All right. So let's actually crack in. So the job of a code completer or autocompleter, some people use the terms interchangeably, is you've got some text box open with a program half written in it, and you've got a cursor in it at some point. And the editor, to pop up that little box, needs to know what are the valid moves you might make next. What are things that you might want to type where the cursor is? And if you are doing say autocomplete in a search box, that's relatively straightforward because the set of things you might want to type is fairly bounded, if you're not Google. Even if you are Google, you can sort of take a statistical sampling of what people have typed in, what of those things are the most popular that start with the characters that the user has already typed. That's something you can do in a nice 10 lines of Python. The thing about code completion is that you’re not typing the same thing as everybody else or even as you typed earlier, so the code completer needs to understand what's going on in your program enough to understand that your cursor is at a position where you’re going to want to type a local variable, and then it's got to understand what's going on to know what local variables are defined at the point in your file where the cursor is and offer you those options, which is kind of daunting if you think about it as a string with some stuff in it. I mean, if you imagine trying to pick that out with string operations it blows your mind. But actually, if you think about it, that is exactly the same problem as your compiler or interpreter for your programming language has. So let's say you are writing Python– it doesn't really have to be Python. Let's say you're writing Python, you type Python myscript.py to run your program, and what that does is it launches the Python interpreter, and the Python interpreter will read in myscript.py and it will follow the instructions, it will do what that file says. Now it doesn't actually scrub through your file character by character seeking through as it executes reading each line, because that would be horrendously inefficient. So what it does instead is it transforms that string, that bunch of characters, into a more useful format, and that process is called parsing. So what it does is that there is a chunk of code called a parser and you feed it this string of bites of characters and it spits out something called an abstract syntax tree, which is a hierarchical tree of objects that represent the code that was ingested. So you could have, again in Python, the top level object will probably be module, and then under that it'll have a list of the statements in that, and one statement might be an assignment and it will have the target is a variable named X, and the value is a number named 42 and that's how it represents the statement, X=42. It could have a function definition statement, which will have some set of information about the arguments in that object and then inside it it will have some list of the statements in that function and so on. And that is a much easier format to deal with because it's just a tree of objects so you can write functions that will walk over this tree, and that is indeed what an interpreter or a compiler does. It walks over this tree, usually spitting out some kind of code. So Python spits out bytecode, if you’re using JavaScript then all sorts of wizardry is going on, but it usually goes via a bytecode intermediate step. If you're using a compiled language like Rust, it's spitting out intermediate code and then assembly and machine code. But that's the basic structure– parse it, get the tree, walk over the tree, and then you can do something useful with it. And actually as an aside, if I'm allowed to go down this alley, parsing is really, really, really cool. That parser code isn't actually even written by a human being. So if you go to your programming language’s repository of choice, you'll find something called a grammar file. And that is a textual specification of what could go into any valid program in this language. You could specify an if statement is going to be the word if, followed by an expression, followed by a colon in Python, followed by a block of other statements, and then followed by maybe an L statement and a block of other expressions, or maybe an L if then a statement then a colon or then something else, and there's a sort of cursive definition that describes anything that could possibly be in that case a valid Python program. What you do is you feed that grammar file to something called a parser generator, which is a piece of code that reads in the grammar file, walks over it, and then spits out code for a parser. So what you've got is, you feed in this text file to a parser generator, you get out code that then runs as a parser, so that's code you can feed your source file to and it will spit out an AST, which is enough to make you feel slightly dizzy, but really, really cool and recursive in the best computer science way. It's fortunate then that if you are doing experiments in code completion, many languages, Python among them, actually has direct access to the parser yourself, so you don't have to deal with all that complexity. If you're running in Python you can import AST and AST.pars, and then you give it a string and it will give you back the AST. Because in Python, the AST is Python objects– well, what’s representable by Python objects. So actually, when I was demonstrating the autocompleter live on stage, I wrote it in Python because you could just get the string of code, feed it to AST.pars, and you get this set of objects that you can recursively walk over. So anyway, parsing, it's really awesome. But autocomplete has very similar problems, because if you’re building a code completer, what you've got is a string of code with the cursor somewhere in it, and what you've got to do is understand what's going on in that program to understand what's going on around that cursor. And what you can do is you can replace that cursor with a magic symbol and then just feed that string to the parser and the parser will produce an AST representing your half-written program, and then somewhere in it will be that magic symbol. And so what you can do is replace the cursor with a magic symbol, speed it to the parser, and then you start walking over the AST. Now, you're not generating code this time– you’re building up a representation of what's going on. So as you walk past a variable definition, X = 42 in Python, or let X = 42 in JavaScript, you record, “Oh, well I know there's a local variable called X now, and it's a number.” And then you can walk through and when you see a function definition, you can look at its arguments and go, “Oh, well this function has arguments called A, B, and C, in which case I have local variables called A, B, and C now walk on in.” And then at a certain point you will find some expression with the cursor in it. Maybe it's Z = and then the cursor. And at that point, you've found the cursor, you know where it is, you know what expression it's in the middle of, you know that it's in the place where you could use a local variable, and you've built up this representation of everything that's currently in scope which means that you can offer a very sensible set of code completions. And that is the basic principle. You feed your code to a parser, you get a tree walk over the objects, and when you hit the cursor you can get a list of sensible completion because by then you know what's going on.
RD That's fascinating. I think when you started talking about it, I was like, “Oh, is this interpreting compiling the program on the fly?” It sounds like it almost is.
ML Certainly it's parsing every time, yes.
RD So when it's building out the AST, what happens if there's errors previously in the program?
ML That is an excellent question. So in the talk, I dealt with a series actually of escalating, “Okay, here's the simple version. Here's the thing I've built in front of you. Now what are the complications that I can't build in five minutes?” And this is absolutely one of them. They all reduce to a central theme, which is that if you’re looking at an AST, you're looking at the program on paper, you’re not looking at it running, which means that you’re having to guess what it's going to do at run time. Now depending on how dynamic or not your language is, the greater or lesser extent of guesses, so there's this principle called the halting problem is one of its names, Turing undecidability. If you are just looking at a program on paper, you can't tell for sure in general what it's going to do at run time, which means that in Python, you can throw an if statement around a function definition. You don't know whether that function's even defined. And obviously that means if you're autocompleting later down the file, you genuinely don't know what is and isn't in scope, which means that you are always guessing. And actually many people these days use something like VS Code, which uses quite loose code completion, because the philosophical difference here– sorry, wild tangent. The philosophical difference is there are basically two types of code editors. There are text editors and then there are IDEs, integrated development environments. And an IDE is typically something like IntelliJ or WebStorm or PyCharm or whichever of the JetBrains fantastic products you use– not a paid endorsement, because Anvil is absolutely one of these. It knows about your project. It knows for sure where all the source files are, where all the imports are, and every edit you do is really in the context of a project. And that means it can be fairly confident about where your source files are, what possible libraries you might import, what environment it's running in. Something like VS Code is fundamentally a text editor with bits of sort of IDE-type functionality like code completion bolted onto it, which means that if you’re editing, if you just open a .py file in code or a .js file, it has no idea what is around it. It can take an educated guess, but at a certain point you'll see VS Code fall back to autocompleting, “Well, I don't really know what's going on here, but at least this is a word you typed earlier in the file and maybe you are typing that word again.” There's a big philosophical difference here. You'll find programmers getting very opinionated about “I want a text editor that's being a text editor and bolting it together with lots of other tools,” or “I want an IDE that knows everything about my code.” I'm an IDE person. I like that generally speaking, the JetBrains suite is less likely to do that to you because it can be really quite disconcerting because it's really how much you trust your autocompleter. Because if your code completer will just fall back to giving you random words you've typed before, then you have to think before hitting the tab key every time. And if it's really always giving you parsed results in which it has high confidence, then you get much more confident. But the point with all of these systems is that they are always guessing. It's not like proving a theorem. Building a code completer is like building the graphics for a computer game. Your only job is to keep the human in front of the monitor happy, which means it's perfectly okay to guess. So if you see a branching if statement around that function definition, just have a heuristic guess that they probably mean to define that function and carry on and maybe you'll give someone a slightly accurate code completion, but it's probably going to keep them productive and happy. So that's the simple version. Ambiguities like that actually are fairly rare in practice, but syntax errors, which is what your original question was about, those happen all the time because it's a half-written program, of course someone's left a syntax error four lines up. And if you feed a program with a syntax error into your classic parser, it will go [popping noise] and give you a syntax error. If you do AST.pars, it'll raise a syntax error in Python, similarly again, choose your parser of choice. That means it's raised an exception rather than giving you an AST, which means you now have nothing to go on. And there are broadly two approaches you can take here. If all you have is that kind of parser, then you can go with the grotty little hacks and you can go, “Well, there's a syntax error on line 14. What if I just blanked out line 14 and tried parsing it again?” This is cheating, but the point is that everything's cheating. You're always cheating. Cheating works, so you're allowed. It's better style to do it the other way, but it does in fact get you an awfully long way just managing the text thread. But the really stylish way to do it is to have a parser with error recovery. So this is a parser that can spot that there's a syntax error, that the text it's been given does not conform to the grammar definition it's been given, and instead of giving up and throwing an exception, it will give you an AST but it will usually have like an error node in it. So, I've got a function definition and then two valid lines and one line with a syntax error and then another line afterwards. And it should give you an AST that has all those other statements in, but then just like an error marker instead of the assignment statement or whatever was supposed to be on line 14. And what that means is you can walk over it and sure, again, you're getting an approximate partial read on the code, but at least you're getting some decent autocomplete. Now of course, the problem with that is that error recovery is again a very dicey business. I mean, this was a famous problem with old C++ compilers. I'm showing my age here, but old C++ compilers had this dreadful habit of failing to recover from errors. So once something went wrong, you've got the original syntax error and then it would try to recover, fail to recover, and then because it wasn't sort of lined up with your code, it would then give you a bunch of syntax errors for every line after that in your program because as far as it was concerned, none of this made sense, which is tricky. So, error recovery is another of these approximate processes that's there to keep a human happy. Some parsers are better at it than others. It is the unfortunate lot of the Python autocomplete developer that the pgen parser used in Python is spectacularly bad at error recovery because of the particular way that parser is constructed. So actually, I'm afraid to admit it on a podcast, but here I am doing it. Anvil's code completion still uses the grotty little hacks of mashing the text around when there's a syntax error so that you can identify the syntax error and still code complete on other lines.
MK So considering that you have quite a storied history with code completion and going through a variety of different parsers and compilers, I'm very curious as to when you are trying to design Anvil’s code completion, what were the big problems or big things that you wanted to have as part of Anvil that you were like, “I hated how that was done. I'm going to do this so much better and it's going to be fixing everything and it's going to be magical.” What were the big things you were excited to work on there?
ML All right. So I think we have to acknowledge here that there are really, really good code completers out there in the wild. There are ones built into commercial products like the JetBrains suite, great fan.
MK Yeah. JetBrains just produces quality stuff.
ML Yeah. The JetBrains Suites are pretty excellent. There's a bunch of open source ones as well. So Microsoft open sourced a bunch that they used in the language service for VS Code. Also if you're a Python person, then there's a package called Jedi, which is a Python code completer. And these things are in fact great and I don't have huge problems with any of them really. The big problem is really twofold. One is that Anvil is a full stack development environment which means that when you’re typing your code, the environment is aware of what schema that you've had for the built in database, what tables you have, what columns are in it, what components you've dragged and dropped onto your screen, what functions are available on the server code? So this is a classic example of things that are wrong with modern autocompletion, not so much with modern autocompleters, but the way that we build code today. When we are building for the web, you are writing two programs. You write a JavaScript program in the web browser and a Python or whatever program on the server, and they have to talk to each other over Rest, and that means neither of them really knows what's going on inside the other one, which means that by the time you've got a record out of the database and served it over a Rest endpoint, and then you've ingested it into your JavaScript, the editor that you're using to edit your JavaScript has no idea what the server is about to serve it up on that HTTP endpoint and so code completing that is really difficult and there is some progress with this with open API but the tooling is clunky as heck still. So a big thing we wanted to do with Anvil is that the environment knows about your server code as well as your client code, which means that when you make a server call, it can code complete, “Hey, these are the functions you might want to call on the server. These are the arguments they take. This is what this thing returns so I will give you sensible autocomplete if you use its return value,” and we could have taken an off-the-shelf completer like Jedi and mashed a bunch of those features into it, but the other really killer problem is that these off-the-shelf code completers, they're expecting to be used in a classic local IDE which means they're expecting files. And Anvil, the online editor, well it's an online editor, so when a programmer is typing, there is just not a lot of time between keystrokes. We move fast, you do not have 300 milliseconds to send the current state of your code to the server, run it through something like Jedi, and get the results back. There are a couple of online code scratch environments that try to use this autocompletion system and it's almost unusable because it's so far behind where you’re typing. So we knew we couldn't do that, which meant that we basically had to have one in the browser and so we chose to roll our own. We used the Sculpt parser because Sculpt is a Python to JavaScript compiler, which we already have because we have a web framework that runs Python code in the browser so we have a Python to JavaScript compiler lying around so we just yanked out it's parser and AST and run your code through that and then sort of home built the autocompleter. And a thing that's really nice about building the architecture that way is that from the ground up natively it knows about the full stack, it knows about UI components, it knows about server code, it knows about your database schema in a way that would've been quite difficult to hack in with that fidelity to an existing completion engine. But honestly, if that'd been like a tractably easy way forward, I would not have embarked on this journey, and honestly, there's a lot I wouldn't have learned so I'm kind of glad I went there. But it was very much a decision born of necessity in that one.
MK With your experience with code completion and everything around that, you must be aware of GitHub Copilot that has launched recently and I'm curious as to where you see code completion coming from that standpoint versus what GitHub Copilot is trying to achieve as well.
ML So Copilot is sort of a completely different beast to classic code completion. It's this honking great big neural network. It is kind of treating your code more like English prose than like code. And this has some advantages, it displays an astonishing amount of what looks like semantic understanding of what you’re doing and the ability to sort of help you with that creative step of what you’re writing next. But equally as a result of that, it's sort of firmly into that simulating creativity space. It's not about, “What are my valid moves next?” It's about, “Make something up for me next.” It's the difference between what chess moves are available next on this board, and what's the next sentence of this poet. It's an incredible achievement. I don't think we'll ever replace traditional parsing-based code completion because when you’re using Copilot you're okay hitting the tab key, waiting a couple of seconds and reading what it produces and seeing if it's a good idea. When you’re using code completion, it's kind of burrowed into your brain stem. I said you don't have more than a couple of milliseconds because that's the length of the feedback loop you are using with your code completer. You just want to type x.i tab, and it will type x.initialize for you. Copilot is not going to give you that, it's giving you something different, and I am looking forward to a world in which we all get to use both.
[music plays]
BP All right, everybody. It is that time of the show. We're going to shout out the winner of a lifeboat badge– someone who came onto Stack Overflow and helped save some knowledge from the dustbin of history and shared some answers with the community. “Best performance for string-to-Boolean conversion,” awarded yesterday to Tomasz Nurkiewicz. Thank you so much, Tomasz, for coming on and answering this question. You've helped a lot of folks in the community. And if you're curious, we'll have this one in the show notes. All right, everybody. I am Ben Popper, Director of Content here at Stack Overflow. You can always find me on Twitter @BenPopper. Email us with questions or suggestions, podcast@stackoverflow.com. And if you enjoyed the conversation, leave us a rating and a review on your podcast platform of choice.
RD I'm Ryan Donovan. I edit the blog here at Stack Overflow. You can find me on Twitter @RThorDonovan. And if you have a great idea for a blog post, email me at pitches@stackoverflow.com.
MK I’m Matt Kiernander. I'm a Developer Advocate here at Stack Overflow. You can find me online in most of the places @MattKander.
ML And I am Meredydd Luff. I'm Founder and CEO at Anvil. You can find Anvil at anvil.works. I am at @Meredydd on Twitter, although I try to post as little as I can get away with, and Meredydd@anvil.works. It's been great being here. Thank you so much for having me.
BP Yeah, thanks for coming back on. We appreciate it. All right, everybody. Thanks for listening and we'll talk to you soon.
[outro music plays]