前言(Foreword)

　　本文档是 Unilang 语言解释器的设计规格说明。

　　解释器实现 Unilang 基础语言。

　　本文档遵循的体例和参见上述链接的语言规范文档。此外，本文档使用原理强调解释作为设计依据的注释。

实现定义行为

　　当前实现指定以下 Unilang 基础语言的实现定义行为：

标准库模块操作

　　若环境变量 UNILANG_PATH 的值非空，则需求字符串模板是这个值以单字符子串 ";" 分隔后的结果；否则，默认值是以下模式串构成的序列：

"./?"
"./?.u"
"./?.txt"

用户环境初始化

　　用户环境初始化加载当前工作目录的 init.txt 实现，行为依次包括：

运行等效用户环境初始化的默认行为的操作。
提供以下构建和包管理库的定义。

项目维护注记

版本号更新

　　版本号以 C++ 宏的方式定义，被用于生成版本字符串。当前定义在 src/Main.cpp 中。

　　当前 REPL 中使用版本字符串。用户程序使用在 std.system 中提供的 version-string 可访问版本字符串。

　　版本号是自增的，和依赖管理 API 详细设计类似，符合语义化版本要求。一般一个小修改只修改最后的版本号，发布版本可修改前两位。主版本号仅在确认放弃现有 API 兼容时修改。

　　原则上，解释器中任意不兼容的功能变更（包括增加、删除和修改）都需要修改版本号，以便用户检查支持的特性。因为通常难以证明一个修改任意情况下都保持解释器和之前的行为兼容，所以可以视为任意修改都要求修改版本号。但是存在以下例外：

除非另行指定，版本号修改总是仅在中心化的默认分支上进行。
- 这避免项目内多个并发开发分支的同步困难。
- 发布版本通常直接在默认分支上进行。若因发布工程(release engineering) 流程需要单独的分支，应确保避免和其它分支的版本号冲突。
- 具体分支（及下游）修改版本号以外的版本标识（包括版本字符串）不需要受此约束。
为减少维护开销，在没有修改版本宏定义所在的源文件的情形下，除非作为发布版本，不要求修改版本号。这些情形版本号仍然被跳过，直到下一次修改 src/Main.cpp 累积这些修改次数。

整体设计

　　解释器的核心是一个 REPL(read-eval-print loop) 。接受用户输入，求值并输出反馈。

　　解释器的核心功能以 Interpreter 类提供。主函数中初始化这个类的成员准备基础环境。

原理作为原型实现，解释器比其它的复杂的指令翻译如 JIT(just-in-time) 或 AOT(ahead-of-time) 编译器的设计都相对简单。相对地，直接实现的性能可能较进一步优化的其它实现明显更低。以解释器原型为功能基线，未来可以演进为其它更复杂的形式，以改进性能并解决其它潜在的可用性问题。

实现环境

　　解释器使用 C++ 作为宿主语言(host language) 进行实现。Unilang 基础语言是解释器支持实现的语言。在互操作(interoperation) 的意义上，C++ 同时是本机语言(native language) 。

原理 C++ 是较普遍使用的语言。C++ 的实现性能通常较好，实践丰富，适合实现解释器。使用 C++ 实现解释器，在和 C++ 互操作上具有优势，适合本项目的主要需求（实现 GUI 框架）。

　　当前依赖 C++11 。

　　外部依赖引入了较新版本的 C++ 标准库特性的替代。

　　部分类型名使用 using 引入，之后不使用命名空间前缀。

　　由于 Unilang 基础语言的特性，对象语言的一部分功能可以由基础语言的程序代码被解释而实现，Unilang 同时是元编程(metaprogramming) 意义上的元语言(meta language) 和对象语言(object language)（这种元编程事实上是一般意义的反射(reflection) ）。原型实现中，标准库特性可能使用本机实现或非本机的对象语言派生(derivation) 。两者可在性能和实现难度上有不同的优势。相同功能的两种不同实现方式在功能上应等价，以便于相互替换，按需调整。具体功能在此不整体具体限定，而视具体功能的实现需求而定。

程序表示

　　程序或程序片段及其中表示的实体对应的数据结构是其对应的表示。

　　关于相关原理，另见语言实现演进方案。

外部表示

　　程序以语言规范文档要求提供外部表示(external representation) 。外部表示支持源代码形式的输入，作为翻译单元(translation unit) ，经分析求值的输入。

内部表示

　　程序的外部表示经分析得到的其它表示都属于内部表示(internal representation) 。

　　本设计中的解释器中的求值部分对 AST（abstract syntax tree ，抽象语法树） 直接解释，即 AST 解释器。以 AST 作为 IR（intermediate representation ，中间表示） 是所谓的 HIR（high-level IR，高层中间表示） 的最直接的形式之一。其它 IR 相对于作为输入的 HIR 来讲是 LIR（low-level IR，低层中间表示）。当前设计不指定 LIR 。

原理 AST 解释器相对引入其它 IR 的解释器（典型地，字节码(bytecode) 解释器）的优势是和语言规范中的语义描述直接对应，更适合作为原型。同时，AST 解释器在结构上的可扩展性一般更好，演进为实际可用的编译器比其它形式的解释器更低，参见以下编译器演进方案的相关章节。

规约

　　本设计中的求值被映射为一个 TRS（term reduction system ，项求值系统）模型。作为一类主要的重写系统(rewrite system) ，这可直接用来表达程序的形式语义(foraml semantics) （更具体地，使用操作语义(operational semantics) 的方法，表达小步语义(small-step semantics) ）；同时，表达语言的实现时，它高度同构于 AST 解释器。

　　TRS 中的规约(reduction) 是输入到输出的有向的变换。一系列规约的步骤(step) 经过一定的组合可替换 IR 的某个项(term) 的节点，实现 TRS 重写(rewrting) 。这种重写以解释器中的原生本机代码实现，或调用被解释的对象语言（在此为 Unilang 基础语言）的程序片段实现功能。

　　重写取得规约规则指定的范式(normal form) 时，规约终止。因为语言规范的要求，除非作用显式地未指定，相关的计算作用需具有确定性，范式在所有可能的规约路径中也应当具有唯一的形式。

注释这种性质即 TRS 的 Church-Rosser 属性。在形式语义模型的设计中，一般需证明规约规则符合这项属性（如 λ 演算的 Church-Rosser 定理）。本实现当前是非形式描述，不给出证明，但实现仍需原则上保持这一性质。

抽象机

　　因为 C++ 的嵌套函数调用不可靠（任意深度的嵌套函数调用可能耗尽实现资源而引发 C++ 的未定义行为；一般实现中，用尽调用栈引发的错误无法被可移植地处理），在无法证明对象语言的嵌套函数调用深度有限时，使用异步的形式进行调用。这要求解释器保存规约之间的状态，而不能完全地通过 C++ 参数传递。这种状态在持有程序执行所需资源的上下文(context) 数据结构保存。

　　上下文中保存异步规约动作(action) ，通过类似顶层跳板(trampoline) 函数循环调用剩余的动作，实现程序逻辑的推进。

　　本设计基于 CEK 抽象机实现规约模型。CEK 抽象机的 C(Control) 即为输入和经过规约变换的 AST ；E(Environment) 为环境；K(Continuation) 等价保持异步规约动作。 E 部分也在上下文中保存，同时因为 Unilang 已支持一等环境，可直接通过对象语言程序访问其内容。关于 C 和 E 部分的保存，另见以下求值规约的描述。

注释未来扩展可支持一等续延(first-class continuation) ，允许对象语言编写的用户程序直接操作异步规约动作。非异步规约的实现难以实现这些扩展（需要全程序变换，不适合一般解释器）。

　　上下文和宿主环境中的 C++ 线程一一对应。上下文之间相互隔离，不同的上下文允许多线程并发执行，一个宿主线程至多同时执行一个上下文的程序。

　　TRS 在上下文中实现。上下文同时保存具有 AST 数据结构的当前被规约项，在被实现的对象语言意义上是当前线程中作为原始输入被求值的表达式的值或其中的中间表示。

　　上下文引用跨上下文的全局状态(global state) 。全局状态包含所有上下文默认都可能使用的公共资源，并提供规约表达式的公共例程。其中，可变状态被最小化。

原理

　　最小化可变状态允许提升多线程执行环境中的数据局域性，减小数据争用和锁定的必要性，便于使用细粒度锁(fine-grained lock) 而不是 GIL（global interpreter lock ，全局解释器锁）避免可变共享数据的修改引起数据竞争。

　　这对多线程执行环境的支持至关重要。因为 GIL 极大地影响程序中不同上下文上的表达式并行求值性能，一旦被引入，即难以通过不破坏 API 兼容性的重构消除。因此，从头避免 GIL 是比从现有设计中移除 GIL 更可行的做法。

数据结构

　　AST 节点上可指定对象语言中的对象和表达式对应的内部表示的具体数据结构。

　　为支持一般的 AST ，项节点具有子节点和值数据成员(value data member) 。

　　值数据成员保存对象的宿主值(host value) ，是实现中和基础语言对象对应的 C++ 值。

　　宿主值具有不同的类型，通过类型擦除(type erasure) 的方式在特定的 C++ 对象中保存，称为后者的目标(target) 。一个对象至多只能有一个目标。目标可能间接嵌套（即对象 x 的目标 y 可以有目标 z ）。只有符合特定条件的目标才构成宿主值。这种机制允许运行时确定对象的类型而实现 Unilang 中的动态类型。

　　宿主值和对应的 Unilang 对象动态类型的具体关系，参见以下关于类型映射的描述。

　　本设计中，AST 的节点和表示对象的节点共用数据结构，统称为项节点(term node) 。项节点的每个子节点和节点具有相同的抽象数据类型，是一个子项(subterm) 。项节点包含子项的容器，以允许具有不同数量的子项。

原理共用数据结构避免规约时引入分阶段的(phased) LIR 简化设计和实现，提升可扩展性。

　　为实现语言规范要求，表示的对象的项还需要具有标签(tags) 。在作为 AST 而不作为对象的表示(representation) 使用时，项的标签被实现的具体步骤占用，但不得影响作为求值结果的对象中的标签的正确性。

原理标签本质是运行时每对象相关的元数据。因为基础语言不提供直接可用的类型系统辅助元数据管理，为避免过大的开销，元数据中只能具有有限的状态，且被用于构建类型系统。如 C++ 的值类型(value cateory) 在此以表示对象的项中的标签体现。

　　典型的对象的内部表示只使用项的子项和值数据成员之一。这种表示称为正规的(regular) 。特定的对象可具有非正规(irrgular) 表示，即同时要求具有非空的子项和值数据成员。

资源管理

　　本设计中没有 GC（garbage collector ，垃圾回收器）。取而代之，解释器和本机语言互操作的实现应使用显式分配和 C++ RAII 兼容的方式管理资源。

原理主要原理和 Unilang 设计不要求 GC 一致。全局的 GC 限制了确定性的资源释放，使一般的 RAII 无法实现。GC 更有利于吞吐量，而不利于 Unilang 要求支持的客户端应用。GC 可在需要时被扩展实现引入，但在一个现有的已依赖 GC 管理资源的实现中修改而不是重新资源管理的设计以排除 GC 通常没有可操作性。

　　这种机制强调明确的资源所有权。本设计中，项节点对子项的容器和值数据成员具有独占所有权；子项的容器对每个子项具有独占所有权；这些被占用子对象的对象是项的子对象（尽管严格地说，在 C++ 意义上不一定构成作为类类型对象的项的子对象）。一般地，值数据成员对宿主值具有所有权，但这可能被 C++ 层次上改变（如使用共享所有权的智能指针作为宿主值）。此外，环境对变量绑定具有所有权（因此本实现基于 CEK 而不是 CESK 抽象机，尽管也可以使用 C++ 的分配机制利用自由存储(free store) ）。

