Built a toy lisp compiler. Despite being a toy project, it's still quite interesting imo. The interesting bit is it's small. 1500 LOC (Racket) and 50% is test. Also, since it's small and the compiler logically separates the compilation steps, it's pretty easy to understand what's going on.
The compiler does 4 steps to compile an expression.
E.g. not 5
will be written with the prefix notation (not 5)
.
And we write (not 5)
as (if 5 0 1)
in this example, because it's easier to explain to this way.
Side note: not
can be defined in terms of the primitive if
, and shipped in a runtime library.
The compilation stages will be:
- first compilation step
Simply wrap expression in a tag (L0: ...)
and literal in the datum tag (L0: datum ...)
(M0→L0 '(if 5 0 1)) ; -> '(L0: if (L0: datum 5) (L0: datum 0) (L0: datum 1))
- second compilation step
write the primitive if
as a function of 1 argument, 0 is the index into the argument list
(L0→L1 (M0→L0 '(if 5 0 1))) ; -> '(L1: if 0 (L1: datum 5) (L1: datum 0) (L1: datum 1))
- third compilation step
this is the more interesting step, this code basically looks like assembly
The not 5
expression is compiled to the code below, and when it runs, it does:
- set the name
result
to be5
- run
jump_false
, which jumps to labelelse_0
ifresult
is false - sets the name result to
1
(i.e. true) and jump to end_0 to finish the routine
; compiled code
(compiled:L2
'((L2: set_result 5)
(L2: jump_false else_0)
(L2: set_result 0)
(L2: jump end_0)
(L2: label else_0)
(L2: set_result 1)
(L2: label end_0))
'())