5 ms·

Always wanted to ask an academic about this. Compilers take input source and libraries and maybe some configuration parameters (in C you can pass preprocessor

by txdv 6y ago

Always wanted to ask an academic about this. Compilers take input source and libraries and maybe some configuration parameters (in C you can pass preprocessor definitions, etc) and produce an output. No network calls, no conditional file IO - the only side effects that are needed have to be done at the beginning, when you load source files and other libraries. Why are so many compilers not utilizing more pure functional paradigms? Focusing on transformations of input to output instead of doing side effects. It seems like such a perfect fit.

girvo 6y ago
Anecdotally: because my compiler was surprisingly slow following a purely functional architecture. Though that was likely my own idiocy more than anything anyone else can draw a conclusion from :)
- mhh__ 6y ago
  What language? When I write functional code (the compiler can enforce purity) in D I can usually get it running fairly quickly, but because of various things (memory locality, memory usage, etc.) I can see it being a problem in problem in the more traditional functional languages. Ultimately for single-threaded applications avoiding state is usually just slower, however, it also buys correctness. Eliminating mutable state in composition can also massively improve the parallelism available to the programmer without making changes to the implementation.
pharmakom 6y ago
In academia many compilers are written in functional languages, particularly OCaml. Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. As a result, compiler implementation languages follow popular language trends. I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance.
- MaxBarraclough 6y ago
  > Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. I wouldn't say so, I think 'serious' compiler developers seem to take a fairly level-headed view here. Python and JavaScript for example aren't likely to ever be self-hosting, as it wouldn't make much sense. There's PyPy of course, but people only pay attention to PyPy when it does impressive things with performance, it doesn't get all that much 'credit' for being written in RPython. If that were all it brought to the table it would be viewed as a mere curiosity. Java is moving to be more self-hosted (Graal), but this can bring real advantages (fewer undetected buffer overflows inside the JVM for instance), it's not being done just because it's cute. Compilers can of course be written in all manner of different languages, I don't think it's a mistake that DMD is written in D, or that GNAT (the Ada frontend for GCC) is written in Ada, or that GHC is written in Haskell. It could serve as a useful example of a complex program written in that language, and it only requires that contributors know the language they're compiling. > I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance. In that specific instance I suspect you might be right, but this is just guesswork.
  - onei 6y ago
    I've never used it, but [1] claims to be a much faster js/typescript compiler than some of its competitors and written in Rust. 1. https://github.com/swc-project/swc https://github.com/swc-project/swc
  - pharmakom 6y ago
    Hmmm my conclusion was drawn from the following languages having their main compiler written in that language: Haskell, Java, Scala, OCaml, Kotlin, C++, C#, F#, Rust, Go, Nim, Zig... Not criticising any of these choices, but one has to wonder why. Most of these compilers were rewrites after a bootstrap implementation was created in an existing language.
    - gpderetta 6y ago
      at least two reasons come to mind: simplified bootstrapping and being a testcase and a source for feature requests for the language itself (especially important early on when there are few large codebases in that language).
mhh__ 6y ago
It's definitely true, but compilers also need to change quickly and run fast which can put a lot of strain on the initial architecture. Also, although the books tell you compilers are all cause and effect there's are parts that are pretty intertwined, be that parsing C++ or even the way that x86 is sufficiently complicated that performing instruction selection and scheduling requires some jiggling because of the complexity of the ISA and the breadth of microarchitectures available.
- deleted 6y ago
  [deleted]
UncleMeat 6y ago
Tons of toy compilers are written in functional languages. Standard ML or ocaml are probably the first thing that grad students would reach for when developing a compiler from scratch that isn't intended for production purposes. However, in the real world everybody is using GCC/LLVM because they have rich open source communities and your work might actually get used by humans. LLVM in particular is nicely architected to be easily extensible so you can focus on just the compiler feature you want rather than bothering with all the other stuff needed around it. So then you are bound to the architectural decisions of these platforms. GCC in particular is a bit of a spaghetti mess and was designed long before pure functional design was trendy so you just sort of need to live with it. Immutable IR is also a big challenge since the IR tends to actually be quite large. Making copies of it is sloooow.
- g_delgado14 6y ago
  > in the real world everybody is using GCC/LLVM Wasn't Rust bootstrapped with OCaml? I'm sure there are additional popular(ish) languages (i.e. Elm and PureScript) that are compiled with pure FP languages.
  - zanellato19 6y ago
    It was, but it produced LLVM IR from the beginning, iirc
