peg-bootstrap

ve to compile itself.

otstrap/blob/master/peg.md (from a peg grammar with semantic actions to javascript, 66 lines of code) - https://github.com/kragen/peg-bootstrap/blob/master/handaxew... (tangles a literate program in virtually any plain-text format, such as markdown, html, restructuredtext, or tex, into virtually any plain-text programming language, 208 lines of code; used to tangle both itself and the peg compiler compiler above) - http://canonical.org/~kragen/sw/dev3/meta5ix.m5 (from meta5ix, a language for writing parsers derived from val schorre's meta-ii, to meta5ix assembly, 18 lines of code; it is a top-down parsing language with limited backtracking, like pegs, but less expressive and implementable without heap allocation or the ability to backtrack past the beginning of a line; see http://canonical.org/~kragen/sw/dev3/meta5ixrun.py for an m5asm interpreter) - http://canonical.org/~kragen/sw/dev3/meta5ix2c2.m5 (from a slightly different variation of meta5ix to c, 133 lines of code) most of these do take the same ast-free approach as the linked blog post and crenshaw, just emitting code as they finish parsing a production (or, in the case of stoneknifeforth, a token), but ur-scheme in particular does not; it uses scheme s-expressions as its syntax tree, because some kind of syntax tree is necessary to be able to allocate some local variables on the stack while also supporting closures. peg-bootstrap can certainly handle code that builds an ast with its semantic actions, but its implementation of itself just glues together snippets of javascript text also worth mentioning in this connection: - darius bacon's work, especially parson (for example, https://github.com/darius/parson/blob/master/eg_calc_compile...) - the oberon compiler in wirth and gutknecht's oberon book - the later chapters of sicp

