A Systems Programming Language?

When we speak of a language suitable for systems programming, we really mean the implementation of the language. After all, interpreted C could exist, but you wouldn't probably want to make a kernel with it, while a Linux kernel has been translated (almost) entirely to ML and used in a research system. If memory serves, the ML Linux kernel was just as fast on all the standard benchmarks as the C version, or perhaps faster.

To get around to the actual question: what are the real characteristics we demand for a systems-programming language implementation, and which are merely an accident of history? I think the answer is this: the implementation should be fast, and it should be possible to exploit the full capabilities of the machine either through constructs of the language directly or by linking assembler modules into the rest of the program. Linkages are well-understood, so the question boils down to making the language execute rapidly.

Certainly we want a means of calculation which produces results quickly, using a minimum of CPU resources. This means that the implementation must translate arithmetic directly to corresponding CPU arithmetic instructions. For this to work, numeric data must be stored in ways that require minimal effort to load and store. This is why the parameters to and local variables of the current routine are ordinarily held as words relative to some register, such as the stack pointer or base pointer on an X86.

So much for arithmetic. There are two other major concerns for a programming language: control and abstractions. The latter can be thought of as procedural and data abstractions.

Control means conditional and repeated execution. If arithmetic happens with CPU-native data types, then CPU-native conditional jumps (or perhaps predicated execution, if you go in for Itanium2-style code) are the choice means to implement control.

Data abstraction is done quite differently in languages like Perl vs. those like Pascal. I claim that the Pascal approach is inherently more reliable. In Perl, everything is either a scalar, a list, or an associative dictionary. Having that, Perl strives to make the most common access patterns to such structures be relatively quick. On the other hand, in Pascal, there is a proper "type algebra" of arrays, records, sets, and scalar types. Expressions in the executable portion of the code must properly match the type declarations up front. In Pascal, this is not done for the programmer's benefit. It's done so that the Pascal compiler can determine at compile time how to write code to access particular data by name or index, without having to keep the names or definitions around at run time. The cost saved is the cost of consulting a dictionary for each use of an aggregate type. The reason type definitions must come before their use in Pascal is that the compiler must be implementable in a single pass. So now we have it: advance knowledge of data structures can be built into data access methods, allowing said methods to be specialized to their actual use, which produces rapid data manipulations. In truth, Perl's lists and hashes are done in terms of these very ideas. However, the generality of the Perl hash is excessive in certain contexts, and it decelerates Perl code. Thus, people don't write kernels in Perl.

As a rule, it seems early generality is a performance brake, despite being a boon to the rapid development of small programs. Consider the standard means of procedural abstraction: the subroutine. I consider subroutines to fall into two categories: those which compute a function of their arguments, and those which cause externally-visible effects based upon their arguments. The latter do not normally return a value, but they may fail for a variety of worldly reasons, and both categories may fail if the arguments are not suited to the operations.

In general, subroutines are converted directly to a stack-based analogue. Each declared routine gets an entry point and a calling convention. Meanwhile, every mention of the routine is converted to a call to this entry point surrounded by appropriate set-up and tear-down. Friends, that's premature generality, and C suffers badly from it. The presence of the "inline" keyword in C99 is more a symptom than a cure: programmers should not be worrying about that detail. Rather, it's incumbent upon a good compiling implementation of a language to automatically identify suitable candidates for "inlining" and just produce good code. For one thing, any routine called from only one place is a fabulous candidate. Also, very small routines are also good candidates. But in any event, the language definition should leave that concern to the compilers. This is why Haskell programs occasionally outrun their C analogues. It's not the algorithm, but the quality of its implementation. Tail-call elimination, for example, seems like a really good idea, but it makes odd demands on the stack. It's easiest done by pushing the return address beneath the actual parameters to a subroutine, but the CPU normally provides a simple way only to do the opposite. Therefore, if you want to eliminate tail calls, you get bulkier programs which probably run just as slow as the naive stack-based evaluator. The real gains come from converting recursive routines into iterative ones, unrolling loops, and automatically inlining good stuff. That's what eliminates wasted cycles. Well, that and fundamental algorithmic improvements.

We know what performance characteristic the CPU stack offers: allocation and release are stupefyingly quick, but you can only release at the top of the stack. This produces a fine model for function evaluation as long as no data outlives its activation record. However, some data usually does. It's called a return value. It has to be given back to the caller. This is usually done with a register, but structured return values can actually be treated as implicit output parameters. The caller provides a pointer to the location where space has been reserved for a returned record. The limitations of the stack are traditionally overcome by way of a dynamic heap. However, consider a kernel: it has no heap in the normal sense. There's just physical ram and an MMU. The kernel must implement a system for the allocation of pages, not bytes. It's also known that an automaton with two or more stacks is Turing-complete. This leads to some ideas for later on. For now, know that dynamic memory allocation is important for applications, but it seems a mistake to embed the idea of a single global heap into the grammar of the programming language.

I have not explicitly deconstructed polymorphism as it relates to data abstraction. Presumably, various concrete classes of data are associated with operations with mutually corresponding semantics. A call that makes use of polymorphism means that we wish to invoke the correct implementation of the semantics given the concrete class of a particular datum, when that concrete class is not necessarily known in advance (such as at compile time). I'm working on this idea that polymorphism is only half of a whole concept. I'll cover it in another article.

By now, we've seen the basic ideas behind a fast implementation of a language. But truly, one factor is often neglected. A good systems programming language must first of all be a good programming language. And this requirement is so huge that it's a topic in itself. The best thing about a good programming language is that the suitability for systems-level programming is only a compiler away.