> 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
> 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.
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.
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.