底层实现：编译器

Python 程序可以直接运行，但这种简洁的使用方式隐藏了语言实现中的许多问题：源码怎样变成可处理的程序结构，动态值怎样跨越 C++ 接口，变量与类型怎样被记录，以及生成的本地代码怎样重新回到 Python。实现一个 Python 编译器，不只是把语法翻译成另一种语言，还需要补齐支撑这些语法的运行时和调用边界。

本书以 Matx 为基础，讨论一个受限 Python 子集怎样被转换成 C++，编译为动态库，再从 Python 中加载和调用。Matx 不追求兼容完整的 Python，而是保留一条能够实际运行的编译链路，使运行时对象、数据容器、函数调用、抽象语法树、代码生成和 FFI 可以在同一个项目中被观察。

全书沿两条相互交汇的主线展开。一条主线把 Python 源码转换为 Matx AST，并通过 Visitor 和 Rewriter 生成 C++；另一条主线实现对象、动态值、容器和函数等语言运行时机制。两条主线最终在动态模块处汇合：生成的程序通过统一的 C ABI 导出函数，Python 再经由 FFI 找到并调用这些本地实现。

Matx 编译流程

引言

Python 适合快速编写和组合程序，但当一段逻辑需要进入 C++ 运行时、生成可独立加载的动态库，或者与其他本地模块共同执行时，仅保留 Python 函数对象还不够。编译器需要取得函数源码，理解其中的参数、类型和表达式，再为它生成具有明确调用边界的本地实现。

可以从一个最小的带类型函数开始。它只有一次加法，却已经包含参数声明、类型标注、返回语句和函数调用这些基本要素，足以展示一条完整的编译链路：

def add(a: int, b: int) -> int:
    return a + b

对 Python 来说，它只是一个可以直接调用的函数；对编译器来说，它却要经过源码解析、程序表示、代码生成、本地编译和动态加载，最后才能以接近原函数的方式重新回到 Python：

simple_compile(add, "add.so")

module = module_loader("./add.so")
native_add = module.get_function("add")
result = native_add(10, 20)

Matx 实现的正是这条链路。本书不会试图讲完一个工业编译器，而是通过这个规模较小的项目，观察一门动态语言如何穿过 C++ 运行时，最终变成可以加载和调用的本地程序。

原理

编译器的本质不是替换关键字，而是在两种程序表示之间保持语义。Python 中的加法、变量、循环和容器都有自己的执行规则；生成 C++ 时，可以改变它们的表示方式，却不能改变参数的求值顺序、变量指向的值以及函数返回的结果。

Matx 是一个提前编译（Ahead-of-Time，AOT）的源码到源码编译器。它不直接生成机器指令，而是先把 Python 子集转换成 C++，再借助现有 C++ 编译器生成动态库：

Python 源码
    ↓ 解析与语义检查
Matx AST
    ↓ 代码生成
C++ 源码
    ↓ g++
本地动态库

选择 C++ 作为目标语言，可以复用成熟编译器完成优化、机器码生成和平台适配。但 C++ 只能解决静态代码的编译，无法自动提供 Python 的动态值、容器、对象生命周期和跨语言调用。最终程序实际上由两部分共同组成：

                         编译期

 Python 函数
      │
      ▼
 Python Frontend ──────────────┐
      │                        │ 构造 C++ AST 对象
      ▼                        ▼
   Matx AST ◄──────── Function Registry
      │
      ▼
 Visitor / Rewriter
      │
      ▼
  C++ 源码 ────────► C++ Compiler ────────► 动态库
      │                                      │
      │ 调用                                 │ 加载与查找
      ▼                                      ▼
 ┌──────────────── Matx Runtime ─────────────────┐
 │ Object / Value / Container / Function / FFI  │
 └──────────────────────┬────────────────────────┘
                        │
                        ▼
                   Python 调用结果

                         运行期

图的上半部分是编译器：Frontend 理解 Python，AST 保存程序语义，Rewriter 生成 C++。下半部分是运行时：它既让 Python Frontend 能够创建 C++ AST 对象，也为生成代码提供动态值、容器和函数接口，最后再通过 FFI 把动态库接回 Python。

简单的整数加法可以直接生成 C++ 运算符；Python 列表、字典和动态对象则必须调用 Matx Runtime。代码生成器需要为每种语义选择正确的落点：能够静态表达的部分交给 C++，需要动态行为的部分保留为 Runtime 操作。

编译期与运行期

Matx 的流程还可以分成两个时间阶段。编译期读取 Python 源码、构造 AST、确定类型并输出 C++；运行期加载生成的动态库，接收 Python 参数并执行本地函数：

编译期
Python Function → Python AST → Matx AST → C++ → .so

运行期
Python Value → FFI → .so 中的函数 → FFI → Python Value

Runtime 同时服务于两个阶段。编译期，Python 前端通过 Runtime 创建并持有 C++ AST 对象；运行期，生成代码通过同一套值、容器和函数协议处理参数与结果。这种统一让编译器自身和编译产物不必各自实现一套对象模型。

两条主线

本书首先讨论如何把 Python 编译成 C++。这条主线关心源码解析、AST 转换、类型处理、C++ 生成、本地编译和动态加载。它回答的是：一个 Python 函数如何变成真正执行的本地代码，并继续保留可从 Python 调用的接口？

但这不只是语法翻译。为了传递 Python 的动态值，Matx 需要实现值表示；为了持有字符串、容器和 AST，Matx 需要实现对象与生命周期；为了支持列表和字典，Matx 还需要定义容器语义。函数、作用域、类型标签和跨语言对象同样不能由 C++ 编译器自动提供。

因此，第二条主线是亲手实现 Python 的关键机制：

Python 的值       → Value / McValue
Python 的对象     → object_t / object_r
Python 的容器     → List / Dict / Set / Tuple
Python 的函数     → PrimFunc / Function
Python 的名称     → ScopeContext / PrimVar
Python 的执行边界 → C API / 动态模块

这里的“实现 Python”不是复刻 CPython，也不意味着兼容完整的 Python 语言。Matx 选择一个受限子集，重新实现支撑它所必需的语言结构和运行时，再用 C++ 代码生成代替字节码虚拟机完成执行。两条主线最终汇合为同一个问题：要把 Python 编译成 C++，究竟需要自己实现多少 Python？

不同层次

这条链路中有几组名称相近但职责不同的结构。先区分它们，可以避免把编译器自身的数据与生成程序运行时的数据混在一起：

这些结构有时使用相似的名字，是因为它们在不同边界上解决同一类问题。例如 Function Registry 和模块函数表都根据名称查找函数，但前者服务于编译器核心，后者服务于编译产物；两者不能合并为同一张表。

实现

下面沿着 add 的编译过程，观察输入程序如何穿过上述结构。这里的重点不是再次罗列文件，而是确定每个模块位于哪一层，以及前一层的输出如何成为后一层的输入。

Python Frontend

simple_compile 接收的是一个已经存在的 Python 函数对象。函数能够被 CPython 调用，但编译器真正需要的是定义它的源码。Frontend 先使用 inspect.getsource 取得文本，再通过 ast.parse 得到 Python AST：

Python Function
      ↓ inspect.getsource
Python Source
      ↓ ast.parse
Python AST

Python AST 解决了语法识别，却仍然包含完整 Python 的节点和动态语义。SimpleParser 从中选择 Matx 支持的子集，解析类型标注和名称作用域，并把较复杂的语法降低为更基础的结构。例如第一次赋值变成变量声明，for range 变成初始化、条件和 WhileStmt。Frontend 决定“哪些 Python 程序可以进入编译器”，也负责让进入后端的程序具有明确含义。

这里的 Python Frontend 是一个编译器层次，而不是名为 frontend 的包。当前代码主要对应 compiler.py、parser.py 和 scope_context.py：它们分别启动编译、转换 AST，并管理作用域与符号。

AST

Python AST 仍然属于 Python 自身。Frontend 会继续把它转换成 Matx 的抽象语法树：

PrimFunc "add"
├── 参数: PrimVar "a", PrimVar "b"
├── 返回类型: PrimType(int64)
└── ReturnStmt
    └── PrimAdd(a, b)

从这一刻开始，函数不再是一段文本，而是一组可以检查、遍历和转换的 C++ 对象。

AST 是编译器各阶段之间的协议。Frontend 不需要知道每个节点最终输出成什么 C++，Rewriter 也不需要重新理解 Python 的缩进和语法；两者只需对 PrimFunc、PrimAdd 和 ReturnStmt 等节点的含义达成一致。这种中间表示把“理解源语言”和“生成目标语言”分开。

Runtime

AST 中的 PrimFunc、PrimVar 和 PrimAdd 都有不同的字段与类型，但 Python 前端需要通过统一接口持有它们。节点还会被多个父节点共享，不能依靠裸指针随意管理生命周期。

因此 Matx 首先需要一套对象体系：Node 类保存实际数据，引用类提供类型化接口，侵入式引用计数决定何时释放对象。AST、函数和模块都建立在这套机制上。

但不是所有数据都适合变成堆对象。调用 native_add(10, 20) 时，两个整数更适合直接保存在固定布局的值中。Matx 因此还有一套值体系，用类型标签和联合体统一传递整数、浮点数、字符串指针和对象指针。

对象体系解决复杂数据的身份与生命周期，值体系解决不同数据的统一传递。两者在运行时接口处相互配合。

Container

一个函数不只有单个节点。它有参数列表、默认参数和多条语句，模块还要保存多个函数。以 add 为例，两个 PrimVar 被放入 Array<PrimVar>，函数体中的语句被放入 SeqStmt。

