I’m going to use this opportunity to reiterate one of my favorite excessively-pendantic points: Compilers are called “compilers” due to an accident of history. The original compiler did little more than append a standard library to an assembly program, fixing up function calls to it so that the programmer didn’t need to precompute its memory location. In other words the original compiler was actually a “linker”, and did little more than compile things together.
If things were named logically, a compiler would actually be called a “translator”, because the analogy with the human jobs is nearly perfect. A human interpreter listens to all or part of a statement, then provides the equivalent in another language, with speed being of higher importance than accuracy. Whereas a human translator takes a completed text and takes an arbitrary amount of time to create a product where quality is of paramount importance. (We can perhaps even go so far as to say that languages that are created to be interpreted differ from languages created to be compiled are meant to be used differently, in much the same way that as the distinction between spoken and written natural lanuages.)
If you read IBM documentation from the ‘60s and ‘70s, they often referred to the program that converted FORTRAN or COBOL into machine code as a translator. Even in the ‘90s, the Psion Series 3’s embedded programming language used Translate rather than Compile as the verb in the menu that generated a stand alone (though still bytecode) program. I am not sure when compiler took over from translator as the preferred verb but I tend to use translate and interpret when explaining to non-geeks because they understand the difference between doing a single translation pass over a book and having a version in another language versus reading in one language and speaking each sentence in another (and the relative latency and throughput of both ideas translate directly into the programming language context).
I wonder if partial evaluator is a better term than a translator. A translator can technically translate pascal to C or vice versa without changing the level of abstraction.
I would still call that a translator. The term doesn’t imply how different the two languages are. (And I’m would be surprised if nobody had ever written a Pascal compiler that just compiled to C. If it works, it’s still considered to be a compiler.)
I think the key difference between a conventional compiler and a C to Pascal converter is that it performs a lossy transform. There are many C programs that map to the same x86 assembly, for example, because the act of compiling strips a lot of identifiers and, with optimisation, will reassociate arithmetic and so on. I contrast, a source translator tries to preserve the bits of the source that matter only to humans.
Both this and the linked post are great, but I spent a lot of the time I was reading them both wondering to myself “What the fuck is this Boyfriend language that I never heard about?”
I like that distinction. Another way I’ve phrased it is that interpreters are a function of argv, but compilers aren’t. (Obviously a compiler has its own argv, but you can probably see what I mean)
For example, I remember someone on Reddit made the claim that Python has compile-time metaprogramming.
Python has a bytecode compiler, and you can do stuff before main() in Python. And that “stage” is often used to do things like what you would do with constexpr in C++ or comptime in Zig.
But it’s not compile-time – it’s interpreted runtime. Because you can use sys.argv in the stage before main. So Python has a single stage of execution with runtime reflection, not 2 stages (compile-time metaprogramming, then runtime)
(Python does have a bytecode compiler, but no compile-time metaprogramming. It doesn’t expose a hook in the actual bytecode compilation phase, although it does export a reflective bytecode compiler interface at runtime. [1])
One thing I found interesting is that AFAIK PyPy’s RPython (which is different than Python) makes this real: the compiler “starts” at main().
I do a similar thing in Oil:
In the interpreted Python mode, it computes a bunch of stuff before main(), and then main() uses that data.
In the translation to C++, the C++ code generators import the stuff before main(), evaluate it, and then write the result to global C++ data structures. The C++ code then uses those “baked in” globals, incurring zero startup time.
For example, this is done with the huge array of regular languages in the lexer, flag parser definitions, computed string constants, computed lookup tables (e.g. Pratt parser precedence), and more! Other shells have traditional C++ code gen steps to do the same thing, but I’ve come to like this “one program but partially evaluated” style.
Request: someone should write a follow-up explaining Futamura projections :) As I understand it, it’s a form of partial evaluation where you take a interpreter + compiler, and get a compiler for free.
I think it should be possible to do it with “Make a Lisp” which has lots of real implementations – https://github.com/kanaka/mal
For that case, the problem with BF is that nobody knows how to write a BF compiler in BF, and even if they could, nobody could read it. i.e. the compiler/interpreter examples were in Rust and not BF
[1] edit: just realized that the author’s Converge language explored precisely that issue for a Python-like language :) https://convergepl.org/about.html
This is a great insight! Thank you for sharing. It makes sense that the transition would happen when brackets are precomputed and turned into loops, because the resulting AST is topologically distinct; in a certain sense, Brainfuck-with-precomputed-loops is not able to express certain indeterminate crashy programs like “+]”. (I didn’t test it, but it looks like this program should crash your “+ bracket caching” Rust program by visual inspection.)
I’ve been thinking about this categorically, and this all lines up with what I’ve got so far. In particular, we should think of a compiler as a sort of composition of fancy functors, with one of those functors acting as the interpreter. Here, we could imagine that BF is the (syntactic) category of Brainfuck programs, with each object representing an equivalence class of programs (under your favorite equivalence relation). Then, starting with “+ bracket caching”, we are first compiling by sending programs to a new category BFLoop of Brainfuck programs whose ASTs always express correctly-nested loops.
Pedantically, we’re mapping from BF to BFLoop + 1, because “+]” is an element of BF but not BFLoop. This seems to be one of the great practical advantages of compilation, akin to making illegal states unrepresentable.
The use of Big O here is hiding a lot of details, and I think having one f function here miscommunicates the differences in approaches. What work is happening at compile time affects what work happens at runtime, and thus changes the definition of f. CPython’s f(m) >> GCC’s f(m), so much so that I would give them different identifiers: say a(m) for evaluation of a function and b(b) for the evaluation of a function with the overhead of maintaining a virtualized environment (aka interpreting bytecode). For some programs, the interpretation may lead to O(b(m)) > O(a(m)) because of the overhead of env bookkeeping and instruction translation to the target machine. JIT compilation fits nicely here as it describes a runtime transition from O(b(m)) to O(a(m)).
This is also apparent in the final table listing the different BF interpreters from the last post. The base interpreter running hanoi.bf in 13.404±0.0785 seconds and the final reorganized interpreter running it in 0.484±0.0038 seconds (~97% reduction in runtime) tells me we’re talking about different fs here with different O(f(m))s.
I’m going to use this opportunity to reiterate one of my favorite excessively-pendantic points: Compilers are called “compilers” due to an accident of history. The original compiler did little more than append a standard library to an assembly program, fixing up function calls to it so that the programmer didn’t need to precompute its memory location. In other words the original compiler was actually a “linker”, and did little more than compile things together.
If things were named logically, a compiler would actually be called a “translator”, because the analogy with the human jobs is nearly perfect. A human interpreter listens to all or part of a statement, then provides the equivalent in another language, with speed being of higher importance than accuracy. Whereas a human translator takes a completed text and takes an arbitrary amount of time to create a product where quality is of paramount importance. (We can perhaps even go so far as to say that languages that are created to be interpreted differ from languages created to be compiled are meant to be used differently, in much the same way that as the distinction between spoken and written natural lanuages.)
If you read IBM documentation from the ‘60s and ‘70s, they often referred to the program that converted FORTRAN or COBOL into machine code as a translator. Even in the ‘90s, the Psion Series 3’s embedded programming language used Translate rather than Compile as the verb in the menu that generated a stand alone (though still bytecode) program. I am not sure when compiler took over from translator as the preferred verb but I tend to use translate and interpret when explaining to non-geeks because they understand the difference between doing a single translation pass over a book and having a version in another language versus reading in one language and speaking each sentence in another (and the relative latency and throughput of both ideas translate directly into the programming language context).
In greek, compilers are actually called ‘translators’ (μεταγλωττιστές).
Same in Finnish, kääntäjä.
I wonder if partial evaluator is a better term than a translator. A translator can technically translate pascal to C or vice versa without changing the level of abstraction.
I would still call that a translator. The term doesn’t imply how different the two languages are. (And I’m would be surprised if nobody had ever written a Pascal compiler that just compiled to C. If it works, it’s still considered to be a compiler.)
I think the key difference between a conventional compiler and a C to Pascal converter is that it performs a lossy transform. There are many C programs that map to the same x86 assembly, for example, because the act of compiling strips a lot of identifiers and, with optimisation, will reassociate arithmetic and so on. I contrast, a source translator tries to preserve the bits of the source that matter only to humans.
Both this and the linked post are great, but I spent a lot of the time I was reading them both wondering to myself “What the fuck is this Boyfriend language that I never heard about?”
The linked post does link the first occurrence of “BF’ to the Wikipedia page for the BrainFuck language though.
Oh, it was absolutely my own fault for misunderstanding =P
I like that distinction. Another way I’ve phrased it is that interpreters are a function of
argv, but compilers aren’t. (Obviously a compiler has its ownargv, but you can probably see what I mean)For example, I remember someone on Reddit made the claim that Python has compile-time metaprogramming.
Python has a bytecode compiler, and you can do stuff before main() in Python. And that “stage” is often used to do things like what you would do with
constexprin C++ orcomptimein Zig.But it’s not compile-time – it’s interpreted runtime. Because you can use
sys.argvin the stage before main. So Python has a single stage of execution with runtime reflection, not 2 stages (compile-time metaprogramming, then runtime)(Python does have a bytecode compiler, but no compile-time metaprogramming. It doesn’t expose a hook in the actual bytecode compilation phase, although it does export a reflective bytecode compiler interface at runtime. [1])
One thing I found interesting is that AFAIK PyPy’s RPython (which is different than Python) makes this real: the compiler “starts” at main().
I do a similar thing in Oil:
For example, this is done with the huge array of regular languages in the lexer, flag parser definitions, computed string constants, computed lookup tables (e.g. Pratt parser precedence), and more! Other shells have traditional C++ code gen steps to do the same thing, but I’ve come to like this “one program but partially evaluated” style.
Request: someone should write a follow-up explaining Futamura projections :) As I understand it, it’s a form of partial evaluation where you take a interpreter + compiler, and get a compiler for free.
I think it should be possible to do it with “Make a Lisp” which has lots of real implementations – https://github.com/kanaka/mal
And then maybe compile to: https://en.wikipedia.org/wiki/SECD_machine
For that case, the problem with BF is that nobody knows how to write a BF compiler in BF, and even if they could, nobody could read it. i.e. the compiler/interpreter examples were in Rust and not BF
Ideas here: https://old.reddit.com/r/ProgrammingLanguages/comments/10m1d76/distinguishing_an_interpreter_from_a_compiler/j618x8j/
[1] edit: just realized that the author’s Converge language explored precisely that issue for a Python-like language :) https://convergepl.org/about.html
This is a great insight! Thank you for sharing. It makes sense that the transition would happen when brackets are precomputed and turned into loops, because the resulting AST is topologically distinct; in a certain sense, Brainfuck-with-precomputed-loops is not able to express certain indeterminate crashy programs like “+]”. (I didn’t test it, but it looks like this program should crash your “+ bracket caching” Rust program by visual inspection.)
I’ve been thinking about this categorically, and this all lines up with what I’ve got so far. In particular, we should think of a compiler as a sort of composition of fancy functors, with one of those functors acting as the interpreter. Here, we could imagine that BF is the (syntactic) category of Brainfuck programs, with each object representing an equivalence class of programs (under your favorite equivalence relation). Then, starting with “+ bracket caching”, we are first compiling by sending programs to a new category BFLoop of Brainfuck programs whose ASTs always express correctly-nested loops.
Pedantically, we’re mapping from BF to BFLoop + 1, because “+]” is an element of BF but not BFLoop. This seems to be one of the great practical advantages of compilation, akin to making illegal states unrepresentable.
The use of Big O here is hiding a lot of details, and I think having one
ffunction here miscommunicates the differences in approaches. What work is happening at compile time affects what work happens at runtime, and thus changes the definition off. CPython’sf(m)>> GCC’sf(m), so much so that I would give them different identifiers: saya(m)for evaluation of a function andb(b)for the evaluation of a function with the overhead of maintaining a virtualized environment (aka interpreting bytecode). For some programs, the interpretation may lead toO(b(m))>O(a(m))because of the overhead of env bookkeeping and instruction translation to the target machine. JIT compilation fits nicely here as it describes a runtime transition fromO(b(m))toO(a(m)).This is also apparent in the final table listing the different BF interpreters from the last post. The base interpreter running hanoi.bf in
13.404±0.0785seconds and the final reorganized interpreter running it in0.484±0.0038seconds (~97% reduction in runtime) tells me we’re talking about differentfs here with differentO(f(m))s.