ix2c.m5 (precompiled version at http://canonical.org/~kragen/sw/dev3/meta5ix2c.c). Meta5ix written in itself is only 18 lines of code. Briefly, "" encloses expected input, {} encloses a line of output, [] encloses repeating constructs, commas separate alternatives (implemented without backtracking), fnord skips leading whitespace, $it copies the last <<>>-enclosed input token to the output, and other $variables interpolate locally-defined assembly labels. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" Meta5ix, like my earlier peg-bootstrap https://github.com/kragen/peg-bootstrap/blob/master/peg.md (66 lines of code, compiles to JavaScript, supports backtracking), is not really something you want to write a parser for your application language in. It's a compiler-compiler you can extend to support the parsing constructs you actually want for your language, then recompile with itself. Dave Long described META-II as "a field-improvised lever", and I think that's true of these as well, but maybe an even better analogy is Archimedes's fixed point.

articularly awkward and inefficient way to output that 1 or 0. A compiler for Brainf*** or SK-combinators or the untyped λ-calculus would be "more real" in that sense. More practical, and maybe also fitting into 150 lines, might be a language for something like a programmable calculator (untested sketch): program ::= stmt | stmt ";" program. stmt ::= "print" numexpr | variable ":=" numexpr | "while" numexpr comparator numexpr "{" program "}". comparator ::= "<" | ">" | "==" | "!=" | "<=" | ">=". numexpr ::= term | numexpr "+" term | numexpr "-" term. term ::= factor | term "*" factor | term "/" factor | term "%" factor. factor ::= atom | "-" atom | "+" atom | atom "^" factor. atom ::= "(" numexpr ")" | numeric_constant | variable. That's powerful enough to conveniently write, for example, a numerical root finding program for an arbitrary arithmetic expression. Maybe for pedagogical purposes (which, as I said, I am totally ignorant of) it would be useful to leave out one of the levels of precedence and some of the operators and have the students add them as an exercise. But I think that within a complexity budget of 150 lines of code you can maybe be even more ambitious than that. Darius Bacon's example compiler in https://github.com/darius/parson/blob/master/eg_calc_compile... is a bit more stripped down than that, but in its 32 lines of code it compiles arithmetic assignment statements to a three-address RISC-like code (though using an unbounded number of registers). https://github.com/darius/parson/blob/master/eg_calc_to_rpn.... is a 16-line version that compiles the same language to a stack machine like your tutorial example: from parson import Grammar, alter g = Grammar(r""" stmt* :end. stmt : ident '=' exp0 ';' :assign. exp0 : exp1 ('+' exp1 :'add')*. exp1 : exp2 ('*' exp2 :'mul')*. exp2 : '(' exp0 ')' | /(\d+)/ | ident :'fetch'. ident : /([A-Za-z]+)/. FNORD ~: /\s*/. """)(assign=alter(lambda name, *rpn: rpn + (name, 'store'))) ## print ' '.join(g('v = 42 * (5+3) + 2*2; v = v + 1;')) #. 42 5 3 add mul 2 2 mul add v store v fetch 1 add v store Of course that still contains no control flow, so it's still not a very convincing example of why you'd take the extra trouble to write a compiler rather than an interpreter. In 66 lines of code in https://github.com/kragen/peg-bootstrap/blob/master/peg.md I wrote an example compiler which compiles a PEG grammar into a JavaScript parser for that grammar. Admittedly those 66 lines do not include an implementation of JavaScript to run the code on. It compiles the language it's written in. In 132 lines of code in https://github.com/kragen/stoneknifeforth/blob/master/tinybo... I wrote an example compiler which compiles a crippled Forth dialect into i386 machine code, including an ELF header so you can run the result. It also compiles the language it's written in. It also doesn't include an i386 emulator to run it on. In 83 lines of code in http://canonical.org/~kragen/sw/dev3/neelcompiler.ml Neel Krishnaswami wrote a compiler from the untyped λ-calculus to a simple assembly language for a register machine. It also doesn't include an implementation of the assembly language. In 18 lines of code in http://canonical.org/~kragen/sw/dev3/meta5ix.m5, a simplification of Val Schorre's META-II, I wrote a compiler from grammar descriptions to an assembly code for a parsing-oriented virtual machine. It compiles the language it's written in. A Python interpreter for the machine is in http://canonical.org/~kragen/sw/dev3/meta5ixrun.py (109 lines of code) and a precompiled version of the compiler-compiler for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm. It does recursive descent with only a single token of backtracking; a minimal summary of the most eccentric aspects of its syntax is that "" encloses text to expect on input, {} encloses text to output, <<>> encloses a token to parse from the input that might be copied to the output with $it (or unindented with @it), commas separate alternatives, and [x] is zero or more repetitions of x. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" A slightly incompatible variant of Meta5ix which instead compiles itself to C is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 (133 lines of code, depending on how you count). (No C compiler is included.) The precompiled C output for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.c. Meta5ix is extremely weak and limited, really only enough for a compiler front-end. Dave Long described META-II as "a field-improvised lever", which I think is still apt for Meta5ix. Now, again, I am totally ignorant about pedagogy, so I could be wrong about this, but I think that probably self-compiling compiler-compilers like most of my examples here are not the best tutorial examples, because they refer to themselves in complex and confusing ways. But I feel like they represent pretty good evidence that you can do something a lot more interesting in a 150-line-of-code compiler than evaluating a Boolean circuit.

ause I think it's often helpful to see the temporal development of a program from a simpler version to a more complex version. The simpler version is easier to understand and helps you focus on the most fundamental aspects of the program. https://www.youtube.com/watch?v=KoWqdEACyLI is a 5'30" screencast (not by me) of explaining the development of a Pong program in this fashion. I think it's usually easier to understand a program in this fashion than by trying to understand the final complete version bit by bit, the way something like "TeX: The Program" forces you to do. ๛ Still, generally speaking, soi-disant literate programming tools—including my own—generally fail to take advantage of the most compelling aspect of the computer as a communication medium: its ability to simulate. When I dive into a new code base, it's never entirely by reading it—whether top-down, bottom-up, or in any other order. The cross-reference links added by things like CWEB (or, you know, ctags) are helpful, of course, but invariably I want to see the output of the program, which CWEB doesn't support at all! (Although Knuth's TeX: The Program does manage to include TeX output despite being written in CWEB, that's in a sense sort of a coincidence; this is not a feature CWEB can provide for any programs other than TeX and METAFONT.) Books like Algorithms, by Knuth's student Sedgewick, are full of graphical representations of the outputs of the algorithms being discussed, and this is enormously helpful—perhaps even more so than the source code; see https://algs4.cs.princeton.edu/22mergesort/ for some examples from the current version of the book, which is lamentably in Java. It's better still, though, when you can edit the code and see the results—when diving into a new code base, I tend to execute modified versions of the code a lot, whether in the debugger or with extra logging or what. Paper books can't do this, but that's no excuse for not doing it when we're writing for readers who have computers. Philip Guo's Python Tutor http://pythontutor.com/ provides dynamic visualization of the memory contents of, in theory, arbitrary code (in the supported languages, including of course Python, but also C, C++, Java, JS, and Ruby). There are things you can display with animation that you can't display in a static page, but Algorithms gets quite far with static printed images, and I think static visualization is better when you can make it work, for reasons explored at length in Bret Victor's http://worrydream.com/MagicInk/. Python Tutor doesn't scale to large programs, but Dorothea Lütkehaus and Andreas Zeller's DDD can control GDB to create such visualizations for anything you can run under GDB (or JDB, Ladebug, pydb, or perl -d). Unfortunately there's no way to share the output of either DDD or Python Tutor, except maybe a screencast, and despite having been around since 01995, DDD has never been popular, I suspect because its Motif UI is clumsy to use. https://edoras.sdsu.edu/doc/ddd/article20.html shows what it looked like in 02002 and https://youtu.be/cKQ1qdo79As?t=106 shows what it looked like in 02015. ๛ Of course, spreadsheets are by far the most popular programming environment, and they have always displayed the program's output when you open it—even to the exclusion of the code, mostly. I've experimented with this sort of thing in the past, with things like http://canonical.org/~kragen/sw/bwt an interactive visualization of the Burrows–Wheeler transform, and so it's been heartening to see modern software development moving in this direction. The simplest version of this is things like Python's doctest, where you manually paste textual snippets of output in the code itself, and a testing tool automatically verifies that they're still up-to-date; Darius Bacon's Halp https://github.com/darius/halp is a more advanced version of this, where the example output updates automatically, so you can make changes to the program and see how they affect the results. ๛ The most polished versions of this approach seem to have adopted the name "explorable explanations", and many of the best examples are Amit Patel's, which he has at different times termed "interactive illustrations" https://simblob.blogspot.com/2007/07/interactive-illustratio..., "active essays" (I think? Maybe I'm misremembering and that term was current in Squeak around 02003: http://wiki.squeak.org/squeak/1125), and "interactive visual explanations". I wrote a previous comment about this on here in 02019: https://news.ycombinator.com/item?id=20954056. However, Amit's explorables, like many other versions of the genre, de-emphasize the underlying code to the point where they both don't display the actual code and don't let you edit it. They're intended to visualize an algorithm, not a codebase. Mike Bostock, d3.js's original author, has created https://bl.ocks.org/ for sharing explorable explanations made with d3, and is doing a startup called ObservableHQ which makes things like this a lot easier to build: https://beta.observablehq.com/d/e639659056145e88 but at the expense of a certain amount of polish and presentational freedom. Also, unfortunately, ObservableHQ programs seem to be tied to the company's website—you can download their output, but very much unlike TeX, the programs will only be runnable until the company goes out of business. So if you aspire to make a lasting contribution to human intellectual heritage, like TeX, GCC, or d3.js itself, ObservableHQ is not for you. ๛ R Markdown (by JJ Allaire—yes, the Cold Fusion dude—and Yihui Xie, among others) is one of the more interesting developments here; as with noweb or HandAxeWeb, you edit something very close to the "woven" version of the source code (in a dialect of Markdown); but, in a separate file alongside, RStudio maintains the results of executing the code, which are included in the "woven" output, and may be textual or graphical. Moreover, as with Halp or ObservableHQ, these results are displayed in a notebook-style interface as you're editing the code. https://bookdown.org/yihui/rmarkdown/notebook.html has a variety of examples, and Xie is rightly focused on reproducibility, which is very challenging to achieve with the existing tooling. https://bookdown.org/ lists a number of books that have been written with R Markdown, and https://github.com/rstudio/rmarkdown explains the overall project. Of course the much more common notebook-style interface, and the one that popularized the interaction style, is Jupyter (influenced by SageMath), which mixes input and output indiscriminately in the same file and peremptorily makes backward-incompatible changes in file formats; the result is a lot of friction with version-control systems. Nevertheless, it supports inline LaTeX, it's easy to use and compatible with a huge variety of existing software, and it can include publication-quality visualizations, so there's a lot of code out there in Jupyter notebooks now, far more than in any system that purports to be a "literate programming" system. Notable examples include Peter Norvig's œuvre (there's a list at https://github.com/norvig/pytudes#pytudes-index-of-jupyter-i...). I find this a very comfortable and powerful medium for this form of literate programming; recent examples include https://nbviewer.jupyter.org/url/canonical.org/~kragen/sw/de..., https://nbviewer.jupyter.org/url/canonical.org/~kragen/sw/de..., and https://nbviewer.jupyter.org/url/canonical.org/~kragen/sw/de..., which are maybe sort of embarrassingly bad but I think demonstrate the potential of the medium for vernacular expression of vulgar software, as well as lofty Norvig-type things. ๛ Konrad Hinsen has written about the reproducibility and lock-in problems introduced by Jupyter, for example in https://khinsen.wordpress.com/2015/09/03/beyond-jupyter-what..., and has been using Tudor Gîrba's Glamorous Toolkit https://gtoolkit.com/ to explore what comes next. He's been hitting the reproducibility problem pretty hard in http://www.activepapers.org/ but the primary intent there is, as with the explorable-explanations stuff, code as a means to producing research ("How should we package and publish the outcomes of computer-aided research"), rather than maintainability and understandability of code itself. I think this is a promising direction for literate programming as such, too.

> ::= <idchar>+ " "* | "(" " "* <sexp>* ")" " "* And many, many huge systems have been written in Lisps whose grammars amount to little more than that. My favorite grammars are PEGs, which accommodate scannerless parsing rather better than LL(1) and LALR(1) parsers, because PEGs have infinite lookahead with worst-case linear-time parsing (at the expense, it must be admitted, of being a huge memory hog). PEGs are also composable in a way that LALR and LL grammars aren't. I wrote a one-page PEG parser generator targeting JS at https://github.com/kragen/peg-bootstrap/blob/master/peg.md a few years back. But I think an excessive focus on the syntax of a programming language really detracts from what's really revolutionary about programming languages (and compilers), which is their semantics. We have much better theories of semantics now than we had in the 1970s when the traditional compilers course was being laid out. Books like Essentials of Programming Languages can be wonderful introductions to the fuzzier ones, and there's a lot of work in things like Coq and Idris to come up with tractable formalizations. But you don't need much of a theory of semantics to get a simple compiler up and running! But I haven't ever actually taught a compilers course, so maybe my ideas are miscalibrated about what students would enjoy and find motivating (having a working compiler for a simple language after doing the first problem set) and what students will find difficult out of proportion to any rewards it might bring (getting recursive-descent parsers for complex grammars working, debugging precedence rules, refactoring grammars to eliminate left recursion, encountering unexpected exponential-time parse failures, etc.).

ssible ELF executable, which turns out to be 45 bytes, which unfortunately has been broken by recent Linuxes: http://www.muppetlabs.com/~breadbox/software/tiny/teensy.htm... Based on Brian's work, I wrote a self-compiling compiler for a tiny dialect of Forth: https://github.com/kragen/stoneknifeforth which is about two pages of code if you remove the comments. I also wrote a PEG compiler-compiler in JavaScript which is one page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md --- ultimately I want to make a version that generates StoneKnifeForth code instead of JS, but I haven't gotten around to it. I also designed a minimal CPU architecture: https://github.com/kragen/calculusvaporis but I only have software implementations for it so far, and no interesting code. And I wrote a metacircular interpreter for Bicicleta in half a page of code, which I guess is some kind of "minimal coding example": http://lists.canonical.org/pipermail/kragen-hacks/2007-Febru... https://github.com/kragen/screenfuls is a collection of tiny, readable programs that do interesting things.

since by default, they don't support left recursion. The OMeta folks figured out how to cleanly support left recursion in PEGs, but you lose the linear-time guarantee.) One very appealing attribute of PEGs is that you can conveniently extend PEGs to support parameterized productions, which could be crucial in building up a library of general-purpose parsing productions that could reasonably be used to shorten the time to define new languages. k4st claims in http://news.ycombinator.com/item?id=2330672 that Pratt top-down operator-precedence parsers are also cleanly composable. I didn't know that, and it seems like a surprising claim, but I don't really understand Pratt parsers yet. Crock has written an excellent article on Pratt parsers as his Beautiful Code chapter, and his JSLint is written with one. I think this is the same text as his chapter: http://javascript.crockford.com/tdop/tdop.html Earley parsers can parse any context-free sentence in worst-case O(N³) time. Context-free grammars can, of course, be easily composed. Quoting Earley's abstract, "It has a time bound proportional to n³ (where n is the length of the string being parsed) in general; it has an n² bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars." John Aycock has written an Earley parser generator called SPARK which is included with Python, and is reportedly pretty efficient. He's advocated using it specifically because of the composability concern. http://pages.cpsc.ucalgary.ca/~aycock/spark/ Laurie Tratt just posted this other thing about parsing that's currently on the front page of HN; it's really excellent, and duplicates much of what I've written above: http://tratt.net/laurie/tech_articles/articles/parsing_the_s...