Matx 同时需要表示 Python 的动态容器，因此实现了两组容器：Array<T>、Map<K, V> 为 C++ 内部结构保留类型约束；List、Dict、Set 和 Tuple 则用 McValue 保存运行时动态值。迭代器让打印器和代码生成器能够遍历这些内容。

Function

Python 前端中的 PrimVar(...) 并不是纯 Python 数据类。它最终需要调用 C++ 构造函数，但 Python 不知道这些函数的链接符号和具体签名。

Matx 将构造函数注册为带名字的全局函数：

ast.PrimVar
ast._OpAdd
ast.ReturnStmt
ast.PrimFunc

函数包装器把不同的 C++ 签名统一成 McValue(Parameters)。Python 只需按名称取得函数，传入运行时值，就能获得对应的 AST 对象。函数注册表由此成为 Python 前端与 C++ 编译器核心之间的入口。

这也解释了 Runtime 为什么出现在编译期：SimpleParser 虽然由 Python 编写，真正构造的却是 C++ 中的 PrimVarNode、PrimAddNode 和 PrimFuncNode。Function 与 FFI 把 Python 的解析逻辑连接到 C++ 的程序表示。

Visitor

得到 PrimFunc 后，不同阶段会对它执行不同操作。Printer 把节点转换成便于观察的文本，Rewriter 则生成可以交给 C++ 编译器的源码。

它们都通过 Visitor 遍历 AST。Visitor 根据节点的运行时类型索引，将 PrimAddNode 分派给加法处理函数，将 ReturnStmtNode 分派给返回语句处理函数。节点只负责保存程序结构，具体操作则放在独立的访问者中。

对 add 函数，Rewriter 最终会生成类似下面的主体：

int64_t add(int64_t a, int64_t b) {
    return (a + b);
}

实际输出还包括参数检查、返回值转换和模块注册信息。simple_compile 将源码写入 .cpp，再调用 g++ 生成 add.so。

这里完成了从源语言到目标语言的语义映射：

PrimFunc       → C++ 函数定义
PrimVar        → 带类型的局部变量或参数
PrimAdd        → C++ 加法表达式
ReturnStmt     → C++ return 语句
List / Dict    → Matx Runtime 容器操作

目标代码不是 Python 源码的逐行转写，而是 AST 节点在 C++ 与 Runtime 中的对应实现。

生成结果

实际使用当前 Matx 编译这个函数：

def add(a: int, b: int) -> int:
    return a + b

生成的 C++ 文件包含下面的函数主体：

int64_t add(int64_t a, int64_t b) {
  return (a + b);
}

但这个函数还不能由 Python 直接调用。生成文件中还有一个 C 包装函数。省略重复的错误文本后，其关键代码为：

int add__c_api(Value* args, int num_args,
               Value* ret_val, void* resource_handle) {
    // 检查 num_args == 2，且两个参数均为 Int

    auto result = add(args[0].u.v_int,
                      args[1].u.v_int);

    ret_val->t = TypeIndex::Int;
    ret_val->u.v_int = result;
    return 0;
}

真正的 add 只负责计算，add__c_api 负责检查并拆出参数，再设置返回值及其类型。生成文件最后把包装函数写入函数数组，并用名称 "add" 建立注册信息：

BackendFunc __mc_func_array__[] = {
    (BackendFunc)add__c_api,
};

FuncRegistry __mc_func_registry__ = {
    "\1add\000",
    __mc_func_array__,
};

因此，“把 Python 编译成 C++”实际包含两类输出：

Python 函数语义 ──→ add          执行真正的计算
Python 调用边界 ──→ add__c_api   转换参数与返回值
模块发现协议   ──→ registry     让加载器找到函数

这三部分一起进入 add.so。缺少第一部分就没有本地实现，缺少后两部分则虽然生成了机器代码，Python 却无法发现和调用它。

FFI

生成的动态库不能直接向 Python 暴露 C++ 对象。它导出一组遵循 C ABI 的函数指针，以及函数名和函数指针之间的对应关系：

add.so
├── add                  生成的 C++ 函数
├── add__c_api           C 调用包装
├── __mc_func_array__    函数指针数组
└── __mc_func_registry__ 函数注册信息

module_loader 使用 dlopen 打开动态库，再通过 dlsym 读取注册信息。module.get_function("add") 找到对应函数指针，并将它重新包装成 Matx 的统一 Function。

当 Python 调用 native_add(10, 20) 时，FFI 把 Python 参数转换成 Value[]，生成模块读取两个整数并执行 C++ 函数，返回值再沿相反方向变成 Python 整数：

Python int
   ↓
Value[]
   ↓
C API 包装函数
   ↓
生成的 C++ 函数
   ↓
Value
   ↓
Python int

至此，一个 Python 函数完成了从源码到本地执行，再回到 Python 调用界面的闭环。

从全书结构来看，Runtime、Container 和 Function 建立编译器与生成程序共用的运行时基础；AST 与 Visitor 负责程序的内部表示和目标代码生成；Python Frontend 提供源语言入口；FFI 则把生成的本地模块重新接回 Python。后面的每一篇都会展开其中一层，但它们共同服务于同一条主线：

理解 Python 程序
    ↓
用 Matx AST 保存其语义
    ↓
用 C++ 与 Runtime 实现这些语义
    ↓
把本地结果重新交给 Python

阅读后续章节时，可以用下面的源码位置建立对应关系：

这些文件并不是彼此隔离的模块。parser.py 通过 Function Registry 创建 expression.h 中的节点，rewriter.h 遍历这些节点并引用 Runtime 接口，runtime_module.h 最后加载生成结果。表格用于定位代码，前面的关系图则用于理解它们为何连接。

Runtime 运行时

引言

编译器不只需要把加法、循环等语法翻译成 C++，还要决定程序中的值怎样存在。生成的代码必须知道一个值是整数、字符串还是容器，明确它占用多少内存、由谁持有，以及通过函数参数和返回值传递时怎样保留类型信息。否则，即使一条表达式能够被翻译成合法的 C++，程序也无法正确保存和交换其中的数据。

这些问题在 Python 中通常不会直接暴露。变量可以随时引用不同类型的值，容器可以混合保存整数和对象，字符串的内存也由运行时自动管理。先看一段普通的 Python 代码：

count = 42
name = "matx"
items = [count, name]
result = items[1]

count 是整数，可以直接映射到 int64_t；name 是需要管理内存的字符串；items 又在同一个容器中保存了两种不同类型。取出 items[1] 时，底层代码还必须知道这个值是字符串，才能正确复制、返回和释放它。

如果只使用 C++ 原生类型，整数、字符串和容器需要完全不同的函数签名与存储方式。它们也很难通过同一套 C API 在 Python 和生成的动态库之间传递。Matx 的运行时就是这段 Python 代码与底层 C++ 表示之间的桥梁。

Matx 因此需要回答三个问题：

1. 不同类型的值怎样通过同一个函数接口传递？
2. 字符串、容器等动态对象由谁管理生命周期？
3. 只拿到一个通用值时，怎样判断它的实际类型？

在运行时中，整数和浮点数可以直接保存在一个带类型标签的联合体中：

McValue number(42);
McValue ratio(0.5);

字符串、容器和 AST 节点则需要额外的内存或对象结构。运行时在堆上创建这些对象，管理它们的生命周期，再把对象指针放入通用值：

Str text("matx");
McValue value(text);

为什么不只使用一套结构？一种做法是让所有值都继承同一个对象基类，包括整数和浮点数。这样类型关系很统一，但每个数字都要在堆上分配对象，并参与引用计数。前面的 count = 42 原本只需要复制八字节整数，现在却会变成一次对象创建和一次间接访问。大量算术运算会为这种统一付出不必要的成本。

另一种做法是把所有内容都直接放进 Value。固定大小的联合体可以保存整数、浮点数和指针，却无法直接容纳长度不定的字符串、列表或 AST 节点。如果让 Value 分别管理每一种复杂类型，它就必须知道所有对象的内存布局、继承关系和释放方式，最终会变成一个不断扩张的巨大分支。

Matx 因此采用两套相互配合的结构：

• 值体系直接保存整数、浮点数等轻量值，并提供固定的 C ABI 布局。
• 对象体系管理字符串、容器、AST 和动态模块等堆对象，负责引用计数、继承与运行时类型。
• 当复杂对象需要通过统一接口传递时，值体系只保存它的指针和类型索引。

这样，count 可以直接存在 Value 的联合体中，items 则由对象体系管理，McValue 仍能使用相同接口表示两者：

对象体系
object_t ── object_p<T> ── object_r
   │          │               │
对象基类   管理引用计数      类型擦除引用
   │
   └──────────────┐
                  ▼
值体系       Value ── Any ── McView / McValue
             固定布局  类型接口   借用 / 拥有

object_r 适合在 C++ 内部以统一方式引用不同对象；McValue 则可以同时保存立即数和对象指针，适合函数参数、返回值与 FFI。对象体系负责身份、继承和生命周期，值体系负责统一传递。本章将分别解释它们，并说明两者如何在 McValue 中汇合。

实现

运行时需要分别实现对象管理、类型识别和值传递，再通过 McValue 将它们组合成统一接口。下面先从具有身份和生命周期的对象开始。

Object

object_t 是运行时对象的共同基类。AST 节点、字符串、容器和动态模块最终都继承自它：

