Macros in Rust

Rust has a macro system now!

Well, it has the beginning of a macro system. There are a few things that are glaringly absent:

  • hygiene — It’s really nice to have hygiene, but the standard Dybvig algorithm for hygienic macro expansion was a bit too big to implement, and still have time for all the other things.
  • macro scope / macro export — Currently, macros can only be used in the same file they were defined, and they don’t respect any kind of scope.
  • AST agnosticism — The macro expander gives privileged status to expressions. But it would be nice to be able to abstract over other parts of the AST.

In spite of these things, a story for declarative macros in Rust has taken shape:

  • Macro expansion has its own phase, and the compiler can emit expanded code, which can be useful for debugging.
  • Macro expansion happens in the “correct” but unintuitive order: the outermost macro invocation is expanded first.
  • Syntax stores a “backtrace” indicating the series of macro invocations that produced it. This has been useful for debugging errors in code produced by complex macros. However, it’s a bit of a hack. In particular, doing the Right Thing for macro-defining macros would require making the backtrace into a tree…
  • You can use Macro By Example to define macros. It’s a simple, intuitive, declarative way to specify macros, borrowed from Scheme. Unfortunately, I can’t find any good introductions to it, so all I can suggest to the curious reader is that they search for “ellipses” in JRM’s Syntax-rules Primer for the Merely Eccentric, or reading the paper that codified the system: “Macro-by-example: Deriving syntactic transformations from their specifications”.

Complicated macro invocations in Rust currently look much like Scheme macros, if you turned all the parentheses into square brackets. We have some interesting ideas for how things could be different. But that’s for the future, and for now, I’ll sign off.

Dwarf Fortress

My brother is learning how to play Dwarf Fortress. We talk about it over IM sometimes.

Eric: “I’m learning how irrigation works”

Eric: “for example, I have now irrigated my hospital”

If all you’ve heard about Dwarf Fortress is isolated anecdotes, you probably don’t have a very clear idea of what kind of game it is. Neither do I, and I’ve spent many hours playing it. Things that you may need to think about in Dwarf Fortress include (a) prevalence of ores in different geological layers (b) danger of infection of untreated wounds (c) jealousy amongst aristocrats regarding room furnishings (d) risk of military training injuries (e) ease of access of drawbridge/floodgate/hatch control levers (f) pasture size for grazing animals (g) psychological impact of failure to bury the dead.

Dwarf Fortress has a maddening difficulty curve, and even a good player has many corners of the game that they still do not understand. The UI is inconsistent and inconvenient, but often quite powerful.

It reminds me of some software tools. TeX comes to mind, and Git (a little), and especially Emacs. They are powerful, strange, and complex. It’s virtually impossible to learn any of these tools without having an in-house guru to run to when you get stuck. And when you do start to get the hang of one of them, to the point that you can be a mini-guru to your friends, you begin to worry about what percentage of your brain you’ve devoted to it. There are probably other essential tools that are similarly baroque.

Now here’s the thing that puzzles me: what’s going to happen in the future? Emacs has been around for over 30 years. I’d be surprised if the number of Emacs users were shrinking. Most of the programmers I’ve known use it, regardless of what generation they come from. Can this go on forever?

Like Dwarf Fortress, I suspect that everyone who’s ever used it has had fantasies about throwing it away and building a new Emacs, without all of the baked-in, grotty design decisions from the past. None of this dynamically-scoped elisp nonsense, let’s use Scheme! Let’s revamp the built-in terminology so that “window” means what it means everywhere else! Let’s figure out a better default set of keybindings! Let’s have something like ELPA, except less not-used-by-anyone!

Someday, one of those mad visionaries will succeed. And we will be given a text editor better than Emacs. Can you imagine?

Sharp knives

Oh, great. I’m hitting the extended metaphors already.

The studio apartment that I’m living in for the summer is quite nice, but it came with the dullest knives I have ever used. It’s common to hear that sharp knives are safer than dull knives, but I’m not sure that I agree. Sharp knives are slightly more dangerous to carry around, or wash, or even to look at (though if you get injured looking at a knife, your looking technique needs a lot of work). The advantage that sharp knives have is that they cut things.

If, upon discovering your knives are dull, you decide not to eat fresh produce, then dull knives are, in fact, quite safe, right up until you die of scurvy. On the other hand, if you decide that you really need chopped onions, you’ll wind up moving your dull knives in a sort of mashing motion that’s kind of like a parody of cutting. (Also, you’ll have to stop repeatedly to wipe the tears from your eyes so that you can see.) This is dangerous. It’d be more dangerous to do with a sharp knife, but you don’t, because you could just cut things with a sharp knife.

As you can probably tell, I’m thinking about type safety here.

Most things that people are interested in doing are inherently a little bit unsafe. But if you’re using a crippled tool (even if it was crippled in the name of safety), you’ll wind choosing between (a) doing things the convenient yet appallingly dangerous way, and (b) not actually doing anything (at least at any noticeable speed). For this reason, adding a restriction to a language can endanger users, by forcing them to use unsafe constructs and workarounds.

Rust’s type system’s strength doesn’t lie in having fancy features to prevent array bounds issues or integer overflow. As type systems go, it’s fairly traditional. Its strength is that the type-related features of the language are designed so that the user doesn’t need to (and can’t) subvert the type system. The main guarantee that Rust provides over C++ isn’t the avoidance of some particular kind of error, it’s that when the type system says an expression has type τ, the value it produces actually has type τ. It’s like having a knife rack that doesn’t drop your knives on your feet.

