Llogiq on stuff

All Languages are Equal (but Different)

With this post I want to explore the reasons why I think Turing Equivalence is way overhyped and show why Rust is on some levels more powerful than Haskell, Python, Java, C, or Assembly.

There have been many attempts to define the “power” of programming languages, though all I’ve seen so far are either wrong or (intentionally or by accident) blurry.

One level to look at is Turing-Completeness. I won’t go there because the languages I intend to compare are all already Turing-complete. Apart from that, the perhaps most notorious attempt to define “Power” comes from Paul Graham’s essay Beating the Averages. His ‘Blub paradox’ in one fell swoop equates power with abstraction, and makes it a psychological issue: If your chosen language is less powerful, you aren’t able to think more powerfully.

Apart from the general fuzzyness of his argument, I think the correlation his argument hinges on is incidential. His point that Lisp is much more powerful than other languages because “programs writing programs” is made moot by one classic counterexample: There are a lot of Brainfuck programs writing other Brainfuck programs to do things, yet no one would argue that Brainfuck be as powerful as Lisp.

As an aside, there are a few libraries that mangle Java Byte Code, which one can use to effectively write code at runtime. Sure, they may not be as easy to use as Lisp’s defmacro, but they get the same thing done. Rust has a hygienic macro facility you can use for simple cases, and it is possible to write compiler plugins for complex ones (though this requires unstable APIs). If all else fails, you can write a program that writes another program in just about any language (as per the example above).

So what is “power”? Regarding programming languages, it is the set of useful things it lets a programmer express. This is very specific to both the programmer and their goals. Abstraction plays into it, but is not the whole picture.

Abstraction is a double-edged sword. The more abstraction you choose, the less control you retain. E.g. GC is a great tool for memory safety, but you pay for it with loss of control when something is reclaimed; both in the dreaded GC pauses and higher memory footprint of your application. For a great deal of programs, this is a good tradeoff.

Old-school hackers will also know the feeling of power one gets when fully controlling the machine, something impossible in the fluffy pampered world of high level languages. This is yet another kind of power, and it sometimes allows hackers to do great and surprising things (If you haven’t written any assembly code yet, I hereby invite you to try it – a few hours should be enough to at least get some “Hello, World” program to run, and you may well find that it isn’t as complex as it’s made up to be).

Both abstraction and power apparently are not evenly distributed. For example (dons flame-retardant suit) I argue that static typing is in a sense more powerful than dynamic typing, because you can express constraints with the former that you need to document for the latter (and hope for the best).

In another sense, (dons another layer of asbestos) dynamic typing is more powerful than static typing, because the latter will restrict the set of programs the compiler will accept, and that may include programs that are valid, but whose validity cannot be proven by (or to) the type checker. In practice, this often trades up front fast iteration for debugging later. For small, easy to debug programs, this is a good tradeoff.

Of course, there are dimensions of power within the type system itself (which is after all why it’s a mainstay of CS research) – e.g. Java’s type system is more powerful than Go’s, because you can express generic types in Java, whereas you need to resort to interface{} and hand-waving in Go. C#’s system is still more powerful, because it retains type information at runtime and thus can express constraints Java cannot.

So the power to restrict possible programs is something that can be useful, but (if experience is a valid guide) will mostly benefit large programs and/or libraries. For the latter, being able to restrict usage can help as a guide (some people call this strategy type-directed programming). On the other hand, for small one-off scripts, its value is reduced. So far, so well-published.

It is easy to see that restricting the space of valid programs can enable a programmer to write things that would be infeasible without the restrictions, like an undirected search in open space will run out of resources long before reaching the goal where a directed search easily finds it.

In Rust, we have another way of restricting access: We can use the borrow checker to require either read-only access from multiple targets or a single target with full access. Compare this to C++, where we have but convention and careful coding to rely on, this allows us to change code and let the compiler sort out the consequences.

This is so great because it frees the programmer from thinking about global interference of his changes, something that functional languages usually try to do by restricting mutable state. Since many programs require some state to run, those languages cope by either wrapping it in burritos monads (e.g. Haskell), or just allowing it anyway (e.g. Lisp, ML). In the former case, the type system limits the effects, while in the latter, there is nothing to protect you from interfering with other code in a way that may cause unforeseen circumstances.

That this freedom from certain concerns amplifies the power of a programmer is to be expected. Musicians will often train to play certain sequences by repeating them until they can play them without thinking (I believe the term for that is “muscle memory”). A programmer with a tool that takes care of some things for them will have more attention free for other things, and thus can manage more complex problems. If you choose Rust, you let the compiler be your muscle memory.

Incidentially, this also explains the popularity of Java: Current IDEs are so good they free programmers from caring about a lot of things, so they can focus on the problem at hand. In Rust, the compiler takes care of a lot of things that would be outright scary in another language. I’m longing for the day that IDEs for Rust reach the same level of maturity as they currently have for C++ or Java. Programming in such an environment will be very powerful.