　　复制表示对象的项时，若标签指定项可被转移，可按需转移作为源的项对象具有所有权的子对象；否则，宿主语言层次上可直接复制项对象或其子对象。

求值规约

　　一个对象语言中的表达式被表示为 AST 的一个项被规约，在所有规约步骤结束后，对应位置的项上剩余的重写结果就是这个表达式的求值结果；规约步骤中进行的副作用，即为表达式求值的副作用。

　　以此作为前提，求值算法被表达为已知表示表达式项上的规约。实现求值算法要求的表达式的求值变换的规约是求值规约。其它规约称为管理(administrative) 规约。

原理管理规约可隐藏一些不在对象语言中出现的状态。这也给扩展 AST 解释器为编译实现而不需要引入其它分阶段的 IR 提供可能性。

注释管理规约实现的规则子集是强规范化的(strongly normalized) 。这保证符合语言规范的程序，除非程序自身的语义包含非终止条件，解释器的规约步骤总是保证可终止。

　　和上下文保存当前动作以实现 CEK 抽象机的 K 的作用类似，上下文总是保持当前项的引用和当前环境的非空指针，以满足 CEK 抽象机可以确定 C 和 E 状态的要求。异步规约中，在确定需要和先前状态不同的表达式规约时，从上下文取项的引用作为规约函数的参数，同时上下文自身的引用也作为可选的参数。

原理提供项的引用实质在逻辑上是冗余的，在典型的 C++ 实现中可能浪费解释器运行时的寄存器带宽。但这和上述的规约函数设计的理由类似，同样能减少异步和同步规约的混合实现，且有利于扩展性，实际并不必然增加明显的开销。

　　求值规约确保作为范式的求值结果的内部表示符合可在对象语言中出现的对象的表示。

　　平凡(trivial) 规约表示可此次规约中剩余的步骤忽略而不改变规约语义。被除非另行指定，规约过程中的非正规表示是平凡的(trivial) 。

规约函数

　　一次规约局限一个项上修改实现重写，这个项称为当前项(current term) 。当前项上一般包含一系列规约的步骤，即一轮规约迭代。

　　规约步骤的基本形式以 C++ API 的规约函数(reduction function) 形式表现（可以是签名兼容的 C++ 函数对象）。规约函数接受项节点的引用，同时表示输入和重写的输出；可选地接受上下文引用或其它函数；返回一个表示这一步规约结果的值。

原理项共用输入和输出的设计类似底层体系结构的寄存器，但它是结构化的（允许不限数量的子项），同时允许运行时动态分配子项。这种设计和底层机器表示并不相近而常常不具有性能上的优势（特别地，运行时可能需要分配新的项节点），但相对其具有的灵活性而言，也没有特别大的劣势。在强调性能的场合，若需局部优化，可替换局部的其它数据结构（一般同时使用 C++ 本机实现）。在规约函数直接接受项节点引用而不像传统 CEK 模型的典型实现那样只保留上下文引用，允许混合异步（一般情形）和可预测调用深度时的同步（特化情形）规约步骤，同样有利于扩展性。

　　规约函数的返回值称为规约状态(reduction status) ，描述一次规约调用操作结束后的状态的结果，包括以下几种情形：

部分规约(partial reduction) ：需要继续进行规约。表示不是完整的求值规约，也可以仅是管理规约。一般仅用于异步规约。
中立规约(neutral reduction) ：规约成功终止，且未指定是否需要保留子项。
纯值规约：规约成功终止，且不需要保留子项。
非纯值规约：规约成功终止，且需要保留子项。
重规约：当前项需重新进行规约迭代，而首先需要跳过当前项上当前一轮迭代的剩余的规约动作。

　　纯值规约的正规化操作对子项进行清理(cleanup) ，使子项的容器被清空。

原理一个表达式的求值规约可包括不同的步骤，这些步骤可能明确作为中间表示的项表示的是对象，而具体对象的正规表示可能只有值数据成员而要求不存在子项。此时，项需要被清理以符合要求。考虑到子项的清空操作在宿主语言层面具有无异常抛出保证且不蕴含资源去配外的副作用，同一个项上的子项的清空之间是幂等(idempodent) 的，即一次和连续多次清空操作效果相同。再根据项对子项独占所有权可有推论：一个项上的连续的清理操作可合并为一次而不改变程序的可观察行为。同时，只有求值规约终止，项才表示求值结果。结合以上两点，清理操作一般可被推迟到求值规约的最后一个求值步骤。规约结果中指定了这些不同的要求，允许合并同一个表示同一个被求值表达式的项在一次求值规约中的多次清理操作。

名称解析

　　求值规约中，名称解析实现求值算法把符号类型的值转换为对象引用值的过程。

　　这个过程要求参照上下文的当前环境的绑定以取得可用于查询名称是否在作用域中存在。这个过程原则上是抽象的，不要求依赖环境内部的数据结构，所以调用环境提供包含实现逻辑的接口实现。

函数调用

　　函数调用机制实现语言规范要求的合并子调用和参数求值。

　　为实现语言规范约定的求值算法，函数调用首先总是需要求值第一个子节点，以这个子节点表示的第一个子表达式的值作为函数对应的合并子。第一个子表达式称为头表达式(head subexpression) 。这种求值表达式时总是先求值头表达式的取得的结果称为 WHNF(weak head normal form) 。

　　合并子（或者其它在合并子位置上起到合并子作用的 C++ 本机数据结构）保持一个上下文处理器(contextual handler) 。上下文处理器本质上和规约函数兼容的 C++ 函数对象。在规约取得 WHNF 之后，项由上下文处理器进一步处理，实现具体合并子被调用时蕴含的程序逻辑。若合并子是应用子，则在进一步处理前，上下文处理器首先负责保证 WHNF 中剩余的子项（表示函数的各个实际参数）被求值。按语言规范，这些子项之间的求值顺序未指定，实现也不提供附加保证。

原理尽管和调用的逻辑无关，WHNF 中已经被求值的头表达式仍在上下文处理器可见，而不被移除；上下文处理器应保证这些项最终被移除，而不影响调用的求值结果的表示。这允许上下文处理器把头表达式所在的子项挪作它用，在某些情形避免附加的子项分配。

　　为支持安全性保证，不指定允许非安全操作的函数，默认返回时进行返回值转换。这在规约中表现为提升(lift) 项：若项表示引用值，则重写项为引用值引用的对象的值。这个过程中，对象被复制初始化——可能被转移或被复制。

　　函数调用包含 WHNF 的求值结果是函数左值（合并子的引用值）或右值（合并子对象）的情形。对后者，实现应确保合并子对象具有足够的生存期，在被调用时生存期没有结束。

原理这允许合并子的静态环境具有足够长的生存期，其捕获对象不会在合并子调用时被释放。这也适合 C++ 实现的合并子的上下文处理器（可以是带有状态的函数对象或捕获对象的 lambda 表达式）。

　　用户程序可以通过特定的操作构造合并子。定义合并子的形式参数和变量等义等操作共用相同的语法，即通过形式参数树指定需在函数体或初值符求值前初始化的变量。构造合并子时对形式参数树进行检查。调用合并子时，省略检查以提升性能。与此不同，定义变量时，变量绑定前直接对被定义的变量的形式参数树进行检查。

　　当前设计中，变量绑定和名称解析逗不会被缓存，这可能在以后实现以进一步优化用户定义的合并子的调用性能。

PTC（proper tail call，真尾调用）

注释 PTC 不仅仅在对象语言中的函数调用使用，而且在 eval 等直接求值的情形下也被使用，这不一定对应程序语法上的递归重入。[Cl98] 中以 Scheme 的子集为对象语言定义的 PTR(proper tail recursion) 更广，但其形式上本质相同，除了本设计因为支持链式环境（因为语言规范要求一等环境对象支持父环境）而无法实现比一般 PTC 更强的 SFS(safe for space) 保证。

　　为支持 PTC 要求，基础语言中的函数调用一般包含 TCO（tail call optimization，尾调用优化）。这不需要全程序表示的重写（典型地，CPS 变换）。本设计中，这通过使用特殊的 TCO 异步规约动作作为抽象机中存储的当前上下文实现。

原理这种设计一般并不是最高效的，但避免依赖具体体系结构的实现细节，也避免依赖 CPS 或者 ANF 需要全程序变换和对各种 IR（乃至对象语言设计）附加限制，同时具有相对较好的互操作兼容性。

注释 TCO 动作和 PODI 2020 公开的一篇论文中的 extra continuation frame 有相似之处，但本设计之前没有参照其它设计，具有此设计没有的一些特性（详见以下的幂等操作的描述），且不使用编译实现。

　　典型地，要求实现 PTC 的上下文可包含以下操作序列：

保存当前的环境并更新环境。
分配活动调用关联的临时对象（函数右值）。
可选地请求异步重规约。
异步规约被替换或求值的项。
可选地提升项（变换函数应用替换的结果是非引用）。
结果的正规化。

　　对应的不支持 TCO 的异步实现中，以上每个操作都可以是一个规约动作，随嵌套调用的递增，随动作分配的资源被不同动作所有而无法被复用，导致嵌套尾调用的程序的空间复杂度总是不满足 PTC 要求。在 TCO 动作支持的实现中，支持操作复用：以上部分操作是幂等的，被合并到同一个 TCO 动作，以适当的顺序调用而允许不改变程序的可观察行为，但同时实现 PTC 要求的空间复杂度保证。某些同类的幂等操作之间不需要严格的顺序，这些操作可以被按种类重新排列并合并——以其中的一个操作代替在 TCO 动作生存期中发生的多次操作，而实现操作压缩(operation compression) ，其空间占用不随嵌套调用的层数增加。

　　不能重新被排序的同类的多个非幂等的操作和生存期相关，包括：

设置环境时，确保被设置环境的父环境的生存期；
分配临时对象时，确保临时对象最终能被及时释放。

　　这些操作在一个 TCO 动作的生存期内可能有多个实例，因为以下几个原因而无法合并：

语言规范要求生存期开始和结束的顺序影响程序的可观察行为；
对象模型相关的语义规则没有允许合并不同的对象；
需提供宿主语言互操作支持，一般无法证明实现这些合并不影响可观察行为。

　　TCO 动作初始化后负责同一个尾上下文的嵌套操作的资源分配和管理。这些资源包括进入嵌套调用时的活动记录（当前环境）和作为临时对象需在整个 TCO 动作生存期存活的函数右值（函数调用求值的 WHNF 的头表达式求值结果）。

　　在需要 PTC 的程序执行上下文中，首先确保 TCO 动作存在（若逻辑上可确保一定存在，可不附加检查 TCO 动作是否存在，直接按 TCO 动作访问抽象机的上下文对象中的当前动作），然后用 TCO 动作提供的操作向其中添加资源。和普遍使用 GC 的设计不同，此处解释器实现需要显式地插入帧压缩(frame compression) 操作以回收 PTC 不需要继续使用的之前嵌套调用时引入的环境和被环境对象所有的其它资源，实现操作压缩。

　　符合以上要求的 TCO 动作蕴含：

当前项的引用。
当前项作为临时对象的守卫（使用 RAII 确保在异常时能释放资源，下同）。
操作结果请求状态（即要求尾调用后进行项提升的次数）。
已知的受到 TCO 管理而具有所有权的作为临时对象的函数对象。
当前处理的尾环境的守卫。
保存当前活动记录帧（环境）的记录列表。

