Show HN: A compiler and VM for a simple language, in 150 lines of code | Hacker News Reader

Show HN: A compiler and VM for a simple language, in 150 lines of code

gist.github.com

200 pointsp4bl045 comments

As another comment also alludes, there's probably quite a lot more work required before this could be called a complete compiler (without heavy qualification as to what it actually compiles, since the language of boolean expressions probably isn't something that most people would consider to be a programming language per se); that said, toy languages like this are a great way to explore some fundamental principles of programming language theory.

Boolean expressions have very trivial denotational semantics (since there's no recursion or state), so you could try formalising these in Coq (FRAP [1] and Software Foundations Vol. 2 [2] are both good places to learn more about this).

Next, you could write formal operational semantics for your VM, and then finally prove that your compiler is correct in a formal sense (i.e. the image of any well-formed input under the compiler operation has a terminating execution in the operational semantics that yields the same value as would be obtained by the execution of the input expression under the denotational semantics).

The last part would require implementing the compiler in Coq, but since you've written it in OCaml it probably wouldn't be very hard to port.

[1] : https://frap.csail.mit.edu/main

[2] : https://softwarefoundations.cis.upenn.edu/plf-current/toc.ht...

Edit: Having looked at your profile I now realise that you probably know all of this already, but it might be informative for anyone else reading :)

Coq is so much fun. It makes writing proofs feel like playing a video game.

I've just finished writing a Coq tutorial [1] that is aimed at programmers (rather than, say, computer scientists). It covers topics like programming with dependent types, writing proofs as data, universes & other type theory stuff, and extracting verified code—with exercises.

[1] https://github.com/stepchowfun/proofs/tree/main/proofs/Tutor...

For those wondering what language this is for before clicking on it: it's not much more than what I think would traditionally be called an expression evaluator, and very simple one at that --- it only recognises binary logic expressions, and the 150 lines doesn't include the parser or lexer either. Not a bad attempt for what is presumably a first try, but I think "complete compiler" is overselling it.

there's no type checking, which i'd say is a fairly integral part of a compiler...

but it does use a parser generator to generate a parser that constructs an ast and it then iterates that ast to generate a bytecode.

that's basically a compiler, even if the language is basic expressions.

B has no type checking either.

On the other hand, using a parser generator and not counting its output in the line count does seem like cheating.

> using a parser generator and not counting its output in the line count does seem like cheating

Yeah maybe I should count OCaml's standard library lines of code too. Maybe also count expanded macros and inlined functions at each call site? At which point should I stop? Are assembly language pseudo-instructions cheating too?

Common, don't be ridiculous.

I don’t see how, I would only count the input lines to the parser generator.

Type checking is a part of semantic analysis, which the author explicitly says isn’t present.

Even so, the language it is compiling has only one type, so it isn’t possible for a program to have type errors.

Just like in C++ one never need to check if a reference is null—it simply can’t be expressed in the language, thus preventing any errors of that kind, a single type prevents all kinds of type errors. One might argue that this is the most powerful way to do type checking. It simply isn’t possible to have an error.

fair enough. regardless i think it's a work of art and meets the definition of compiler in my mind. i hope that the author chooses to publish the rest of their course materials and does so in a language i understand. i expect they are/will be fantastic.

> there's no type checking, which i'd say is a fairly integral part of a compiler...

There are compilers for dynamically typed languages.

Hey there, author here :). The language is intentionally very simple indeed, because the goal is to showcase all indispensable steps of a complete compiler. I initially wrote it for my students as an introduction to my compiler class (for the very first session).

> would traditionally be called an expression evaluator

It is not an evaluator, evaluators are included (the different eval functions).

> the 150 lines doesn't include the parser or lexer either

This is just wrong:

    $ cat *.ml{,l,y} *.c | sed '/^\s*$/d' | wc -l
    149

and these 149 lines (okay, 169 if you count blank lines which are removed using sed in the count above) include the two `eval` and the `run` functions which are not actually part of the compiler but here for clarity (they help understanding how the successive intermediate representations of the boolean expressions work — without them the entire project is less than 130 lines).