What are macros good for?

A macro is an abstraction that provides source-to-source transformations to programmers.

If you’re a C++ programmer, macros (C++ has two macro systems; I here refer to the one called “templates”) are for abstracting over types. You generate a class for vectors of ints with the macro invocation template<int>.

If you’re a programmer in a first-order language, like ACL2, macros are for abstracting over functions. You can’t pass f to a map function, but you can write a macro that generates code that maps f over a list.

If you program in an eager language, and you miss laziness, you can use macros to make it easy to handle thunks.

This suggests that macros exist to paper over deficiencies in a language. You only need them if your language has second-class features.

Sure, a language without first-class functions is pretty lame, as is a typed language without any kind of type abstraction. But even the lambda calculus has a second-class feature: binding.

Making let a function (so you can write let(x, 6, x*7)) doesn’t make any sense. Functions take values as arguments; in order to make the connection between x and x*7, it’s necessary to understand x as a name, not a value. A macro, which operates at a syntactic level, can do this easily: simply drop the x into argument position in a lambda, and you’ve got a binding.

This turns out to be useful. Schemers, who have first-class functions and don’t need to worry about static types at all, use macros more than anyone else, because they love making new binding constructs. They play with different kinds of pattern matching, new and strange ways to define functions, loops that bind variables, and other fun things.

Once you have a macro system, it’s fairly easy1 to make macros that define macros, thereby providing delicious meta-abstraction. Is this totally fulfilling? Is there anything else that can provide even more abstraction over second-class language features?

I have no idea what those questions even mean.

  1. If a programming languages person says “fairly easy”, it’s a faux pas not to laugh. 

Bootstrapping is hard, let’s go bootstrapping!

Rust is now a bootstrapped language, so the Rust compiler is written in Rust. (Sometimes it seems like applying things to themselves is the only trick in computer science.) This means that modifying the Rust compiler is a bit mind-bending at times. If I write about it, perhaps I’ll remember what’s going on.

Here’s what the build process is like:

  • I make some change to the code.
  • I type make check to set everything going. 1
  • The build system downloads a snapshot version of the Rust compiler from a known location, and calls it ‘stage0’.
  • The build system uses stage0 to compile my modified source code, producing stage1, a compiler that behaves differently, according to my changes. But is it correct?
  • To find out, the build systems uses stage1 to build the code again. The stage2 compiler, since it came from the same source code, should behave exactly the same as the stage1 compiler — they both reflect my changes.
  • Two programs that behave the same should produce the same output for any given input. So, stage1 and stage2 ought to produce the same output when they compile the source code. stage1’s output is stage2. The build system goes through the process one last time, running stage2, whose output is stage3. If stage2 is exactly equal to stage3, then there’s a good chance that the compiler works.

So you have (let me count) 3 compiles in there. The confusing part is when something goes wrong. Something crashed: I have a source location, so I know where the problem is. But what level is it at? Did compilation fail because I broke the code being compiled, or the code doing the compiling? It’s a fun problem.

  1. Among other things, it also runs through the source, making sure that none of the 30,000 lines of code is longer than 78 characters. (This is probably correlated with Graydon’s fondness for terse variable names.) It’s a tight constraint, but it does mean that three buffers of code can fit side-by-side-by-side on my laptop screen. 

What I like about Rust

The laptop that I’m currently typing on has an amount of RAM that, 10 years ago, would have been a respectable hard drive size. It has four processor cores, and it can efficiently run arbitrary other operating systems in userspace. And when I drag windows around on my screen, they wobble because it looks cool. Truly, we live in the future.

So, as a programming languages person, it is kind of distressing that a great proportion of the software that it runs is written in C or C++. Not that C isn’t a nice language design, but it dates back to the 1970s, and it wasn’t a particularly state-of-the-art language then.

If programming languages people have been writing anything useful on their whiteboards while everyone else has been making technology indistinguishable from magic (i.e. flashy, fascinating, fickle, and flaky), why are people still writing in the same languages?

The answer, as always, is that C is faster than everything else. Which is true. But aren’t there dozens of powerful, principled languages that are fast enough? What’s wrong with Scheme and Haskell and Scala? What do you programmers want?

Rust's answer is that the reason that those languages can't be systems languages is not that they're too slow, it's that their performance is too hard to predict. Systems programmers like C because they have a pretty good idea how it would get translated to assembly, and how slow some particular construct is. They aren't willing to run their project through a profiler every time they have to make a decision about how to write some loop. So Rust strives to imitate C's performance predictability.

The other part of this task, the hard part, is the elusive property known as “expressiveness”. And that’s where Rust can make programmer’s lives easier. That’s the exciting part. Already, in my first day of programming in Rust (incidentally, Rust is self-hosting now; we’re writing the Rust compiler in Rust), I made use of the fact that blocks have values:

  auto sc = alt(e.imports.get(defid._1)) {
    case (todo(?item, ?s)) { s }
    //map_crate should have visit_view_item ed us already
    case (_) { fail; nil[scope] }
    //remove the nil[scope] when fail has type α

Once fail typechecks properly, this code will be pretty nice. Already, it’s much clearer than it would have been in C.