posts/compiler-development-rust-or-ocaml

[giscus[bot]]

posts/compiler-development-rust-or-ocaml

https://hirrolot.github.io/posts/compiler-development-rust-or-ocaml.html

[B1Z0N]

First

[Hakimba]

I loved reading this, really clear and straightforward!

[ljw1004]

Here are stats on the hack typechecker https://github.com/facebook/hhvm/tree/master/hphp/hack:

• Typing - 15% - core PL things like type inference, type checking, semantics. (Of course a lot of this code is plumbing to support type inference, but I just counted everything in the "typing/" directory...). I think this category is what the author refers to as "complex data transformations".
• Simplistic AST and representations - 40% - Here I'm talking about simplistic storage of AST and related structures, and simplistic transformations of them. There's no advanced theory or coding here. We're closer to syntax than semantics. I think this is what the author refers to as "recursively defined data structures". Both functional and object-oriented have seem to have been equivalently good. The surprise I learnt in both Hack and C# teams is that perf is correlated strongly with number of bytes allocated, so a key criterion for a production compiler is that your choice of language help you with memory parsimony.
• Big data coding - 20% - O(project) data-structures and algorithms to maintain search index, incremental typechecking rdeps, ...
• Systems - 15% - This includes OS things like file-system interaction, file notifications, process interaction, shared memory, and application-system things like moving chunks of data from one place to another and orchestrating chunks of work.
• Plumbing - 10%- String manipulation. "Utils" directory. Error codes. That kind of thing.

My experience with the C# compiler https://github.com/dotnet/roslyn was that a huge amount of the codebase was (1) error reporting, heuristics, tracking information to make good compiler error messages. And (2) "compiler as a service" so that plugins and IDE could access things like the concrete syntax tree, the typed-AST, the symbol graph, the IL, and so on. For this the most important language criterion was making a friendly API, for which functional style immutable data was important, and object orientation was handy. Arguably that might even mean implementing the API in the same language that users write plugins (because users will want to write plugins in the language they're most familiar with), which might mean implementing the compiler in that language too.

The internals of the C# compiler also doesn't have deep PL semantics problems to solve -- it just needs to represent its type system okay. The PL work is a few switch statements, a load of visitors, a few graph algorithms, and that's about it. Many languages would have done fine. I think things like SSA form and register coloring come at the IL/JIT layer, not the compiler.

[Voronar]

OCaml GADT looks pretty good.
Coding Term type as Rust enum is not powerful as OCaml GADT, but maybe Rust typestate pattern can help a bit. It differs from enum approach, but looks pretty type safe:

struct Bool(bool);
struct Int(i32);

mod sealed {
    pub trait Sealed {}
    impl Sealed for super::Bool {}
    impl Sealed for super::Int {}
}

pub trait TermState: sealed::Sealed {}

struct Term<TermState>(TermState);

type BoolTerm = Term<Bool>;
type IntTerm = Term<Int>;

impl BoolTerm {
    fn new(value: bool) -> Self {
        Self(Bool(value))
    }
    fn not(self) -> Self {
        Self(Bool(!self.0 .0))
    }
    fn and(self, right: Self) -> Self {
        Self(Bool(self.0 .0 && right.0 .0))
    }
    fn val(self) -> bool {
        self.0 .0
    }
}

impl IntTerm {
    fn new(value: i32) -> Self {
        Self(Int(value))
    }
    fn neg(self) -> Self {
        Self(Int(-self.0 .0))
    }
    fn add(self, right: Self) -> Self {
        Self(Int(self.0 .0 + right.0 .0))
    }
    fn val(self) -> i32 {
        self.0 .0
    }
}

fn main() {
    let b = BoolTerm::new(true).and(BoolTerm::new(false)).not();
    let i = IntTerm::new(2).add(IntTerm::new(2)).neg();

    println!("{:?}", b.val());
    println!("{:?}", i.val());
}

[hirrolot]

The approach looks similar to the Tagless Final (TF) encoding of terms, as demonstrated by Oleg Kiselyov et al. You can find a more structured version here. Beware: I don't think this approach has been used in daily Rust practice, so probably it has many dark corners when applied in Rust. In particular, Rust has no first-class polymorphism, which is needed for certain types of manipulation with TF.