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?
- 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).
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.
> 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?
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.
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) ;).
> 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.
It is, but I think he is understandably upset because people are engaging with you in good faith but you aren’t reading or acknowledging what they write. Sometimes, it’s good to just take a step back and start with something like “Oops, I missed you are a professor and this is a teaching tool. Disregard that part. I do think, however…”
Otherwise, you’re bound to annoy someone even if you think you are technically contributing.
The whole point is that I absolutely don't care who or what he is; everyone can learn from the C4 family, and if anything, it would be highly suited to someone teaching compilers.
Otherwise, you’re bound to annoy someone
I see the title has been changed now, but I was certainly annoyed when it was advertised here as a "complete" compiler.
How studying something super optimized to be small is more practical than learning something step by step?
I am not saying studying those tiny compilers is not useful, just that they are not a good starting point for most people. First you need to learn the basics then you can learn (and appreciate) those tiny compilers.
It's because everything can be seen at once. The feeling of "that's it?" when you realise the underlying simplicity. Most people think compilers must be incomprehensibly complex. Yet the truth is far from that.
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.
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.
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.
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.
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.
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!
> 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.
51 comments
[ 4.2 ms ] story [ 127 ms ] threadExamples :
- 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).
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.
On the other hand, 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.
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.
There are compilers for dynamically typed languages.
> 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:
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) ;).
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)
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.
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.
Otherwise, you’re bound to annoy someone even if you think you are technically contributing.
Otherwise, you’re bound to annoy someone
I see the title has been changed now, but I was certainly annoyed when it was advertised here as a "complete" compiler.
I am not saying studying those tiny compilers is not useful, just that they are not a good starting point for most people. First you need to learn the basics then you can learn (and appreciate) those tiny compilers.
Far from the only one, but here was mine: https://codewords.recurse.com/issues/seven/dragon-taming-wit...
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.
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 :)
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...
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):
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:
Thanks for all your interesting links :).
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!
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.
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.