> Not a bad attempt for what is presumably a first try

It's not ;). It is however targeted at beginner compsci students who have absolutely no idea how compilers are built yet :).

> but I think "complete compiler" is overselling it.

It does lexing & parsing to produce an AST of a boolean expression, then a traversal of this AST to transform it into a second intermediate representation (an AST of NAND-only expression), then compiles the expression into a list of instructions (and this paradigm shift is a big step that is tough to teach to some students, believe me ^^), and then emits the corresponding bytecode (which here is 1:1 with the imperative instructions), and then the VM interprets this bytecode. I don't think I'm overselling it :).

The only way it is not complete — and that's written in the README — is that it has absolutely no semantics analysis (there is only one type, and no names, so there is nothing to analyze ^^), but that is not mandatory to be called a compiler.

Then again, this is only the first hour of a semester long compiler class (which covers semantic analysis, don't worry) ;).

The only way it is not complete — and that's written in the README — is that it has absolutely no semantics analysis

I was referring to the complete lack of flow control. Could you compile the compiler with itself, for example?

Then again, this is only the first hour of a semester long compiler class

If you're taking a course, you might enjoy "leaping ahead" by studying C4 and C4x86. They are also VM-based, and self-compiling, yet still tiny. I think they really raised the bar on what a tiny-and-complete compiler is. (https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8746054)

> Could you compile the compiler with itself, for example?

That's only possible if you write the compiler in the language it compiles. By this account writing a Python compiler in something else than Python, for example in C, would make it incomplete? It doesn't make much sense.

> If you're taking a course (…)

You should read my post more carefully, I think.

> I was referring to the complete lack of flow control. Could you compile the compiler with itself, for example?

This is not a requirement for it to be a compiler.

> They are also VM-based, and self-compiling, yet still tiny. I think they really raised the bar on what a tiny-and-complete compiler is.

The purpose of OP's compiler is educational so this comparison makes no sense.

While it may not be "a requirement", considering that the very first compiler I'm aware of (Böhm's) was already written in itself, it's a fairly valid question why wouldn't you make an educational compiler with these properties.

> an educational compiler with these properties

Far from the only one, but here was mine: https://codewords.recurse.com/issues/seven/dragon-taming-wit...

One question: what is the binary size of the compiler?

The native binary produced by ocamlopt is 917KB, the bytecode produced by ocamlc is 156KB.

I must admit I didn't expect such "big" files.

Out of curiosity I tested to compile a completely empty OCaml program: the native binary is 365KB and the bytecode is 21KB.

I don’t know much about OCaml but one reason could be linking unnecessary libraries

Presumably you’re linking in a large GC etc?

I think people are getting hung up on the word "complete." This is a complete compiler in the sense that "hello world" is a complete (but minimal) program.

Yes exactly :), I meant that it does everything from lexing the source code to emitting bytecode instructions (and provides the VM to run this bytecode). It is not a part of a compiler, it is a tiny, simple, stupid, but complete, compiler.

I want to preface this comment with the fact that I'm terrible at teaching and know nothing about it, so it's entirely possible that your example compiler is much better for pedagogical purposes than the ones I'm going to suggest here. But I think they all have a significantly higher "power density", which at least from my point of view makes them more interesting and inspiring.

I think mostly people are complaining that the language it compiles isn't a programming language, so it omits a lot of things that compilers for programming languages have to handle. And so it feels a bit like much ado about nothing: because there are no variables, loops, or values beyond single-bit values, the program it compiles can only ever produce a constant, predetermined output, and that output can only ever be 1 or 0. So the compiler is just sort of a particularly 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.

As I wrote elsewhere, I use this tiny compiler as an introduction to the course, which goes into much more details and of course covers how to compile realistic programming languages (with multiple types of data, variables, conditional and loop control structures, functions, pointers, list and arbitrary structures, etc.) down to assembly code.

Thanks for all your interesting links :).

