3.1 The Mercury backends

The Mercury compiler was has two backends.

The first backend implemented by the Mercury team translates Mercury programs to what is effectively assembly-level code in C syntax. Most compilers generate either assembly level code (either assembly code itself or binary machine code), so the first part is quite conventional. The second part, generating this assembly level code in C syntax, was rare at the time, though it has become more common since. We chose that approach because it allowed us to take advantage of the huge amount of work put into C compilers, both in terms of making C available on pretty much all commonly used platforms, and generating for them not just code that works, but fast code.

Like most compilers, the Mercury compiler has representations for both the source code and the target code. In compilers for imperative languages, these are usually called the abstract syntax tree (AST) and the intermediate representation (IR) respectively. The Mercury compiler’s versions of the these are substantially different, so we use different names for them: the high-level data structure (HLDS) and the low-level data structure (LLDS).

The low-level code generated by the original backend is about as far from the code that a human C programmer would write as it is possible to get. Later on, as part of a research project, we investigated translating Mercury code into idiomatic C code, with a view towards making the approach general enough to be able to produce idiomatic code in other imperative programming languages as well. We call the compiler’s internal representation of this kind of the code the medium-level data structure (MLDS), since it is clearly lower level than Mercury code, but higher level than assembly code.

From the names of these internal representations, Mercury calls the first backend the LLDS backend, and the second backend the MLDS backend. The first generates low (assembly) level C code, while the second generates either high level C code, Java code, or C# code.