ufo 6y ago
My 2 cents: Algebraic data types (tagged unions) are very useful for representing syntax trees and other things of the sort. I'm not sold on the idea of going 100% purely functional (a-la haskell) though. Even a compiler written in a nonfunctional language is already going to be architected as a series of passes. The thing that makes it hard is not the presence of mutable global state. It's more the actual algorithms and optimizations.
SJC_Hacker 6y ago
I'm no academic, but functional languages have performance problems that simply cannot be handwaved away. For example, say you have a function that modifies an array. In a pure function, you cannot mutate in place, the function would need to return a "new" array. This necessitates at least a partial copy. I have seen proposed solutions for this where the array structure is some type of index table, where you can just mutate part of it and still maintain most of the original, thus avoiding having to potentially copy a huge amount of memory. However there is an unavoidable performance penalty, and also introduces issues like cache misses/pipeline stalls come in to play.
titzer 6y ago
A lot of compilers for functional languages do exactly that. Each intermediate representation of the program is expressed as an algebraic datatype and each phase is a transformation from one (immutable) IR to another. A simple compiler might be 3 to 5 such IRs, but a more complex compiler might be dozens of passes. The problem is that dozens of passes means dozens of copies. Compilation gets quite slow. It's not clear how to make a really fast compiler that has to do so much copying. All of the compilers that I have worked on, except the toy compilers in grad school, used complex, mutable, and ultimately graph-based IRs. Controlling exactly the memory representation of the IR is important when a compiler does a lot of inlining and other optimizations, because a design mistake here can mean the IR for a compilation unit gets enormous and compilation time goes superlinear. I designed the core of V8's optimizing JIT and these issues are really important for an industrial compiler.
fooker 6y ago
>Why are so many compilers not utilizing more pure functional paradigms? Focusing on transformations of input to output instead of doing side effects. It seems like such a perfect fit The primary engineering and scientific challenge of compilers is optimization. That is all about finding a needle in a haystack, converting that to a slightly different needle, and putting it back in the same location in the haystack. This is something functional languages are fairly poor at.

by txdv 6y ago

girvo 6y ago

Anecdotally: because my compiler was surprisingly slow following a purely functional architecture. Though that was likely my own idiocy more than anything anyone else can draw a conclusion from :)

mhh__ 6y ago
What language? When I write functional code (the compiler can enforce purity) in D I can usually get it running fairly quickly, but because of various things (memory locality, memory usage, etc.) I can see it being a problem in problem in the more traditional functional languages. Ultimately for single-threaded applications avoiding state is usually just slower, however, it also buys correctness. Eliminating mutable state in composition can also massively improve the parallelism available to the programmer without making changes to the implementation.

pharmakom 6y ago

In academia many compilers are written in functional languages, particularly OCaml. Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. As a result, compiler implementation languages follow popular language trends. I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance.

MaxBarraclough 6y ago
> Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. I wouldn't say so, I think 'serious' compiler developers seem to take a fairly level-headed view here. Python and JavaScript for example aren't likely to ever be self-hosting, as it wouldn't make much sense. There's PyPy of course, but people only pay attention to PyPy when it does impressive things with performance, it doesn't get all that much 'credit' for being written in RPython. If that were all it brought to the table it would be viewed as a mere curiosity. Java is moving to be more self-hosted (Graal), but this can bring real advantages (fewer undetected buffer overflows inside the JVM for instance), it's not being done just because it's cute. Compilers can of course be written in all manner of different languages, I don't think it's a mistake that DMD is written in D, or that GNAT (the Ada frontend for GCC) is written in Ada, or that GHC is written in Haskell. It could serve as a useful example of a complex program written in that language, and it only requires that contributors know the language they're compiling. > I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance. In that specific instance I suspect you might be right, but this is just guesswork.
- onei 6y ago
  I've never used it, but [1] claims to be a much faster js/typescript compiler than some of its competitors and written in Rust. 1. https://github.com/swc-project/swc https://github.com/swc-project/swc