class object_t {
public:
    virtual ~object_t();
    virtual int32_t Index() const;
    virtual std::string Name() const;

    void IncCounter() noexcept { ++count_; }
    void DecCounter() noexcept {
        if (--count_ == 0) delete this;
    }

protected:
    int32_t t_{0};
    std::atomic<int32_t> count_{0};
};

对象内部保存类型索引和引用计数。Matx 没有直接用 std::shared_ptr，而是通过 object_p<T> 管理侵入式引用计数。复制 object_p<T> 时计数加一，析构或重新赋值时计数减一；移动则直接转移指针。

auto node = MakeObject<StrNode>(std::string("matx"));
object_p<StrNode> copy = node;

MakeObject<T> 负责创建对象并写入运行时类型索引。对象的引用计数存放在对象本身，因此同一个对象无论经过何种包装，都共享同一份所有权状态。

object_r 在 object_p<object_t> 外再提供一层类型擦除。上层代码可以统一保存 Object，需要具体类型时再通过 As<T>() 检查：

class object_r {
public:
    template<typename T>
    const T* As() const noexcept {
        if (data_ && data_->IsType<T>()) {
            return static_cast<const T*>(data_.get());
        }
        return nullptr;
    }
};

具体运行时类型通常采用 Node 与引用类分离的形式。例如 StrNode 保存 std::string，Str 则继承 object_r，向用户提供构造、访问和运算接口。这种结构也为写时复制提供了统一入口。

TypeContext

C++ 的 RTTI 只能处理 C++ 继承关系，不能直接作为稳定的 FFI 类型编号。Matx 为每个运行时对象分配一个整数类型索引，并记录它的父类型：

class StrNode : public object_t {
public:
    static constexpr int32_t INDEX = TypeIndex::RuntimeStr;
    static constexpr std::string_view NAME = "RuntimeStr";
    DEFINE_TYPEINDEX(StrNode, object_t);
};

TypeContext 保存类型名称、索引和父索引。IsFrom(child, parent) 沿父链向上查找，因此 IsType<T>() 不只能够判断精确类型，也能判断继承关系。内置类型使用固定索引，扩展类型可以从 TypeIndex::Dynamic 开始动态分配。

Object
├── RuntimeStr
├── RuntimeList
├── RuntimeDict
├── RuntimeSet
├── Module
└── 动态注册类型

类型名称与索引的对应关系同时被 C API、函数注册和 Python 对象包装使用。它不仅服务于 C++ 内部的类型转换，也是不同语言之间识别对象的共同协议。

Value

对象适合字符串和容器等需要生命周期的数据，但整数和浮点数没有必要单独分配对象。Matx 使用 C 兼容的 Value 统一保存立即数、字符串、指针和对象地址：

union Union {
    int64_t v_int;
    double  v_float;
    char*   v_str;
    void*   v_pointer;
    Dt      v_datatype;
};

struct Value {
    Union u{};
    int32_t p{0};
    int32_t t{0};
};

t 是类型标签，决定联合体中哪个成员有效；p 保存字符串长度等附加信息。这个结构没有构造函数、析构函数或模板成员，可以直接出现在 C API 的函数签名中。

基础类型使用负数标签，对象类型使用非负索引：

Null / Int / Float / Str / Pointer / DataType < 0
Object 及其派生类型                         >= 0

这种划分让 value.t >= TypeIndex::Object 成为对象判断，同时避免给整数、浮点数和裸指针增加引用计数。

Any 与 McValue

裸 Value 适合 ABI，却不适合直接在 C++ 中使用。Any 为它增加类型查询与转换接口：

Any value = McValue(42);

if (value.Is<int64_t>()) {
    int64_t number = value.As<int64_t>();
}

Any 本身不负责资源释放。在它之上，Matx 区分两种使用方式：

• McView 只观察已有值，不增加对象引用计数，也不释放字符串或对象。
• McValue 拥有值，负责复制、移动和销毁资源。

这一区分对函数调用很重要。输入参数只在调用期间有效，可以使用一组 McView 或 Any；返回值需要离开当前栈帧继续存在，因此必须由 McValue 持有。

McValue 的复制行为取决于类型：整数和浮点数直接复制，C 字符串分配新缓冲区，运行时对象增加引用计数。移动操作则转移底层 Value，并将来源设为 Null。

McValue a("matx");
McValue b = a;             // 复制字符串

McValue x(Str("runtime"));
McValue y = x;             // 共享对象并增加引用计数

析构时，McValue::Clean() 根据类型标签执行对应操作：字符串使用 delete[]，对象调用 DecCounter()，立即数不需要清理。所有资源规则都集中在这一处，容器、函数和 FFI 不需要重复判断所有权。

DataType

DataType 和 TypeIndex 都描述类型，但用途不同。

TypeIndex 回答“这个运行时值是什么对象”，例如 RuntimeList 或 Module；DataType 描述编译器中的标量数据格式：

struct Dt {
    uint8_t c_;   // int、uint、float 或 handle
    uint8_t b_;   // 位宽
    uint16_t a_;  // lanes
};

例如 DataType::Int(32) 表示 32 位整数，DataType::Bool() 表示单 lane 的 1 位无符号值，DataType::Handle() 表示运行时对象或指针。Dt 只有四字节，可以作为 Value 的一个联合体成员跨越 C API。

两套类型信息分别服务于不同阶段：AST 和代码生成使用 DataType 推导表达式类型，运行时和 FFI 使用 TypeIndex 判断实际对象。不要把“编译期数据类型”和“运行时对象类型”混为一套系统，是 Matx 能同时处理静态代码与动态值的基础。

运行时边界

对象系统解决身份、继承和生命周期，值系统解决统一传递与跨语言布局。二者在 McValue 处汇合：立即数直接存入联合体，对象则以指针和类型索引进入同一接口。

容器正是这套机制的直接使用者。List 和 Dict 自身是引用计数对象，内部元素则由 McValue 保存。下一篇将沿着这个边界说明不同容器如何共享一套值表示，并提供各自的遍历接口。

Container 数据容器

引言

运行时不仅要传递整数和浮点数，还要表示下面这样的 Python 数据：

record = {
    "name": "matx",
    "scores": [91, 87, 95],
    "tags": {"compiler", "runtime"},
}

for name, value in record.items():
    print(name, value)

这些容器可以嵌套不同类型的值，还需要支持索引、查找和遍历。Matx 没有直接把 std::vector 或 std::unordered_map 暴露给编译后的程序，而是在运行时对象体系之上实现了自己的容器。

从运行时看，record 不是一块连续的数据，而是一组通过 McValue 相互引用的对象：

DictNode
├── "name"   → StrNode("matx")
├── "scores" → ListNode
│              └── [91, 87, 95]
└── "tags"   → SetNode
               └── {"compiler", "runtime"}

外层字典负责键值查找，列表和集合分别保存自己的元素；字符串、列表、集合和字典又都由运行时对象体系管理生命周期。容器需要解决的因此不只是“把元素放在一起”，还包括嵌套对象怎样持有、动态值怎样比较，以及不同容器怎样被统一遍历。

实现

Matx 的容器建立在运行时对象与 McValue 之上。类型明确的内部结构和类型动态的 Python 数据采用不同容器，但共享相同的对象生命周期与遍历基础。

Node

容器沿用运行时对象的两层结构：Node 类保存数据，引用类提供接口。

例如，ListNode 继承 object_t，负责保存元素；List 继承 object_r，负责持有节点并转发操作：

class ListNode : public object_t {
    std::vector<McValue> data_;
};

class List : public object_r {
public:
    McValue& operator[](int64_t i) const;
    void append(McValue value) const;
    size_t size() const;
};

这种分工让容器直接复用对象体系的引用计数和运行时类型检查，同时保持接近普通 C++ 容器的使用方式。

Array 与 Map

Array<T> 和 Map<K, V> 保存经过类型擦除的 object_r，但在接口处通过模板恢复类型。它们主要服务于 AST 等类型明确的内部结构。例如，一个函数的参数可以表示为：

Array<PrimVar> params{a, b};

调用者只能向其中放入 PrimVar，读取元素时也直接得到 PrimVar。底层对象仍然通过 object_r 统一保存，模板接口则在 C++ 编译期保留元素约束。

List、Dict、Set 和 Tuple 则保存 McValue。它们允许整数、浮点数、字符串和其他运行时对象出现在同一个容器中，更接近 Python 的动态语义：

List values{McValue(42), McValue(3.14), McValue("matx")};
values.append(true);

Dict config;
config[McValue("debug")] = McValue(true);

两组容器不是重复实现：前者在 C++ 编译期提供类型约束，后者在运行时保留动态类型。

Array<PrimVar>：元素类型由 C++ 模板确定
List：          元素类型由每个 McValue 的标签确定

AST 结构优先使用前者，避免把类型错误推迟到运行时；编译后程序中的 Python 容器使用后者，保留混合存储不同值的能力。

共享语义

容器引用类的复制不会复制全部元素，而是共享同一个 Node：

List a{McValue(1), McValue(2)};
List b = a;
b.append(3);

此时 a 和 b 都能看到第三个元素，因为二者持有同一个 ListNode。Node 的引用计数保证最后一个容器引用离开后才释放元素，元素中的 McValue 再分别处理立即数、字符串和对象的所有权。

这种浅复制符合 Python 可变对象的引用语义，也避免在函数传参时复制整个容器。需要注意的是，共享 Node 和复制 McValue 是两个不同层次：复制容器引用只增加 Node 的引用计数，向容器中插入元素则会按照 McValue 的规则复制或移动该元素。

