前言

前段时间，我在 XXX 上投入不少精力（详情见前文），从中接触并大量使用了 XXX 这门领域特定语言。随着了解逐渐深入，我越来越感受到 XXX 语言自身的局限性：性能一般、功能简陋。再加上产品多年没有维护，于是我萌生出加以改进的想法。

在调研了市面上常见的产品，并与同事交流之后，我发现多数领域特定语言：

• 不支持变量定义，或者支持定义但缺乏垃圾回收机制，导致内存占用大
• 简单地深度优先遍历并执行 AST，对控制流语法支持有限
• 不图灵完备，支持的语言特性不足，后续拓展难度大

出于实验目的，我尝试设计一门解决上面问题的新语言。新语言核心需要足够简单却又不失灵活性，具有丰富的特性。因此在业余时间，我实现了这门语言，快速验证了想法，为集团相关领域做点技术储备。

背景

领域特定语言（Domain-specific language，DSL）是专用于特定应用领域的计算机语言。在安全风控领域，为了对抗瞬息万变的违规内容变种形式，安全策略方需要及时制定、调整各个场景的策略方案。以往采用硬编码将安全策略部署到服务中的方法，灵活性已经跟不上策略的频繁变动。使用 DSL 编写策略规则，能够避免服务的更新发布，从而降低策略迭代的风险，缩短策略部署上线的时间周期。

在集团内部，DSL 被广泛使用在 XXX 之中…（后续省略敏感内容）

特性

新语言是动态类型函数式的解释型语言，函数是一等公民（first-class functions），具有五种基本类型：Void， Number， String， Closure¹， Continuation²。Closure 是闭包，绑定当前上下文中的词法作用域变量，是语言特性的基础。Continuation 是延续，保存了求值上下文，可以用来实现复杂的控制流。

目前语言支持尾调用优化，具备运行时常量池，实现了标记-清除垃圾回收算法。具体的特性及例子如下：

• 支持协程、异常等控制流 (coroutines.gs, exception.gs)
• 多阶段求值 (multi-stage.gs)
• 惰性求值 (lazy-evaluation.gs)
• 结构体 (binary-tree.gs, list.gs)
• 面向对象编程 (oop.gs)
• 原生支持全精度有理数 (values.gs)
• 支持词法作用域和动态作用域 (scope.gs)
• 与 golang 自然交互 (interaction.go)

语法与语义

<comment> := #.*\n
<number> := [+-]?0 | [+-]?[1-9][0-9]*
          | [+-]?0\.[0-9]*[1-9] | [+-]?[1-9][0-9]*\.[0-9]*[1-9]
          | [+-]?0/[1-9][0-9]* | [+-]?[1-9][0-9]*/[1-9][0-9]*
<string> := "( [^"\] | \" | \\ | \t | \n )*" 
<lexical-variable> := [a-z][a-zA-Z0-9_]*
<dynamic-variable> := [A-Z][a-zA-Z0-9_]*
<variable> := <lexical-variable> | <dynamic-variable>
<intrinsic> := void | add | sub | mul | div | mod 
            | lt | eq | and | or | not  
            | type | id | getline | put 
            | callcc | eval | reg | go
<binding> := <variable> = <expr>
<callee> := <intrinsic> | <expr>
<expr> := <number> | <string> | <variable>
        | lambda ( <variable>* ) { <expr> }
        | letrec ( <binding>* ) { <expr> }
        | if <expr> then <expr> else <expr>
        | ( <callee> <expr>* )
        | [ <expr>+ ]
        | & <lexical-variable> <expr>

核心实现

堆、栈、帧

语言解释器在运行时会遍历语法树，执行到的树节点会以 Layer 结构体被压入栈中，执行完成则被弹出栈。当闭包或延续被执行，则会被作为新帧的 Layer 入栈。

相同帧的 Layer 共享同一个环境。帧与帧之间的环境互相独立。环境会记录当前帧中变量名在堆的位置。

闭包被创建时，会保存当前环境中的词法作用域变量；闭包被执行时，会把保存的变量作为新帧的环境。延续被创建时，会保存当前运行时栈；延续被执行时，会把保存的栈替换回运行时栈。

词法作用域的变量名，仅在栈顶帧的环境中查找。而动态作用域的变量名会按照栈顶到栈底的顺序，依次检查每个帧的环境。

堆存放的是变量值的引用。当变量名不再被使用，需要从堆中移除变量值的引用，这样宿主语言才能识别出空闲对象并进行回收。

垃圾回收

可能有人会疑惑：明明宿主语言已经具备垃圾回收的能力，为什么我们还要自己去实现呢？

这是因为宿主语言生成的对象始终被解释器中的变量所引用。解释器要做的是，识别出生命周期结束的变量，从解释器堆中移除该变量值的引用，这样宿主语言才能回收已分配的内存。

当触发垃圾回收时，解释器会遍历运行时栈，标记每一帧使用到的变量。如果变量是闭包或者延续，则会递归地标记其中用到的变量。

以下图为例，假设解释器堆的第一个变量引用是垃圾回收的起点。那么垃圾回收结束时，解释器堆上会只留下绿色背景的引用。黄色背景的对象因被引用到而被保留，白色背景的对象会因不被引用而被宿主语言回收。

尾调用优化

由于使用堆栈的运行模型，再加上函数式语言的特点，如果没有做专门的优化，语言的执行性能会很差，内存占用大，很容易出现栈溢出的情况。针对这种问题，我做了尾调用优化：

闭包或延续被执行，会往栈上压入新帧。假如当前执行位置位于上一帧的末尾，那么解释器可以重用已有的栈帧，减少内存的使用。

因此我们更加提倡使用尾递归的风格来编写程序，这有助于解释器进行尾调用优化。

letrec (
  worseSum = lambda (n) {
    if (eq n 0) then 0 
    else (add n (worseSum (sub n 1)))
  }
  betterSum = lambda (n acc) {
    if (eq n 0) then acc 
    else (betterSum (sub n 1) (add n acc))
  }
){
  [
    (worseSum 100)   
    (betterSum 100 0)  # more effective
  ]
}

性能表现

在 Macbook pro 2019（2.6 GHz 六核 Intel Core i7）机器上，跑 100w 层递归的性能表现如下：

其他示例

• 输入输出 (echo.gs)
• REPL³ (repl.gs)
• Y 组合子⁴ (y-combinator.gs)
• Quine⁵ (quine.gs)

未来展望

• 进行静态分析优化：常量折叠、尾调用分析、闭包活跃变量分析等
• 支持 Hindley-Milner 类型推导或类型检查
• 探索更好的垃圾回收机制⁶