　　[Cl98] 指出被分析的对象语言中，非尾调用的上下文只有参数的求值。Unilang 基础语言没有增加此种分析方法不适用的构造，因此结论相同。不过，为了减少 TCO 动作的创建开销，本机实现可以直接跳过判断，而不依赖 TCO 动作。PTC 转而以本机实现保证。

注释因为 C++ 自身不支持 PTC 保证，这里通常使用循环而不能使用 C++ 递归调用。

诊断

　　语言规范要求的错误都实现为 C++ 异常。

　　为区分不同的来源，设计了不用的异常类。

　　REPL 捕获异常并输出错误消息，以指示不同的错误。

类型映射

　　除列表的 Unilang 对象在类型擦除后被统一保存在 ValueObject 中。

　　宿主值满足以下类型映射关系（部分没有被语言规范明确要求）：

TermNode ：列表和非列表对象。
- TermNode 中保存 TermNode 类型的容器。因为需可靠地支持不完整类型（在 TermNode 中保存递归类型），不能使用 ISO C++17 以前的标准库容器。
  - 虽然主流实现的扩展（包括 libstdc++ ）在之前的序列容器中都已经支持不完整类型，但是本项目严格限制依赖非标准扩展。
- TermNode 保存 ValueObject 类型的值数据成员 Value 。
  - ValueObject 是支持类型擦除的类型。它可能是空值，或具有一个目标类型(target type) 类型的宿主对象(host object) ，作为在宿主语言（即 C++ ）中保存的宿主值(host value) 的表示。
- TermNode 还包含枚举 TermTags 类型的标签，作为指定对象可能作为临时对象、只读或其它状态的元数据。
- TermNode 在表示基础语言中的对象以外，也用于其它中间表示。参见以下章节。
- TermNode 可以作为对象的表示。
  - 当值数据成员是空值时，对象是列表（右值）。列表的元素使用容器中的子节点表示。
  - 非列表的对象可以使用值数据成员表示。
  - 只使用列表的子节点或值数据成员之一的对象表示为正规表示。其它表示是非正规表示。
  - 非正规表示中，节点具有超过一个子节点，在其中的一个子节点具有 TermTags::Sticky 标签。
    - 因为 TermTags::Sticky 标签只占用一个位，又称为粘滞位(sticky bit) 。
    - 具有粘滞标签的项是粘滞项(sticky term) 。
    - 表示对象的节点的子节点若具有粘滞项，则仅应存在一个。
    - 粘滞项之前若存在子节点，则整个节点表示一个非正规列表(irregular list) ，这些子节点是节点的前缀(prefix) 。前缀是最后一个元素之前的（可能有多个）元素的表示。
    - 粘滞项和之后的子节点以及值数据成员共同构成一个对象的非正规表示。若整个节点表示非正规列表，则这些成员构成最后一个元素的表示。
ValueToken ：#inert 的宿主类型。
TokenValue ：符号。
shared_ptr<Environment> ：环境强引用。`
EnvironmentReference ：环境弱引用。`
TermReference ：引用值。
ContextHandler ：本机函数类型。
- ContextHandler 是支持类型擦除的函数类型。类似 std::function 空值调用时抛出异常。非空值具有目标类型的函数对象。
- 目标类型为 FormContextHandler 类型的 ContextHandler ：合并子。
string ：字符串。
bool ：布尔类型。
bool 以外的 C++ 整数类型：整数。
C++ 浮点类型：浮点数。

　　宿主类型可同时表示非宿主值。特别地，在表示 Unilang 中的列表值之前，TermNode 对象即可表示语法分析结果（见以下读取的描述）。这允许直接复用而非另行分配对象，有利于简化实现并提升性能。

非平凡非正规表示

　　平凡的表示可在规约中被转换，因此以下只关心非平凡的非正规表示。

　　表示对象的内部表示的项非平凡非正规表示只在以下情形存在：

特定的子对象引用：
- 合并子子对象引用（通过合并子的引用值解包装构造）。
- 子有序对引用（其中子列表引用可通过带有 & 引用标记字符的结尾绑定构造）。
不具有正规表示的列表对象。

　　以上表示的子对象引用中，项的值数据成员持有 TermReference 类型的值，保留某个子项的引用。子对象引用的项的子项数应为 1 ，该子项持有 shared_ptr 的实例的非空值且其指向的对象和值数据成员持有的 TermReference 值的 get() 结果应引用同一个项对象。

　　因为广义列表无环，不具有正规表示的列表对象是无环非真列表。

　　无环非真列表是不属于其它情形的非正规表示可表示的一等对象，具有至少一个子项表示一等对象。

　　不考虑所有权时，无环非真列表总是能被表示为一个元素和一个非列表元素构成的有序对。

　　类似真列表：

无环非真列表不支持环。
无环非真列表对其中的元素具有所有权，但其中的元素的销毁和释放顺序未指定。

　　除最后一个元素外，无环无环非真列表的元素依次由表示无环非真列表的项的子项表示。

　　若最后一个元素能以单一的 ValueObject 值表示，则表示无环非真列表的项的值数据成员是这个元素的表示；否则，表示无环非真列表的项子项中的若干个后缀和值数据成员是这个元素的表示，其中第一个子项的标签具有粘滞位。

　　表示一个无环非真列表的节点在具有粘滞位的子项前的子项是它的子节点前缀(prefix) 。其它节点的所有子项是它的子节点前缀。

　　推论：列表的前缀元素是表示它的项节点的子节点前缀对应表示的元素，即其中忽略非列表有序对最后元素后的剩余元素。

原理

区分有序对和其它非平凡非正规表示可直接通过检查项中是否存在带有粘滞位的第一个子项。这一操作的时间复杂度是 O(1) 。
对象的前缀元素是列表的前缀元素的保守扩展。两者的表示和 TermNode 子节点前缀对应。

注释 cons 对的所有权及初始化和销毁的相对顺序和仍遵循作为其表示的项节点对其子对象的关系。

解释器核心结构

　　本节概述作为 REPL 的解释器核心的顶层结构。

读取

　　当前输入的来源仅支持以行为单位的标准输入。

　　输入被作为字符串，经过词法分析器分解为词素序列，然后用简单的语法分析器匹配 ( 和 ) ，若不匹配则抛出异常。

　　之后，检查中缀变换，替换 ; 和 , 为函数。

　　为避免宿主实现过深嵌套调用的未定义行为，语法分析使用单独的栈而不是 C++ 调用栈递归解析表达式，中缀变换也使用类似的单独的数据结构遍历表达式。

　　解析后输出 TermNode 类型的对象表示 AST 。

求值

　　求值部分的核心为 CEKS 抽象机，把表达式求值作为项重写系统(term rewriting system)的规约(reduction)。

　　求值过程中的抽象机中的表示使用本文档的约定。表示保持相对的稳定，以支持和 C++ 互操作。这种互操作允许语言中的特性以 C++ 代码的形式实现，即本机实现(native implementation) 。而通过指定基础语言代码进行求值，也可以实现派生特性的非本机实现。

　　以 TermNode 对象表示的抽象语法树直接被作为被求值的表达式，按实现求值算法的规约步骤，重写为符合语言规格的仍以 TermNode 表示的输出。

　　为避免宿主实现过深嵌套调用的未定义行为，可能递归重入的操作使用异步调用实现。

打印

　　默认情况下 P 仅包含 E 的副作用蕴含的输出。

　　为便于调试，环境变量 ECHO 用于启用 REPL 回显，相当于以隐含的求值结果是参数，继续求值 display 函数。

库特性实现

　　对象以本机实现。

　　部分标准库操作使用本机实现。

　　其它操作利用 Interpreter 提供的接口，直接以 Unilang 源代码字符串作为输入进行求值，得到派生实现。

基础环境

　　基础环境以新建环境并逐一初始化其中的标准库绑定的形式实现。

　　初始化的标准库特性中，一部分是本机实现。

详细设计

　　本章介绍实现中的 API 的主要功能设计。

　　正式的 API 在主命名空间 Unilang 中。不公开的内部实现在其中的未命名(unnamed) 命名空间中。

外部实体引用

　　外部依赖包含命名空间 std 和 ystdex 中的实体，分别由标准库和 YSLib 提供。

　　以下声明被引入到主命名空间中：

using ystdex::byte;
using ystdex::size_t;

using ystdex::lref;

using ystdex::any;
using ystdex::bad_any_cast;
using ystdex::function;
using ystdex::make_shared;
using std::pair;
using std::shared_ptr;
using ystdex::string_view;
using std::weak_ptr;

namespace pmr = ystdex::pmr;

　　大多数声明和 ISO C++17 的同名声明一致，只有 lref 是作为 ISO C++2a 的 std::reference_wrapper（相比之前的标准版本，允许不完整类型）的简写。

　　对应于 ISO C++17 的 std::pmr 中的实体在需要被实现使用时，以类模板的形式被引入，如：

template<typename _tChar, typename _tTraits = std::char_traits<_tChar>,
	class _tAlloc = pmr::polymorphic_allocator<_tChar>>
using basic_string = ystdex::basic_string<_tChar, _tTraits, _tAlloc>;

using string = basic_string<char>;

　　此处 string 不同于标准库的 std::string 。因为历史原因，ISO C++ 的异常类必须使用后者，需要注意区分。

　　类模板 sfmt 是类似 std::sprintf 的，但返回 string 而不是指定参数的格式化字符串例程。

　　类型 ValueObject 是类似 ISO C++17 std::any 的对象，在此被作为中间表示的基本对象类型，可关联各种的运行时类型的值即目标。目标是 Unilang 中的值关联的 C++ 宿主值。默认初始化的 ValueObject 具有空值，不关联目标，目标类型为 void 。

词法处理

　　词法分析的规则是极简的：主要通过空白符拆分记号。记号直接同词素作为字符串处理，仅当必要时区分类别。

函数 CheckLiteral ：检查参数并消除提取可能包含的单引号或双引号。
函数 DeliteralizeUnchecked ：假定字符串参数存在引号，返回去除引号的字符串参数。
函数 Deliteralize ：返回去除引号的字符串参数，或当不存在引号时为 char() 。
函数 IsGraphicalDelimiter ：判断字符是图形分隔符：括号、逗号或分号。
函数 IsDelimiter ：判断字符不是图形字符（由 std::isgraph 定义）或是图形分隔符。
类 ByteParser ：分析字节流，提取符合词法要求的词素。
枚举 LexemeCategory ：词素类别：符号、代码（单引号字面量，当前未使用）、数据（双引号字面量）或扩展（派生实现中未归类字面量，当前未使用）。基础语言中其它字面量在此统一处理为符号。
函数 CategorizeBasicLexeme ：归类输入的词素，取词素类别。

异常

　　实现可使用以下异常类，具有以下继承关系：

UnilangException ：异常基类，派生自 std::runtime_error 。
- TypeError : 类型错误。
  - ListTypeError : 列表类型错误。
  - ListReductionFailure ：列表规约失败，用于合并子调用。
- InvalidSyntax : 语法错误。
  - ParameterMismatch ：参数不匹配。
    - ArityMismatch : 元数不匹配。
  - BadIdentifier ：标识符错误：用于名称解析。

项节点

　　项节点是语法处理接受的输入和输出类型，也被之后的求值使用，表示被规约项。