List 与 Tuple

List 使用 std::vector<McValue>，支持追加、删除末尾元素和清空。索引由 ListNode::at 完成，并接受负数索引：-1 会先转换为最后一个元素的位置，再交给 std::vector::at 检查边界。这让生成代码可以保留 Python 常用的负索引行为，而不必在每个调用位置重复转换。

Tuple 只公开读取和遍历接口。TupleNode 在构造时复制元素，并用连续数组保存它们。接口上的不可修改性使它适合表示固定参数、字典条目等结构。List 与 Tuple 因此可以保存相同的 McValue，区别在于容器是否允许结构发生变化。

Dict 与 Set

Dict 和 Set 建立在哈希表之上，因此 McValue 必须提供相等比较和哈希规则。查找一个键时，运行时先根据类型和值计算哈希，再用相等比较确认是否为同一个键。字典保存键值对，集合只保存唯一的值：

Dict env{{McValue("x"), McValue(10)}};
bool found = env.contains(McValue("x"));

Set labels{McValue("B"), McValue("I")};
labels.insert(McValue("E"));

Dict 还提供 items、keys 和 values 三类迭代视图。它们共享同一个哈希表迭代器，只改变解引用时返回键值对、键还是值，对应 Python 中的 dict.items()、dict.keys() 和 dict.values()。

Iterator

当前代码中存在两层迭代机制。第一层是容器直接提供的 begin() 和 end()。它兼容 C++ 范围循环，也是目前完整可用的遍历方式：

for (const McValue& value : values) {
    // 使用 value
}

这种方式要求调用位置知道具体容器类型。函数注册或跨语言调用只拿到一个 Any 时，则需要不依赖 List::iterator、Dict::iterator 等具体 C++ 类型的遍历接口。第二层因此是类型擦除的运行时 Iterator。IteratorNode 定义统一协议：

virtual bool HasNext() const = 0;
virtual McValue Next() = 0;
virtual int64_t Distance() const = 0;

GenericIteratorNode 用回调适配具体遍历过程，并把原容器保存在一个 McValue 中。这样即使外部只持有 Iterator，容器也不会在遍历结束前被释放。

Iterator::MakeGenericIterator 可以通过回调包装具体遍历过程，但接收 Any 并按运行时类型自动选择容器适配器的重载尚未接通。因此，当前完整可用的路径仍是各容器自身的 begin() 和 end()；类型擦除的 Iterator 只在调用方已经提供遍历回调时使用。

容器由此把上一章的对象和值真正组合起来：容器自身依靠对象体系获得身份和生命周期，内部元素通过 McValue 保留动态类型，迭代接口再把这些元素交给函数调用和后续程序处理。

Function 函数调用

引言

编译器中的许多能力最终都表现为函数调用：Python 前端需要构造 AST 节点，编译流程需要调用代码生成入口，动态模块也需要向外提供已经编译好的函数。然而，这些函数原本具有不同的 C++ 签名：

Str make_str(std::string value);
PrimExpr make_add(PrimExpr a, PrimExpr b);
McValue node_get_attr(Parameters args);

如果调用者必须在编译期知道每个函数的参数和返回类型，Python 前端就只能为每个 C++ 接口编写一套绑定，动态加载的模块也无法通过统一方式暴露能力。Matx 需要在保留 C++ 强类型接口的同时，为运行时建立一个与具体签名无关的调用入口。

这个入口由函数注册表提供。函数先被转换成统一的 Function，再以字符串名称保存；调用者只需准备一组运行时参数，就能查找并执行目标函数：

函数名称 + 运行时参数
          ↓
     FunctionRegistry
          ↓
  参数转换 → C++ 函数 → 返回值包装
          ↓
        McValue

这样，调用者与函数实现不必直接依赖对方。Python 前端、编译器组件和动态模块只需共同遵守名称与运行时值的约定。

实现

Matx 将所有注册函数统一为一种签名：

using Function = std::function<McValue(Parameters)>;

Parameters 表示输入参数，McValue 表示返回值。无论原函数接收整数、字符串还是 AST 对象，进入注册表以后都表现为 Parameters → McValue。

Parameters

一次函数调用可能包含不同数量、不同类型的参数。Parameters 不复制这些值，只保存参数数组的首地址和长度：

class Parameters {
    Any* item_;
    size_t size_;
};

其中每个元素都由 Any 表示，因此同一组参数可以同时包含整数、字符串和对象引用。Parameters 只是调用期间的临时视图，不拥有底层数组；调用者必须保证参数在函数返回前有效。这种设计避免了跨边界调用时不必要的复制，也允许函数直接遍历数量不固定的参数。

函数适配

开发者仍然可以使用清晰的强类型接口注册函数：

REGISTER_GLOBAL("runtime.Str")
    .SetBody([](std::string value) {
        return Str(value);
    });

FunctionWrapper 负责将这个 Lambda 适配成统一的 Function。它首先通过 FunctionTraits 取得参数数量和类型，再使用 std::index_sequence 展开参数下标。上面的函数在运行时相当于执行：

return McValue(
    func(ConvertArg<std::string>(params[0]))
);

ConvertArg<T> 位于动态值与强类型 C++ 之间。它按照目标类型检查并恢复参数：

• 整数和浮点数从 Any 中读取数值；
• std::string 从运行时字符串恢复；
• DataType 读取编译器中的数据类型；
• object_r 的派生类型先检查对象，再恢复相应引用；
• McValue 保留原始动态值。

如果参数不足或类型不匹配，转换过程会抛出异常，错误不会继续进入实际函数。目前包装器只要求实参数量不少于形参数量，多出的参数不会被拒绝。

两种注册方式

REGISTER_GLOBAL 用于普通函数或 Lambda：

REGISTER_GLOBAL("ast.PrimAdd")
    .SetBody([](PrimExpr a, PrimExpr b) {
        return PrimAdd(a, b);
    });

它保留强类型函数的写法，并自动完成参数转换。对于本身已经接受动态参数的函数，可以直接使用 REGISTER_FUNCTION：

static McValue NewTuple(Parameters args) {
    // 遍历全部参数并构造 Tuple
}

REGISTER_FUNCTION("runtime.Tuple", NewTuple);

后者不再经过强类型参数适配，适合可变参数函数以及需要自行解释参数的底层入口。两种方式最终都会得到相同的 Function。

函数注册表

FunctionRegistry 是进程内的全局注册表，使用 std::unordered_map 保存名称与函数，并用互斥锁保护注册、查找、删除和枚举操作。重复注册同名函数会直接报错，避免后加载的模块悄悄覆盖已有实现。

函数名称通常带有命名空间：

runtime.Str
runtime.Tuple
ast.PrimAdd
rewriter.BuildFunction

名称不仅用于分类，也构成不同组件之间的接口约定。运行时构造函数以 runtime 开头，AST 构造函数以 ast 开头，代码生成入口则位于 rewriter 下。C API 的 GetGlobal 同样从这张表中取得函数，因此 Python 前端不需要直接链接每个具体的 C++ 实现。

静态注册

注册宏会定义一个静态变量。程序或动态库被加载时，这个变量先于正常调用完成初始化，将名称和函数写入注册表：

#define REGISTER_GLOBAL(Name)                   \
    static auto& unique_name =                  \
        FunctionRegistry::Register(Name)

因此，新增一个 AST 节点构造函数时，不需要再修改集中式的初始化列表。实现文件只要包含一条注册语句，链接进程序以后，相应能力就能通过名称被发现。这种分散声明、集中查找的方式降低了模块之间的依赖，但也要求包含注册代码的目标文件确实被链接或加载，否则对应名称不会出现在注册表中。

注册表中保存的不是函数地址本身，而是 std::function。它既能容纳普通函数，也能保存带捕获状态的 Lambda。代价是调用时多了一层间接跳转和动态参数转换；对编译器控制流程和跨语言调用而言，这部分开销通常小于它带来的接口统一。

C API 边界

Python 不能直接操作 std::function、McValue 或 C++ 异常，因此 Matx 又在注册表外提供了一层稳定的 C API。GetGlobal 根据名称找到 Function，复制一份并以不透明的 FunctionHandle 返回。Python 只保存这个句柄，不需要了解它在 C++ 中的实际类型；句柄不再使用时由 FuncFree 释放。

真正调用时，FuncCall_PYTHON_C_API 接收一组 C 结构体 Value：

Python 对象
    ↓  参数打包
Value[]
    ↓  构造只读视图
McView[] → Parameters
    ↓
Function
    ↓  返回值转换
Value
    ↓
Python 对象

C API 先为每个 Value 建立 McView，再用它们构造 Parameters。这种视图不会取得输入值的所有权，调用结束后即可丢弃。函数返回的 McValue 则会被转换回 Value；对象的引用计数和字符串缓冲区由相应的 C API 释放函数继续管理。

C++ 中的类型错误也不能越过 C ABI 直接传播。C API 会捕获运行时异常，把错误文本保存在线程局部区域，并用非零状态码通知 Python。Python 扩展再读取错误信息并抛出 Python 异常。这样，参数转换失败仍能保留清晰的错误边界，而不会让 C++ 异常穿过不兼容的调用栈。

示例

以构造加法表达式为例，Python Frontend 的 add() 实际查找 ast._OpAdd。它在 C++ 中接收两个 PrimExpr：

REGISTER_GLOBAL("ast._OpAdd")
    .SetBody([](PrimExpr a, PrimExpr b) {
        return PrimAdd(a, b);
    });

