How I Made My Language 130 Faster by Transpiling to Python AST

In my pursuit to enhance the speed of SkyForge, a programming language inspired by Russian syntax, I embarked on a journey to transpile it to Python's Abstract Syntax Tree (AST). Initially, I had written a tree-walking interpreter in Python, which proved to be significantly slower than the standard CPython interpreter. Simple computations, such as calculating the 32nd Fibonacci number, took over a minute, causing embarrassment considering the language's claim to be easier than Python.

After exploring various options, including rewriting in C, using Cython or Nuitka, or developing a full compiler, I decided to take a different approach: transpiling to Python's AST. This method aligned with my expectations and yielded impressive results. Herein lies the story of how I achieved this feat.

Python's standard library provides an `ast` module, allowing the creation of a Python AST manually, which can then be compiled into native CPython bytecode using the `compile()` function. This bytecode executes at C speed, bypassing the interpreter overhead. Rather than traversing my own AST and evaluating each node, I opted to translate my AST into Python's AST and harness CPython's capabilities.

The transpilation pipeline consists of three main components: Lexer, Parser, and Transpiler. The Lexer breaks down the input source code into tokens, the Parser constructs an AST from these tokens, and the Transpiler converts the generated AST into Python's AST, which is subsequently compiled into bytecode. This entire process can be encapsulated within approximately 600 lines of Python code, requiring no external dependencies. The pipeline can be visualized as follows:

1. `def compile_skf(source : str, filename : str):`

2. `tokens = Lexer(source).tokenize()`

3. `program = Parser(tokens).parse()`

4. `py_ast = transpile(program)`

5. `return compile(py_ast, filename, "exec")`

To illustrate, consider the following SkyForge function:

```python

функция сумма(a, b) {

вернуть a + b

}

```

The parser generates a `FunctionDef` node with the function name `сумма`, parameters `(a, b)`, and a body containing a `Return` node with a `BinOp` node inside. The transpiler's `func_def` method converts this structure into the following Python AST:

```python

ast.FunctionDef(

name = "сумма",

args = ast.arguments(

posonlyargs = [],

args = [ast.arg(arg = "a"), ast.arg(arg = "b")],

kwonlyargs = [],

kw_defaults = [],

defaults = [],

vararg = None,

kwarg = None,

),

body = [ast.Return(value = ast.BinOp(left = ast.Name(id = "a", ctx = ast.Load()), op = ast.Add(), right = ast.Name(id = "b", ctx = ast.Load())))],

decorator_list = [],

returns = None,

)

```

While the process of creating a method for each AST node type may be tedious, it is ultimately a mechanical task. Once this foundation is established, the transpiler can be deployed effectively. However, there were a few challenges encountered along the way.

Firstly, Python 3.12 and later versions strictly validate AST positions. Older Python versions were more forgiving, filling in missing line number and end line number values. Starting from 3.12, compile() enforces that `end_lineno` must be greater than or equal to `lineno`, and a child's range must remain within the parent's range. Ignoring this constraint led to frequent `ValueError` exceptions, such as:

`ValueError: AST node line range (2, 1) is not valid`

To resolve this issue, all positions within the AST were set to default values (lineno = 1, col_offset = 0, end_lineno = 1, end_col_offset = 0) before compilation. This approach, although resulting in inaccurate error positions, ensured that the code ran without error. Although not ideal for a transpiler requiring precise error reporting, it proved to be a trade-off worth making.

Secondly, the `ast.Compare` node, which represents comparisons, differs from the `ast.BinOp` node, which handles binary operations. A common mistake was to equate comparisons with binary operations using a single `BinOp` constructor. This oversight resulted in a `TypeError`, as the compiler rejected comparisons as invalid operator types. By differentiating between `ast.Compare` and `ast.BinOp`, the transpiler could correctly convert comparisons into their respective AST representations.

Throughout the transpilation process, careful attention to Python's evolving AST validation rules and the distinction between various AST node types proved crucial. By addressing these challenges head-on, I successfully transpiled SkyForge to Python's AST, achieving a 130-fold speed improvement compared to the original Python interpreter.