NoCainterTag ：标签类型，用于初始化没有子节点的 TermNode 。
TermNode ：项节点类型。
- 包含递归的容器类型 Container ，使用兼容 std::list 的 ystdex::list 实现，以避免 ISO C++17 前 std 关联容器使用不完整类型作为模板参数的未定义行为（尽管 libstdc++ 可使用，但未明确支持），并提供较好的兼容性（libstdc++ 直至 GCC 5 没有实现部分分配器相关的接口）。
- 包含上述容器类型的子节点（也是被归约项的子项）容器对象。
- 包含 ValueObject 类型的 Value 对象：值数据成员，主要用于叶节点。
TNIter 和 TNCIter ：TermNode::Container 的迭代器别名。
节点分类谓词：接受 TermNode 参数，判断是否符合特定的构造。节点中应不存在环，可表示真列表(proper list) 。
- IsBranch 判断节点是枝节点(branch node) 或非叶节点，即具有子节点的节点。
- IsBranchedList 判断节点是分支列表节点(branched list node) 同时是枝节点和列表节点。
- IsEmpty 判断节点是空节点(empty node) 同时是叶节点和列表节点。
- IsExtendedList 判断节点是扩展列表节点(extended list node) 是枝节点或列表节点。
- IsLeaf 判断节点是叶节点(leaf node) ，即不具有子节点的节点，表示空列表或不具有子节点非列表。
- IsList 判断节点是列表节点(list node) 是值数据成员为空的节点。
项节点访问函数模板：
- Access 按指定目标类型访问节点的值数据成员。
- AccessFirstSubterm 断言为枝节点并访问第一个子项。
- MoveFirstSubterm 转移第一个子项。
- ShareMoveTerm 转移到 shared_ptr 实例中。
- RemoveHead 移除节点的第一个子节点。
函数模板 AsTermNode 构造没有子节点的以特定类型的值为值数据成员的节点。
函数模板 HasValue 判断节点的值数据成员是否等于指定的参数值。

语法处理

　　因为使用的语法是上下文无关的简单语法，直接使用手工实现的分析器，主要逻辑只包含匹配括号。

仿函数 LexemeTokenizer 是词素标记器：转换输入为以词素为作为值数据成员的节点。
函数模板 ReduceSyntax 遍历迭代器序列，递归匹配括号，把输出添加到参数指定的节点。若多余左括号则抛出异常。添加节点使用参数指定的标记器(tokenizer) （默认为 LexemeTokenizer ）。需要适应不确定嵌套层数的输入，所以使用单独的栈而不是直接使用 C++ 递归函数实现。

项和值的访问接口

　　使用 TermNode 作为项时具有一些公共的操作。

类型 TokenValue ：记号值，和 string 不同但可互相转换的类型，作为符号的宿主类型。
函数 TermToNamePtr ：访问作为记号值的项的值数据成员，失败时结果是空指针。
函数 TermToString ：转换项为字符串表示，主要用于输出错误。
函数 TermToStringWithReferenceMark ：同上，但包含区分引用值的标记。
函数 ThrowListTypeErrorForInvalidType ：抛出类型检查失败时的列表类型错误。
函数 TryAccessLeaf ：尝试访问特定类型的值数据成员，失败时结果是空指针。
函数 TryAccessTerm ：同上，但非叶节点视为失败。
类型 AnchorPtr 作为环境内部保存的引用计数数据指针。
类 EnvironmentReference 表示环境引用，是 Unilang 环境弱引用的宿主类型。
类 TermReference 表示项引用，是 Unilang 引用值的宿主类型。
- TermReference::get 取引用的项。项引用保持被引用项来源的环境的引用计数，调试模式下默认可启用安全性检查。若锁定的环境引用为空，则检查失败。
函数 ReferenceTerm 当参数表示的项的值数据成员是引用值时结果是表示被引用对象的项，否则是参数。
用于兼容引用值和非引用值项的访问的实现内部使用的便利接口：
- ResolvedTermReferencePtr
- ResolveToTermReferencePtr
- TryAccessReferencedTerm
- ResolveTerm
用于检查项不是列表的内部使用的便利接口：
- CheckRegular
- AccessRegular
- ResolveRegular
仿函数 ReferenceTermOp ：功能同函数 ReferenceTerm 。
函数 ComposeReferencedTermOp ：复合函数和 ReferenceTermOp ，用于在不支持引用值的操作上添加间接访问被引用对象的支持。

基本规约接口

　　规约是语义处理的核心，转换项为其它的项，以完成求值。这里提供规约接口依赖的类型。一部分规约例程和上下文无关，在这里一并提供。

枚举 ReductionStatus ：规约结果。用于规约后对项的处理，如正规化（参见以下描述）。
函数 CheckReducible ：判断规约结果是否可继续规约。
函数 RegularizeTerm ：正规化项：清理子项使其成为一个非列表。
项提升操作：以 Lift 为前缀的函数，用其它参数决定的项替换到第一个参数指定的项，前者通常是后者的* 规约函数：以 Reduce 为前缀且以 TermNode& 为第一个参数类型的函数，实现小的规约步骤，转换项并返回规约结果。

上下文接口

　　上下文在规约中起到关键作用。上下文保存动作作为将被执行的规约步骤。当上下文中动作为空时，规约终止。

类 Environment ：环境。包含表示变量绑定和父环境的数据成员。类型 shared_ptr<Environment> 是 Unilang 环境强引用的宿主类型。
类型 ReducerFunctionType ：表示动作的函数类型 ReductionStatus(Context&) 。
类型 Reducer ：规约器，兼容 ReducerFunctionType 的多态函数调用包装，是动作的一般表示。
类型 ReducerSequence ：Reducer 的序列，表示一系列动作。
类 Conext ：上下文，包含当前环境、当前动作、下一求值项的引用和规约中需要保存的其它的公共状态，也提供解释器使用规约的内部入口。替换当前环境的操作称为切换(switch) 。
- 父环境通过子对象 Parent 引用。这个对象具有 ValueObject 类型，可支持不同类型的父环境的表示。父环境最终通过环境强引用访问。
- 上下文实现环境查找的逻辑。查找父环境取环境强引用时，调试模式默认附加检查。若锁定的环境引用为空，则检查失败。
类型 ContextHandler ：上下文处理器，兼容签名为 Reduction(TermNode&, Context&) 的规约函数的多态函数调用包装。
函数模板 AllocateEnvironment ：分配环境。
函数模板 SwitchToFreshEnvironment ：创建新环境并切换当前环境。结果是被切换的先前上下文中的当前环境。
函数模板 EmplaceLeaf ：在环境的变量绑定中插入对象。
函数 ResolveEnvironment ：以可能作为环境的宿主类型访问参数指定的值数据成员或项，失败时抛出类型错误异常。
类 EnvironmentSwitcher ：切换环境的便利接口，作为守卫(guard) 以支持异常安全的对当前环境的切换操作。
类型 EnvironmentGuard ：包装 EnvironmentSwitcher 的守卫。

其它支持接口

枚举 ValueToken ：单元类型(unit type) 的实现，表示 #inert 的宿主值。
类 Continuation ：续延(continuation) ，保存 ContextHandler 对象的异步规约动作，调用时从上下文的下一求值项恢复被规约项作为参数。
函数 ThrowInsufficientTermsError ：抛出子项不足的异常。
类 SeparatorTransformer ：转换中缀分隔符。用于把逗号和分号替换为前缀形式的内部表示。
类 FormContextHandler ：形式上下文处理器。用于构成合并子的宿主类型，即以 FormContextHandler 作为目标类型的 ContextHandler 。
- 在 FormContextHandler 中存储一个非负整数包装值(wrapping value) 表示应用子求值到底层操作子前需要对实际参数求值的次数。对大多数应用子，这个值等于 1 ；对操作子，这个值等于 0 。
注册函数用的便利接口：基于上下文处理器，向指定的对象（上下文或环境）添加函数，用于 Unilang 标准库的实现。
- WrappingKind
- RegisterHandler
- RegisterForm
- RegisterStrict
- UnaryExpansion
- RegisterUnary
函数 BindParameter ：实现参数绑定。
- 支持 Unilang 函数调用和 $def! 中的递归模式匹配。
- 绑定匹配后以操作数中的实际参数初始化作为形式参数的对象。
- 初始化时，根据操作数中的 TermTags 等状态进行复制消除(copy elimination) ，避免创建多余的对象副本。

求值算法的实现

　　以 ReduceOnce 为前缀的函数实现了主规约算法，这是对应 Unilang 求值算法的全局规约实现。具体步骤的其它实现包括 ReduceCombined 等。

标准库操作的本机实现

　　因为是基本的特性或者，由本机实现比非本机实现更直观容易，一些标准库操作的底层操作逻辑以 C++ API 的方式提供，包括以下规约函数：

If
Cons
Eval
MakeEnvironment
GetCurrentEnvironment
Define
VauWithEnvironment
Wrap
Unwrap
Sequence

标准库实现

　　初始化解释器时初始化上下文。其中，初始的当前环境是基础环境。基础环境中初始化绑定，就是标准库提供的绑定：

对标准库对象的初始化，直接修改 Context 的绑定。
对本机实现的应用子，使用 RegisterStrict 。
对本机实现的操作子，使用 RegisterForm 。
对非本机实现的库函数，使用解释器的 Perform 成员函数接受基础语言代码，其中包括 $def! 等可在当前环境添加绑定。

　　之后，切换当前环境到内部，完成对基础环境的隐藏。

解释器模块

　　解释器的 REPL(read-eval-process loop) 功能由解释器模块提供直接的支持。

　　解释器模块提供以下 API ：

类 SeparatorPass 提供过滤输入预处理。这个类的对象作为函数对象，把带有分隔符的输入中变换为不带有分隔符的 AST 。
类 Interpreter 提供 REPL 和其它解释器用户界面实现的直接支持。
- 这个类的初始化时创建必要的上下文（包括基础求值环境），并设置预处理和语法分析例程，并直接分配 REPL 需要的资源（如 REPL 被规约项）。
- 这个类根据 ECHO 环境变量是否非空指定 REPL 是否自动回显。
- 这个类支持读取文件加载为翻译单元的功能。
- 成员函数 Read 是读取源代码并分析为 AST 的入口。
- 成员函数 ReadFrom 同 Read ，但支持指定使用的上下文，用于加载翻译单元。
- 成员函数 Evaluate 是求值的入口。求值转交给根上下文对象实现。
- 成员函数 WaitForLine 取外部环境的输入。输入预期为源代码形式。
- 成员函数 Process 在取得输入后完成 REPL 中循环内部的对一次输入的完整处理。这里的处理也包含捕获异常而转换为适当的错误消息。在退出时，它负责展开(unwind) 上下文的活动记录帧，以确保外部无法引用帧中间接引用的（生存期可能已结束的）临时资源。
- 成员函数 Run 是 REPL 的主入口。它调用 WaitForLine 取得输入，并调用 Process 完成 REPL 余下的响应。这些调用在循环中重复，实现 REPL 。
函数 PrintTermNode 输出节点的内部表示。

解释器程序入口

　　解释器命令行程序启动时，初始化类 Interpreter 的对象。

　　在完成必要的标准库实现的初始化后，程序转交控制给这个其中的运行程序的函数，解析输入，并输出运行程序得到的求值结果。

　　为支持不同的程序运行形式（如 REPL 输入的行和脚本文件），运行程序的函数包括：

Run
RunLine
RunScript
RunLoop

诊断

　　当前实现中程序若引起错误，则抛出本机异常回到解释器入口并输出错误。

　　诊断的信息包含源代码信息和其它来源。

　　输出的错误可包含源代码信息。当指定非空的环境变量 UNILANG_NO_SRCINFO 时，不使用源代码信息。

　　之后，输出对剩余续延的追踪(backtrace) 记录，类似其它一些语言中出错时的调用栈的栈帧列表。首先输出的项是接近当前函数调用较近的帧，直到解释器入口。

　　续延追踪直接处理的是在上下文中保存的规约器序列。若规约器是续延，则作为续延输出；否则，根据其目标类型或者保存的附加的源代码信息，尝试输出其中可用的字符串以改进诊断消息提示的可读性。

