首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

实践贴:如何编写一个简单的Python编译器

本文最初发表在 Medium 博客,经原作者 Max Gorynski 授权,InfoQ 中文站翻译并分享。

在本文中,我们将用Python编写一个Python到C的编译器。这一点特别容易做到,因为Python有一个内置的解析器库,并且许多CPython内部构件对编写扩展程序来说都是公开的

到本文的最后,通过几百行Python代码,我们将能够编译并运行以下程序:

代码语言:javascript
复制
$ cat tests/recursive_fib.py
def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

def main():
    print(fib(40))
$ python3 pyc tests/recursive_fib.py
$ ./bin/a.out
102334155

本文实现了一个非常小的Python子集,甚至完全放弃了管理内存的尝试,因为我无法理解手动引用计数。也许有一天我能找到一种方法来实现简单GC的交换,像Boehm那样。

这个项目的源代码可以在Github上找到。

依赖

我们需要Python3、GCC、libpython3和clang-format。

在基于Fedora 的系统上,执行命令如下:

代码语言:javascript
复制
 $ sudo dnf install gcc python3-devel clang-format python3

在基于 Debian 的系统上,则需执行如下命名:

代码语言:javascript
复制
$ sudo apt install gcc python3-dev clang-format python3

该程序在 Windows、Mac、FreeBSD 等系统上可能也能正常运行,但是我还没有测试过(或提供自定义的编译器指令)。欢迎大家进行 PR!

手写的第一遍

在进入编译器之前,让我们用 C 语言使用 libpython 手工编写一个斐波纳契数列(fibonacci)。

正如 Python 嵌入式指南所描述的那样,我们需要包含 libpython 并在main.c中初始化它:

代码语言:javascript
复制
#define PY_SSIZE_T_CLEAN
#include <Python.h>
int main(int argc, char *argv[]) {
  Py_Initialize();
  return 0;
}

为了针对 libpython 进行编译,我们将在python3-devel中安装 python3-config ,并使用它来告诉我们编译过程中的每一步应该输入什么内容。

代码语言:javascript
复制
$ gcc -c -o main.o $(python3-config --cflags) main.c
$ gcc $(python3-config --ldflags) main.o
$ ./a.out; echo $?
0

太酷了!现在,我们考虑翻译斐波纳契数列的实现,我们希望尽可能长时间地将所有内容作为 Python 对象进行保留。这意味着需要在所有函数之间传递和接收 PyObject* ,并将所有 C 的整数转换为 PyLong* (其为PyObject*的“子类型”)。可以想象在你对其进行操作之前,Python 中的所有内容都是一个object

有关 Python 中对象的更多信息,请查看 Python 文档中的“数据模型”页面。

要将一个 C 的整数映射到一个PyLong*,我们使用 PyLong_FromLong 。反向映射,我们使用 PyLong_AsLong

要比较两个PyObject*,我们可以使用 PyObject_RichCompareBool ,它可以在不考虑参数类型的情况对这两个参数进行比较。如果没有这个辅助函数,我们将不得不编写复杂的检查来确保两边相同,如果相同,则将它们解包为它们的基础 C 值并比较 C 值。

我们可以使用 PyNumber_Add PyNumber_Subtract 来进行基本的算术运算,还有许多类似的辅助函数可供我们进行后续操作。

现在我们可以编写翻译程序了:

代码语言:javascript
复制
#define PY_SSIZE_T_CLEAN
#include <Python.h>
PyObject* fib(PyObject* n) {
  PyObject* zero = PyLong_FromLong(0);
  PyObject* one = PyLong_FromLong(1);
  if (PyObject_RichCompareBool(n, zero, Py_EQ) || PyObject_RichCompareBool(n, one, Py_EQ)) {
    return n;
  }
  PyObject* left = fib(PyNumber_Subtract(n, one));
  PyObject* two = PyLong_FromLong(2);
  PyObject* right = fib(PyNumber_Subtract(n, two));
  return PyNumber_Add(left, right);
}
int main(int argc, char *argv[]) {
  Py_Initialize();
  PyObject* res = fib(PyLong_FromLong(7)); // Should be 13
  return PyLong_AsLong(res);
}

