Compiler Development: Rust or OCaml?(hirrolot.github.io) |
Compiler Development: Rust or OCaml?(hirrolot.github.io) |
I don’t even like rust.
It does feel like the code was ported as-is to Rust, and only adjusted slightly to compile; there are going to be pain points as a result of this process. I suspect this is the source of some of the author's complaints, especially given:
> Although it provides us with a greater sense of how the code is executing, it brings very little value to the algorithm itself.
Rust is, in general, for people who find value in having that information; it is okay to not want to have to worry about ownership, borrowing, safety, etc., but it seems a bit odd to complain about this when that's what Rust is for? If you want to focus on just the algorithm, and not how it's executing, then OCaml is definitely a valid choice.
However, the point about GADTs - can Rust's recently-stabilized GATs not work in the same way? Though I will admit that Rust's GATs don't seem nearly as powerful as OCaml's GADTs in this regard.
that's the point of the article - rust gives you a lot of low-level control, but if you don't actually need that control then you're paying the cost in ergonomics for nothing.
The Rust one reads like...well a program. A program that's not as beautiful, but is very much designed to be taken apart, debugged, improved, etc.
I fully agree that if you're writing pure, recursive, data structure manipulations, OCaml is likely a better fit. It's closer to mathematical notation and I see the elegance in that. But if I were to take that data structure manipulation and turn it into a compiler with thousands of lines that I navigate with an IDE, with logging, with annoying little edge cases, with dozens of collaborators, I'd choose Rust.
While working at Routine (YC W21), I was tasked with porting our core library to iOS to minimize duplication of business logic. This was a lucky opportunity to write something resembling a compiler: it took in schemas described with our in-house data exchange library and generated C (for FFI) and Swift code (for the end users, i.e., iOS developers).
Since Routine uses OCaml for everything (which was a big motivator for joining the company—I wanted to see how that would work out), I wrote it in OCaml. The end result is a 3-5k LOC project. It's by no means a full compiler, but it was lots of fun to write. The language got in the way incredibly rarely. On average, it made my life a lot easier. We did encounter our fair share of issues, mostly due to the cross-compilation tooling[1], third-party libraries, and intricacies of FFI. Those do take their toll on sanity.
I tried my hand at writing small compilers / interpreters in Rust, and the experience was nowhere near as smooth. It was fun, and the runtime performance is definitely there, but the ergonomics aren't the same. I especially miss first-class modules whenever I code in something other than OCaml now.
[1]: we initially used esy [2], flirted with Nix, and eventually switched to opam-cross-ios [3].
[1]: https://github.com/esy/esy/
[2]: https://github.com/ocaml-cross/opam-cross-iosWith such requirements, I think a point that is fair to make is that Rust acts as a great middle-ground. It avoids the cost of automatic memory management and provides low-level control while also having a more powerful type system and a more "functional" style.
Brushing off the actual efficiency of the produced binary seems like a huge oversight when dealing with a compiler.
For instance, passing RefCell<u32> by value as their code does makes no sense (just use u32...), and the code seems to have a lot of clones, most of which are probably unnecessary, while not having a single instance of the "mut" keyword.
In fact, I'm pretty sure it's completely broken, since their gensym doesn't do what they want, due to their wrong use of clones and refcells (it should take an &mut u32 and just increment it).
And definitely not idiomatic at all.
People should do basic research before writing something silly like this. Qualifying your statement with 'usually' is just a chicken sh*t approach. Common Lisp and Racket have optional strong typing, leaving the responsibility and choice to the developer. Common Lisp is great for implementing compilers. You also have things like Typed Racket and Coalton. The latter is completely statically typed ala MLTON
Sounds to me like they are comparing bad code and good code, not the languages themselves.
So the answer apparently is simple: between two languages, for an important project use the one which you wield best.
The same article could easily be written the other way around. We could start with a high performance rust program (which makes use of arena allocators, internal mutation and any other rust features you love) and then try and convert it line by line into ocaml. We would find that many of rust's concepts can't be clearly expressed in ocaml. The ocaml code would end up uglier and measurably slower than rust. And just like that the article would reach the opposite conclusion - that rust is clearly the better language!
But this is silly.
In general, you obviously can't translate between languages line by line like this and expect to have a good time. A beautiful C program is constructed using different ideas than a beautiful Lua program. And a beautiful Ocaml program is very different from a beautiful rust program.
Some obvious examples of ocaml ideas being overapplied to rust in this article:
1. The types don't really need to be wrapped in Rc here.
2. Rust generally prefers mutable imperative code over applicative code. And if you insist on applicative patterns, functions should take a &Foo.
3. Rust code usually doesn't rely on recursion that much, so the lack of guaranteed TCO isn't something people in the community care about.
4. Rust is optimized for runtime performance over code beauty or code size. Of course rust is less elegant looking than a garbage collected language! The trade is that it should also run faster. But where are the benchmarks to make the comparison fair?
The match example is just straight out bad rust code. This code:
fn eval(term: &Term) -> Value {
match term {
Bool(b) => Value::Bool(*b),
Not(m) => match eval(m) {
Value::Bool(b) => Value::Bool(!b),
_ => panic!("`Not` on a non-boolean value"),
},
// ... lots more nested matches & panics
}
}
fn eval(term: &Term) -> Value {
match term {
Bool(b) => Value::Bool(*b),
Not(Value::Bool(b)) => Value::Bool(!b),
// ... (all other valid patterns)
_ => panic!("{term} invalid"),
}
}
> Other alternatives to consider is Haskell and various Lisp dialects. If you have already “tamed” Haskell (my congratulations and condolences), probably learning OCaml just for writing a compiler is not going to be worth it; if you have not, OCaml is a much more approachable language.
This is an interesting claim, as I thought Haskell and OCaml were more or less equivalently inscrutable.
1) built in eval -- this allows you to transpile to the host language which is invaluable for writing small tests
2) multiline string syntax -- for evaling more than just one liners
3) built in associative and sequential arrays (for the ast)
4) first class closures
5) panic support (for aborting early from unimplemented use cases)
The AST can be represented as an associative array. Each element type can have a 'type' field and rather than pattern matching, you can use if/else. Performance doesn't really matter for the bootstrap compiler because it will only ever be run on relatively small input sets. To get started, you simply walk the ast to transpile to the host language. The snippet is then evaled in the host language to test functionality. Closures allow you to implement the visitor pattern for each ast node, which allows contextual information to be seamlessly interwoven amongst ast nodes during the analysis/transpilation steps.
Keeping all of this in mind, I have identified luajit as my personal favorite language for compiler development. It checks the boxes above, has excellent all around performance for a dynamic language (particularly when startup time is included -- js implementations may beat it on many benchmarks but almost always have slow start up time relative to luajit) and provides a best in class ffi for host system calls. You can run 5000+ line lua scripts faster than most compilers can compile hello, world.
The other reason I like lua(jit) is the minimalism. Once you master lua (which is possible because of its small size) it becomes very obvious that if you can implement something in lua, you can translate the lua implementation to essentially any other language. In this way, there is a sense in which writing a lua implementation becomes almost like a rosetta stone in which a translation can be produced for nearly any other language. With more powerful languages, it is hard to resist the temptation to utilized features that can't always be easily transported to another language. In other words, lua makes it easy to write portable code. This is true both in the sense that lua can be installed on practically any computer in at most a few minutes and in the sense that the underlying structure of a lua program that transcends the syntax of the language can be ported to another computing environment/language.
Another benefit of transpiling to lua is that your new language can easily inherit lua's best properties such as embeddability, fast start up time and cross platform support while removing undesirable features like global variables. Your language can then also be used to replace lua in programs like nginx, redis and neovim that have lua scripting engines. This of course extends to transpiling to any language, which again should be relatively easy if you have already transpiled to lua.
You can add additional annotations in OCaml if you want, or just query the type of a term in Merlin.
> a compiler with thousands of lines that I navigate with an IDE, with logging, with annoying little edge cases, with dozens of collaborators, I'd choose Rust.
Why? OCaml supports logging and IDEs. Simple elegant code without the burden of manual memory management, makes it better able to cope with edge cases, being taken apart and refactored etc. Less of the complexity budget has already been spent.
To be clear, elegance is important. A language absent of elegance would be a bore to write (cough Java cough). But too much elegance and it can eclipse the legibility of the language. No type annotations is elegant. Is it legible? Not in my opinion. But perhaps it is in yours.
If types can be perfectly inferred, I don't see why I wouldn't take advantage of it. Whatever Ocaml IDE you use will easily be able to tell you the types anyways
You could write a compiler for Pascal in Python or another very slow language and it would be faster than a Rust or C++ compiler written in Rust or C++. That is because those languages have designs that make compilation algorithmically slow, while Pascal was designed to be fast to compile.
It becomes visible when you build a large project: you notice that when you face 100k LOCs, efficiency of every compiler's part starts to matter, and RAM usage may grow to uncomfortable levels if your compiler does not care enough.
People like fast compile times and people either like to use (or are forced to use) languages that are inherently slow to compile. That's exactly why compiler performance is absolutely critical.
If the compiler is for JIT, then efficiency will be important.
I'd want to believe that compiler engineers really put effort into compilers performance, but I just don't buy it.
LLVM, GCC, MSVC, etc, etc all of them touch C/C++ and are slow as hell
For compilers written in other languages I'd say that still LLVM is the bottleneck
>It avoids the cost of automatic memory management and provides low-level control.
What "low-level control" do you need? It is not firmware development.
Btw: Microsoft rewrote their C# compiler from C++ to C#.
It's really easy to accidentally write code that walks off a performance cliff on unexpected input, but that's likely to get hacked around if someone reports it as slow compilers do annoy people.
In my opinion, OCaml would see even more widespread use if the documentation were improved. I find it a chore to figure out how to use OCaml well. I also would like to use third-party libraries like Jane Street's Base because they've put a lot of work into providing even more functionality in their standard library, but their documentation is absolutely atrocious (where it exists at all).
OCaml is a mature language but does not have a very supportive ecosystem. I'm hoping the renewed interest will prompt changes there.
I felt that way about a dozen years ago. These things have cycles, apparently. But they also recently released multi-core OCaml in OCaml 5 which opens some doors for OCaml that were previously not open.
Edit:
I have used OCaml in production and currently I don't see a point to doing it again for the vast majority of problems. From a holistic language + runtime point of view OCaml occupies a space where it's not useful enough from a runtime perspective to replace any of the more convenient languages that exist and not low-level enough to fill the spot of any of the good alternatives in that space. Modularity-wise functors are nice but ultimately plenty of alternatives exist even it the lower-level languages.
With all that said, people should probably use the hell out of it if they're excited. It's a bit tiring seeing the constant stream of misinformation regarding alternatives to OCaml, though. There are good reasons it's losing out in industrial use to even languages like Haskell.
What would be the idiomatic way for the function `eval` to provide good error messages in Rust?
What you really probably want is to make this a Result type-returning thing, and then have have `not` be a function of type Value -> Result<Value,ErrType>, and then you can do not(eval(m)) and panic at the top-level.
enum Term { Bool(bool), Not(Box<Term>), ... }
that your code simply does not typecheck. `Not` expects a `Box<Term>`, not a `Value`.
It's also worth noting that one would probably want to consider something like
Not(Not(Bool(true)))
a valid term, which your implementation wouldn't.
In any case, I stand by all the other points I’ve made in my comment.
No it can't. You're missing the recursive call to `eval`.
I also wish it was a bit more performant, but here it's likely my medium to high level code and not luajit's fault. However running the test suite in plain Lua seem some order of magnitude slower than luajit, so it's a lot faster than plain Lua at least.
EDIT: this was a really interesting read!
JITs are just some part of what's under the general "compilers" term
In any case, it wouldn't make sense from having a bootstraped compiler point of view.
If current top of heap + allocation size > buffer size, allocate an extra buffer for the arena. Save the current top in a temp variable. Add the allocation size to the top Return the temp variable.
It's fast, and the amortized memory overhead per allocation is near zero because you don't need to track allocation sizes or free lists, since you only free the whole arena at once (one or more buffers).
It's ideal for anything where the lifetime of allocations is known to be roughly the same. E.g. a data structure you'll free all at once.
Not that there is anything wrong with Rust if you are ready to pay the price of having so much low level things to deal with.
Rust has a pretty darn good ecosystem too btw. chumsky for parsing, rowan for syntax trees, salsa for incremental computation, miette for errors, inkwell/walrus for code generation.
> I tend to prefer hand written parsers, either via a combinator library or fully manually.
That’s common with people used to languages which provide poor parser generators.
The Ocaml program is mostly matching followed by a chain of operations. It’s far removed from elegance for elegance sake. Meanwhile Rust is handicapped by the machinery it forces you to deal with as a lower level language introducing life time.
Type annotations are a non issue. They are systematically provided in Ocaml in a different file than the code. This header file is not provided here because well it’s a blog post.
The first thing I'd suggest, as someone who's done their fair share of Rust compiler dev, is to stop using `Box` and `Ref` everywhere. Terms should not own their child terms; the idiomatic way to handle this is to use an arena and typed IDs, and pass a reference to the arena when you need access to the underlying data from the ID.
Edit: Either I remembered wrong or it's changed. Now it uses some kind of custom wrapper around Box: https://github.com/rust-lang/rust/blob/master/compiler/rustc... So actually, the Rust compiler itself uses owned children in its AST!
> RefCell<u32>
I'm not sure.
https://play.rust-lang.org/?version=stable&mode=debug&editio...
But also, the editor plugins don't work on the compiler itself? Why's that? So you can't use Merlin on the OCaml compiler? That doesn't seem great.
And what's with the syntax highlighting being funky? The highlighter appears to think that a lot of these files have unterminated comments or string literals.
I don’t know of many production compilers that use parser generators
If you know the language, and you have a bunch of users, and you are writing a parser for it, by all means, write a parser by hand and give it the best error recovery that you can muster. If you are developing a language and want to do a bunch of experiments, it pays dividends to use a parser generator. And then there is the whole space of DSLs and mini-languages you encounter, where beautiful error messages are a nice-to-have, but you would rather ship a generated parser and move on to more important work.
It’s easy to focus on compilers from the perspective of familiar languages like writing compilers for Rust or for OCaml, but you may end up writing a compiler that gets used by a much smaller number of people, for smaller tasks.
I don't mean to blame you for that; you are answering a question about something that you did not say. But I find it frustrating that Mehnir seems to be cited as this fantastic cornerstone of the OCaml ecosystem when I haven't been presented with a good example of how it's better than any other parser generator. Not just my parent comment (who also decided to cast aspersions on my knowledge), but others in the OCaml community too.
Simple to write, debug, recover from errors, provide decent error messages, unit test, integrate into build systems, IDEs etc.
I also believe that nearly all the popular compilers these days do something similar - gcc was rewritten a few years ago in this fashion because of the technical benefits I’ve listed above.
The vast majority of real languages have hand-rolled parsers and there is no real reason they shouldn't.
lmao
The premise of this question is incorrect: you can't not use the borrow checker in Rust. Instead, you are satisfying the borrow checker by ensuring at the point of use (deref of the ID) that there is valid data by providing a provably-live reference to the arena in which it was allocated.
In another language like C/C++, you'd just use a raw pointer, which is ergonomically-nice, but there's no guarantee that it actually points to a valid object. Rust forces you toward a solution that is guaranteed to be safe, and logically makes sense when you think about it -- nodes in a graph should not own other nodes in the graph; instead, they should be owned by the graph itself, and other nodes should simply hold references to each other. This is how you tend to implement safe and efficient graphs in C++ anyways, the only difference being that in Rust your references are indices, whereas in C++ your references are raw pointers.
I already told you that it has full support for disambiguating LR(1) grammar and still generating a parser which is easy to read. How do you want me to paste a full parser in a HN comment?
Most generators only support LALR(1) grammar which is limiting and don’t deal with corner cases as gracefully.
I get that you are hell bent on wanting Rust to prevail here but Rust will always be a subpar experience for wiring anything which doesn’t strongly benefit for its low level primitive. Rust has annoying semantics and a convoluted syntax. I can bear with that when the performances are needed but writing a compiler in it is just unnecessary pain. It’s also one of the only thing for which I would actually use Ocaml.
I have a question for you then: why is it that so many projects that are not performance bound, that are not low level systems projects, why do they use Rust and not OCaml? OCaml had a 22 year head start after all.
My main take on the “which language do I write my compiler in” conversation is that some of the various code transformation passes are just more convenient to write in a language which makes it easy to use both mutation and garbage collection, which puts OCaml above both Rust and Haskell. I think parsing is an easier problem to solve in the first place.