　　对无法识别的续延，使用名称 ? 作为占位符。当前实现中，调试模式的解释器输出规约器的目标类型的类型信息（具体内容依赖 C++ ABI ）代替这个占位符，以便区分缺失规约器名称的不同规约器。

源代码信息

　　源代码信息包含两类：源代码名称和符号上的源代码信息。

　　解释器的实例保存当前源代码名称。对 REPL ，初始名称为 *STDIN* ；对脚本，初始名称为脚本文件的名称。

　　加载文件会改变当前源代码名称。

　　符号上的源代码信息通过词法分析时初始化。词法分析时，对记号的位置进行记录，保存在内部 ValueObject 对象的持有者同时保存 TokenValue 的值和对应的源代码信息。

　　保存的源代码信息在之后的求值跟随 TokenValue ，直至所在的 ValueObject 对象被销毁。在此之前，访问所在的 ValueObject 对象可取得对应的源代码信息。

　　处理 BadIdentifier 异常时，访问引起异常的符号，若存在源代码信息，则记录到异常对象中。

　　诊断处理 BadIdentifier 异常时，从中提取可选的跟随符号的源代码信息。

名称表

　　为维护可读性，解释器维护一个名称表，记录实现中已知的对象的名称。

　　这些对象主要包含：

特定类型的规约器的目标函数。
不随类型判断，而随调用处初始化时指定的名称的续延。

　　追踪续延记录时，若发现匹配名称表中已存在的项，则同时输出对应的名称。

尾操作符名称

　　求值符号时，若符号在合并子应用的操作符的位置，则其 TokenValue 值不被立即替换而是另行保存到所在的合并项的值数据成员。

　　对规约合并项的判断由当前规约项上下文保存的规约合并项指针比较确定。

　　规约列表保存当前被规约项指针为规约合并项指针，当确定第一个项是合并子而成功规约合并时，在调用合并子前清除上下文中保存的规约合并项指针。这保证不干扰操作数中包含其它的操作符的情形。

　　若第一个子项不是合并子时，列表规约失败，抛出异常。此时，对应的操作数位置的名称在被规约项的值数据成员中保存。直接提取这个值作为名称保存到异常消息，在诊断中输出。

　　对成功的列表规约，尾上下文初始化 TCO 动作时从合并项中提取保存的值数据成员，转移到 TCO 动作中。

　　当发生异常输出诊断时，TCO 动作作为已知类型的规约器的目标函数被访问。同时，TCO 动作保存的操作符名称也被尝试访问并在诊断中输出。若其中同时存在源代码信息，则对应的源代码信息也被一并输出。

互操作支持

　　解释器使用 C++ 语言实现，支持 C++ 和对应实现的二进制互操作。

内部表示

　　项的标签的具体的二进制表示不被依赖。

注释语言的语义规则允许（可证明不同时出现）时，实现中不同的标签可能复用相同的二进制表示。

　　为互操作目的，约定表示一等对象的值的表示总是满足：

项和子项的标签中不具有 TermTags::Temporary 。
项的标签中不具有 TermTags::Sticky 。
至多只有一个子项的标签具有 TermTags::Sticky 。
- 若存在这样的子项，它是非平凡正规表示的起始子项。此时，项的值数据成员应非空。

注释作为非一等对象，被绑定对象时临时对象时，项的标签可具有 TermTags::Temporary 。

语言实现演进方案

　　以 AST 解释器作为基础语言的实现，不仅相对容易实现原型和评估语言设计，同时也更容易扩充为编译器。

核心语言实现结构和选型策略概述

　　现有实现提供 AST 解释器。相对依赖字节码的解释器，AST 解释器和编译器的构造更加相似。不论何种解释器，编译器前端总是可以复用其中的词法和语法分析实现，但不总是能够复用其语义。

AST 中心架构

　　考虑到正确实现语义的支持几乎总是一个实用的语言实现工程中的主要开销。仅仅复用在此之前的前端(frontend) 的意义相对受到很大限制。因此，IR 向保持更多源代码信息的高层提升，会在实现相同的支持程度的前提下，使总体工程开销下降。而 AST 同时是这种 HIR 中最直接自然的选择，因为：

若没有 AST ，则需要具体语法树即分析树(parse tree) 保存（或至少暂存）结果，在接近 AST 的生成开销下又极大地提升实现的复杂性，并因为现实可实现性和实现开销的理由间接削弱源语言自身的可修改性。
AST 在逻辑上可以通过分析树直接删除部分细节简化（规约）得到，这种抽象使之允许语言的实现者能自主控制保持任意多（任意接近分析树结构）的，同时能控制和源语言的细节隔离。这种直接性使 AST 是逻辑上最简单的此类 HIR 。
不论是避免单独保存分析树和直接规约，都确保实现只需保存 AST 就能提供其它 HIR 的功能，使实现简单、可修改同时高效。
AST 能通过可控地删除细节设计，而作为多种不同源语言互操作的通用语(lingua franca) ，而使单一的语言实现支持多语言(polyglot) 交互环境，乃至同时成为多种源语言的高效的实现。

　　因此，以 AST 作为唯一的公开 HIR 并在语言实现中最大化复用的架构具有其它替代 HIR 无可比拟的优势。

　　GraalVM 是利用这种架构的一个工业级实现的主要实例，相对替代语言实现，它基本体现了以上所有主要的优势，其架构已支持多种语言的高效实现，多语言互操作不需要翻译 IR 的开销。其中，Graal 编译器接受的 HIR 就是 AST 。

　　不过，GraalVM 的 AST 是使用 Java 语言的数据结构，并不是 Java 语言中取得一等支持的语言特性。

　　与之不同，因为支持同像性(homoiconicity) ，Unilang 中的核心数据结构（如列表）直接能无开销地映射到核心运行时，而非单一的编译器组件。这允许：

进一步减少需要的 IR 到内部数据结构翻译的步骤和间接层。
- 因为源语言中的特性的要求，基线解释器和编译器中总是需要这种 HIR ，所以会被自然地复用。
对所有不同源语言实现默认总是使用统一的语言实现框架，通过更大的复用程度减少整体复杂性。
- 这类似 GraalVM 中的 Truffle 。但 GraalVM 中，Truffle 默认是可选，JVM 语言不经 Truffle 而直接使用 Graal 编译器 API 。
- 这种设计仅对非 JVM 语言添加 Truffle 作为适配层而减少冗余实现，但整体有两个层次（ Graal 编译器和 Truffle ）的 API 而较复杂，对全新的语言实现并不必要。
- 如有必要（一个合理理由是利用现有其它实现），仍然可以添加更多适配层，类似 Truffle 以上的 Sulong 运行 LLVM 位码而能复用 LLVM 的代码生成结果。

　　更进一步地，Unilang 原生对 eval 的原生强调使它能自然利用这种架构的 API 提供功能。这类似 GraalVM 中的关键方法 org.graalvm.polyglot.Context.eval ，但有以下不同：

因为默认假定源语言（即 Unilang ）中支持同像性表示的 AST ，不需要指定语言。
多语言混合的无翻译开销互操作粒度更细：允许基于表达式的求值而非函数调用。
因为不是便利接口，仅直接接受 IR（即 AST ）作为源代码单元，不分析源代码的序列化形式；语法分析被解耦到具有其它原语（如 read ）的 API 处理。

字节码

　　字节码是一种二进制序列化目标代码格式，因被序列化的存储为字节流固名。它可以直接作为被语言实现执行的 IR 。另一种强调运行时映像的实质相同的名称是位码(bitcode) 。

　　使用字节码作为 IR 的解释器通常称为“字节码解释器”，应注意这里解释仍然指针对高级源代码的解释，因此习惯上这不仅仅是指以字节码作为输入的解释实现，还包含从源语言翻译生成字节码的前端。以字节码作为输入的解释实现，习惯上称为（解释）执行引擎（如许多 ECMAScript 的直接实现），或者归类为运行时的一部分（如 CLR ）。其中，明确类似机器 ISA 的执行引擎被称为虚拟机（如 JVM ）。

　　完整复用包括字节码方案在内的此类实现的进一步优化方式较为有限，主要包括：

在字节码以上添加更多层 IR ，加入优化编译器遍，优化后翻译到原有的字节码。
在字节码以下添加更多层 IR ，改进现有执行引擎，翻译成本机代码（本机 JIT 编译）。
使用字节码实现的语言实现解释引擎，然后编译解释引擎自身，生成本机执行代码。
把执行引擎或整个解释器改由硬件实现。

　　本质上，字节码执行引擎是一个后端(backend) ，这和本机（机器）代码（以处理器作为硬件实现的后端）在功能上是重复的。这也显示，生成本机代码的传统编译器，复用字节码作为编译器的 IR ，也需要基本抛弃字节码执行引擎，然后改用生成本机代码的后端取而代之。而经验表明，专为高级语言设计的字节码通常因为缺乏具体机器的特征或针对机器特性的可扩展性，不适宜直接作为本机编译器的编码。传统 AOT 编译器框架，如 GCC 和 LLVM ，无一都是专用 IR 。

　　所以，许多改进为编译器的字节码解释器实现，都选择添加 IR ，使用本机 JIT 编译。但这样，字节码的可移植性就削弱了。而且，因为市场原因，这种策略的有效性在可移植性削弱之前就是有限的——二进制兼容性问题同样会困扰以字节码形式大规模部署的程序。

　　与字节码解释器不同，AST 和编译器结构上天然类似——最直接的编译器就是遍历 AST（等效的其它操作一般更复杂）然后对每个 AST 节点执行代码生成操作，差异仅仅是遍历 AST 的具体操作。虽然生成代码的操作可能相当复杂，但这基本上不影响相同部分的其它结构。

　　因此，AST 解释器经过少量修改，即可能成为传统的编译器。如果代码生成的是字节码，AST 解释器即构成了字节码解释器的前端。此外，这些操作也可以被替换为代码分析的操作，而成为代码静态分析器。这个意义上，AST 解释器框架实现了抽象解释器(abstract interpreter) 。作为比字节码原生更高级的表示，必要时 AST 可以代替字节码作为外部表示应用于程序部署；这能使被部署的程序具有近似源代码的可移植性和比源代码更小的开销——甚至允许用户自行扩展语言实现而不必破坏整体的二进制兼容性。

　　GraalVM 对 AST 编译器的复用和集成的相关解释器运行时（如 Sulong ）运行时可兼容不同的字节码执行，证明这种集成方案是实际有效的。

在线部分求值器(online partial evaluation)

　　少数实现如 PyPy 这样使用以上的编译解释引擎自身的字节码解释器改进方案。这类方案依赖 Futamura projection 的变种，使用语言子集（对 PyPy 即 RPython ），实现在线部分求值器(online partial evaluator) 进行优化实现。

　　这类方案的优点同时包括更有效的性能优化（如 PyPy 性能普遍优于 CPython ）。这个优势足够明显到可以直接以语言子集代替字节码而不考虑字节码解释器的演进路线。即便是传统的 AOT 编译实现（而不是为了改进字节码解释器），使用类似的方式对后端进行部分替代也是潜在有益的，因为在线部分求值器通常能直接复合多种优化变换，能比 AOT 编译器框架中的遍在编译效率上更有效，而允许在相同的资源限制下采用更激进的优化策略。

　　对已有的语言，这类方案的缺点主要是兼容性问题。而对新设计的语言，兼容性问题并不存在，但实现部分求值器本身对语言设计有一定的难度，同时一定程度上相对传统编译器有更大的工程风险。因此，本方案计划把这类方案作为改进包括编译器在内的语言翻译实现的长期目标，而不视图直接实现。