这里保留了宏展开后的核心结构；源码通过 REGISTER_MAKE_BINARY_OP 完成同样的注册。Python 前端调用这个名字时，参数已经被转换成运行时对象。C API 将它们放入 Parameters，随后从注册表取得函数：

Function* fn = FunctionRegistry::Get("ast._OpAdd");
McValue result = (*fn)(params);

在 Python 一侧，这个函数并不会以手写绑定的形式出现。前端通过 GetGlobal 取得一个通用的可调用对象，调用时再把两个表达式对象交给相同的参数打包逻辑。包装器依次将两个 Any 恢复为 PrimExpr，调用 Lambda 构造 PrimAddNode，再把结果包装成 McValue 返回。整个过程可以表示为：

Python: add(lhs, rhs)
              ↓
       GetGlobal("ast._OpAdd")
              ↓
       Parameters(lhs, rhs)
              ↓
 ConvertArg<PrimExpr> × 2
              ↓
       C++: PrimAdd(a, b)
              ↓
      McValue(PrimAddNode)

这个例子中存在两次类型转换。第一次发生在 Python 与 C API 之间，将 Python 表达式对象转换为带类型索引的 Value；第二次发生在 FunctionWrapper 中，将动态的 Any 恢复为注册函数声明的 PrimExpr。返回路径按相反顺序执行。Runtime 负责保存值的类型与生命周期，Function 只负责按照目标签名检查和传递它们。

注册表也让调用方向得以反转。Python 前端不必由 C++ 主动调用，而是在加载扩展后自行查找 ast._OpAdd、runtime.Tuple 或 rewriter.BuildFunctions。后续增加新的构造函数时，只要遵循相同的命名和参数约定，Python 侧就能继续复用同一个调用器。

同一条调用链既适用于整数和字符串，也适用于容器与 AST 对象。函数注册表解决了“如何找到并调用一种能力”，而参数转换将 Runtime 的动态值重新带回 C++ 的强类型世界。下一篇将继续讨论这些函数最常构造和处理的对象：抽象语法树。

AST 抽象语法树

引言

Python 源码适合人阅读，却不适合编译器直接处理。空格和换行承担语法作用，同一种运算也可能写在不同上下文中；如果类型检查、代码改写和 C++ 生成都反复分析源码字符串，各阶段不仅容易重复工作，也很难共享已经得到的信息。

编译器因此先把程序转换成抽象语法树（Abstract Syntax Tree，AST）。例如：

def add(a: int, b: int) -> int:
    c = a + b
    return c

进入 Matx 后，函数本身可以表示为下面的节点关系：

PrimFunc "add"
├── 参数: PrimVar "a", PrimVar "b"
├── 返回类型: PrimType(int64)
└── 函数体: SeqStmt
    ├── AllocaVarStmt
    │   ├── 变量: PrimVar "c"
    │   └── 初始值: PrimAdd(a, b)
    └── ReturnStmt(c)

这棵树省略了缩进、括号等表面形式，只保留函数、变量、运算和返回等语义结构。一个节点也不再只是语法名称：PrimVar 保存变量类型，PrimAdd 保存操作数和结果类型，PrimFunc 保存参数、函数体与返回类型。后续阶段只需处理这些结构化对象。

Matx 的 Python 前端会先读取 Python AST，再构造自己的 AST。前者描述完整的 Python 语法，后者只保留编译器支持的子集，并补充 C++ 生成需要的类型和运行时信息。因此，Matx AST 既是源程序的内部表示，也是 Python 与 C++ 之间的语义边界。

实现

Matx 将 AST 分成表达式、语句、类型、函数和模块几层。它们不是相互独立的容器，而是逐层组合：

IRModule
  └── BaseFunc
        └── Stmt
              └── BaseExpr

Type ──描述变量、表达式和函数返回值

表达式组成计算，语句安排执行顺序，函数把参数和语句组织成可调用单元，模块再为多个函数和类建立全局名称空间。

Node 与引用

所有 AST Node 最终都继承 object_t，自动获得引用计数和运行时类型索引。具体数据保存在 Node 中，对外传递的则是继承 object_r 的引用类：

class PrimVarNode : public PrimExprNode {
public:
    std::string var_name;
    // datatype 继承自 PrimExprNode
};

class PrimVar : public PrimExpr {
public:
    DEFINE_NODE_CLASS(PrimVar, PrimExpr, PrimVarNode);
};

PrimVarNode 保存名称和类型，PrimVar 管理节点的引用并提供类型化访问。DEFINE_NODE_CLASS 生成构造、复制、移动和 operator-> 等公共代码。复制一个 PrimVar 时通常只增加底层节点的引用计数，不会复制整棵子树。

这种表示适合 AST：同一个变量节点可以同时出现在初始化语句、加法表达式和返回语句中。各处共享的是同一个符号对象，而不是三个只有名称相同的副本。节点数组由 Array<T> 保存，函数属性由 Map 保存，构造入口则通过 Function 注册表暴露给 Python，前面介绍的 Runtime 结构都在这里汇合。

表达式

表达式以 BaseExprNode 为公共基类，并分成两条分支：

BaseExpr
├── PrimExpr    带有 DataType，可产生运行时值
└── AstExpr     函数等更高层的编译结构

常见的 PrimExpr 节点包括：

二元运算共享相同的节点布局：

template <typename T>
class PrimBinaryOpNode : public PrimExprNode {
public:
    PrimExpr a;
    PrimExpr b;
};

PrimAdd(a, b) 保存左右操作数，并以左操作数的 DataType 作为结果类型；比较节点则产生布尔类型。类型直接附着在表达式上，代码生成器不必在输出每个运算时重新查找变量声明。当前构造器主要记录类型，完整的操作数兼容性仍由前端解析和检查过程保证。

函数调用使用稍有不同的结构：

class PrimCallNode : public PrimExprNode {
public:
    BaseExpr op;
    Array<PrimExpr> gs;
};

op 表示被调用对象，gs 保存实参。被调用对象可以是内置 Op，也可以是用户函数对应的 GlobalVar。这样，a + b、内置函数和普通函数调用虽然来源不同，最终都能通过明确的表达式节点交给后端。

语句

表达式描述“计算什么”，语句描述“何时计算以及结果放在哪里”。Matx 支持的语句形成另一棵继承树：

Stmt
├── ExprStmt / Evaluate
├── AllocaVarStmt / AssignStmt
├── ReturnStmt
├── SeqStmt
├── IfStmt / WhileStmt
└── ClassStmt

SeqStmt 使用 Array<Stmt> 表示一个顺序代码块。IfStmt 保存条件、真分支和假分支，WhileStmt 保存条件与循环体。代码块嵌套在控制语句中，控制语句又可以作为外层代码块的一个元素，执行结构自然由树的层次表达。

变量的首次定义和后续赋值被区分为两种节点：

class AllocaVarStmtNode : public StmtNode {
public:
    PrimVar var;
    BaseExpr init_value;
};

class AssignStmtNode : public StmtNode {
public:
    BaseExpr u;
    BaseExpr v;
};

AllocaVarStmt 同时建立变量和初始值，后端可以据此生成带类型的 C++ 局部变量声明；AssignStmt 只改变已经存在的目标。这个区别在 Python 源码中并不总是显式存在，却是生成静态 C++ 代码时必须补充的信息。

类型

Matx 使用两种相互配合的类型表示。DataType 是紧凑的值类型，记录标量类别、位宽和通道数，适合直接附着在大量表达式上。Type 是运行时对象，可以继续派生：

Type
├── PrimType          标量类型
├── ClassType         类类型
├── TypeVar           类型参数
└── GlobalTypeVar     全局类型名称

局部变量和普通运算主要使用 DataType，函数返回值则使用 Type，从而为类和类型参数保留空间。GetRuntimeDataType 可以从 PrimType 取出底层 DataType；不能直接映射为标量的对象类型则以句柄形式进入运行时。

这两层表示分别服务于高频的底层计算和可扩展的语言类型。如果所有地方都使用对象化的 Type，简单整数运算也需要访问运行时对象；如果只使用 DataType，又无法表示类和类型变量。

函数与模块

函数节点继承 BaseFunc。PrimFunc 的参数是已经确定类型的 PrimVar，适合进入当前代码生成流程；AstFunc 还能保存普通 BaseExpr 参数和类型参数，用于表达更高层的函数结构。当前 Parser 生成的是 PrimFunc：

class PrimFuncNode : public BaseFuncNode {
public:
    Array<PrimVar> gs;   // 参数
    Array<PrimExpr> fs;  // 默认参数
    Stmt body;
    Type rt;             // 返回类型
};

AST 还定义了 IRModule，可以用来组织多个函数和类：

Map<GlobalVar, BaseFunc> func_;
Map<GlobalTypeVar, ClassType> class_;

GlobalVar 是函数在模块中的符号，BaseFunc 才是函数定义。调用表达式只引用 GlobalVar，不用把被调用函数的整棵树嵌入当前函数。模块结构因此可以同时保存定义和定义之间的引用关系。

不过，当前 Python simple_compile 走的是一条更直接的路径：SimpleParser 将函数保存在自身的字典和顺序表中，编译器取出全部 PrimFunc，组成 Array 后传给 rewriter.BuildFunctions。IRModule 已经存在于 C++ AST 中，但尚未成为这条 Python 编译路径的必经容器。区分这两点很重要：前者说明 AST 的组织能力，后者才是当前代码实际执行的流程。

示例

再次观察开头的 add。解析函数签名时，前端先为参数建立带类型的变量：

