7 ms·
I wrote a 231-byte Brainfuck compiler by abusing everything
- xiphias2 5y agoWouldn’t outputting amd64 instructions and jumping to it create a shorter interpreter?
- mjevans 5y agoIsn't a compiler supposed to produce one or more of: machine code, link-able segments of machine code, or at least 'bytecode' for a 'virtual' machine? The definition of this problem strikes me far more as either a transpiler or a pre-processor for a Domain Specific Language.
- thewakalix 5y ago“Compiling to C” is an established strategy; for instance, GHC used to compile to C--, a subset of C. This doesn’t seem wrong to me; after all, assembly is already an abstraction layer over machine code, and outputting assembly would hardly be “uncompilerish” behavior. I suppose it depends on whether you view C as a low-level language.
- anonymfus 5y ago> GHC used to compile to C--, a subset of C. C-- is not a subset of C.
- wccrawford 5y agohttps://en.wikipedia.org/wiki/C-- https://en.wikipedia.org/wiki/C-- > The name of the language is an in-joke, indicating that C-- is a reduced form of C, in the same way that C++ is basically an expanded form of C. ("--" and "++" mean "decrement" and "increment".)
- BenjiWiebe 5y agoQ&A #5 of https://www.cs.tufts.edu/~nr/c--/faq.html https://www.cs.tufts.edu/~nr/c--/faq.html explains why C-- is not a subset of C.
- DonHopkins 5y ago“C++++-= is the new language that is a little more than C++ and a lot less.” -Bill Joy Bill Joy’s Law: 2^(Year-1984) Million Instructions per Second https://donhopkins.medium.com/bill-joys-law-2-year-1984-million-instructions-per-second-3a8c92165cfe https://donhopkins.medium.com/bill-joys-law-2-year-1984-mill...
- thewakalix 5y agoYou’re right, and as it happens, GHC compiles first to Cmm and then (as one half-deprecated option) to C.
- DonHopkins 5y agoC combines the power of assembly language with the readability and maintainability of assembly language.
- pajko 5y agoA compiler compiles something to something. For example, gcc compiles C code to assembly, which is then compiled to machine code by gas. Clang does the same: https://freecompilercamp.org/clang-basics/ https://freecompilercamp.org/clang-basics/
- user-the-name 5y agoClang definitely does not output assembly code and invoke an assembler. It generates machine code directly. It can optionally also generate assembly code if you want to look at it, but it does not do this during normal compilation.
- misnome 5y agoClang doesn't generate LLVM IR as part of it's normal process?
- user-the-name 5y agoNot in a text file, no. It generates LLVM data structures that can be serialised to a text format, but aren't. The only external binary clang invokes is, optionally, the linker. Otherwise, everything is done in one executable invocation without temporary files.
- aetherspawn 5y agoYes and no. It uses the llvm API rather than pipe to llc
- pajko 5y agoNot saving everything to files and not doing things via multiple executables does not mean that a compiler does things in a single step, generating machine code directly from the source code. Both gcc and clang support the -save-temps switch to keep intermediate files during the compilation process. These files are created even without this argument, except that their names are randomly generated somewhere and the files are deleted afterwards.
- TheMatten 5y agoAdding to thewakalix's answer, many compilers use LLVM as a backend, where LLVM's IR is higher-level-than-bytecode language too. So that would mean that e.g Clang or current GHC wouldn't qualify either.
- user-the-name 5y agoLLVM is a static library that you link. Clang does not generate LLVM IR text files, it invokes LLVM's code generator directly.
- Al-Khwarizmi 5y agoIn classic compiler theory, the term "transpiler" doesn't even exist, they're all compilers.
- 411111111111111 5y agoThey literally didn't exist back then though. so not just the term was unknown back then, the practice itself too...
- KMnO4 5y agoApparently Intel shipped a transpiler for 8080 to 8086 source code in 1978. https://en.wikipedia.org/wiki/Source-to-source_compiler#Intel_CONV86 https://en.wikipedia.org/wiki/Source-to-source_compiler#Inte...
- cout 5y agoLikewise, the first C++ compiler (cfront) might today be considered a transpiler.
- nextaccountic 5y agoA transpiler is a compiler
- Banana699 5y agoThere is no fundamental difference between compilers, code formatters, preprocessors or transpilers. Anything that takes a program and outputs another program related to it by some semantics is a compiler. That said though, I do agree that calling an assembler like this (brainfuck is a kind of assembly) a compiler stretches things a bit, for an entirely different reason: usually there is some sort of a complexity threshold of the input language. The compiler has to at least maintain a symbol table for named entities (traditional assemblies has variable-like entities, macros and subroutines, the assembler has to keep track of all that). Brainfuck is completely linear, with no named entities at all. The "compiler" looks like a dumb string processor, just iterates over one buffer to transform it into another buffer, and doesn't maintain any sort of structures on the code being translated. By the strict "compiler : program->program" definition, this doesn't matter. But my intuition holds that dumb string processing is a bit short of "true" compilation.
- xg15 5y ago> There is no fundamental difference between compilers, code formatters, preprocessors or transpilers. Anything that takes a program and outputs another program related to it by some semantics is a compiler. That is arguing semantics and, while not wrong, I think it muddies the waters: By that logic, sed and awk are compilers. In the end, only machine code can be executed, so you'll need something at the end of your chain that produces machine code or at least executes your DSL in an interpreter loop. So I think a distinction between "compilers" that generate machine code and "compilers" that don't is worthwhile.
- dgb23 5y agoWhere do you draw the line? Is javac not a compiler?
- bidirectional 5y agoMost researchers I've spoken to loathe the term transpiler.
- TazeTSchnitzel 5y agoPlenty of compilers target relatively high-level languages. They're no less compilers for it; “transpiler” feels fairly arbitrary to me. With a bit of effort and the right add-on (https://github.com/JuliaComputing/llvm-cbe https://github.com/JuliaComputing/llvm-cbe) you can make any LLVM-based compiler produce C code!
- danparsonson 5y agoIf you'd like to see some tiny BF interpreters, have a look here: https://www.hugi.scene.org/compo/compoold.htm#compo6 https://www.hugi.scene.org/compo/compoold.htm#compo6 98 bytes, the smallest!
- aetherspawn 5y agoThe smallest compiler would copy the BF program to the end of this interpreter.
- Brian_K_White 5y agoOMG THIS This is my favorite answer to why this should or should not qualify as a compiler. If translating to c is a compiler then anything is a compiler and the term has no meaning at all.
- klyrs 5y agoThe word we need here is "trivial". A compiler is a function (or possibly, nondeterministic process) from source code in a first language, to source in a second language. The languages can be the same, for example, in the case of metaprogramming. The identity function is a trivial compiler. Calling it a non-compiler only serves to complicate the definition of compiler, with no discernable benefit.
- tylerhou 5y agoHow do you define "trivial?" I've created a new language called Brainfuck2 that is exactly the same as Brainfuck except the + symbol is replaced with a t. Clearly my compiler from Brainfuck2 => Brainfuck does not implement the identity function, and is less than 50 bytes.
- klyrs 5y agoAh, well that depends. The simplest definition is that the identity function is the only trivial compiler. One might take a more expansive view, that your Brainfuck2 language is homomorphic to brainfuck through a character-replacement table (though I must ask -- does your compiler introduce bugs if the original brainfuck source contains comments?[1]), and decide that character-replacement is trivial. You could even go further, and say that context-free token-replacement is trivial, at which point TFA counts as trivial compiler. That said, I'd estimate that most brainfuck compilers are trivial under that interpretation. [1] if you did it right, it's idempotent, which is about as close to trivial as a nontrivial function gets under the lens of symbolic dynamics, but I'm getting a bit far afield
- user-the-name 5y agoThe original Brainfuck compiler was 240 bytes, and created executables directly rather than relying on an external toolchain.
- Zardoz84 5y agoI find the DLang version far more easy to understand. Also, it could do compiler optimizations : https://theartofmachinery.com/2017/12/31/compile_time_brainfuck.html https://theartofmachinery.com/2017/12/31/compile_time_brainf...
- xg15 5y agoa 231-byte Brainfuck-to-C compiler* It's still an impressive feat, and very informative on the assembly details - but doesn't feel as incredible as the headline makes believe as the core logic seems to be a string search-and-replace of the strings in the "reviewing brainfuck" table. Seems to me, you could write the next brainfuck compiler in sed.
- zelon88 5y agoIt seems more like a parser than a compiler. It doesn't write a binary, it just translates brainfuck to C source code. In the OPs defense, they did say "by abusing everything."
- barosl 5y agoA compiler doesn't have to emit machine code. It just needs to translate one language into another, which the author's program does. Also, a parser implies having an internal, structured representation. As the C language is neither internal nor structured, I'd say the program is more likely a compiler.
- recursive 5y agoI blame the rise of the word "transpiler" for making people think that compilation is some more magic/narrow/special thing.
- whatshisface 5y agoThere is a practical, empirical distinction between compilers and transpilers. Most compilers in practice have backends full of deep and well-explored techniques specific to machine code like register allocation, window optimizations, and other stuff like that. Most transpilers you see out in the wild share more in common with compiler frontends in the techniques and the theory they apply.
- mywittyname 5y agoThe term transpiler arose when there was a need to denote a special kind of compiler whose target is another language or version of the same language.
- panic 5y agoHere's an even smaller one for 64-bit Linux: https://gist.github.com/ianh/61e6219f0a9866b31a2b864033c1812e https://gist.github.com/ianh/61e6219f0a9866b31a2b864033c1812... $ uname -a Linux personal-1 4.19.0-6-cloud-amd64 #1 SMP Debian 4.19.67-2 (2019-08-28) x86_64 GNU/Linux $ as -g -o bf.o bf.S && ld -o bf bf.o $ size bf.o text data bss dec hex filename 167 0 0 167 a7 bf.o $ size bf text data bss dec hex filename 199 0 0 199 c7 bf
- ndesaulniers 5y agoWould a jump table create a smaller compiler? Trade off an indirect call (and more static data) for all of those comparisons.