　　GraalVM 的 Graal 编译器中也使用部分求值，对包括 Truffle 实现的解释器和被运行的程序的 AST 表示整体作为目标程序进行优化，取得较好的性能。

解释器扩展

　　从 AST 解释器直接扩展得到编译器，没有上述的明显问题。这也是本方案首先提供 AST 解释器作为原型实现的原因之一。

　　关于解释器整体结构对之后实现的影响的一个现实的例子是，Ruby 语言的官方实现 CRuby 1.x 的 MRI 是 AST 解释器，2.x 的 YARV 是字节码解释器，3.x 的 3x3 实现 JIT 编译器时概念上重新切换到 AST 解释器而非直接基于 YARV 。以性能为目标，字节码的设计在不能被硬件直接利用时，很大程度是多余的。

基线

　　在开发和部署其它改进的实现后，现有的 AST 解释器原型仍计划被长期维护作为功能模型提供参考实现，以检验迭代过程中的稳定性。这种解释器被作为基线(baseline) 实现。这是因为无论使用哪种替代实现，都难以实现从 AST 解释器上直接扩展为解释执行程序以外的目的设计的动作（如调试支持）相当的灵活性。特别地，基于 TRS 的 AST 解释器允许修改规约项内的求值算法而不需要调整翻译器实现的主要结构，这是使用其它形式的 IR 不具备的。

整体路线

　　本设计整体使用替换后端为生成本机代码的传统编译器后端的演进方案。为了避免单独后端适配不同机器的工作量，本设计计划使用 LLVM 作为后端的默认实现。

　　由于基础语言设计中的特性具有的普遍的动态性以及 LLVM 提供的库不能直接和 AST 解释器同构并支持相同的功能，部分 AST 解释器实现的功能被保留为运行时直接实现。使用解释器替换的方案允许不调整解释器实现的其它部分，允许逐步地把添加使用 LLVM 的后端进行代码生成，具有较好的可修改性。

实现修改形式

　　新特性的添加和现有特性的改动都首先在基线解释器上实现，先行评估语言设计的改动对实现的稳定性、兼容性和有效性等的影响。

　　基线解释器中的本机原生（C++ 代码）实现的功能可能可以移出到动态库进行加载。为简化实现，暂无具体要求。

　　基线解释器中的包含非本机程序派生（基础语言代码）实现的库函数，可以移至外部文件在初始化或根据被解释的程序逻辑进行加载，以减少对解释器的修改需求，并优化解释器冷启动性能。现阶段对解释器内建和外部加载的代码没有其它区别，以后可指定不同的可移植性要求，以允许在解释器内建的派生实现可通过依赖特定于解释器实现的内部机制进行优化。

　　不论是核心语言还是标准库特性，内建在基线解释器的实现都可能考虑添加代码生成操作，把部分或者全部的执行逻辑被转换为 LLVM 后端支持的代码。如发现实现困难或者效果不佳等原因，不适合迁移使用代码生成实现，可以保持基线解释器的运行时实现，或回退修改设计和基线解释器实现，进行迭代。

　　为节约工作量和比对改动的有效性，现阶段基线解释器和代码生成实现共享命令行入口，实现为同一个程序（可视为解释器和编译器驱动）。现有解释器上直接接受命令行开关来切换到代码生成模式。

ABI 计划

　　暂定 ABI 非公开，但是需要确定，至少代码生成内部和互操作需要用。

基于简化 C++ 互操作和工程复杂性，默认依赖 Itanium C++ ABI 。（当然不都需要用上，至少相当多 C++ 旮旯特性在 Unilang 中没有对应。）
已知设计需要考虑的问题：
- 类型位宽。
- 对象的对齐需求。
- 函数调用约定。
- 和 C++ 本机异常互操作相关的问题。
  - 因为 C++ 不提供可移植的互操作，基线解释器没有实现支持。短期内可能无法其它替代方案（基于内建异常或续延等原生运行时机制）的支持。

类型语义

　　原则上基础语言不需要复杂的类型系统，而仅对求值算法要求的类型进行识别和反馈（检查类型错误）。更高级的类型系统通过用户程序由库实现。但是和互操作相关的部分要求需要支持附加的类型语义。同时，提供一些原生的支持可能有助于更有效和安全的实现。

　　要点：

许多类型相关的特性的语义上的工作被平摊到代码生成上（因为 HIR 到 LIR 自带整数位宽这样的基本类型信息，静态类型检查之后不需要特别处理，直接生成即可）。
类型标注：和现有的对象中的动态类型可能不同，主要是需要在面向代码生成的 IR 中保留一个位置用于提取类型信息。
- 需要确定一个类型检查算法涵盖 RFC 0 出现的类型标注，并考虑在基线直接支持。这部分支持可能会保留在运行时中，而不全部翻译为 LLVM IR 支持的类型（以避免受到限制）。
- 不论是解释器还是编译器前端都运行算法进行静态类型检查。静态类型检查的语法构造在 AST 中出现，然后可以在遍历 AST 时即时地检查而就地消费掉，在之后的 IR 中暂时不需要使用。
  - 继续保留类型标注可能有助于优化，但本方案因为主要的优化依赖 LLVM 后端，所以这部分暂时没有很大的必要。

其它支持改进

　　原则上其它功能也都是用库实现。但核心语言实现仍可能在特定任务中提供更有效的支持。这包括：

（非 RFC 0 直接任务）框架相关的支持。
- 首先需要确定除了类型系统外还需要增强哪些部分，再确定这些部分是否在基线解释器中实现更有利。
- 互操作 API 绑定自动化方案的可行性因为工作量问题（参照 Shiboken ）暂时没有明确的解决思路。

显式类型扩展

概要

　　核心语言中，因使用潜在类型(latent typing) ，类型在源代码是隐式的。为允许实现更好地提供类型检查等功能，并对未来的优化提供更多支持，需要在现有设计中添加显式类型支持，包括：

在程序源代码中允许引入变量的绑定构造中添加类型标注语法。
扩充关于类型的语义支持。
- 整理现有支持的类型并归类，提供类型系统。
- 扩展定型(typing) 机制。
  - 提供基于显式类型标注的类型构造(type formation) 。
- 可选地，提供类型检查(typechecking) 。

　　类型标注是可选的。从现有设计扩充仍允许向后兼容，同时支持渐进类型(gradual typing) 而保留允许程序以其它方式引入和这里的功能近似的机制（包括基于定理证明等其它方式实现的静态类型系统）的扩展能力。

实现参考

　　以下是一些从动态语言添加类型标注方案的实例。一些语言通过扩展提供，另一些则是扩展其它语言而以新的语言提供。

Python: PEP 484
ECMAScript: TypeScript
- TypeScript 当前不能及时提供较新版本的语言规范，这里以手册代替，即使其中的介绍页明确说明它不能代替语言规范。
Racket: TypedRacket
CHICKEN Scheme: Types

整体演进路线

　　因为类型系统规则和机制设计的复杂多样性，当前首先支持语法，以扩展核心库的方式提供可能引入绑定构造的函数。这些函数兼容原有语法，并支持分析类型为指定的元数据。

　　当前忽略元数据的作用，除类型标注自身的合法性检查，源程序去除类型标注后不影响剩余程序的语义。以后可在语言规范中补充要求语言中总是进行特定的类型检查。类型系统的其它功能可以通过其它库进一步提供。

注释需要访问已知标注类型的功能可能由扩展的工具实现。

代码生成方案

　　代码生成方案是上述语言实现演进方案的主要部分。

　　经以上讨论，在基线解释器上添加代码生成而支持编译 Unilang 基础语言的主要方案如下：

实际输出 LLVM IR 作为本项目的目标 LIR(Low-level Intermediate Representation) 。
相对地，LIR 之前的 IR 是 HIR(High-level Intermediate Representation) 。现在主要有 AST(Abstract Syntax Tree) ，对应解释器代码里的 Unilang::TreeNode 数据结构。以后可按需安插不同层次的 HIR（基本都是 AST 以后的中间 IR ）。
因为可依赖 LLVM ，需新设计和实现的部分是翻译 AST 生成 LIR 的模块。
- 分析器和一些语法检查可以直接使用现有 Unilang 解释器模块，构成统一的语言前端。
概念上（功能等价的意义上）生成 C++ 源代码的子集，另外补充运行时支持 eval 等无法简单静态翻译实现的操作（类似 R⁵RS+ 的主流实现思路）。
- 补充运行时也使用 Unilang 解释器模块。
- 因为基础语言的设计原则上非常动态，需要补充一些约定保证有些值是可以静态确定的，以便允许静态翻译而不需要复杂的证明。
  - 动态设计在工程目的上是有意的。因为从动态到静态可以通过补充约定实现，而从现有静态实现添加 dynamic 相对困难得多，甚至可能需要分析器以后的阶段整体重做（对 C++ 这样的语言，考虑到兼容性，几乎就是工程上不可行的）。
  - 已知需要静态化限制的是一等环境，这样源语言的功能基本上就弱化为 Scheme 。
    - Scheme 的解释器、编译器和运行时有很多实现可以参考。
    - 原则上，直接基于这个子语言即允许比 C-like 语言实现更多的前端优化（特别地，如 Chez 具有 polyvariant partial evaluator ），以后若有资源可以和其它代码生成模块并行迭代。（C-like 语言前端优化很有限，大多完全依赖 LIR 以后的中端和后端。）
    - 不过考虑到 Unilang 为了互操作的简便和对象模型的清晰，如 C++ 一样支持 object identity/lvalues 而默认不允许任意的 object intern ，上述优化可能更受限，效果可能和论文不符。留待以后讨论。
综上，代码生成实现可以直接往 Unilang 解释器上扩充。 * 把解释器的主 REPL 入口替换成代码生成遍历例程，得到编译器前端。 * 编译器驱动器和解释器可以是同一个可执行程序，用不同的选项指定工作模式（本机代码生成或 REPL ）。
- 之后对代码生成实现的迭代的主要工作之一是在已有代码生成实现的基础上，进一步确定可以静态优化的部分，把剩余依赖运行时的逻辑提前并实现局部的代码转换逻辑，然后让代码生成例程调用。
计划添加设计 IR ，以转换 AST 到 LIR 相近的结构的实现更容易。

　　同时考虑基于 IR 的优化：

2021 Q1/Q2 不强调 HIR 优化，但要避免给以后的工作添加困难。
LIR 优化让 LLVM 后端实现。基本上只要生成了 LLVM IR 就足以满足主要需求，暂时不需要太关心 LLVM 会在这里遇到瓶颈。

　　扩充代码生成方案后，解释器的顶层组成如下：

待设计和实现 集成上层语言的语法扩展模块，以映射上层语言具体语法到基础语言。
基础语言由现有解释器可直接得到 AST 的内部表示，作为 HIR 。
JIT 模块：基于使用 LLVM7 ORCv1 JIT ，在解释器内直接调用 LLVM 库生成 JIT IR 的内部表示，并替代部分原有规约例程加速执行。
- 初始化：使用 llvm::orc::RTDyldObjectLinkingLayer 等。
- 待完善 解释器在线转换 HIR ，生成 LLVM IR 。
- 待设计和实现 替换现有解释器规约例程。
- 待完善 JIT 驱动 API ，对接解释器调用入口和代码生成例程。

　　不被当前方案采用，但可在未来重新评估的其它备选实现方式：

设计支持基础语言的分离式 LLVM 前端，转换 HIR 生成 LLVM IR 。
LLVM IR 生成的离线 LLVM bitcode 单独执行的模块作为运行时后端。
AOT 编译模块，生成二进制映像。

翻译单元粒度

　　基础语言的最小翻译单元是被求值的表达式。

　　在此之上，允许映射任意的翻译单元到 LLVM 模块。