a → PrimVar("a", int64)
b → PrimVar("b", int64)

解析 c = a + b 时，符号表让名称 a 和 b 指向已有的 PrimVar。加法生成 PrimAdd(a, b)，赋值左侧第一次出现，因此整条语句被表示成：

AllocaVarStmt
├── var: PrimVar("c", int64)
└── init_value: PrimAdd
    ├── a: PrimVar("a", int64)
    └── b: PrimVar("b", int64)

前端随后把 c 加入符号表。解析 return c 时，得到的是引用同一变量的 ReturnStmt。两条语句进入 SeqStmt，再与参数和返回类型共同构成 PrimFunc。SimpleParser 以函数名记录这个结果，simple_compile 最后将收集到的 PrimFunc 交给代码生成器。

源码名称
   ↓ 符号表
PrimVar / GlobalVar
   ↓ 组合表达式
PrimAdd
   ↓ 组织执行顺序
AllocaVarStmt + ReturnStmt
   ↓
PrimFunc
   ↓
Array<PrimFunc>
   ↓
rewriter.BuildFunctions

到了代码生成阶段，后端看到的已经不是 Python 文本，而是一组类型明确、层次稳定的对象。它可以把 AllocaVarStmt 输出为局部变量声明，把 PrimAdd 输出为加法表达式，再把 ReturnStmt 输出为 return。AST 解决了程序如何表示的问题；下一篇将继续讨论 Printer、Visitor 和 Rewriter 如何遍历并转换同一棵树。

Visitor 遍历与重写

引言

AST 把程序变成了一组节点，但节点本身不会打印、分析或生成代码。以表达式 a + b 为例，同一个 PrimAddNode 可能被用于：

• 打印成便于调试的 (a + b)；
• 生成可以编译的 C++ 表达式；
• 收集其中引用的变量；
• 在优化阶段替换某个子表达式。

如果把这些操作都写进 Node 类，新增一种操作就要修改所有节点。Matx 采用 Visitor，把“数据结构”和“对数据执行的操作”分开。

这里存在两个不同的问题。第一个是：当手中只有 PrimExpr 或 Stmt 这样的基类引用时，怎样找到具体节点对应的处理函数？第二个是：找到当前节点以后，怎样继续处理它的子节点？Visitor 负责类型分派，具体的 Printer 或 Rewriter 则决定递归顺序和处理结果。

基类引用
   ↓ Visitor 按类型分派
具体 Node
   ↓ 操作决定是否递归
子表达式与子语句
   ↓
文本、分析结果或 C++ 源码

这种分离让 AST 的节点定义保持稳定。增加一种新的处理任务时，可以实现新的 Visitor，而不必把代码生成、调试打印和分析逻辑同时塞进每个 Node。

实现

类型分派

NodeVisitor 是最底层的分派表。它以节点的运行时类型索引为下标，保存对应的函数指针：

PrimAddNode::Index() ──→ VisitExpr_(PrimAddNode*)
PrimVarNode::Index() ──→ VisitExpr_(PrimVarNode*)
ReturnStmtNode::Index() ──→ VisitStmt_(ReturnStmtNode*)

访问一个 object_r 时，NodeVisitor 读取 Index() 并直接查表。调用者只需要持有基类引用，分派结果仍然是具体的 Node 类。

在此之上，Matx 按节点家族提供三种访问者：

PrimExprVisitor<R(const PrimExpr&, Args...)>
StmtVisitor<R(const Stmt&, Args...)>
TypeVisitor<R(const Type&, Args...)>

模板参数决定返回值和附加参数。例如 Printer 返回 Doc，Rewriter 不返回值，而是额外接收一个输出流。各访问者只需要覆盖自己关心的 VisitExpr_、VisitStmt_ 或 VisitType_。

这套机制结合了两层分派：类型索引表先找到节点对应的入口，虚函数再调用当前 Visitor 子类的实现。因此 AST 节点不需要为 Printer、Rewriter 等每种用途分别增加虚函数。

递归遍历

Visitor 只负责“当前节点该交给谁”，不会自动访问子节点。递归逻辑由具体操作决定。打印加法表达式时，需要显式访问左右操作数：

Doc VisitExpr_(const PrimAddNode* op) override {
    Doc doc;
    doc << "(" << Print(op->a)
        << " + " << Print(op->b) << ")";
    return doc;
}

这看似多写了一些代码，却允许不同任务选择不同遍历策略。例如打印器访问两个分支，常量分析可以在获得确定结果后停止，变量收集器则可以忽略类型字段。

没有注册处理函数的节点会进入默认分支。因此，增加一种 AST 节点时，需要同时为实际使用它的 Printer、Rewriter 或分析器补充处理函数。节点类型决定“它是什么”，各个 Visitor 决定“在当前任务中怎样处理它”。

AttrVisitor

另一类遍历针对节点的字段，而不是节点类型。Node 类通过 VisitAttrs 暴露具名属性：

void PrimVarNode::VisitAttrs(AttrVisitor* visitor) {
    visitor->Visit("var_name", &var_name);
    visitor->Visit("datatype", &datatype);
}

NodeAttrNameCollector 忽略字段内容，只收集名称；NodeAttrGetter 则根据名称读取值。它们通过全局函数 runtime.NodeGetAttrNames 和 runtime.NodeGetAttr 暴露给前端，使 Python 可以检查 C++ AST 对象，而不必为每个字段编写一套 C API。

节点通过实现 VisitAttrs 明确选择要暴露的字段，因此它是一套按需开放的轻量反射接口。NodeVisitor 根据节点类型选择行为，AttrVisitor 则根据字段名称读取内容，两者解决的问题不同。

Printer

AstPrinter 同时继承表达式、语句和类型 Visitor。它把节点转换成 Doc，再由 Doc::str() 生成字符串。

Doc 不只保存普通文本，还保存换行和缩进等结构化原子。这样打印函数和代码块时，可以先组合文档，再统一处理排版：

Doc doc;
doc << "return " << Print(value) << ";";

直接向字符串追加内容很难统一处理嵌套代码块：子节点需要知道当前缩进，父节点又需要决定换行位置。Doc 将“要输出什么”和“怎样排版”分开，复合节点可以先组合子文档，最后再统一生成文本。

Printer 的主要用途是观察 AST。注册函数 ast.AsText 让 Python 前端也能取得这种表示。它输出接近源码的可读形式，帮助确认前端生成了哪些节点，但不承担最终模块的编译输出。

Rewriter

当前项目中的 Rewriter 名字容易让人误以为它会返回一棵修改后的 AST。实际上，它遍历 AST 并将等价的 C++ 写入 std::ostream，职责更接近代码生成器。

例如，变量声明节点：

AllocaVarStmt(c, int64, PrimAdd(a, b))

会被输出为类似下面的代码：

int64_t c = (a + b);

Rewriter 还维护生成过程所需的状态：

• var_dict_ 将 PrimVarNode* 映射为唯一的 C++ 变量名；
• 作用域栈和缩进计数控制代码块；
• GetTypeInfo 将 DataType 映射到 C++ 类型及运行时标签；
• 容器节点被转换为 List、Dict、Set 和 McValue 操作。

容器方法还需要语义映射。例如 Python 的 list.append 保持为 append，set.add 生成 insert，set.discard 生成 erase。这说明代码生成不是简单拼接源码，而是在两种语言的运行时接口之间做翻译。

Rewriter 还必须区分表达式和语句的输出环境。表达式写入当前输出流，不主动结束一行；语句负责缩进、分号和换行；IfStmt、WhileStmt 与函数节点则建立新的代码块。AST 中的嵌套关系由此重新变成 C++ 的括号和执行顺序。

SourceRewriter

基础 Rewriter 输出函数或类的 C++ 定义，SourceRewriter 在其外部补充可独立编译的模块结构：

C++ 头文件与运行时上下文
        ↓
函数和类定义
        ↓
C API 参数检查与包装函数
        ↓
函数名表、函数指针表和模块初始化入口

rewriter.BuildFunction、BuildFunctions 和 BuildClass 是注册给前端的入口。生成函数时，C API 包装层检查参数数量和基础类型，再把 Value 转成 C++ 参数；返回结果则写回 Value。动态模块因此不需要暴露 C++ 名字改编后的符号，只需导出约定的 C 数据结构。

对于类，SourceRewriter 还会读取 ClassMembers、MethodName 和 MethodType 等属性，把成员定义与方法组织到同一个 C++ 类和模块接口中。函数 AST 描述函数内部的计算，而这些属性补充类和模块级别的生成信息。

示例

以前一篇的语句 c = a + b 为例，AST 中已经包含：

AllocaVarStmt
├── var: PrimVar("c", int64)
└── init_value: PrimAdd(a, b)

Rewriter 从语句节点开始。StmtVisitor 根据类型索引把它分派到 VisitStmt_(AllocaVarStmtNode*)。该处理函数先根据 DataType 输出 int64_t，再为变量 c 分配当前函数内唯一的 C++ 名称，随后递归输出初始值。

初始值是一个 PrimExpr，因此进入 PrimExprVisitor：

PrimAdd
├── PrimVar("a")
└── PrimVar("b")

PrimAddNode 的处理函数先写入左括号，再分别访问左右操作数。两个 PrimVarNode 通过 var_dict_ 找到参数在 C++ 中的名称。递归返回后补上运算符和右括号，最终得到：

int64_t c = (a + b);

完整的分派过程是：

Stmt
 ↓ StmtVisitor
