cajulang

How Caju works

From a .caju file to a running program: the stages of the compiler, how values live in memory, the garbage collector, calls and panics, and how the compiler ends up running in your browser. Everything shown here comes from the real compiler.

From source to executable

The compiler is a chain of stages, each one written in Caju (compiler/*.caju). Follow a small program through them: pick a stage to see what it produces.

02

Lexer

lexer.caju cuts the text into tokens: keywords, names, operators, numbers, texts. Each token keeps its line and column, which is how every error later points at the right place. Line breaks become NEWLINE tokens: they end statements.

The sample program · main.caju
fn add(a: int, b: int) -> int {
  return a + b
}
 
print(add(2, 3))
What this stage produces: tokens
  1. fnKEYWORD 1:1
  2. addNAME 1:4
  3. (OP 1:7
  4. aNAME 1:8
  5. :OP 1:9
  6. intNAME 1:11
  7. ,OP 1:14
  8. bNAME 1:16
  9. :OP 1:17
  10. intNAME 1:19
  11. )OP 1:22
  12. ->OP 1:24
  13. intNAME 1:27
  14. {OP 1:31
  15. ↵NEWLINE 1:32
  16. returnKEYWORD 2:3
  17. aNAME 2:10
  18. +OP 2:12
  19. bNAME 2:14
  20. ↵NEWLINE 2:15
  21. }OP 3:1
  22. ↵NEWLINE 3:2
  23. printNAME 5:1
  24. (OP 5:6
  25. addNAME 5:7
  26. (OP 5:10
  27. 2NUMBER 5:11
  28. ,OP 5:12
  29. 3NUMBER 5:14
  30. )OP 5:15
  31. )OP 5:16
  32. ↵NEWLINE 5:17
  33. ∎EOF 6:1

A compiler that compiles itself

The Caju compiler is written in Caju. To get the first one, a small compiler written in JavaScript is used once; after that, the compiler compiles its own source.

  1. 1

    Stage 0

    bootstrap/*.js: the original compiler, in JavaScript, run by Node.

  2. 2

    Stage 1

    Stage 0 compiles compiler/main.caju: a native caju, made by the JavaScript compiler.

  3. 3

    Stage 2

    Stage 1 compiles the same source: now a compiler made by a Caju compiler.

  4. 4

    Stage 3

    Stage 2 compiles it again. Stage 2 and stage 3 must be identical byte for byte: the compiler reproduces itself.

  5. 5

    caju.wasm

    With --target wasm, the compiler compiles itself to WebAssembly; caju.wasm then compiles itself to the same bytes too.

cmp build/caju2 build/caju3 && echo okstage 2 == stage 3

Every change to the compiler is checked this way, besides the test suite: if stage 2 and stage 3 differ, something in the compiler changed the meaning of the compiler itself.

Values in memory

Every value fits in one 64-bit word. Numbers and booleans are the word itself; everything else is a pointer to an object made by the runtime.

s := "caju"
s
●
str
len
4
byte
c
byte
a
byte
j
byte
u
NUL
0

A pointer to [length][UTF-8 bytes][0]. Texts never change: + makes a new one, and the same literal is shared by the whole program.

The garbage collector

The runtime allocates objects in 64 KB pages and collects them with mark and sweep, written in Caju (rt/gc.caju). Try it: the roots are the program's stack and globals.

Each object is reachable from a root or not. Press Mark.

RootsHeapstack: liststack: userglobal: cache[]intarray*User"Ana"mapmap"old"structclosure
  • not yet visited
  • marked (reachable)
  • garbage
  • freed

The collector is conservative: any word on the stack or in an object that looks like a pointer into an object keeps it alive. That is why a pointer must never live only in a register during a call, and why the WebAssembly version keeps every value that must survive a call on a stack in memory. A collection starts when the memory allocated since the last one passes what survived it (at least 8 MB).

Calls, defer and panic

Every call pushes its arguments on the stack and every function keeps its locals in a frame. defer, panic and recover are part of the runtime.

↑ caller
locals
sum
list ●
arguments
a = 2
b = 3
frame ($fp) →
↓ callee
locals
x
y ●
temporaries
t ●
stack pointer ($sp) →

A call

The caller pushes the arguments (and the closure, for a function value) and calls; the callee finds argument i of n at a fixed offset and makes room for its locals. Results 2, 3... travel in g.ret.

The depth limit

A counter of calls left starts at 10,000 and each call takes one: the 10,001st nested call stops with "Too much recursion" instead of crashing.

defer

A function with defer links a record into a list (rt_dtop); each defer adds a node with the function and its already evaluated arguments. They run from last to first when the function returns.

panic and recover

panic runs the deferred calls from the newest record to the oldest. If one of them calls recover(), execution jumps back to the function that deferred it, which returns normally. In WebAssembly that jump is a wasm exception.

Caju in your browser

The playground runs the real compiler, compiled to WebAssembly, without a server.

  1. 1

    The release

    Each GitHub release has caju-wasm.tar.gz: the compiler as caju.wasm, the standard library and the runtime as text, and a small JavaScript host.

  2. 2

    The worker

    The page starts a Web Worker that loads caju.wasm and an in-memory file system with the library.

  3. 3

    Compile

    Your files go into that file system and caju build --target wasm runs inside caju.wasm, as it would on Linux: the host answers its system calls (open, read, write...).

  4. 4

    Run

    The new module runs in the same worker; what it writes comes back to the page as it is written. Stop terminates the worker.

Playground →

Around the compiler

caju test

Finds *_test.caju files and runs them: describe, it and expect from std/testing.

caju pkg

Packages are GitHub repositories; minimal version selection and a caju.lock with SHA-256 hashes.

caju mcp

A Model Context Protocol server: AI assistants check, run and test Caju code with structured results.