编译并运行它:

代码语言:javascript
复制
$ gcc -c -o main.o $(python3-config --cflags) main.c
$ gcc $(python3-config --ldflags) main.o
$ ./a.out; echo $?
13

非常棒!但是我们在某个地方作弊了。我们假设fib函数的输入是一个整数,并且将这个假设传播到了所有编写了PyNumber_ *操作的地方。当我们编写编译器时,在调用数字辅助函数之前,需要检查两个参数是否都是整数,否则可能需要调用字符串连接辅助函数或其他完全相同的函数。

编译器架构

我们将代码分为四个主要部分:

  1. libpyc.c:生成代码的辅助函数
  2. pyc/context.py:作用域和在内存中编码的实用程序
  3. pyc/codegen.py:从 Python AST 生成 C 代码
  4. pyc/__main__.py:启动入口(entrypoint)

当我使用现有的解析器编写新的编译器时,我几乎总是从启动入口和代码生成器开始,这样我就可以研究 AST 了。但是,如果我们先从实用程序开始,那么解释代码是最容易的。

我们还需要一个空的pyc/__init__.py

libpyc.c

这个 C 文件中将包含三个辅助函数,用于进行安全地加法、减法和打印操作。它将被连接到生成的 C 文件的顶部。目前,我们仅支持整数,但是此结构为以后支持更多类型打下了基础。

在调用特定于数字的方法之前,我们将使用 PyLong_Check

代码语言:javascript
复制
#define PY_SSIZE_T_CLEAN
#include <Python.h>
inline PyObject* PYC_Add(PyObject* l, PyObject* r) {
  // TODO: allow __add__ override
  // Includes ints and bools
  if (PyLong_Check(l) && PyLong_Check(r)) {
    return PyNumber_Add(l, r);
  }
  // TODO: handle str, etc.
  // TODO: throw exception
  return NULL;
}
inline PyObject* PYC_Sub(PyObject* l, PyObject* r) {
  // TODO: allow __add__ override
  // Includes ints and bools
  if (PyLong_Check(l) && PyLong_Check(r)) {
    return PyNumber_Subtract(l, r);
  }
  // TODO: handle str, etc.
  // TODO: throw exception
  return NULL;
}
inline PyObject* PYC_Print(PyObject* o) {
  PyObject_Print(o, stdout, Py_PRINT_RAW);
  printf("\n");
  return Py_None;
}

就是这样!我们可以在 Python 中将它们生成为字符串,但这样做会很麻烦。通过使用一个专用的 C 文件,我们可以利用语法突出显示功能,因为这个文件只是 C 代码。并且由于我们已将所有函数标记为内联函数(inline),因此在 Python 中不将这些函数作为字符串嵌入是没有任何运行时成本的。

pyc/context.py

该文件将包含一个Context类,用于管理作用域中的标识符,并将其代理给一个包含了编写 C 代码行辅助函数的Writer类。

我们将在Context中拥有Writer类的两个实例,这样我们就可以写入主体(或当前 / 主要)区域和初始化区域。

如果有任何变量声明在了顶层,则必须使用初始化区域。我们不能在函数外用 C 语言初始化这些变量,因为每个PyObject*都必须在调用Py_Initialize之后创建。在进入编译后的 Pythonmain函数之前,这一部分将被写入 C 的main函数中。

代码语言:javascript
复制
import copy

class Writer():
    content = ""
    def write(self, exp: str, indent: int = 0):
        self.content += ("  " * indent) + exp
    def writeln(self, stmt: str, indent: int = 0):
        self.write(stmt + "\n", indent)
    def write_statement(self, stmt: str, indent: int = 0):
        self.writeln(stmt + ";", indent)