AllocaVarStmtNode
 ├── 输出类型和变量名
 └── PrimExpr
      ↓ PrimExprVisitor
    PrimAddNode
      ├── PrimVarNode → a
      └── PrimVarNode → b

Printer 遍历同一组节点时不会生成类型声明，而是得到便于阅读的表达式；其他分析器也可以复用分派结构，选择收集变量或检查节点。Visitor 让一棵 AST 支持多种解释方式，SourceRewriter 则进一步把函数输出包装成可编译、可加载的 C++ 模块。下一篇将回到流程起点，介绍 Python 前端如何读取 Python AST、创建 Matx 节点并启动代码生成。

Python 前端

引言

前面几篇分别介绍了 Runtime、Container、Function、AST 和 Visitor。它们解决了值如何表示、节点如何构造以及 C++ 代码如何生成，却还没有说明一个普通的 Python 函数怎样进入这套系统。用户写下的仍然是 Python 源码，其中只有名称、表达式和控制结构，并不存在 PrimVar、SeqStmt 或 PrimFunc。

Python 前端负责连接这两层。它读取函数源码，借助 Python 自带的 AST 理解语法，再完成名称解析、类型推断和语法降低，最终构造出 Matx 能够处理的 AST。simple_compile 是这条编译流程对用户提供的入口：

def sum_to(n: int) -> int:
    total = 0
    for i in range(n):
        total = total + i
    return total

simple_compile(sum_to, "sum_to.so")

它并不是调用 CPython 执行函数，而是读取函数源码，将支持的 Python 子集转换成 Matx AST，再生成并编译 C++ 动态库。

Python 很适合描述程序：函数、分支、循环和容器都可以用简洁的语法表达。但动态语言允许变量在运行时改变类型，也允许对象随时增加行为，C++ 后端无法原样接受这些语义。前端的任务因此不只是“解析 Python”，还要确定名称指向哪个变量、表达式产生什么类型，以及复杂语法应当转换成哪些基础节点。

整个过程可以概括为：

Python 函数对象
    ↓ inspect.getsource
Python 源码
    ↓ ast.parse
CPython AST
    ↓ SimpleParser
Matx PrimFunc
    ↓ rewriter.BuildFunctions
C++ 源码
    ↓ g++ -shared -fPIC -O2
动态库 .so

这里存在两棵不同的 AST。ast.parse 产生的是 CPython 提供的语法树，它忠实描述 Python 语法；SimpleParser 产生的是 Matx AST，它只保留后端需要的节点，并为变量和表达式附加运行时类型。

前端位于两种语言之间：向上接受 Python 的表达方式，向下只输出类型和执行顺序都足够明确的 IR。某种 Python 语法如果无法可靠地映射到 Matx AST，就应在这里被拒绝，而不是留给生成的 C++ 在运行时产生模糊错误。

实现

获取源码

simple_compile 接收一个 Python 函数对象，通过 inspect.getsource 取得定义，再用 textwrap.dedent 去掉嵌套环境带来的公共缩进：

source = textwrap.dedent(inspect.getsource(target))
tree = ast.parse(source)

这种方式简单，但也意味着目标必须有可读取的源码。交互式环境中临时创建的函数、动态生成的函数或某些装饰器包装后的对象，可能无法被 inspect 正确还原。

编译器还会扫描目标函数中的直接构造调用。如果调用名对应全局命名空间中的 Python 类，它会一并取得类源码，与函数源码合并后重新解析。这样，编译一个使用类的函数时，不必要求调用者手工传入类定义。

节点转换

SimpleParser 继承 ast.NodeVisitor，但覆盖了默认行为：遇到没有显式支持的语法节点时直接报错，而不是悄悄遍历其子节点。这保证编译器不会忽略自己无法表达的语义。

以赋值为例：

total = total + i

前端先把右侧变成 PrimAdd，再查询当前作用域。如果 total 尚未定义，就生成 AllocaVarStmt；如果已经定义，则生成 AssignStmt。因此 Python 中同一种赋值语法，在 Matx AST 中会区分变量声明和后续赋值。

函数参数和返回值必须带有受支持的类型标注。当前映射为：

handle 表示由运行时管理的动态值或对象。局部变量的类型由初始化表达式推断，后续赋值会检查是否兼容；目标类型为 handle 时可以接收不同的运行时对象。

类型推断以已经构造的 Matx 表达式为依据。比较与逻辑节点产生 bool，浮点字面量产生 float64，容器和字符串使用 handle；算术表达式则合并左右操作数的数值类型。这不是面向完整 Python 的通用类型系统，而是一套与当前 AST 和 C++ 表示直接对应的规则。

作用域与符号

ScopeContext 为每个代码块维护符号表和类型表。查找变量时从最内层作用域向外进行：

当前 if/while 作用域
        ↓ 未找到
外层函数作用域

Python 的名称在前端阶段被解析为同一个 PrimVar 对象。代码生成器随后用 Node 地址识别变量，并为它分配唯一的 C++ 名称。这比在后端再次使用字符串查找更可靠，也能避免不同作用域中的同名变量发生冲突。

ScopeContext 还保存待处理的 Python 节点。进入函数、条件分支或循环体时，前端建立新的上下文层；退出代码块时再恢复外层。解析过程由此同时维护源码遍历位置和符号可见范围。

语法降低

Python 语法与当前 C++ AST 并不总是一一对应，前端需要将复杂结构降低为已有节点。

for i in range(...) 是最直观的例子。Matx 没有独立的 ForStmt，因此前端只支持 range 循环，并把它转换为初始化、条件判断、WhileStmt 和步长更新。range 的参数先保存到临时变量，避免带副作用的表达式被重复求值。

布尔表达式、链式比较、条件表达式以及包含前置语句的循环条件也会被拆成临时变量、IfStmt、WhileStmt 和基础逻辑节点。这里的“降低”不是格式变化，而是用更小的节点集合保持原语义和求值顺序。

容器则有直接对应关系：

[a, b]       → ListLiteral
{a, b}       → SetLiteral
{k: v}       → DictLiteral
obj[index]   → ContainerGetItem
obj.append(x) → ContainerMethodCall

类也通过降低进入已有运行时结构。构造对象时，前端先创建一个动态字典保存成员，再展开 __init__；属性读取和写入分别转换为 ContainerGetItem 与 ContainerSetItem。方法调用则根据已经收集的方法定义展开，并用临时变量保存参数和返回结果。这样无需为类另建一套完全独立的运行时对象模型。

语言子集

前端覆盖函数、赋值、返回、if、while、for range、基础算术与比较、布尔运算、容器字面量、索引和部分方法调用。它定义的是一个可以静态转换的 Python 子集：

• for 只支持遍历 range，目标必须是单个名称；
• 不支持 for-else、while-else 和切片；
• 一次赋值只支持一个目标；
• 普通函数调用尚未作为通用语法处理，属性调用主要面向容器和受限的类方法；
• 不支持的类型标注和 AST 节点会直接抛出异常。

这些限制应被看作当前编译器的语言边界，而不是运行时自动提供的 Python 兼容能力。

生成与编译

解析完成后，SimpleParser 保存入口函数及解析过程中产生的其他函数。simple_compile 将它们放入 Array<PrimFunc>，再通过函数注册表取得：

to_source = matx_script_api.GetGlobal(
    "rewriter.BuildFunctions", True
)
cpp_code = to_source(Array(functions), Str("fn")).data

生成的源码被写到与目标动态库同名的 .cpp 文件，随后执行类似命令：

g++ -shared -fPIC -O2 sum_to.cpp \
  -I/path/to/Matx/src \
  -L/path/to/Matx/build -lcase \
  -o sum_to.so

当前 simple_compile 直接调用系统 g++，并依赖配置中的源码目录和构建目录。编译成功只说明动态库已经产生；要从 Python 中查找并调用其中的函数，还需要模块加载器和跨语言调用协议，这正是下一篇的主题。

示例

以开头的循环为例：

for i in range(n):
    total = total + i

Matx AST 没有 ForStmt，因此前端首先保证 range 参数只求值一次。这里的 n 会被保存为临时变量，循环变量 i 则用起始值初始化：

AllocaVarStmt("__range_end", n)
AllocaVarStmt("i", 0)

随后根据步长方向构造循环条件。默认步长为 1，因此核心结构相当于：

WhileStmt(i < __range_end)
└── SeqStmt
    ├── AssignStmt(total, total + i)
    └── AssignStmt(i, i + 1)

当 range 显式给出负步长时，条件改为 i > end；步长表达式同样先保存到临时变量。这个转换既保留了 Python 对 range 参数的求值次数，也让后端只需实现一种 WhileStmt。

完整过程如下：

Python ast.For
    ↓ 检查迭代对象是否为 range
保存 start、end、step
    ↓
初始化循环变量
    ↓
根据 step 选择 < 或 >
    ↓
WhileStmt
├── 原循环体
└── 循环变量更新

前端对布尔短路、链式比较、条件表达式和类方法也采用类似方法：先确定 Python 的求值规则，再用临时变量和基础 AST 节点表达同样的顺序。由此生成的 PrimFunc 已经不依赖 Python 解释器，可以直接交给 Rewriter 输出 C++。下一篇将继续说明编译得到的动态库如何被加载，并重新表现为 Python 可以调用的函数。

FFI 动态模块

引言

