5 ms·
I Wrote a Compiler
- DustinEgg 1y ago[dead]
- TMWNN 1y agoI thought a compiler, with no adjective or caveat, should turn a HLL into machine language. Isn't what this describes—turning BASIC into Go—more accurately described as a "pseudocompiler" or "Go compiler" or somesuch? I know Emacs is always said to have a "bytecode compiler" that processes Elisp code, not a "compiler" per se. Am I mistaken?
- pxc 1y agoThe standard term for this kind of compiler is "transpiler", afaik. Here's the Wikipedia page for such things, which also taught me several other names for them: https://en.m.wikipedia.org/wiki/Source-to-source_compiler https://en.m.wikipedia.org/wiki/Source-to-source_compiler
- kragen 1y agoThe standard term for "transpiler" is "compiler", though.
- ratmice 1y agoSo, if he had invoked go for you would it be a compiler? Another definition is that it translates a source language into a target language.
- meisel 1y agoWhat would you call TypeScript’s tsc, which translates TS to JS? Microsoft would say it’s a compiler: https://code.visualstudio.com/docs/typescript/typescript-compiling https://code.visualstudio.com/docs/typescript/typescript-com...
- andsoitis 1y agoThey do, but that article also mixes “transpile” and “compile” often enough that it is near impossible to deduce what different meanings they might ascribe.
- fao_ 1y agoStrictly speaking it's a transpiler, but honestly the delta between the target language (Go) and the source language (BASIC) is very fluffy and wooly, from what I remember from my PL theory days the distinction was always fuzzy enough that people used whatever term felt right to them. An example off the top of my head — Chicken Scheme (call-cc.org) calls itself a compiler but it's target language is C
- tuveson 1y agoThis kind of question winds up being the CS equivalent of “is a hotdog a sandwich”. I agree that transpiler is a more accurate term for it and that a hotdog is not a sandwich. But there are lots of languages that start life as compile-to-C things. Many compiled languages today output LLVM IR which is not machine language. Similarly people would probably call javac a compiler, even though it outputs bytecode.
- vrighter 1y agoA compiler is a language translator. To me it makes no difference whether it generates machine code (one type of language, machine executable), asm (equivalent language but which needs additional preprocessing into machine code), or some other language (which also needs additional preprocessing into machine code, but the tool for this is another compiler). Or it might output Java bytecode or MSIL, which doesn't even target a real, physical machine at all. They translate one language into another. The line between compiler/transpiler just doesn't make sense to me.
- orthoxerox 1y agoLet's put it this way: if a program translates code written in a "smarter" language into code written in a "stupider" language, then it is okay to call it a compiler. If it translates a restricted subset of BASIC into Go, it doesn't really do anything beyond replacing one syntax with another.
- vrighter 1y ago"Smarter" and "stupider" are completely subjective terms. It translates one language into another, while maintaining logical correctness and its original semantics. Some cases are easier to do than others, but it doesn't change the nature of what is being done: language translation. It isn't as simple as you think. Ex. in basic, the goto statement allows you to jump from anywhere to anywhere. Go has restrictions, such as it may not jump over variables coming into scope (being declared), nor can it jump into another scope, only outwards. So, for starters, this probably needs to scan the BASIC code for variables and hoist everything to the top as well as rewrite any code where it is trying to jump into a deeper scope (ex. jump from the topmost scope of a function into the body of a for loop). Yes, it is a compiler. Maintaining semantics.
- ethan_smith 1y agoA compiler is any program that translates from one language to another (source-to-source, source-to-bytecode, or source-to-machine code), so translating BASIC to Go is indeed a proper compiler, just as GCC translating C to LLVM IR before machine code is still a compiler.
- khaledh 1y agoThe original term for "compiler" was not restricted to compiling down to machine code. From Grace Hopper's paper "The Education of a Computer" (1952)[1]: Specifications for computer information, a catalogue, compiling routines, and subroutines will be given after adding another level to the block diagram. As Fig. 5 stands the mathematician must still perform all mathematical operations, relegating to the UNIVAC programming and computational operations. However, the computer information delivered by the mathematician no longer deals with numerical quantities as such. It treats of variables and constants in symbolic form together with operations upon them. The insertion of a fourth level of operation is now possible, Fig. 6. Suppose, for example, the mathematician wishes to evaluate a function and its first n derivatives. He sends the information defining the function itself to the UNIVAC. Under control of a "compiling routine of type B", in this case a differentiator, using task routines, the UNIVAC delivers the information necessary to program the computation of the function and its derivatives. From the formula for the function, the UNIVAC derives the formulas of the successive derivatives. This information processed under a compiling routine of Type A yields a program to direct the computation. Notice the case for two "compilers": Compiler B (differentiator) compiles symbolic notation to another program, that is fed to Compiler A, which produces an executable that does the actual computation. IMO, a better term for a compiler would have been a "translator." [1] https://dl.acm.org/doi/pdf/10.1145/609784.609818 https://dl.acm.org/doi/pdf/10.1145/609784.609818
- kragen 1y agoThank you for digging this up. I agree about "translator". They were called "compilers" because the first ones were little more than linkers.
- khaledh 1y agoIndeed. I believe the first use of the word compiler (by Hopper and her team) was to describe "compiling" a bunch of existing machine code subroutines into a whole program, rather than translating one language into another.
- npalli 1y ago>The original authors of yacc were Mike Lesk and Eric Schmidt - yes that Eric Schmidt. Incorrect, they were authors of lex. yacc was authored by Stephen Johnson. Surprising to me is all the authors are still around, even though the tools are over 50 years old!. Shows how young computer science field is.
- musicale 1y agoWho coauthored "The C Programming Language" anyway? Oh right, prof. Kernighan. https://www.cs.princeton.edu/~bwk/ https://www.cs.princeton.edu/~bwk/
- cestith 1y agoThe “k” in awk, of course. I’ve never met Kernighan or Weinberger personally. I did have a great conversation once with Al Aho and Larry Wall, largely about the history and mutual influence of programming languages upon one another.
- tapirl 1y ago[flagged]
- orthoxerox 1y agoyes, that Eric Schmidt.
- tapirl 1y ago[flagged]
- deleted 1y ago[deleted]
- gthompson512 1y ago@dang I feel like this is getting close to the lowest level of discourse and occurs somewhat often these days where people overly reference the output of some AI and then are challenging the results without googling. I feel a proper hacker ethos would spur someone to find a real answer. So in honor of the name of the site maybe disallow refutations or other dismissals of a submission based on the output of an AI or overly long discussion that is offtopic about an AI?
- bastawhiz 1y ago>The original authors of yacc were Mike Lesk and Eric Schmidt - yes that Eric Schmidt. I don't know if it's worth mentioning, but the author of the post is David Singleton, the former CTO of Stripe. I almost hadn't noticed until I saw the domain.
- refulgentis 1y agoI worked ~4 layers underneath him when he led Android Wear at Google, and every year or two that happens to me, and it puts a smile on my face. Gotta have love of the game to do this at that level. IIRC, and man, maybe I'm making it up, but, lore was he always made time on a regular schedule to hack. Usually 1 layer from the bottom isn't coding so much anymore. (oddly, I didn't realize he was *CTO* of Stripe until a few months back, when his new thing with Hugo Barra was announced)
- azhenley 1y agoTinyBASIC is fun and beautifully simple. I wrote a 3-part tutorial for making a TinyBASIC-to-C compiler using Python a few years ago. Let’s make a Teeny Tiny compiler https://austinhenley.com/blog/teenytinycompiler1.html https://austinhenley.com/blog/teenytinycompiler1.html
- tuveson 1y agoI know BASIC is kind of a “bad” language, but there’s something so delightful about it. If we’re plugging TinyBASIC projects that others might find interesting, I made an MMO TinyBASIC REPL the other day: http://10klob.com/ http://10klob.com/
- musicale 1y agoBASIC is an amazing language that computing novices (including humanities majors) could learn in an afternoon, that could be efficiently compiled or compactly interpreted, that was small enough to support dozens of interactive users on a mainframe or minicomputer, or to fit into a tiny 8-bit microcomputer – and yet was largely equivalent to FORTRAN in terms of its expressive power. I think the closest modern equivalents might be Python (for easy onramp and scalability from microcontrollers to supercomputers) and JavaScript (for pure ubiquity in every device with a web browser.) I wonder if there is a modern-ish (?) environment that can match Visual BASIC in terms of easy GUI app programming. Perhaps Python or Tcl with Tk (Qt seems harder) or maybe Delphi, or perhaps a modern Smalltalk.
- andsoitis 1y agoDelphi for sure. And while you have to run it on Windows, it can create binaries for Windows, macOS, Linux, and mobile. https://www.embarcadero.com/products/delphi https://www.embarcadero.com/products/delphi
- cestith 1y agoFreePascal and Lazarus get you close on other platforms I think. It’s been ages since I’ve looked into it.
- icemanind 1y agoI wrote a full fledged interpreter by hand for a vintage BASIC language. I called it Basice (I'm Icemanind, so Basice is a play on BASIC and Iceman). It's a little outdated now though. I wrote it using C# and it doesn't use any external libraries, like yacc or flex. It's all by hand. You can see it at https://github.com/icemanind/Basice https://github.com/icemanind/Basice
- matthewmueller 1y agoLove reading these. Keep these blog posts coming!
- WoodenChair 1y agoThis is very similar to the project I have in Chapter 2 of my new book Computer Science from Scratch [0]. It's also Tiny BASIC without INPUT. I called it NanoBASIC. But it's an interpreter not a compiler. This tutorial is a nice starting point. The chapter is much more comprehensive, so if you want to get into the weeds, I can recommend my own chapter (of course). But it's in Python, not Go. The code is on GitHub[1]. But this tutorial is great too. 0: https://nostarch.com/computer-science-from-scratch https://nostarch.com/computer-science-from-scratch 1: https://github.com/davecom/ComputerScienceFromScratch https://github.com/davecom/ComputerScienceFromScratch
- musicale 1y ago> Yes, this is what I do for fun. Don't we all? ;-)
- teo_zero 1y agoWait! What are == and != doing in a BASIC language? Heresy! :)
- dps 1y agoYeah, I really should have included <> :-) Fun to see this post from the deep archive get some interest - thanks for reading!
- fjfaase 1y agoSince 1990, I have developed software with C and later C++. Now that I am working on a C compiler, I am learning new things about the language. So, writing a compiler (or an interpretter) can really help to get a deep understanding of a programming language.
- deleted 1y ago[deleted]
- WalterBright 1y ago> It’s possible to write the lexer and parser entirely by hand I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome. One advantage of doing them by hand is better, more targeted error messages are easier to fold in.
- fredrikholm 1y agoI suspect that this is the more common opinion, especially when the desired outcome is real world use. Recursive descent is surprisingly ergonomic and clean if one gets the heuristics right. Personally I find it way easier than writing BNF and its derivatives as you quickly get into tricky edge cases, slow performance and opaque errors.
- hombre_fatal 1y agoYeah, grammars seem easy at first, but they're full of arcane knowledge like writing your tokens with the right affinity and greediness, ensuring back tracking is performant, and that you'll get good error messages. Same with parser combinators. Not until a bunch of trial and error do you build up the intuitions you need to use them in production, I think. Despite two decades of using those, I've found it much simpler to write my own scanning or RD parser.
- WalterBright 1y agoD was originally designed to require only one token lookahead, but it turns out to get the aesthetic I wanted, that arbitrary lookup was needed. That turned out to be very handy when adapting it to compile C code. Much of the parser code, if you compare the code with the BNF grammar, is a 1:1 correspondence. Super easy to do.
- sph 1y ago> I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome. It's also the most annoying if you're writing a new language. You want to iterate on its ideas, but can't do so until you have a parser done. I've been designing a few language concepts over the past year, and it feels 80% of this time has been writing and debugging parsers; by the time I get to the meat of language design - the shape of its AST, the semantics of it - any small syntactic change means going back to update the lexer and parser stage. Doesn't help that I can't settle on a syntax. BTW I first started with PEG, which are nice in theory, but I feel the separation of lexing and parsing stage to very helpful to reduce boilerplate (handling whitespace in PEG is obnoxious). Later, I hand-wrote my parsers (in C), but it's gotten so repetitive I've dedicated a weekend to just learning lex/yacc (actually flex/bison). Even if parsers are easy to write, it's good to have higher level tools to reduce the tedium of it.
- kristopolous 1y agonice to see that the red dragon book is still a thing. I've heard people have stopped using the wizard book.
- p4bl0 1y agoI like these kind of fun projects! I wrote a very small but complete compiler and VM for a very simple language: boolean expressions. I use it as a "what to expect" type of introduction during the first session of my compiler course. The whole code is here, it is less than 150 lines of OCaml code (plus a few lines of C for the VM) and uses standard parsing tools: https://gist.github.com/p4bl0-/9f4e950e6c06fbba7e168097d89b0e46 https://gist.github.com/p4bl0-/9f4e950e6c06fbba7e168097d89b0...
- djoldman 1y agoHow does one debug a grammar? This has always eluded me. Where is the special tooling to help spot errors?
- tiu 1y agoI am probably misunderstanding your requirements but if you are looking for something like regex101 then https://omrelli.ug/nearley-playground/ https://omrelli.ug/nearley-playground/ and https://bnfparser.firebaseapp.com/ https://bnfparser.firebaseapp.com/ although not sure how much 'practical' are they. Googling gives [2], [3], [4]. [2] https://mingodad.github.io/parsertl-playground/playground/ https://mingodad.github.io/parsertl-playground/playground/ not sure. [3] https://chrishixon.github.io/chpeg/playground/ https://chrishixon.github.io/chpeg/playground/ [4] https://mdkrajnak.github.io/ebnftest/ https://mdkrajnak.github.io/ebnftest/
- djoldman 1y agoThanks!
- dugmartin 1y agoIf you use something like Antlr (https://www.antlr.org/ https://www.antlr.org/) it has visualization tools and an online tester (http://lab.antlr.org/ http://lab.antlr.org/). There are also tools for visualizing generic EBNF grammars like this: https://jacquev6.github.io/DrawGrammar/ https://jacquev6.github.io/DrawGrammar/
- likium 1y agoNotably, this is written by David Singleton, who at the time was the CTO of Stripe.
- firesteelrain 1y agoI have played around with the Crafting Interpreters book. Maybe the author oversimplifies a bit, but it seems with yacc and lex that nothing is really stopping anyone from making their own language and compiler. It always seemed like black magic. But the same could be said about books, nothing is stopping you from writing a book except good ideas, story, and structure.
- throw10920 1y agoBASIC is a good candidate for an easy language to implement. I'd also propose Pascal, Lisp (because S-expressions make parsing easier), and FORTH.
- jcuenod 1y agoThis is great! I feel like there's been a resurgence of interest in language design and compilers of late. I have no business having an interest in this kind of thing, but even I have been inspired to try and make the changes to javascript that I think would improve it: https://chicory-lang.github.io/ https://chicory-lang.github.io/
- norir 1y agoWriting a compiler without first learning how to write a parser is like learning to play an instrument without practicing scales.
- deleted 1y ago[deleted]