Oh, of course I didn't mean to imply that that was all you were teaching! I was just thinking that maybe a compiler that did something a little more impressive (for the effort required to understand it) might arouse more interest and provoke less No-True-Scotsman criticism. Though, honestly, stupid criticism is the vast majority of what HN is capable of, and you shouldn't take the uninformed criticism of HN commenters too seriously.

Of course the compilers you teach later on with variables, conditionals, loops, multiple types, pointers, etc., are more capable and thus more impressive. But presumably they also require even more effort to understand than the "tiny" compiler you're presenting in this gist.

I hope you find many things you enjoy in the links! Even if they aren't directly useful as pedagogical examples, they do demonstrate, for example, that a plain recursive-descent parser is already "two-pass" enough to handle assignment to variables, contra the statement in your gist, "In a more complex language (e.g., adding support for assignment to variables), we would need an additional front-end pass after the parser." Indeed, StoneKnifeForth is a single-pass compiler in less code than your tiny compiler that supports not only assignment to variables, but also arrays, I/O, conditionals, loops, defining and calling subroutines with arguments, pointers, ELF output, and i386 machine code generation with peephole optimization. And it's not because it's written in a more powerful language than OCaml; it's written in the profoundly substandard dialect of Forth that it implements, which lacks Forth's compile-time metaprogramming facilities and in which only one character is significant in identifiers.

I was wondering if maybe my memory of StoneKnifeForth was wrong and it wasn't actually 132 lines of code, because that sure sounds like a lot of functionality in 132 lines of code. It turns out it's 117 lines of code, not 132. (The build process builds a version with comments stripped out, called trimmed.tbf1, and verifies that it compiles identically, to find this out.)

So maybe you can learn some things from them that will enable you to write better compilers!

Oh, you should see the 128-line compiler OP unveils in the second hour of the class, now that students have the gist. And by the end of third hour...

I'd love to!

Sooo nice :-) It looks like small cute kitten to me, sorry.

Don't be sorry for this nice comment! I totally understand the cuteness feeling ^_^.

If you like The Arts, and remarkable results, the website of Pablo ( https://pablo.rauzy.name/ ) is a thing to behold.

Where can I learn more about mll and mly files? I've hand-rolled parsers and it's always my least favorite part of toy languages.

https://v2.ocaml.org/manual/lexyacc.html

Search for ocamllex and ocamlyacc. Also Menhir.

So weird, within the last hour I was wondering why I never see regular, old, lex and yacc around anymore, and then I came across this, which made realize it's probably because they generate C. Funny. I guess these output OCaml?

Yes, they do. Lex and yacc equivalent tools are available for many languages.

Examples :

- Python: https://ply.readthedocs.io/ (I already used it in a very small project, again for my students, here is an example of how it works: https://gist.github.com/p4bl0-/f5ed1e60fdc5e76a2d321bc8708a7...)

- Racket: https://docs.racket-lang.org/parser-tools/ (it's really great, I previously used Racket for my compiler course but I've switched to OCaml a few years back, because Racket parser tools don't go well with Typed Racket).

k. so this is an OCaml parser for a toy language?

I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days.

I just feel like I need to learn another language to learn the language to be efficient.

That's not really a criticism of the language, but it feels a little code-golfy.

Is there a use for these tools other than writing yet-another-language?

edit:I think ocaml actually can run perl5 modules, if I remember correctly.

> k. so this is an OCaml parser for a toy language?

The parser consists only of the first two files (and it is not even for a "toy language", it is really just for boolean expressions, a toy language could have been a lot more complex!).

> I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days.

> I just feel like I need to learn another language to learn the language to be efficient.

So you don't know OCaml or it's parsing tools and don't want to learn about either, that is your choice but has nothing to do with this project :).

> Is there a use for these tools other than writing yet-another-language?

These tools are made for lexing and parsing. They work as a DSL because it's easier this way. They could have other usages but that's not their point. If you never want to parse anything you may never need them. And that's fine, you can just move along.

Reply on news.ycombinator.com