完成代码生成和动态库编译以后，Python 函数已经变成动态库中的机器代码，但整个编译流程还没有结束。Python 只知道磁盘上多了一个 .so 文件，并不知道其中包含哪些函数，也不知道参数应当怎样转换、返回值应该包装成哪种 Python 对象。对于字符串、容器和 AST 对象，还需要继续处理跨语言的内存与生命周期。

因此，动态库必须提供一套稳定的调用协议：运行时先加载文件并发现其中导出的函数，再把这些函数包装成 Python 可以持有和调用的对象；每次调用时，参数从 Python 值转换成 C 接口能够识别的数据，执行结果再沿相反方向返回。一次完整使用如下：

simple_compile(sum_to, "sum_to.so")

module = module_loader("./sum_to.so")
sum_to = module.get_function("sum_to")
result = sum_to(10)

这几行代码跨越了两个边界：Python 先通过 FFI 调用 Matx 核心库；核心库再加载生成的动态模块，并把其中的 C 函数包装成统一的 Function。

动态库不能只包含一段编译后的机器代码。调用者还需要知道其中有哪些函数、每个函数在哪里、参数应怎样排列、返回值属于什么类型，以及函数对象仍被使用时动态库能否卸载。Matx 为这些问题定义了一套小型模块协议：

Python
   ↓ Python C Extension
Matx 核心运行时
   ↓ C ABI
生成的动态模块
   ↓
C++ 函数

Python 与核心运行时之间使用句柄和 Value，核心运行时与动态模块之间使用 BackendFunc。中间的 Runtime 将两侧都转换成前面介绍的 Function、Parameters 和 McValue，从而让上层调用者不必关心函数来自主程序还是新加载的 .so。

实现

C ABI

Python 无法直接理解 object_r、McValue 或 std::function。即使两个动态库都由 C++ 编写，直接共享模板类型还会受到编译器、标准库和名称改编的影响。

Matx 因此在边界上只使用固定布局的数据和 C ABI：

struct Value {
    Union u;
    int32_t p;
    int32_t t;
};

using BackendFunc = int (*)(
    Value* args,
    int num_args,
    Value* result,
    void* resource
);

Value 携带数据、辅助信息和类型标签，BackendFunc 约定参数数组、返回值地址、资源句柄和错误码。接口没有暴露 C++ 类，因此 Python 扩展、核心运行时和生成模块可以遵循同一套调用协议。

这里的 Value 与 Runtime 中的动态值具有相同目标，但使用固定的 C 布局。整数和浮点数直接保存在联合体中，字符串、对象与函数通过指针传递，t 记录类型索引，p 保存字符串长度等辅助信息。边界两侧都根据类型标签解释联合体，避免在 ABI 中出现 C++ 模板。

Python FFI

Python 端同时使用两种连接方式。ctypes 加载 libcase.so，声明 GetGlobal、GetBackendFunction 和 FuncCall_PYTHON_C_API 等基础 C 函数的参数布局。case_ext.so 则是 Python C Extension，负责更复杂的可调用对象、参数转换和对象生命周期。

扩展模块提供两个关键 Python 类型：

• PackedFuncBase 持有 FunctionHandle，并通过 tp_call 表现得像普通 Python 函数；
• ObjectBase 持有 ObjectHandle 和类型索引，是 PrimVar、PrimFunc、Array 等包装类的基类。

例如 Python 构造 PrimVar 时，实际先查找注册函数 ast.PrimVar，再调用：

self.__init_handle_by_constructor__(
    prim_var_, name, datatype
)

扩展模块把 Python 参数转换成 Value[]，调用 FuncCall_PYTHON_C_API。C API 再将每个 Value 视为 McView，组成 Parameters，最终调用注册表中的 Function：

Python 参数
   ↓ case_ext
Value[]
   ↓ FuncCall_PYTHON_C_API
Parameters / McView
   ↓ Function
McValue 返回值
   ↓
Python 对象

ctypes 适合加载库和声明少量稳定接口，Python C Extension 则适合频繁的参数转换和自定义对象。两者并不是两套独立的 FFI：它们最终调用同一组 C API，并共享 FunctionHandle、ObjectHandle 和 Value 协议。

返回值

整数、浮点数、布尔值和字符串可以直接转换成对应的 Python 值。对象返回值只包含 C++ 指针和运行时类型索引，扩展模块还需要知道应该创建哪个 Python 包装类。

@register_object("PrimVar") 首先通过 GetIndex 查询 PrimVarNode 的类型索引，再把索引与 Python 的 PrimVar 类关联。收到对象返回值时，扩展模块按索引调用已注册的创建器，创建 PrimVar 实例并填入句柄。

这让 C++ 负责对象的真实数据和类型，Python 负责用户可见的类和方法。新增一种 AST 对象时，两端需要使用同一个类型名称完成注册。

函数也是一种运行时返回类型。收到函数句柄后，扩展模块会创建 PackedFuncBase；之后对这个 Python 对象使用括号调用，就会再次进入通用的 FuncCall_PYTHON_C_API。因此，全局函数和模块函数在 Python 中具有相同的调用外观。

生命周期

Python 包装对象并不拥有另一份 AST 数据，它只持有 C++ 对象指针。参数转换需要暂时保留对象时，扩展模块调用 ObjectRetain 增加侵入式引用计数；ObjectBase 被回收时调用 ObjectFree 减少计数。计数归零后，C++ Node 对象才会析构。

函数句柄采用不同的管理方式。GetGlobal 返回一个新复制的 std::function，PackedFuncBase 结束生命周期时通过 FuncFree 删除该副本。这样 Python 侧的函数对象不直接依赖注册表内部元素的地址。

模块函数还会持有模块自身的引用。即使 Python 变量 module 已经离开作用域，只要从中取得的函数仍然存在，承载机器代码的动态库就不会被提前 dlclose。否则函数句柄仍在，函数地址却已经失效，下一次调用就会跳转到被卸载的内存。

错误处理

C++ 异常不能直接越过 C 函数边界。C API 使用统一约定：成功返回 0，失败返回 -1，错误文本保存在当前线程的存储中：

try {
    // 调用 C++ 运行时
} catch (std::runtime_error& error) {
    SetError(error.what());
    return -1;
}

Python 扩展检查错误码，再读取 GetError() 并转换为 Python 异常。线程局部存储避免多个线程相互覆盖错误文本。调用者只面对 Python 异常，C++ 侧则仍然可以使用熟悉的异常方式报告参数、类型和模块加载错误。

模块协议

生成的 .so 不依赖 C++ 符号名来发现函数，而是导出约定的 C 符号：

__mc_func_array__       BackendFunc 函数指针数组
__mc_func_registry__    函数名称与数组的对应关系
__mc_closures_names__   需要资源句柄的函数名称
__mc_module_ctx         模块上下文

SourceRewriter 在生成 C++ 时创建这些结构。每个普通函数还会生成一个 name__c_api 包装器，用来检查参数数量和基础类型、调用真正的 C++ 函数，再把结果写入 Value。

名称表和函数指针表按相同顺序排列。模块加载器读取第 i 个名称时，就能把它与第 i 个 BackendFunc 建立对应关系。这样只需要导出少量固定符号，新增用户函数不会改变加载器本身。

加载与查找

runtime.ModuleLoader 创建底层 Library 对象，使用 dlopen(..., RTLD_NOW | RTLD_LOCAL) 打开文件。随后 LibraryModuleNode 通过 dlsym 找到 __mc_func_registry__，读取函数名及其对应的 BackendFunc，建立模块自己的查找表。

Python 的 Module.get_function(name) 调用 C API GetBackendFunction。找到函数后，WrapFunction 将 BackendFunc 重新包装成核心运行时使用的：

std::function<McValue(Parameters)>

包装函数负责完成反方向转换：将 Parameters 变成 Value[]，调用模块函数，再把返回的 Value 变成 McValue。它还捕获 Module 的对象引用，使函数仍被持有时动态库不会提前 dlclose。

示例

现在回到 sum_to(10)：

module = module_loader("./sum_to.so")
sum_to = module.get_function("sum_to")
result = sum_to(10)

module_loader 本身是全局注册函数。它接收动态库路径，调用 dlopen，读取模块导出的函数注册表，并返回一个 Module 对象。Python 包装类持有这个对象的句柄。

module.get_function("sum_to") 随后调用 GetBackendFunction。LibraryModuleNode 在自己的名称表中找到 sum_to__c_api 对应的 BackendFunc，再通过 WrapFunction 得到核心运行时使用的 Function。Python 最终拿到的是 PackedFuncBase，而不是原始函数地址。

执行 sum_to(10) 时，整数 10 被放入一个 Value。调用依次经过两层统一包装：

Python: sum_to(10)
    ↓ PackedFuncBase
Value[0] = Int(10)
    ↓ FuncCall_PYTHON_C_API
核心 Function(Parameters)
    ↓ WrapFunction
模块 BackendFunc
    ↓ sum_to__c_api
C++: sum_to(int64_t n)
    ↓
Value = Int(result)
    ↓
Python int

生成的 C 包装函数检查参数数量和整数类型，调用真正的 C++ sum_to，再把结果写入返回 Value。返回路径经过 BackendFunc、核心 Function 和 Python 扩展，最终得到普通的 Python int。

这条链路看起来较长，却把每一层的职责限制得很清楚：Python 负责用户接口，核心 Runtime 负责动态值和统一函数，模块协议负责发现能力，生成代码负责实际计算。Matx 没有把每个生成函数直接写死在 Python 扩展中，而是让动态模块遵循同一个小型 ABI。至此，从 Python 源码、Matx AST、C++ 生成到动态加载和调用的完整编译流程形成闭环。