Why is haskell good for compiler development?

Learn
#1

Hello you all.

I have some understanding of compilers and I have built a few in Common Lisp.

Why is haskell a good choice for compiler engineering? thanks

I am just trying to discuss. I am more curious about haskell than ocaml but want to hear experienced people say a thing or two about the benefits of haskell. thanks

1 Like
#2

Welcome @manifold93. Your question is very broad, please make it more specific: are you talking a compiler for a functional language? an OOP language? a low-level bit-twiddling language? An existing/well-established language with already lots of compilers? …

Haskell is usually claimed to be particularly productive for DSLs, where you want to embed some particular semantic domain inside a general-purpose language, and interpret structures familiar to domain experts.

#3

tl;dr:

  1. Compilers can be thought of as a pipeline of transformations on source code, a good match with fp
  2. ADTs are really great for describing ASTs
  3. Pattern matching is great for transforming ADTs
  4. Haskell has excellent library support for things you’d like to do when writing a compiler (State, Reader, uniplate, rock, etc.)

I have some old slides from a talk I gave on the topic at a meetup: https://github.com/soupi/rfc/blob/master/compilers-and-haskell.md

7 Likes
#4

On the question: Why Haskell and not OCaml: I choose Haskell instead of OCaml because of many small advantages, that won over Haskell’s problems (two non-working package managers, slow compiler, higher memory usage, space leaks, buggy LSP).

  • Data.Text, Data.ByteString, Data.Sequence, optparse-applicative and … are more comfortable to use than the OCaml versions (or I didn’t find better alternatives)
  • extensions like ViewPatters make the lexer and parser easier to read
  • I prefer using Typed Template Haskell to writing OCaml PPXs (OCaml syntax extensions). TH is useful to e.g. inline generic functions in tests and get all error messages of the test in the same place, instead of one at the location of the function and one in the test.
  • being able to use stuff like “Trees that Grow” (PDF: https://www.microsoft.com/en-us/research/uploads/prod/2016/11/trees-that-grow.pdf) (or actually “Trees that Shrink” Trees That Shrink - Vaibhav Sagar by using strict parameters and Void just to “remove” constructors). I don’t know, if it really does help or results in more boilerplate, but so far I like it.
3 Likes
#5

Generics (in the sense of GHC.Generics) are neat too, not sure what OCaml has in that area but a lot of languages are missing such a thing.

I also use DeriveFunctor which many languages are missing/could not implement.

1 Like
#6

I worked on a compiler in Haskell for a few years, as well as a few non-compiler programming language implementations.

Haskell is great for this in a few ways:

  1. Garbage collection is really convenient, especially when writing evaluators for lambda calculus like the ones that show up in dependent type checkers
  2. Haskell makes it reasonable to express datatypes in various different ways - others have referred to Trees that Grow, but I’ve also really enjoyed representing a datatype as an explicit fixed point of a functor - that’s a fancy way to say that the bit that describes which things a type can be (constant, operator, function call, variable reference, etc) is defined separately from the bit that says what the sub-parts are, allowing these to be recombined in interesting ways, e.g. by interposing a source position around each node in one phase, or by replacing nodes with pointers into an explicit-sharing graph structure in some other phase. These techniques are often possible in other languages, but either the type system won’t let you express it clearly or the syntactic and run-time overhead is too great.
  3. Being explicit about effects in a type signature makes it very clear which parts of the program can do what, which helps keep separate parts separate in a complex program like a compiler.
  4. Many, many PLs have been implemented in Haskell, so there’s a wealth of libraries, written techniques, and folk wisdom to benefit from.
  5. The general benefits of Haskell apply here, like having refactorings result in type errors that function as a kind of to-do list for propagating the refactoring throughout the system, instead of needing to use tests for this purpose.
  6. Many Haskell testing tools are very nice for language development - property-based testing is perhaps most at home in Haskell.

That said, there’s a lot of cool things that can be done in a compiler in Lisp that are hard in Haskell, like having a really low-friction way of writing ASTs as s-expressions that are convenient at a REPL for play and experimentation, having convenient run-time access to the Lisp compiler for making it easier to bootstrap a system, the use of macros to build nice ways to do things like define large sets of primitives, and a language standard that is extremely, extremely stable so code never bitrots. And OCaml is also worth looking into seriously - we don’t have a good competitor to Menhir, for instance.

8 Likes