　　较小的翻译单元可能较大的复用性，但除非有特别针对大量小的翻译单元并行优化的设计，一般相对具有较大翻译开销。LLVM 是参照类 C 语言设计的，这里也不例外。

　　一般地，以一个被加载的模块（如一个文件）符合多数编程语言惯例，也能避免过大的翻译开销。

代码生成支持的特性

　　代码生成机制应能替换一些解释器中的语言特性的实现，因为可（部分）静态地确定的程序属性，消除重复的运行时解释开销(implementation overhead) ，而取得实现有效的程序运行时效率提升。

　　由解释器的现有实现架构，不论是特性还是库特性，都可以通过提供 C++ 本机实现的方式并逐步替换。

　　根据解释开销的存在和在实际程序运行中显著程度以及语言特性的重要性（在程序中是否足够常用），AST 解释器中的不同的语言特性的实现不总是相同程度地适宜被代码生成机制替换。这些判断当前主要依照语义特征通过经验确定。以后可以补充针对性的性能测试，比对不同实现的性能差异而进一步调整被替换的候选特性。

　　当前计划中，这些特性按如下方式归类：

位于程序常用路径，可能通过代码生成改进性能而需优先实现代码替换的特性：
- 变量解析：作用域/静态环境解析、符号管理、符号表查找、替换变量引用为引用值。
- 应用子调用：过程调用。
- 在机器数表示范围内的数值计算：类型检查、操作分派和机器指令选择等。
潜在具有性能提升优势而作为替换候选的特性：
- $let 等可能变换为规则中间表示的用户程序显式引入局部基本块的块操作。
- 能静态确定依赖路径的模块管理和环境构造的相关操作（如 $import）。
预期无法通过代码生成加速（LLVM 缺少这种支持也不便直接实现）的特性：
- 无法静态确定环境的操作子调用。
- 部分依赖动态输入的一等环境的求值（eval 调用）。
- 预期依赖运行时的其它所有库特性（如大整数计算）。
其它特性暂不考虑代码加速，按实现计划的完成情况（进度）和实现效果的反馈（性能测试对比）结果按需调整。

　　确定需进行代码生成替换的特性，应能保证被 LLVM API 支持。

互操作

　　因为不是所有特性都支持通过静态确定特定的代码属性后直接通过生成代码减小解释开销以及兼容解释实现的必要性，只有少数确定的路径支持生成代码，剩余程序(residual program) 仍被解释执行。这种设计本质是一种简化的在线部分求值的解释优化。

启用代码生成的条件

　　代码生成应保留语言规范的指定语义。只有代码生成的内部实现才支持 LLVM 后端优化。

　　当前支持代码生成的入口点是函数体，代码生成首先替换函数体中的求值结构使其在之后更高效。为保持语义正确，这要求调用函数时创建的局部环境（即函数体求值所在的当前环境）是稳定(stable) 的，即其中所有影响语言实现的可观察行为的变量绑定可被静态确定，之后不被改变：

这要求函数定义时不能有需在运行时确定的动态环境。
这同时依赖创建函数时静态环境的稳定性。

　　考虑代码生成的主要目的是优化实现性能，理想情形只有被调用足够频繁使节约的解释开销大于代码生成自身的翻译开销时，才使用代码翻译。在没有对代码的运行时结果进行记忆化(memoization) 处理时，这种判断只能是启发式的。此处代码生成首先排除调用的函数是右值的情形，因为函数右值是临时值，总是可以假定调用只有一次，即使生成代码也需要立即调用，可以假定比直接解释有更大的解释开销。尽管严格地说，生成函数临时值可能有潜在的公共子表达式优化可以提取这种条件取代记忆化，但考虑实现的简单性，当前不支持这种优化路径。

规约实现调整

　　为支持代码生成，规约实现进行如下调整：

Context::ReduceOnce 替换为支持代码生成的实现。

实现注记

　　当前使用 LLVM 通过外部部署。发行版提供的版本默认不支持 RTTI 和异常，但在 Unilang 解释器中需要依赖，需要调整构建命令行选项复原（使用 -fexceptions -frtti ）。

　　因为不依赖 LLVM 库的异常和 RTTI 支持，通过 LLVM 的依赖路径传播异常和 LLVM 库中 RTTI 需要被解释器实现避免。注意 LLVM 中被声明为内联的函数调用中的 new 等调用路径仍可能在 -fexceptions 下抛出异常（而在 LLVM 的库中的代码中因可能以 -fexception ，抛出异常时编译器生成的代码直接调用 abort ），因此这个上下文中无视这个限制。

参考资料

　　基于 LLVM 开发可参照以下官方文档：

LLVM Tutorial
LLVM Language Reference Manual

构建和包管理

　　本章描述 Unilang 项目中支持的可复用的程序组件相关的功能特性支持。

概述

　　构建和包管理需在 Unilang 语言中支持以下方面的特性：

模块管理：
- 模块抽象和约定。
- 模块的调用接口。
- 模块的使用。
依赖管理。
- 依赖实体抽象和约定。
- 依赖实体管理。
构建管理：
- 构建元数据约定。
- 构建操作约定。
- 文件系统使用约定。
- 构建管理功能。
软件包管理：
- 持久存储格式相关实体的约定。
- 包数据维护。
- 仓库维护。

　　除存储格式的约定，以上特性需以 Unilang API 的形式提供，主要为 Unilang 库函数。

　　在此基础上，进一步实现包管理命令行前端工具，对以上 Unilang 库提供的软件包管理功能进行封装，允许从命令行调用维护仓库的功能。

整体设计

　　依照以上特性，设计对应的接口和功能模块，如下：

模块管理：
- 使用环境对象作为基本的程序模块的内部表示。
  - 处理环境的标准库函数操作模块。
    - 使用 $set! 和 $provide! 等创建模块、修改模块中的和提供模块接口。
    - 使用 $import! 等从模块中导入可编程接口。
    - 使用 eval 和 $remote-eval 等调用模块中的调用接口。
    - 使用 load 从外部来源加载模块。
      - 当前只支持文本形式的源文件。以后可以扩展到其它格式。
  - 环境中的变量提供具体特定模块的可编程接口。
- 提供标准库模块 std.modules 作为处理模块的常规 API 。
依赖管理：
- 依赖版本抽象：使用语义版本。
- 依赖名称：Unilang 标识符，持久存储为字符串。
- （名义）依赖实体：依赖名称和版本的组合。
- 依赖对象：依赖实体和被依赖的目标的列表的组合。
- 依赖管理 API ：基于依赖版本、名称和依赖对象上创建和修改。
构建管理：
- 构建操作约定：
  - 构建系统在构建过程中可执行的构建操作包括：
    - 内部操作：构建系统直接实现的功能，可能访问文件系统。
    - 用户操作：用户提供的程序（如回调函数），可被构建系统调用。
    - 调用命令：以宿主环境（操作系统）支持的命令行调用外部程序（如编译器）。
  - 构建过程中不对调用命令的命令行长度上限添加检查。
    - 用户需要自行注意当前工作目录或者命令长度等，以避免构造的命令行过长而不被支持，最终出错。
    - 原理这类错误非常依赖具体的外部环境。即使检查，也不能有效排除错误，且影响原始错误的呈现，而容易干扰错误的排除。
- 构建元数据用于指定构建需要的配置信息，使用一个环境对象以变量绑定的方式保存。
  - 注释可通过父环境的形式指定和覆盖默认值，实现配置模板的复用。
  - 每次构建时只从这个环境中通过名称解析取得要访问的元数据。
  - 除非另行指定，默认元数据的值是绑定在这个环境中的字符串。
  - 访问元数据的值时，其中以未被转义的 $ 作为前缀和标识符构成的子串会被整体解析，替换这个子串为以这个标识符为变量名的元数据的值，直至不存在可替换的子串。对任意输入，替换应最终总是能终止。
  - 构建操作中调用命令时访问元数据的值，同时进行变量替换。
  - 构建系统可识别一些具有特定含义的预定义的元数据。其它元数据由用户自定义，可在自定义的构建操作中使用。构建系统在未来可能添加新的可识别的预定义元数据。
    - 构建系统不使用小写字母起始的名称作为预定义的元数据的名称。用户可自定义这些名称。
    - 用户应避免 POSIX 、操作系统等外部环境定义的周知的(well-known) 环境变量名称作为元数据名称并使其值具有逻辑冲突的含义。
    - 用户应避免使用以下被保留给构建系统或语言的内部实现的任意名称：以 _ 起始的名称；带有 $ 或 __ 作为子串的名称。
- 文件系统使用约定：
  - 表示文件系统路径的字符串使用 / 作为分隔符，. 表示当前目录，.. 表示上级目录。
    - 注释路径语法和兼容 POSIX 的大多数 shell 类似。
    - 路径字符串作为元数据访问时，同时替换其中的变量，此时不访问文件中系统中的数据。得到结果后，不添加检查。若结果是所在文件系统的非法路径，之后使用路径访问文件或调用命令可能出错。
  - 构建目录布局约定：
    - 构建中使用一个目录，可能同时使用其子目录。
    - 具体目录由元数据配置，参见以下关于元数据说明。
  - 除非另行指定，构建过程中，需要创建目录时，隐含创建路径中的同时有必要创建的父目录。
  - 一些元数据的默认值和构建操作可能被开始构建时的当前工作目录影响。在构建之前用户需要自行确保这个当前工作目录符合需要（例如通过 shell 命令切换工作目录再运行构建命令调用这里的 API ）。
- 对每个构建，构建系统识别以下预定义的元数据：
  - PATH ：调用构建命令使用的 PATH 环境变量。
    - 若为空，则构建时首先初始化为继承外部的 PATH 环境变量。
  - SrcRoot 源路径。
    - 若为空，则构建时初始化为默认值：当前工作目录。
    - 除非另行指定，内部操作不会试图向构建命令中传递这个路径以外的源代码。其它构建操作隐含的搜索路径（如编译器隐含的默认系统头文件路径）不被影响。
  - BuildConf ：构建配置名。
    - 若非空，应为能构成会在构建目录使用的文件系统中合法的目录名的值。
  - BuildDir ：构建目录。
    - 若为空，则构建时初始化为默认值：$SrcRoot/.$BuildConf/ 下的 build 。
    - 除非另行指定，构建系统的自动过程不会试图往这个目录以外的路径下写文件。
    - 注释一般建议确保 $BuildConf 非空以允许同时存在多个不同的配置。可指定在 $SrcRoot 外的目录，以避免侵入源码树。
- 构建管理 API ：
  - 元数据的构造和访问，包括解析变量。
  - 构建操作的封装。
  - 构建配置的构造和访问。
  - 预定义元数据的默认初始化。
  - 构建任务的封装、调度和执行。
  - 作为启动构建的入口的高层接口。

依赖管理 API 详细设计