- pharmakom 6y ago
  Hmmm my conclusion was drawn from the following languages having their main compiler written in that language: Haskell, Java, Scala, OCaml, Kotlin, C++, C#, F#, Rust, Go, Nim, Zig... Not criticising any of these choices, but one has to wonder why. Most of these compilers were rewrites after a bootstrap implementation was created in an existing language.
  - gpderetta 6y ago
    at least two reasons come to mind: simplified bootstrapping and being a testcase and a source for feature requests for the language itself (especially important early on when there are few large codebases in that language).

mhh__ 6y ago

It's definitely true, but compilers also need to change quickly and run fast which can put a lot of strain on the initial architecture. Also, although the books tell you compilers are all cause and effect there's are parts that are pretty intertwined, be that parsing C++ or even the way that x86 is sufficiently complicated that performing instruction selection and scheduling requires some jiggling because of the complexity of the ISA and the breadth of microarchitectures available.

deleted 6y ago
[deleted]

UncleMeat 6y ago

Tons of toy compilers are written in functional languages. Standard ML or ocaml are probably the first thing that grad students would reach for when developing a compiler from scratch that isn't intended for production purposes. However, in the real world everybody is using GCC/LLVM because they have rich open source communities and your work might actually get used by humans. LLVM in particular is nicely architected to be easily extensible so you can focus on just the compiler feature you want rather than bothering with all the other stuff needed around it. So then you are bound to the architectural decisions of these platforms. GCC in particular is a bit of a spaghetti mess and was designed long before pure functional design was trendy so you just sort of need to live with it. Immutable IR is also a big challenge since the IR tends to actually be quite large. Making copies of it is sloooow.

g_delgado14 6y ago
> in the real world everybody is using GCC/LLVM Wasn't Rust bootstrapped with OCaml? I'm sure there are additional popular(ish) languages (i.e. Elm and PureScript) that are compiled with pure FP languages.
- zanellato19 6y ago
  It was, but it produced LLVM IR from the beginning, iirc

ufo 6y ago

My 2 cents: Algebraic data types (tagged unions) are very useful for representing syntax trees and other things of the sort. I'm not sold on the idea of going 100% purely functional (a-la haskell) though. Even a compiler written in a nonfunctional language is already going to be architected as a series of passes. The thing that makes it hard is not the presence of mutable global state. It's more the actual algorithms and optimizations.

SJC_Hacker 6y ago

I'm no academic, but functional languages have performance problems that simply cannot be handwaved away. For example, say you have a function that modifies an array. In a pure function, you cannot mutate in place, the function would need to return a "new" array. This necessitates at least a partial copy. I have seen proposed solutions for this where the array structure is some type of index table, where you can just mutate part of it and still maintain most of the original, thus avoiding having to potentially copy a huge amount of memory. However there is an unavoidable performance penalty, and also introduces issues like cache misses/pipeline stalls come in to play.

titzer 6y ago

A lot of compilers for functional languages do exactly that. Each intermediate representation of the program is expressed as an algebraic datatype and each phase is a transformation from one (immutable) IR to another. A simple compiler might be 3 to 5 such IRs, but a more complex compiler might be dozens of passes. The problem is that dozens of passes means dozens of copies. Compilation gets quite slow. It's not clear how to make a really fast compiler that has to do so much copying. All of the compilers that I have worked on, except the toy compilers in grad school, used complex, mutable, and ultimately graph-based IRs. Controlling exactly the memory representation of the IR is important when a compiler does a lot of inlining and other optimizations, because a design mistake here can mean the IR for a compilation unit gets enormous and compilation time goes superlinear. I designed the core of V8's optimizing JIT and these issues are really important for an industrial compiler.

fooker 6y ago

>Why are so many compilers not utilizing more pure functional paradigms? Focusing on transformations of input to output instead of doing side effects. It seems like such a perfect fit The primary engineering and scientific challenge of compilers is optimization. That is all about finding a needle in a haystack, converting that to a slightly different needle, and putting it back in the same location in the haystack. This is something functional languages are fairly poor at.