Typed Python Subset Compiler

This repository is a small, standalone compiler for a typed subset of Python. It parses source with Python's standard ast module, lowers it through typed intermediate forms, allocates x86-64 registers, and emits GNU/AT&T assembly for 64-bit Linux using the System V AMD64 ABI.

It is the cleaned, self-contained form of the latest implementation that was previously under compiler_fun/to_publish. Older compiler stages, experiments, generated binaries, IDE files, duplicate code, and vendored packages have been removed.

Supported language

Programs use Python syntax, but only this subset is accepted:

• Signed 64-bit integer and Boolean literals, variables, and assignment.
• Integer +, -, unary -, and signed comparisons.
• not, binary and/or, ==, !=, <, <=, >, and >=.
• if/else, conditional expressions, and while without else.
• input_int() and single-integer print(value).
• Mutable, fixed heterogeneous tuples of at most 57 fields, including nested tuples, len, and non-negative literal indexing/assignment.
• Typed top-level functions, forward calls, recursion, optimized tail calls, named function values, and higher-order calls using Callable annotations.
• Up to 62 function parameters. With more than six, the compiler passes the first five normally and packs parameter six onward into a tuple in the sixth argument register.
• int, bool, tuple[...], Callable[[...], ...], and None return annotations. A -> None function is a procedure and cannot return a value.

Every function parameter and return type must be annotated. Function definitions must appear before top-level executable statements. The names input_int, print, and len are reserved for builtins.

Integers use two's-complement 64-bit operations: input, output, and comparisons are signed, and arithmetic wraps at 64 bits. Integer literals themselves must fit the signed 64-bit range. Tuple is, ==, and != compare tuple identity, not tuple contents. print deliberately adds no language-level newline.

Unsupported Python includes lists, dictionaries, classes, imports, lambdas/closures, nested functions, multiplication/division, for, while ... else, break, continue, chained comparisons, Boolean operations with more than two operands in one expression, negative/dynamic indexes, keyword/default/variadic arguments, and arbitrary library calls. None is a return annotation, not a runtime value.

Compilation pipeline

Compiler.compile(source) performs these stages:

1. Parse with ast.parse, validate the subset, and desugar short-circuit Boolean operations.
2. Type-check source and create collision-proof internal function symbols.
3. Lower high-arity signatures/calls to the six-register System V convention.
4. Expose tuple allocation, heap checks, and garbage-collector calls.
5. Remove complex operands and lower structured control flow to basic blocks.
6. Select GNU/AT&T x86-64 instructions.
7. Compute liveness and interference, then allocate registers.
8. Spill ordinary values to stack frames and live tuple pointers to %r15's shadow root stack.
9. Patch instructions that x86-64 cannot encode directly, then add prologues, epilogues, and tail jumps.

The C runtime provides signed integer I/O, an initially 16 KiB heap that grows as needed, and Cheney semispace collection that preserves nested and aliased tuple references. The generated process reserves an 8 MiB shadow root stack.

Repository structure

.
|-- compiler.py                    compiler passes and register allocator
|-- type_checker.py                source and control-IR type checking
|-- ir.py                          types and intermediate-representation nodes
|-- x86.py                         x86 nodes and GNU assembly rendering
|-- graph.py                       graph and dataflow support
|-- runtime.c                      integer I/O and tuple garbage collector
|-- main.py                        editable compile -> build -> run example
|-- requirements.txt                Python dependency manifest (stdlib only)
|-- tests/
|   |-- test_compiler.py
|   |-- test_type_checker.py
|   |-- test_semantic_regressions.py
|   `-- test_backend_regressions.py
|-- .gitignore
`-- README.md

There are no third-party Python dependencies. For conventional environment setup, the empty dependency manifest can still be installed safely:

python -m pip install -r requirements.txt

Requirements and setup

• Python 3.10 or newer.
• An x86-64 Linux environment.
• GCC, GNU assembler/binutils, and standard C development files.

On Debian or Ubuntu:

sudo apt update
sudo apt install python3 build-essential

No Python package installation is needed. Clone or copy the repository and run commands from its root.

The emitted assembly is ELF/System V code. It is not compatible with the native Windows x64 ABI or native macOS toolchain.

Windows with WSL2

Install Ubuntu under WSL2, then install build-essential inside it:

wsl --install -d Ubuntu

sudo apt update
sudo apt install build-essential

Windows Python can run main.py; it routes GCC and the resulting ELF program through WSL automatically. The default distribution is Ubuntu. Override it when needed:

$env:COMPILER_WSL_DISTRO = "Ubuntu-26.04"
python main.py

Run and edit the example

Run:

python main.py

Edit the SOURCE triple-quoted string near the top of main.py to change the program. If it calls input_int(), put whitespace-separated input in PROGRAM_INPUT.

The workflow:

1. compiles SOURCE;
2. prints and saves assembly as build/program.s;
3. compiles runtime.c and assembles the program;
4. links build/program;
5. runs it; and
6. prints captured program output under a separate heading.

Compiler, C compiler, assembler, linker, timeout, and runtime failures report their stage, command, and captured diagnostics. Tool stages time out after 30 seconds and the example program after 10 seconds.

Source to assembly to output

Source:

def add(left: int, right: int) -> int:
    return left + right

print(add(20, 22))

Function names are deliberately mangled to avoid collisions. A representative part of the generated assembly is:

.L.compiler.function.0start:
    movq %rdi, %rcx
    movq %rsi, %rbx
    movq %rcx, %rax
    addq %rbx, %rax
    jmp .L.compiler.function.0conclusion

Program output:

42

Using the compiler directly

The Python API returns a printable assembly program:

from compiler import Compiler

source = "print(40 + 2)\n"
assembly = str(Compiler().compile(source))
with open("program.s", "w", encoding="utf-8") as output:
    output.write(assembly)

Build manually on x86-64 Linux:

gcc -std=c11 -O2 -m64 -c runtime.c -o runtime.o
gcc -m64 -c program.s -o program.o
gcc -m64 program.o runtime.o -o program
./program

Tests

Run the complete suite:

python -m unittest discover -v

It covers the source type system, arithmetic/control flow, tuples and collection, recursion/tail calls, higher-order and high-arity functions, evaluation order, compiler reuse, diagnostics, ABI preservation, and full source-to-native execution. Native cases are skipped with an explanatory message when a compatible Linux/WSL x86-64 GCC toolchain is unavailable.