<string> 值可作为依赖名称(dependency name) 。
- 依赖名称应是包含由可打印字服组成的非空字符串，且不包含 / 和 \ 字符。
- 所有预期依赖名称作为值的公开 API 在使用指定依赖名称的参数前蕴含按以上要求对依赖名称进行的合规检查。若检查失败，则引起错误。
类型 <version> ：版本。
- <version> 类型的值具有全序关系，可使用 eqv? 比较其中的相等。
函数 version? ：<version> 的类型谓词。
函数 string->version <string> ：转换语义版本的字符串描述为对应的版本对象。
- 结果是 <version> 右值。
- 描述应为语义化版本指定的语法的版本号，其中可选的后缀被忽略。若参数不具有可被解析为版本描述的格式，则引起错误。
函数 version->string <version> ：转换版本对象为语义版本的字符串描述。
- 结果是 <string> 右值。
函数 version<? <version1> <version2> ：比较版本的小于关系。
- 结果是 <bool> 右值。
类型 <dependency> ：依赖。
- 依赖对象由名称、版本和约束检查谓词构成。其中，约束检查谓词应是参数为 <dependency>... ，返回 <bool> 值的应用子。
- 构造的依赖可包含不符合上述要求的应用子。若约束检查谓词不满足上述要求，则公开 API 中的操作引起约束检查谓词被调用时程序的行为未定义。
- 约束检查谓词的结果非 #f 时，约束被满足(satisfied) 。提供约束的输入的实体 蕴含(imply) 具有对应约束检查谓词的依赖。
函数 dependency? ：<dependency> 的类型谓词。
函数 make-dependency <string> <version> <applicative> ：使用参数指定的实体名称、版本和作为约束检查谓词的应用子创建 <dependency> 右值。
函数 name-of <dependency> ：取参数指定的依赖中的实体名称。
- 结果是 <string> 右值。
函数 version-of <dependency> ：取依赖的版本。
- 结果是 <version> 右值。
函数 check-of <dependency> ：取依赖的依赖检查谓词。
- 结果是 <applicative> 右值。
函数 validate <dependency>+ ：验证依赖条件是否被满足：以第一个参数以外的参数作为参数，调用第一个参数指定的依赖中的依赖检查谓词。
- 结果是调用依赖检查谓词的结果。
函数 strings->dependency-contract <strings>+ ：解析字符串，取对应的约束检查谓词的右值。
- 第一个参数应指定依赖名称。
- 每个字符串格式形式应符合语法 <neg><op><ver> ，其中：
  - 可选的 <neg> 是 ! ，表示要求排除特定版本；否则，表示要求依赖特定版本。
  - 可选的 <op> 是 <、>、<=、>=、^、~ 、= 之一，含义同 Cargo 要求的约定。
  - <op> 和 <ver> 之间可添加有限个水平空白符（空格或水平制表符），不影响含义。
    - 字符串格式中不支持其它字符（如空白符）。
  - 原理兼容 Cargo 的语法和 Cargo 使用的实际实现原则上一致，但考虑实际可能的用例限制空白符为水平空白符，且作为单一依赖的约束不支持逗号分隔的字符串。而 Cargo 不支持的 <neg> 在逻辑上被视为和 <op> 整体上构成一个逻辑操作符，因此不支持 <neg> 和 <op> 之间内部具有空白符。
- 若存在不符合上述语法的字符串，则引起错误。
- 得到的约束检查谓词中蕴含同时符合每个字符串表达的对版本的逻辑约束。
类型 <dependency-set> ：依赖集合。
函数 dependency-set? ：<dependency-set> 的类型谓词。
函数 make-dependency-set <dependency>... ：创建蕴含参数指定的所有依赖集合。
- 注释实现可能进行优化，以减小结果上的其它操作的开销。
函数 has-dependency? <dependency-set> <string> <version>? ：在第一参数指定的依赖集中查询第二参数指定依赖名称的依赖，判断是否存在。若指定了第三参数且不存在和第三参数相同版本的依赖，则视为不存在。
- 结果是 <bool> 值。

构建管理 API 详细设计

函数 resolve-metadata-string <environment> <string> ：在环境中解析元数据字符串，得到经过变量替换的字符串结果。
- 被解析的子串是其中以没有被转义的 $ 起始引用的标识符。
  - 转义的 \$ 表示字符 $ ，不引导被替换的标识符。
  - 转义的 \\ 表示字符 \ ，不引导其它转义序列。
  - 注释替换的变量名同 POSIX 环境变量语法，大小写敏感。适当的转义可避免替换。
- 若需替换而变量不存在或它的值不是字符串，则引起错误。
- 替换进行深度优先搜索：每次替换标识符后，若替换结果还有标识符，则首先在子串内部递归替换，直至不存在未被忽略的标识符，再替换的原先的字符串中。
  - 若搜索过程中发现可引起无限递归替换的标识符，则引起错误。
- 原理深度搜索及其它错误条件对确保解析总是能终止是必要的。这同时不允许替换得到一个 $ 结尾后和被替换的字符串的剩余部分构成一个待解析的子串，保证被替换的子串的整体性。
函数 get-metadata <environment> <string> ：从第一参数指定的环境取第二参数为名称的元数据。
- 若指定的元数据不存在则引起错误。
- 若取得的元数据是 <string> 值，则结果是这个值经过在这个环境中的变量替换的结果。
类型 <build-operation> ：构建操作，是任意的能以一个 <environment> 和可选的 <object> 值作为实际参数调用的 <applicative> 。
函数 command->build-operation <string> ：转换命令字符串为构建操作。
- 结果是一个保存了参数指定的命令字符串的 <build-operation> 对象。调用这个对象只需要一个参数，第二参数会被忽略。调用时，参数的值指定的环境中对命令字符串进行变量替换，结果作为命令，在宿主环境中调用。
函数 complete-build-configuration <environment> ：补全默认构建配置。
- 结果是包含默认构建配置的环境，以参数为第一个环境父环境，并可能有第二个父环境，使结果中包含所有预定义元数据的变量绑定。其中，不在参数中具有绑定的变量在第二个父环境提供绑定，其值是预定义元数据的默认值。
函数 build-with <build-operation> <environment> <string> ：以指定的构建操作和配置构建指定路径下的目标。
- 参数分别指定使用的构建操作、使用的构建配置和表示文件系统路径的字符串。
- 对路径指定的递归扫描，以其中的每个子目录中的非目录文件的相对路径作为参数，调用一次构建操作。构建参数的操作分别是这里的第二参数和非目录文件的（相对此处第三参数的）文件路径。
  - 若路径指定的文件名没有指定一个可访问的目录，则引起错误。
  - 注意假定调用过程中目录的内容不存在外部的并发修改，且目录内部没有循环的符号链接。否则，递归扫描可能无法终止。

QtDemo

　　QtDemo 当前用于内部评估。

　　参照 Qt 官方的 PySide2 第一个例子。Demo 实现的源代码详见 qt.txt 。

解释器支持特性

　　包含以下非公开支持特性：

标准库：
- random.choice
- sys.exit

　　通过 UnilangQt 支持在 Demo 中需要使用的 Qt 绑定特性：

注释当前非公开。
注释除非另行指定，以下被实现的特性都是合并子。
以下直接依赖 Qt 本机实现的名称在非公开环境 UnilangQt.native__ 中提供。
- 以下内部的成员跳过实现：
  - qt_metacall
  - qt_netacast
  - staticMetaObject
- QtCore
  - <string>对象 QT_VERSION_STR
  - make-DynamicQObject
  - QObject-connect
    - 信号连接可直接调用。
  - Qt.AA_EnableHighDpiScaling
  - Qt.AlignCenter
  - QCoreApplication
    - QCoreApplication-applicationName
    - QCoreApplication-organizationName
    - QCoreApplication-instance
      - 注释不直接使用动态库符号 QCoreApplication::self 。
    - QCoreApplication-setApplicationName
    - QCoreApplication-setApplicationVersion
    - QCoreApplication-setAttribute
    - QCoreApplication-setOrganizationName
- QtGui
  - QGuiApplication
    - make-QGuiApplication
    - QGuiApplication-exec
    - QGuiApplication-restoreOverrideCursor
    - QGuiApplication-setFallbackSessionManagementEnabled
      - 注释仅当 Qt 5.6.0 起，6.0.0 前可用。
- QtWidgets
  - QApplication
    - make-QApplication
    - QApplication-aboutQt
    - QApplication-desktop
    - QApplication-exec
  - QWidget
    - make-QWidget
    - QWidget-close
    - QWidget-resize
    - QWidget-hasHeightForWidth
    - QWidget-heightForWidth
    - QWidget-inputMethodQuery
    - QWidget-minimumSizeHint
    - QWidget-move
    - QWidget-paintEngine
    - QWidget-restoreGeometry
    - QWidget-saveGeometry
    - QWidget-setLayout
    - QWidget-setVisible
    - QWidget-setWindowFilePath
    - QWidget-show
    - QWidget-sizeHint
    - 以下内部的成员跳过实现：
      - devType
      - redirected
    - 以下非 public 的成员跳过实现：
      - actionEvent
      - changeEvent
      - dragEnterEvent
      - dragLeaveEvent
      - dragMoveEvent
      - dropEvent
      - enterEvent
      - focusInEvent
      - focusNextPrevChild
      - focusOutEvent
      - hideEvent
      - initPainter
      - inputMethodEvent
      - keyPressEvent
      - keyReleaseEvent
      - leaveEvent
      - metric
      - mouseDoubleClickEvent
      - mouseMoveEvent
      - mousePressEvent
      - mouseReleaseEvent
      - moveEvent
      - nativeEvent
      - paintEvent
      - resizeEvent
      - showEvent
      - tabletEvent
      - wheelEvent
  - QPushButton
  - QLabel
    - make-QLabel
  - QVBoxLayout
    - make-QVBoxLayout
  - QMainWindow
    - make-QMainWindow
    - QMainWindow-addToolBar <string>
    - QMainWindow-createPopupMenu
    - QMainWindow-menuBar
    - 以下非 public 的成员跳过实现：
      - contextMenuEvent
      - event
  - QLayout-addWidget
- QtQml
  - QQmlApplicationEngine *
- QtQuick
  - QQuickView
    - QQuickView-showFullScreen
  - QQuickView_set-source
  - QQuickView_set-transparent
以下名称在环境 UnilangQt 中提供：
- UnilangQt.native__ 中的名称。
- QWidget
Qt API 类型映射（用于传递参数或值）：
- 宿主类型同对象类型：
  - 任意没有在以下另行指定的类类型以外的平凡对象类型
  - QList 的实例
  - QPaint
  - QVariant
  - QCursor
  - QPoint
  - QSize
  - QUrl
- 宿主类型是不同的对象类型：
  - QString 映射为 string
- 宿主类型是 shared_ptr 实例：
  - QLayout
- 作为 *this 时，宿主类型是 shared_ptr 实例：
  - QApplication
  - QGuiApplication
  - QWidget 及其派生类（使用 shared_ptr<QWidget> 或 shared_ptr<const QWidget>）
    - QLabel
    - QPushButton
    - QMainWindow
  - QQmlApplicationEngine
    - QQmlApplicationEngine-load
  - QQuickView

Files

Interpreter.zh-CN.md

Latest commit

History

Interpreter.zh-CN.md

File metadata and controls

前言(Foreword)

实现定义行为

标准库模块操作

用户环境初始化

项目维护注记

版本号更新

整体设计

实现环境

程序表示

外部表示

内部表示

规约

抽象机

数据结构

资源管理

求值规约

规约函数

名称解析

函数调用

PTC（proper tail call，真尾调用）

诊断

类型映射

非平凡非正规表示

解释器核心结构

读取

求值

打印

库特性实现

基础环境

详细设计

外部实体引用

词法处理

异常

项节点

语法处理

项和值的访问接口

基本规约接口

上下文接口

其它支持接口

求值算法的实现

标准库操作的本机实现

标准库实现

解释器模块

解释器程序入口

诊断

源代码信息

名称表

尾操作符名称

互操作支持

内部表示

语言实现演进方案

核心语言实现结构和选型策略概述

AST 中心架构

字节码

在线部分求值器(online partial evaluation)

解释器扩展

基线

整体路线

实现修改形式

ABI 计划

类型语义

其它支持改进

显式类型扩展

概要

实现参考

整体演进路线

代码生成方案

翻译单元粒度

代码生成支持的特性

互操作

启用代码生成的条件

规约实现调整

实现注记

参考资料