&Notepad

Rust: The New LLVM

Note: this post is part of an ongoing series on extensible compilation. See Part 1: “A Coming Revolution in Metaprogramming”.

Introduction

We usually call a program a compiler when it takes code of one form and translates it into code of a significantly different form, often times a different language (and we usually call more minor transformations “macros”). These two components are called the “source” and “target,” the kind of thing you compile from and to. An important question when building a new programming language is what language you will compile to, or what target you choose. Traditionally, a compiler would target platform-specific machine code/assembly (e.g. x86 or ARM). If you compile C with GCC or if you compile OCaml, then chances are your compiler is using one of these targets.

However, there’s no a priori reason why C has to compile to x86 assembly. A C compiler just needs to translate C into something which, when run, has the semantics that the programmer expects from his source code (i.e. the interface, or language, is separated from the implementation, or compiler). At the end of the day, whatever we write has to get translated down into instructions that our processor can understand. CPUs are basically assembly interpreters, and that’s the most fundamental unit of execution that we can target. That said, it’s cumbersome to write a compiler that can take your language and turn it into x86, ARM, MIPS, and a billion other assembly languages. This is part of the inspiration for LLVM, or Low Level Virtual Machine, which is a kind of “abstract assembly” that looks vaguely like machine code but is platform-independent ¹.

Hence, in the modern day, many languages both old and new have started to acquire compilers that target LLVM. Clang, a C/C++ compiler, is Apple’s counterpart to GCC that targets LLVM. Haskell’s GHC compiler uses LLVM. Rust compiles to LLVM ². The list goes on. LLVM owes such widespread adoption to two virtues: first, because it is platform-independent, a compiler writer can target LLVM and then have his language work across platforms (e.g. on Linux, Mac, and Windows machines) as well as with other languages that use LLVM. Second, LLVM is a simpler language to target than traditional assembly languages—it has nice features like infinite registers and recently support for stack frames.

Of course, not every language must be compiled to x86/LLVM, or be compiled at all. Most famously, Java has its own cross-platform bytecode which is the target of the Java compiler as well as a Java bytecode interpreter called the Java Virtual Machine (JVM). The most common JVM, HotSpot, is itself written in C++, which in turn gets compiled to assembly (it’s turtles all the way down). Many other popular scripting languages like Python, Javascript, Ruby, etc. are all executed (or interpreted) by a compiled program.

In all of these cases, choosing a target language is influenced by a number of factors. A big one is interoperability—to my knowledge, the JVM was developed to get Java to run across multiple platforms, and this was a driving motivation for LLVM as well. Dynamic languages like Python choose to get interpreted as it makes it easier to run code shortly after writing it and get feedback. Rust compiles into LLVM because anything higher-level wouldn’t provide sufficient control over the processor and memory.

I bring up all these languages so as to understand what makes a good target language for compilers. In my mind, a lot of languages that compile to assembly do so because it has the fewest opinions on how your program should run. If you compile to the JVM, you already have to shoulder the runtime overhead of a garbage collector. If you compile to Python, well, your program will probably run pretty slowly and you lose any static typing guarantees. This is why LLVM is a great replacement for platform-specific assemblies—its abstraction doesn’t impose any significant overhead or opinions on the programmer while providing a number of benefits. For these same reasons, I believe that future languages that want LLVM-level control should consider targeting Rust instead of LLVM.

The Rust Advantage

When I say that Rust should replace LLVM, the future I envision is thus: languages would compile down into Rust code, so implementing a new language would be writing a program to parse source code and then generate Rust code. Rust in this kind of ecosystem offers five primary advantages over LLVM:

1. Rust has an advanced type system. Interoperability between languages is limited because often times the least common denominator between two programming languages is at the assembly level. Hence, many languages have decent support for calling out to C but not to Python or Java. However, if two languages compile to the same type system, then they can seamlessly interoperate. My current project Lia is a good example of this. This also means that new languages don’t need to fully re-implement type analysis (although they may need to augment the typechecker in some way).
2. Rust has several useful programming constructs that don’t exist in LLVM. A lot of ideas we take for granted in our programming languages like loops, closures, and enums (sum types), have to be re-implemented every time a new language compiles to LLVM. By compiling a language to Rust, not only do you get access to these constructs, but in my mind it’s generally far easier to write the code generator than generating LLVM by hand, particularly with quasiquotations.
3. Rust comes with a package manager, Cargo. A good language is more than its specification and compiler—it needs an ecosystem of libraries and tooling to actually function in the real world. A bare minimum of any viable language today is a package manager for distributing libraries and handling external dependencies. If new languages compiled to Rust, not only would they get a package manager for free, but they also get free access to programs written in every other language that compiles to Rust. Imagine a world where you could have Rust, Java, and Python all in the same ecosystem with seamless type-level interoperability and the same package manager.
4. People actually write in Rust. Whereas LLVM is intended just as an intermediate representation for compilers, Rust is a language actually meant to be written. This means writing a language that compiles to Rust gets all existing Rust libraries potentially for free—no need to rewrite HTTP servers or command-line parsing for the millionth time.
5. Rust only imposes one opinion on your program: that it should be safe. I would argue that the only real difference at the runtime level between programs you can write in LLVM and programs you can write in Rust is that Rust requires all of your programs to be safe, i.e. not have memory errors/data races. Rust does not require you to have dynamic types, garbage collection, or really any particular runtime overhead—all of the hard work is done at compile time. And this is an opinion that I believe should hold for all programs regardless of how you intend to implement your language.

The Rust Disadvantage

This approach is not without drawbacks. I don’t believe these necessarily outweigh the benefits, but they must be considered or addressed when building this next generation of languages.

1. Rust needs to expose more compiler internals. Currently, all compiler internals and syntax extensions are unstable and only available on nightly. There are plans in the works to change this, but these really only allow programmatic access to the parser/AST. If languages with interesting properties at the type-level (e.g. a gradually typed language) were to be implemented in Rust, it would probably need access to the typechecker to avoid reimplementing the entire type system.
2. The story for dynamic languages needs refinement. Specifically, it needs a battle-hardened GC (as far as I know, there’s really only one major attempt so far). Rust also needs some sort of JIT in order to build any kind of REPL (I’m working on this).
3. Error reporting and IDE tooling are insufficient. Ideally a language that compiles to Rust would want to leave things like checking for invalid variable uses (e.g. using a variable that doesn’t exist) to the Rust compiler. However, when rustc emits such an error, there’s no meaningful way to map it back to where it came from in the original source. This is not an unsolvable problem—Javascript has had this for a while with source maps. Additionally, features like syntax highlighting in editors for new languages intermixed with Rust would need to be developed.

Moving Forward

For my dream to become reality, we need a lot of work to develop Rust as a compile target, both on the Rust compiler and on compilers targeting Rust. Several members of the Rust community are working hard on Rust’s metaprogramming features, but more work needs to be done on languages that compile to Rust. To my knowledge, Lia is the first major language that actually compiles directly to Rust. Work on such languages and tooling can slowly push us towards a world where languages are no longer developed in isolation but instead all belong to a cohesive ecosystem. If you have any ideas on how to do this or if you vehemently disagree, send your diatribes to wcrichto@stanford.edu or post in the comments.

References