class Context():
    initializations = Writer()
    body = Writer()
    indentation = 0
    scope = 0
    ret = None
    namings = {}
    counter = -1
    def __getattr__(self, name: str) -> object:
        # Helpers to avoid passing in self.indentation every time
        outputs = [initializations", "body"]
        for output in outputs:
            if name.startswith(output):
                return lambda s, i=None: getattr(getattr(self, output), name[len(output)+1:])(s, i if i is not None else self.indentation)
        return object.__getattr__(self, name)
    def get_local(self, source_name: str) -> dict:
        return self.namings[source_name]
    def register_global(self, name: str, loc: str):
        self.namings[name] = {
            "name": loc,
            "scope": 0,
        }
    def register_local(self, local: str = "tmp") -> str:
        self.counter += 1
        self.namings[local] = {
            "name": f"{local}_{self.counter}",
            # naming dictionary is copied, so we need to capture scope
            # at declaration
            "scope": self.scope,
        }
        return self.namings[local]["name"]
    def copy(self):
        new = copy.copy(self)
        # For some reason copy.deepcopy doesn't do this
        new.namings = dict(new.namings)
        return new
    def at_toplevel(self):
        return self.scope == 0

这些都是很无聊的样板代码。我们继续吧。

pyc/main.py

启动入口(entrypoint)负责读取源代码、解析源代码、调用代码生成器、将源代码写入 C 文件并进行编译。

首先,读取并解析源代码:

代码语言:javascript
复制
import ast
import os
import subprocess
import shutil
import sys
from context import Context
from codegen import generate
BUILTINS = {
    "print": "PYC_Print",
}

def main():
    target = sys.argv[1]
    with open(target) as f:
        source = f.read()
    tree = ast.parse(source, target)

然后,我们将libpyc.c写入主体部分,注册内建函数,并运行代码生成器:

代码语言:javascript
复制
...
def main()
    ...
    ctx = Context()
    with open("libpyc.c") as f:
        ctx.body_write(f.read() + "\n")
    for builtin, fn in BUILTINS.items():
        ctx.register_global(builtin, fn)
    generate(ctx, tree)

接下来,我们创建一个干净的输出目录,并用生成的代码编写main.cmain函数来初始化 Python 和所有的全局变量:

代码语言:javascript
复制
...
def main():
   ...
    # Create and move to working directory
    outdir = "bin"
    shutil.rmtree(outdir, ignore_errors=True)
    os.mkdir(outdir)
    os.chdir(outdir)
    with open("main.c", "w") as f:
        f.write(ctx.body.content)
        main = ctx.namings.get("main")["name"]
        f.write(f"""int main(int argc, char *argv[]) {{
  Py_Initialize();
  // Initialize globals, if any.
{ctx.initializations.content}
  PyObject* r = {main}();
  return PyLong_AsLong(r);
}}""")

最后,我们对生成的 C 代码运行clang-formatgcc

代码语言:javascript
复制
...
def main():
    ...
    subprocess.run(["clang-format", "-i", "main.c"])
    cflags_raw = subprocess.check_output(["python3-config", "--cflags"])
    cflags = [f.strip() for f in cflags_raw.decode().split(" ") if f.strip()]
    cmd = ["gcc", "-c", "-o", "main.o"] + cflags + ["main.c"]
    subprocess.run(cmd)
    ldflags_raw = subprocess.check_output(["python3-config", "--ldflags"])
    ldflags = [f.strip() for f in ldflags_raw.decode().split(" ") if f.strip()]
    cmd = ["gcc"] + ldflags + ["main.o"]
    subprocess.run(cmd)

完整代码如下:

代码语言:javascript
复制
import ast
import os
import subprocess
import shutil
import sys
from context import Context
from codegen import generate
BUILTINS = {
    "print": "PYC_Print",
}

def main():
    target = sys.argv[1]
    with open(target) as f:
        source = f.read()
    tree = ast.parse(source, target)
    ctx = Context()
    with open("libpyc.c") as f:
        ctx.body_write(f.read() + "\n")
    for builtin, fn in BUILTINS.items():
        ctx.register_global(builtin, fn)
    generate(ctx, tree)
    # Create and move to working directory
    outdir = "bin"
    shutil.rmtree(outdir, ignore_errors=True)
    os.mkdir(outdir)
    os.chdir(outdir)
    with open("main.c", "w") as f:
        f.write(ctx.body.content)
        main = ctx.namings.get("main")["name"]
        f.write(f"""int main(int argc, char *argv[]) {{
  Py_Initialize();
  // Initialize globals, if any.
{ctx.initializations.content}
  PyObject* r = {main}();
  return PyLong_AsLong(r);
}}""")
    subprocess.run(["clang-format", "-i", "main.c"])
    cflags_raw = subprocess.check_output(["python3-config", "--cflags"])
    cflags = [f.strip() for f in cflags_raw.decode().split(" ") if f.strip()]
    cmd = ["gcc", "-c", "-o", "main.o"] + cflags + ["main.c"]
    subprocess.run(cmd)
    ldflags_raw = subprocess.check_output(["python3-config", "--ldflags"])
    ldflags = [f.strip() for f in ldflags_raw.decode().split(" ") if f.strip()]
    cmd = ["gcc"] + ldflags + ["main.o"]
    subprocess.run(cmd)

main()

完成了!

pyc/codegen.py

最后,我们编写一个从 Python AST 到 C 的转换层。我们将其分为 10 个辅助函数。有 AST 规范作为参考是很有帮助的。

1/10: generate

代码生成器的入口是generate(ctx: Context, exp)。它能为具有body属性(该属性能存储语句列表)的任何对象生成代码。此函数能为模块、函数体、if 主体等对象生成代码。

我们最先支持的语句是:

  • ast.Assign
  • ast.FunctionDef
  • ast.Return
  • ast.If
  • ast.Expr

对于每个语句,我们只需简单地将生成器传递给关联的辅助函数。不过,在生成表达式的情况下,我们还需在表达式的结果上添加一个空(noop)操作符,否则编译器给出一个未使用变量的警告。

代码语言:javascript
复制
def generate(ctx: Context, module):
    for stmt in module.body:
        if isinstance(stmt, ast.Assign):
            generate_assign(ctx, stmt)
        elif isinstance(stmt, ast.FunctionDef):
            generate_function_def(ctx, stmt)
        elif isinstance(stmt, ast.Return):
            generate_return(ctx, stmt)
        elif isinstance(stmt, ast.If):
            generate_if(ctx, stmt)
        elif isinstance(stmt, ast.Expr):
            r = generate_expression(ctx, stmt.value)
            ctx.body_writeln("// noop to hide unused warning")
            ctx.body_write_statement(f"{r} += 0")
        else:
            raise Exception(f"Unsupported statement type: {type(stmt)}")

记住要主动抛出异常,否则使用新语法调试程序会很困难。

让我们继续深入研究一下这些辅助函数。

2/10:generate_assign

要生成赋值代码,我们需要检查我们是否处于顶层。如果是在顶层,则可以声明该变量,但还不能初始化它。所以我们要将初始化代码添加到程序的initialization部分。

如果不是在顶层,则可以在一个语句中声明并赋值。

不过,在执行这两种操作之前,我们都需要先注册变量名,这样我们就可以在生成的代码中获得一个安全的本地名称。然后,我们编译右侧,这样我们就可以将它赋值给左边。

代码语言:javascript
复制
import ast
from context import Context

def initialize_variable(ctx: Context, name: str, val: str):
    if ctx.at_toplevel():
        decl = f"PyObject* {name}"
        ctx.body_write_statement(decl, 0)
        init = f"{name} = {val}"
        ctx.initializations_write_statement(init)
    else:
        ctx.body_write_statement(f"PyObject* {name} = {val}")

def generate_assign(ctx: Context, stmt: ast.Assign):
    # TODO: support assigning to a tuple
    local = ctx.register_local(stmt.targets[0].id)
    val = generate_expression(ctx, stmt.value)
    initialize_variable(ctx, local, val)

为了实现完成该工作,我们还需要实现generate_expression

3/10:generate_expression

generate中的语句一样,我们需要实现以下几种表达式 :

  • ast.Num
  • ast.BinOp
  • ast.BoolOp
  • ast.Name
  • ast.Compare
  • ast.Call

对于ast.Num,我们只需将字面数字包装为PyLong*。对于ast.Name,我们只需在上下文中查找本地名称。其他的我们则委托给更多的其他辅助函数。

代码语言:javascript
复制
def generate_expression(ctx: Context, exp) -> str:
    if isinstance(exp, ast.Num):
        # TODO: deal with non-integers
        tmp = ctx.register_local("num")
        initialize_variable(ctx, tmp, f"PyLong_FromLong({exp.n})")
        return tmp
    elif isinstance(exp, ast.BinOp):
        return generate_bin_op(ctx, exp)
    elif isinstance(exp, ast.BoolOp):
        return generate_bool_op(ctx, exp)
    elif isinstance(exp, ast.Name):
        return ctx.get_local(exp.id)["name"]
    elif isinstance(exp, ast.Compare):
        return generate_compare(ctx, exp)
    elif isinstance(exp, ast.Call):
        return generate_call(ctx, exp)
    raise Exception(f"Unsupported expression: {type(exp)}")

对于每个表达式代码生成器辅助函数,我们将表达式存储在一个局部变量中,并返回该变量的名称,以便 AST 中的父节点可以引用该子节点。这可能会导致代码生成效率低下(无用的赋值),但是对于这样的项目而言,这并不是什么大问题,而且 GCC 很可能会对其进行优化。更烦人的是,无用的赋值只会使生成的代码难以阅读。

4/10:generate_bin_op

对于二进制运算符,我们需要支持加减运算。其他二进制操作符,如“等号”或“和 / 或”,用ast.Compareast.BoolOp表示。

这很容易编写,因为我们已经在libpyc.c: PYC_SubPYC_Add中准备了辅助函数:

代码语言:javascript
复制
def generate_bin_op(ctx: Context, binop: ast.BinOp) -> str:
    result = ctx.register_local("binop")
    l = generate_expression(ctx, binop.left)
    r = generate_expression(ctx, binop.right)
    if isinstance(binop.op, ast.Add):
        ctx.body_write_statement(f"PyObject* {result} = PYC_Add({l}, {r})")
    elif isinstance(binop.op, ast.Sub):
        ctx.body_write_statement(f"PyObject* {result} = PYC_Sub({l}, {r})")
    else:
        raise Exception(f"Unsupported binary operator: {type(binop.op)}")
    return result

很容易。

5/10:generate_bool_op

我们只需要支持斐波纳契数列程序中的or,但是 Python 中的or比 C 中的要复杂得多。在 Python 中,第一个为真的值会使表达式短路,结果是表达式的值,而不是True

我们将使用goto进行短路,并使用PyObject_IsTrue进行是否为真的检查:

代码语言:javascript
复制
def generate_bool_op(ctx: Context, boolop: ast.BoolOp) -> str:
    result = ctx.register_local("boolop")
    ctx.body_write_statement(f"PyObject* {result}")
    if isinstance(boolop.op, ast.Or):
        done_or = ctx.register_local("done_or")
        for exp in boolop.values:
            v = generate_expression(ctx, exp)
            ctx.body_write_statement(f"{result} = {v}")
            ctx.body_writeln(f"if (PyObject_IsTrue({v})) {{")
            ctx.body_write_statement(f"goto {done_or}", ctx.indentation+1)
            ctx.body_writeln("}")
        ctx.body_writeln(f"{done_or}:\n", 0)
    return result

现在我把它先写下来,如果我们使用循环的话,可以把这个函数移到libpyc.c中。也许会在下一个迭代中改进。

我们继续。

6/10:generate_compare

此函数处理相等和不相等的检查。我们将修改手工翻译程序中使用的PyObject_richcarebool辅助函数。

唯一需要记住的是,右侧是作为数组传递的。因此,我们必须对其遍历,然后对列表中的所有对象应用相等 / 不相等检查。

代码语言:javascript
复制
def generate_compare(ctx: Context, exp: ast.Compare) -> str:
    result = ctx.register_local("compare")
    left = generate_expression(ctx, exp.left)
    ctx.body_write_statement(f"PyObject* {result} = {left}")
    for i, op in enumerate(exp.ops):
        v = generate_expression(ctx, exp.comparators[i])
        if isinstance(op, ast.Eq):
            ctx.body_write_statement(f"{result} = PyObject_RichCompare({result}, {v}, Py_EQ)")
        elif isinstance(op, ast.NotEq):
            ctx.body_write_statement(f"{result} = PyObject_RichCompare({result}, {v}, Py_NE)")
        else:
            raise Exception(f"Unsupported comparison: {type(op)}")
    return result

7/10:generate_call

最后一个表达式很简单。我们首先编译调用的参数,然后编译函数本身,然后像其他任何 C 函数一样使用参数调用函数。直接调用 C 函数会影响与 Python 库的交互(基本上,我们无法与任何库进行交互),但这是最简单的开始方法。

代码语言:javascript
复制
def generate_call(ctx: Context, exp: ast.Call) -> str:
    args = ', '.join([generate_expression(ctx, a) for a in exp.args])
    fun = generate_expression(ctx, exp.func)
    res = ctx.register_local("call_result")
    # TODO: lambdas and closures need additional work
    ctx.body_write_statement(
        f"PyObject* {res} = {fun}({args})")
    return res

这就是表达方式!只需要再支持几个声明辅助函数即可。

8/10: generate_function_def

这是很有趣的一个。首先,我们在作用域中注册函数名称。然后我们复制上下文,使函数体内的变量被包含在函数体内。我们扩大scope,这样我们就离开了顶层。最后,我们编译主体部分。

代码语言:javascript
复制
def generate_function_def(ctx: Context, fd: ast.FunctionDef):
    name = ctx.register_local(fd.name)
    childCtx = ctx.copy()
    args = ", ".join([f"PyObject* {childCtx.register_local(a.arg)}" for a in fd.args.args])
    ctx.body_writeln(f"PyObject* {name}({args}) {{", 0)
    childCtx.scope += 1
    childCtx.indentation += 1
    generate(childCtx, fd)
    if not childCtx.ret:
        childCtx.body_write_statement("return Py_None")
    ctx.body_writeln("}\n", 0)

不必严格检查childCtx.ret,因为即使已经有返回了,我们也可以再发出一个返回。要求generate_return设置此属性,并对generate_function_def进行检查,这样就会使生成的代码更漂亮一些。

9/10:generate_return

非常简单,我们只编译要返回的值,然后发出一个return语句即可。

我们存储返回值,以便函数定义可以知道是否要添加return PyNone语句。

代码语言:javascript
复制
def generate_return(ctx: Context, r: ast.Return):
    ctx.ret = generate_expression(ctx, r.value)
    ctx.body_writeln("")
    ctx.body_write_statement(f"return {ctx.ret}")

我们还有最后一个声明要支持!

10/10:generate_if

你知道该怎么做:编译测试,如果测试是正确的,就进入编译后的主体。我们将再次处理 else 主体。

代码语言:javascript
复制
def generate_if(ctx: Context, exp: ast.If):
    test = generate_expression(ctx, exp.test)
    ctx.body_writeln(f"if (PyObject_IsTrue({test})) {{")
    ctx.indentation += 1
    generate(ctx, exp)
    # TODO: handle exp.orelse
    ctx.indentation -= 1
    ctx.body_writeln("}\n")

我们完成了这个编译器!

尝试一下

按照承诺:

代码语言:javascript
复制
$ cat tests/recursive_fib.py
def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

def main():
    print(fib(40))
$ python3 pyc tests/recursive_fib.py
$ ./bin/a.out
102334155

微基准测试,或使编译器 Twitter 不高兴

请记住,这个实现只完成了 CPython 所做工作的一小部分。

如果你要计时生成的代码:

代码语言:javascript
复制
$ python3 pyc tests/recursive_fib.py
$ time ./bin/a.out
102334155
./bin/a.out  18.69s user 0.03s system 99% cpu 18.854 total

CPython (将main()附加到源文件):

代码语言:javascript
复制
time python3 tests/recursive_fib.py
102334155
python3 tests/recursive_fib.py  76.24s user 0.11s system 99% cpu 1:16.81 total

我之所以提这一点,是因为我为针对C++/libV8 的JavaScript 做了一个类似的编译器项目,当时生成的代码速度与这个几乎相同或稍微慢一些。

在编写这些编译器方面,没有比这更好的了。

原文链接:

https://notes.eatonphil.com/writing-a-simple-python-compiler.html

  • 发表于:
  • 本文为 InfoQ 中文站特供稿件
  • 首发地址https://www.infoq.cn/article/eI4yJXOJM2qEwZMmINEL
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券