Codebase as Database: Turning the IDE Inside Out with Datalog (2020) | Hacker News Reader

Codebase as Database: Turning the IDE Inside Out with Datalog (2020)

petevilter.me

258 pointsrohitpaulk39 comments

The biggest challenge with incrementality in the IDE (I'm not even talking about incremental parsing or whatever) is you're subject to the whims of a given language's build system and how it behaves on multi-million LoC codebases. With sufficient human suffering thrown at the problem, you can approximate decent incrementality, but it ain't easy.

It's not written about anywhere, but there is a long and storied history of trying different takes on "IDE Incrementality" for the Visual Studio IDE, all in service of making it a more palatable experience for people working in utterly massive codebases. Most failed, and the one that stuck (which I worked on for a bit, yay!) still has some weird issues with the experience where an end-user "knows what they want" and get bothered by the fact that stuff is still getting initialized, and they may or may not get what they want in a completion list. It's better than the legacy behavior, where the IDE loads context for all things up front before freeing up the UI (which would mean 10+ minute IDE loading screens for some users). But it's an inherently flawed system.

why isn't the compiler incremental?

It doesn’t need to be / it is, depending on perspective. The C# compiler, for example, has what’s called a “semantic speculative model” wherein it will use various heuristics to know when you need to re-typecheck things or not (e.g., editing just the body of a method without changing a type signature kicks off much less work than if you also change the return type). But it’s also just really fucking fast and will use as many threads as you want it to, so it can also be kinda moot too. Very rarely is the compiler actually a bottleneck in the C# case, but could be in others.

This is a well composed idea. This reminds me slightly of (Rich's?) Codeq https://github.com/Datomic/codeq although codeq is only outlining code/scm relationships and not syntax trees etc. I think I was always hoping codeq would add something like this (for doing what you are doing to validate forms) but the input mechanism probably needed more hammock time

Martin Odersky (lead designer of Scala) also pursued this approach some years ago, not sure if any of this actually went into Scala3. He mentioned this in many talks before, such as https://www.youtube.com/watch?v=WxyyJyB_Ssc (JVMLS 2015 - Compilers are Databases)

Meta uses something very much like this in production. It’s open sourced at https://glean.software/

Thanks for sharing this. I’ll check it out in a bit deeper detail soon.

First reaction though: How many query languages does one need and why has Facebook come to define so many of them? It’s pretty interesting but also somewhat suspicious.

When you hire a lot of talented engineers, they tend to keep themselves busy

It's not a new approach but actually a very old one. The author mentions Intellij but fails to note the history of Eclipse which, via IBM's Visual Age, you can actually trace back all the way to Smalltalk, which arguably had one of the first modern IDEs three decades ago.

Smalltalk programs were stored in a database. There were no .sm source files on disk anywhere. It had a refactoring browser, which was a tool that allowed you to restructure the code. This came straight out of the first research papers on refactoring. It came with a class hierarchy browser as well. It was pretty amazing for the time. Smalltalk was very clever about exposing its internals to developers. Refactoring, introspection, reflection etc. were all things that it supported out of the box. And meta programming, which is something that came out of the Lisp community, was also supported of course.

Visual Age was basically built around IBM's tooling for Java, which included an incremental compiler they built. A lot of the people involved with that had a Smalltalk background (it actually also was a Smalltalk IDE). It stored code in a database. Later, they created Eclipse which dropped the database but kept a lot of the compiler internals that allowed it to be way faster at refactoring and working with Java code than Intellij ever was. I use that every day and I still miss the two orders of magnitude difference in speed that Eclipse used to have. You must think I'm exaggerating. I'm not. Eclipse would be able to compile and be ready to run your code in between key presses. We're talking milliseconds here. In Intellij it's never less than 4-5 seconds and usually a lot more. Even on an M1. I have one. It helps. Faster is better. But it's still slow. It's just architected wrong to be that fast. It would need to internalize the compiler for it to be that fast and it just never did that. It relies on external build tools running via forked processes. It mitigates with a lot of (flaky) caching. That's why it has a top level menu option labeled "Invalidate Caches". Because cache coherence is a hard problem and they have plenty of bugs related to that.

So, it's an old idea and a very good idea. The ultimate version of this idea would be intentional programming (https://en.wikipedia.org/wiki/Intentional_programming) where the core idea is that programming is manipulating abstract syntax trees and that text is a mere serialization of that syntax tree. With intentional programming, you use tools (including editors) that do things with that syntax tree. Sadly, Simonyi, the person who came up with this never really got any traction with the company he founded out of Microsoft for this.

However, modern compiler design is finally starting to acknowledge that there is value in being IDE friendly. A compiler necessarily has to do a lot of the same things an IDE does but with very different requirements. Simply running a compiler from and IDE is slow and leads to a lot of repeated work. A much better approach is a compiler that exposes its internals to the IDE directly and runs incrementally. Like IBM did with Java in the late nineties. The Rust community has also been working on this lately and it's a topic that you see discussed in the context of other compilers. And with VS Code gaining popularity, a lot of languages are now supported through language servers that expose (some) basic refactoring functionality and other things. Mostly this is limited by the underlying tools; i.e. compilers and interpreters. It's nowhere near what Intellij does but it's better than nothing. And it's creating some stimulus for compiler makers to do better.

Jetbrains took their sweet time figuring that out (given they make IDEs and a major language) but their upcoming version of the Kotlin compiler frontend takes some steps in that direction as well. Java is slow in intellij. Kotlin is slower. Because the compiler is doing a lot of work and it can easily take something like half a minute to compile our code base; which isn't that large. I love Kotlin but I don't like how much time it sucks out of my day waiting for stuff to happen in intellij. And it needs to re-compile things quite often. The flipside is that it's a very good IDE that provides a lot of time saving functionality. I have a love / hate relationship with it. Love what it does, hate how slow it is doing it.

> Java is slow in intellij.

If you're comparing IntelliJ with any other major IDE, that's so incredibly wrong. Very bold of you to claim Eclipse is faster at anything. Everyone was using Eclipse 10 years ago, but it was just such a horrible experience that today the large majority of people are either on IntelliJ or even VSCode! WE didn't move because we liked to learn a new tool with different ways of doing things (IntelliJ used to be even more opinionated back then)... most of the devs I know only moved to IntelliJ reluctantly, forced to by everyone else who had already moved saying how much better, faster, polished it was... and once you moved, you would agree and convert more people because it was, and is, just that good.

I still don't understand why Eclipse as an open source project couldn't adapt. Unlike emacs, which is written in elisp, Eclipse is written in Java, the language in which its users are fluent. Why do developers move instead of adapting their IDE?

Funding ! eclipse IDE is in majority maintained by IBM and IBM has decided to allocate less money to Eclipse.

That doesn't explain why the community didn't step up much much more and brought the development to new heights.

What is holding back Java developers from using their Java language to adapt the IDE written in Java that they daily use? If their boss told them to implement a feature, they would do that. But they don't implement the feature when they need it.

It's a relative doddle to make changes or write an extension to Emacs or even a Smalltalk system like Pharo.

Eclipse, by comparison, is complicated. There's a whole lot of scaffolding and frameworkshit that goes into building an IDE that works the way Eclipse does, and that greatly increases the friction of extending it. Plus Eclipse, like most Java programs, is not really a live system that can be extended and changed as you run it; both Emacs and Smalltalk are. Not being live further increases friction. End users aren't really supposed to extend Eclipse themselves, just download and install prebuilt extensions, and this is accounted for in its design.

Visual Studio Code has the same problem. It may be somewhat easier to extend than Eclipse, and it was certainly intended to be so, but doing everything in webshit didn't really address the fundamental issue.

They are talking specifically about the built-in incremental compiler of the Eclipse IDE, not the whole IDE experience.

I moved to intellij because Eclipse's gradle support was lacking and people seemed to no longer care about fixing it to e.g. run bog standard Spring Boot projects. So yes I did move, and no I don't agree with you on this. And after years of using it, it hasn't gotten much better.

Intellij is and was a resource hog. And slow. It's a recurring topic in the Intellij release notes. And it did get better over the years. There are numerous open/unresolved issues in their issue tracker related to all sorts of performance issues. No need for me to file new ones: they know. That's why they keep trying to fix and improve it. But the proper fix is going to require doing what Eclipse did two decades ago, which would be a major architecture change. I don't think they'll ever do that for Java. They might do that for Kotlin though as that is a compiler they've built. Not doing this from day 1 with Kotlin was a design mistake IMHO. But they are working on a more IDE friendly Kotlin compiler.

I've actually demonstrated how slow intellij is to people who told me I was crazy. On their own supposedly heavily optimized setups with their own projects. Edit some code, run some test. Eclipse: no delay whatsoever, test start running immediately. Intellij: it takes at least a few seconds before anything happens. That's the best case scenario. Change even one letter in the code and now it "incrementally" compiles, which in Intellij means firing up a gradle process. In Eclipse, the process already runs. It picks up the change immediately and then the single file that you changed is recompiled. It could even do this on broken code. So you could have compile issues in the file and still run a unit test against the non broken parts. Partial and incremental compilation are hard problems to solve. Eclipse had this, Intellij does not. It does some incremental stuff via gradle. But that takes a lot more time. About two orders of magnitude more. Even on a new M1 macbook pro.

Hm, I actually liked eclipse, once I got a bit used to it. At least for a Java project. Mixed feelings about stability sometimes. Mixed feelings about intelliJ's bloat as well.

Eclipse is definitely faster than InteliJ on the same hardware.

It doesn't start indexing every single project I open, dragging the whole computer to its knees, it does incremental compilation on file save.

VSCode support for Java, relies on libraries from Eclipse headless project, so even when using VSCode you're in fact using Eclipse.

I am not freely touching InteliJ other than the workflows I am forced to, like Scala plugin or Android.

I can't speak to historical Smalltalk -- maybe Alan Kay or Dan Ingalls will come on thread to clarify -- but its lineal descendants, Squeak and Pharo, absolutely do store sources in separate files on disk -- for Squeak, in the SqueakVxx.sources and <image name>.changes files respectively. These aren't really databases, either, just blobs of Smalltalk source each of which contains class definitions and method updates linearly serialized; the Smalltalk system knows how to walk and index them to find the source for a particular method. Contrary to popular belief, the image is not used to store smalltalk source; if you remove either of these files, the Smalltalk system can recover source code for compiled methods in the image from the compiled bytecode, but things like local variable names will be lost. The source files are not intended to be hand-edited directly, of course, but you can, theoretically, do it.

I was probably using visual works at the time I used it (briefly). https://en.wikipedia.org/wiki/VisualWorks

I basically never saw any source files. According to wikipedia, you could export them though. But it's a long time ago and I never did much with smalltalk. I was still in university and this was part of our object oriented programming course.

A file that is easy to read and index sounds like a database to me. Not an sql database obviously.

VisualWorks was probably way different. But I've heard "Smalltalk had no source files, it stored all its program source in the image" enough times in a variety of contexts that I felt the need to address it.

The fact that the files aren't meant to be hand edited already makes it quite clear how it goes, not every kind of image file is a binary blob.

That is why there are export/import tools.

VisualWorks was the same

https://news.ycombinator.com/item?id=32432411

except when it was using ENVY/Developer

https://www.google.com/books/edition/Mastering_ENVY_Develope...

Also my guess is that with Gemstone the code was in the database (but I am just guessing).

https://gemtalksystems.com/products/gs64/

In traditional Smalltalks, all the method objects have a shared object representing the file that method source is stored in (either .sources or .changes, with room for more) and an offset in the method to point to the text. On compilation, all it does is write the new method with metadata to the end of the .changes file, then set the text indexes. There is a mechanism to crunch out all the unused source text and generate a new merged .sources file. If you are all working on the same base version, .sources files can be shared since they are usually read only.

The nice part of doing this is you don't have to use much core for the method source, which was a big deal in 1978. You can easily strip the sources and changes files if you don't need them. eg. when distributing a build to customers. It also lets you remember the change history and enables recovery from crashes and other errors. The basic mechanism is also fairly easy to repurpose to support other change tracking approaches.

The interesting trick, is if you don't have a .sources or .changes, the system will run the Decompiler, which almost always produces readable code that is structured like the original source but with no comments and the local variable names changed to t0, t1, t2,... etc. There have been proposals to keep local var names in the image as to make it a bit less painful. It is surprisingly easy to code like this. There have also been proposals to store the whole source text in the image. You could do it and it wouldn't be hard, but you'd lose the advantages of the external code storage.

This does not count the various project facilities and change lists so you can keep related changes grouped.

`jillesvangurp` may be talking about ENVY/Developer -- "All code is stored in a central database rather than in files associated with a particular image." page 4

https://www.google.com/books/edition/Mastering_ENVY_Develope...

At least in my experience Eclipse was dog slow even on machines with sufficient resources. I switched from Eclipse to Intellij back then speicifcally coz Intellij was faster

The dumb editor parts are slower, but the smart refactoring parts are much faster. Eclipse understands your code while IntelliJ just manages it by passing it around.

Both IBM and Energize also used the same approach for C++, but it was too resource hungry back in those days.

Visual Age for C++ 4, and Energize C++ were their products.

It took almost 40 years to get back to what C++ IDEs were started to look like.

Great post and I’m glad to see someone else spotted the obvious similarity to Smalltalk.

I similarly thought codebase as a database, but the author makes a serious attempt. I'm pretty sure that Lisps fit the model.

Lisps would have easier parsing but that's about it

Functions and macros could help making a DSL, which is suitable for convenient data definition. It could be helpful in more ways than just allowing simpler parsing.

This is very good work

One of my ideas is "lazy invariant maintenance". It should be possible to layer the tip of execution (what should go on next) with lazy incremental materialized invariants. Let the computer decide what is the most efficient approach to solving the computational problem. In other words everything is a query and queries are layered ontop of eachother in arbitrary directions. I think storage or source of truth should be decided by the software. It might be more efficient to arrange data a certain way to sustain multiple types of queries.

https://github.com/samsquire/ideas4#20-lazy-arrange-or-invar...

I mean…

Fundamentally they've done the right thing for the wrong reason.

Yes, code as database instead of code as text files is an old idea that has been tried many times and never really works.

…buuuut, if you look at the places where “not as text” coding works, like blueprint in unreal, you’ll see the successful projects that do this make a new language that takes non text input to the compiler / runtime.

So, building your own language (which is what they did here) to run in your database-ide is actually going to work. There are examples of other things in this category that have worked before.

Thus, the work probably seems quite promising when viewed naively.

…but, I think any conclusions about datalog or general applications of the approach to existing text based programming languages are probably misguided.

The idea of code as data is something that's been churning around in the heads of my colleagues and me for a while now. Compiler optimization in particular is something that can really benefit from this view: The typical fixpoint-style approach of writing optimizers usually requires a ton of fine-tuning in the rules (e.g., manually triggering one rule after a second one fires), and you're still limited to how big a query you can run. On the other hand, start thinking of the optimizer like an IVM system... not could we automate a lot of the hand-tuning, but we can start thinking of scalable cross-module optimizations.

How does this compare/relate to things like https://en.wikipedia.org/wiki/Source_Code_in_Database ?

Source-code can be stored in a database of course. But I think this is about having source-code express the data. In a sense SQL does that already with its data-definition language subset. Or maybe I misunderstood?

Is there a challenge similar to one posed by technical documentation ? In that, the current working methods use files and directory hierarchies, but what if we made a code pool (like a content pool, a pool of topics and other types of content entities) that is easily browsed.

I gotta say. Lately it feels like the internet is always trying to bait me into explaining something properly. My game has been a bit about not doing that because these ideas are old and others have already explored and explained the various tradeoffs involved in the choices I've been making.

However I'll do a bit more now than drop the datalisp.is link :P

What is metaprogramming? Do we metaprogram when we create feature branches in our version control system? Do we metaprogram when we give input to running programs? Do we metaprogram when we use type systems to prove things about our program? Do we metaprogram when we build machine learning models? Do we metaprogram when we package software? For me: "yes" to all of the above.

Isn't "metaprogramming" such a wide-reaching term as to be essentially meaningless? I believe that some words like "language" or "game" can be stretched to cover everything.. so rather than words they are more like perspectives. Metaprogramming is such a thing, it is a perspective, and it happens to be the perspective that I'd like to be able to employ more effectively.

Originally I was deep in math world looking to learn what the future of programming would look like, but I got increasingly frustrated with all the amazing tech they'd developed (the mathematicians) because it wasn't manifested in the cyberworld.... So I figured: I want to build distributed systems. In order to build distributed systems I need a concrete representation for data so that the peers can communicate.

Thanks to hn and lobsters I was aware of many possible representations but for various reasons I believe that canonical S-expressions are sufficient.. For the sake of argument let's assume this is the case; then suddenly there is a concrete place to manifest all the ideas.. okay so what ideas are most urgent? In my mind it is to explore the space of coordination-free programs and this space is spanned by datalog-ish expressivity. From there this name is born: datalisp... I sincerely believe that this is the easiest thing to agree on as a somewhat eternal foundation for further developments in software engineering, otherwise I would still be looking for that foundation.

However there are too many people who are not ready to move on from our current way of keeping score in society and it is hindering our ability to respond to reality. Afaict the highest priority is climate change (at the moment), everything else is noise. We should be working to bring people useful tools for coordinating a response to that crisis but instead I'm shunned, broke, homeless, etc. All because I refuse to be a part of the problem (and I refuse to be a "hero" so I don't do anything well enough for others to admire, I've been trying to leave space for some ambitious academic type or business type but I'm reaching the end of my patience).

What is the goal? why do we work towards it? For me the answer is clear: we need economics that are less vulnerable to the tragedy of the commons. The reason is we need a way to systematically curb pollution.

Now my approach is debatable but no one seems interested in even having the debate. This is perplexing.

Reply on news.ycombinator.com