knazarov.com/content/posts/first_real_program_compiled_with_valeri/note.md

X-Date: 2024-08-23T23:49:16Z
X-Note-Id: 175bdac4-8655-4b75-8205-f44b7311daa0
Subject: First real program compiled with Valeri
X-Slug: first_real_program_compiled_with_valeri

I've reached my first significant milestone with [Valeri](https://git.knazarov.com/knazarov/valeri).
It can now compile something useful to bytecode and then execute it in the virtual machine.

As an example, I've implemented a simple recursive factorial function:

```
(fn fact (n)
    (if (<= n 0)
        1
        (* n (fact (- n 1)))))

(fact 12)
```

If you save this code as `factorial.vli`, you can then run it with `./vli factorial.vli`,
and it will give you `479001600`, as you would expect.

This may not seem impressive at a first glance, but to compile this example the compiler has to support:

- modules (at least top-level)
- functions
- recursion
- lexical scope
- globals
- constants
- arithmetic

Most importantly, this is not a recursive AST evaluator like how many people implement their first Lisp.
This in fact compiles into a bytecode which is then executed on a virtual machine. It means that the performance
is bad (due to lack of optimizations), but not completely abysmal.

The process of compilation is now 2-step:

- Read the source code into "AST" (actually the S-expression form that is a list)
- Recursively step through the AST and emit the bytecode for known special forms
  - As we walk the tree, keep a linked list of lexical context (to find variable bindings)

To emit the bytecode, I'm following an approach that is close in spirit to the
[Incremental Approach to Compiler Construction paper](http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf).
With the exception that the paper uses stack and an accumulator register, and my implementation is
register-based like Lua, see [Lua 5.0 paper](https://www.lua.org/doc/jucs05.pdf) for reference.

I'm very happy about the progress, but also am mindful of the fact that this is only the beginning.
For this compiler to be really useful, it should give decent error reporting (both during the compilation
phase and runtime phase). And this is where the real struggle will begin.