TinyCompiler: A compiler in a week-end

Re:TinyCompiler: A compiler in a week-end by RossBencina on Thursday February 20, 2025 @07:32PM (#43122562)

> lexer + parser + treewalk interpreter

If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter.

I would expect:

lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C

where X includes

  - definition of an intermediate representation (IR)
  - lowering AST to IR
  - static analysis
  - improvers/optimisation passes (at least some simple stuff)
  - code gen including register allocation

This can still be a simple "complicated" program, but there's more to a compiler than an AST interpreter.

EDIT: I notice that the author of the original article has also started work on an optimizing compiler: https://ssloy.github.io/tinyoptimizer/

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by sieve on Thursday February 20, 2025 @07:38PM (#43122623)

> If all you do is construct an AST and interpret it it's not really a compiler is it.

What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-)

> where X includes

I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compile down to C/JS. Many compilers use LLVM as their backend. By your definition, none of them use (or are) compilers.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by RossBencina on Thursday February 20, 2025 @08:12PM (#43122888)

> Would you consider that to be a compiler? :-)

:) No. Under my definition there needs to be some non-trivial transformation into or out of an intermediate and/or target representation (either syntax-directed directly out of the parser, or from a materialized AST). Personally I would argue that even if you trivially "compiled" to sequential bytecode, if the bytecode is then interpreted it is hard to argue that you have created a compiler (the pre-JIT cpython interpreter is still an interpreter, even though it includes a bytecode representation). But I can see that this point can be argued, and historically a school exercise of writing a Pascal-to-pcode converter would be called a compiler, so sure, you can take that perspective if you like. Just don't get confused about whether you are learning to build a compiler (definition 1) or a compiler (definition 2).

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by sieve on Thursday February 20, 2025 @08:24PM (#43122964)

I have written all kinds of compilers, interpreters and vms over the last 15 years. A couple of them for work. The rest for fun. Some vms used RC, others did mark-and-sweep GC. Some vms even did JIT. A lot of them were simple treewalk interpreters because the point was to play with the syntax of the language.

Based on that experience, I would say your definition is more academic than realworldly as javac (or any compiler targeting the JVM) is not a real compiler according to it.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by RossBencina on Thursday February 20, 2025 @09:42PM (#43123399)

> javac (or any compiler targeting the JVM) is not a real compiler according to it

I think it depends on how you interpret my "non-trivial transformation into or out of an intermediate and/or target representation". For example if javac involves IR, SSA based analysis and transformation (which I assume it does) then that would be a non-trivial transformation and I'd call it a compiler. If on the other hand it was a direct syntax-directed transformation to java byte code then I'd call it a translator not a compiler. But I'm not claiming any authority over definitions here. Words aren't my strong suit.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by sieve on Thursday February 20, 2025 @10:05PM (#43123541)

> if javac involves IR, SSA based analysis and transformation (which I assume it does)

https://github.com/openjdk/jdk/blob/master/src/jdk.compiler/...

I am fairly certain that it does not. The JVM is a stack-machine.

I wrote a compiler for a simple programming language that compiled down to JVM bytecode for a project in the early 2010s. Its output for test programs was as fast as the comparative Java ones because they were fairly similar at the bytecode level.

The HotSpot JVM is where all the optimization effort is applied.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by vlovich123 on Thursday February 20, 2025 @11:02PM (#43123888)

I believe there’s some trivial optimization done by the frontend (constant folding, simplifying string concatenation, converting switch statements to lookup tables) but I think they’d agree with you that javac doesn’t really fit their definition of a compiler and that the HotSpot JIT is the true compiler based on how they talked about the Python interpreter pre-JIT.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by milesrout on Thursday February 20, 2025 @09:55PM (#43123479)

I strongly disagree with your definition. A naive syntax-directed translation to bytecode or machine code is still compilation. Lots of production compilers do exactly that eg Wirthian compilers.

[ Parent | on HN ]

Re:TinyCompiler: A compiler in a week-end by Tomte on Friday February 21, 2025 @02:09AM (#43124888)

javac does very, very few things. It intentionally emits byte code close to the source program. The HotSpot compiler in the JVM does the heavy lifting.

[ Parent | on HN ]