Why is it easier to write a compiler in a functional language?

Question

I thought about this question for a very long time, but actually could not find an answer on Google, as well as a similar question in Stackoverflow. If there is a duplicate, I regret it.

Many people seem to say that writing compilers and other language tools in functional languages ​​such as OCaml and Haskell is much more efficient and easier than writing in imperative languages.

It's true? And if so, why is it so efficient and easy to write them in functional languages, and not in an imperative language, such as C? Also, is it not a language tool in a functional language slower than in some low-level language such as C?

Answer 1

Often the compiler works a lot with trees. The source code is parsed in the syntax tree. Then this tree can be converted to another tree with type annotations for type checking. Now you can convert this tree to a tree containing only the elements of the main language (converting syntactic notations like sugar into an uncured form). Now you can perform various optimizations, which are mainly transformations on the tree. After that, you will probably create a tree in some normal form, and then go through that tree to create the target (assembly) code.

A functional language has features such as pattern matching and good support for efficient recursion, which makes it easier to work with trees, so they are generally considered good languages ​​for writing compilers.

Answer 2

A lot of compiler tasks are pattern matching by tree structures.

Both OCaml and Haskell have powerful and concise template matching capabilities.

It is more difficult to add pattern matching to imperative languages, since any value that is evaluated or retrieved to match the pattern against must be free from side effects.

Answer 3

One important factor to consider is that most of any compiler project is when you can organize the compiler yourself and "eat your dog food." For this reason, when you look at languages ​​like OCaml where they are designed to learn the language, they tend to have great features for problems like the compiler.

In my last work with the-esque compiler, we used OCaml precisely for this reason, manipulating the C code, it was the best tool for this task. If people at INRIA built OCaml with different priorities, it might not have been so good.

Nevertheless, functional languages ​​are the best tool for solving any problem, so it logically follows that they are the best tool for solving this particular problem. Q.E.D.

/ me: bounces back to my Java tasks a little less joyfully ...

Answer 4

see also

design template f #

FP groups things “by operation”, while OO groups “by type” and “by operation” are more natural for the compiler / interpreter.

Answer 5

Basically, a compiler is a conversion from one set of code to another - from source to IR, from IR to optimized IR, from IR to assembly, etc. This is exactly what functional languages ​​are designed for: a pure function is just a transition from one thing to another. Imperative functions do not have this quality. Although you can write such code in an imperative language, functional languages ​​specialize in it.

Answer 6

One possibility is that the compiler tends to deal very carefully with all of the many angular cases. Getting the right code is often simplified with design patterns that structure the implementation in a way that matches the rules that it implements. Often this becomes declarative (pattern matching, "where"), rather than imperative (ordering, "when") design and therefore easier to implement in a declarative language (and most of them are functional).

Answer 7

Everyone seems to have missed another important reason. It is very easy to write an embedded domain language (EDSL) for parsers that are very similar to (B) BNF in normal code. Parser comparators, such as Parsec, are fairly easy to write in functional languages ​​using higher-order functions and function composition. Not only simpler, but also very elegant.

Basically, you represent the simplest common parsers as just functions, and you have special operations (usually higher-order functions) that allow you to compose these primitive parsers for more complex, more specific parsers for your grammar.

This is not the only way to make the initial course framework.