G-Machine 第三部分

G-Machine 第三部分#

本文是关于在 MoonBit 中实现 Haskell 懒惰求值的系列文章中的第三篇。在上一篇文章中，我们学习了如何编译 let 表达式以及如何实现基本的算术和比较操作。在本文中，我们将实现一种基于上下文的优化方法，并添加对数据结构的支持。

追踪上下文#

让我们回顾一下我们在上一篇教程 (gmachine-2) 中如何实现原语的。

let compiled_primitives : List[(String, Int, List[Instruction])] = @immut/list.of(
  [
    // Arith
    (
      "add",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Add, Update(2), Pop(2), Unwind]),
    ),
    (
      "sub",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Sub, Update(2), Pop(2), Unwind]),
    ),
    (
      "mul",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Mul, Update(2), Pop(2), Unwind]),
    ),
    (
      "div",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Div, Update(2), Pop(2), Unwind]),
    ),
    // Compare
    (
      "eq",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Eq, Update(2), Pop(2), Unwind]),
    ),
    (
      "neq",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Ne, Update(2), Pop(2), Unwind]),
    ),
    (
      "ge",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Ge, Update(2), Pop(2), Unwind]),
    ),
    (
      "gt",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Gt, Update(2), Pop(2), Unwind]),
    ),
    (
      "le",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Le, Update(2), Pop(2), Unwind]),
    ),
    (
      "lt",
      2,
      @immut/list.of([Push(1), Eval, Push(1), Eval, Lt, Update(2), Pop(2), Unwind]),
    ),
    // MISC
    ("negate", 1, @immut/list.of([Push(0), Eval, Neg, Update(1), Pop(1), Unwind])),
    (
      "if",
      3,
      @immut/list.of(
        [
          Push(0),
          Eval,
          Cond(@immut/list.of([Push(1)]), @immut/list.of([Push(2)])),
          Update(3),
          Pop(3),
          Unwind,
        ],
      ),
    ),
  ],
)

这个实现引入了许多 Eval 指令，但它们并不总是必要的。例如：

(add 3 (mul 4 5))

add的两个参数在执行Eval之前已经处于 WHNF（弱头正常形式），因此，这里的Eval` 指令是多余的。

一种可行的优化方法是在编译表达式时考虑上下文。例如，add 需要其参数被求值到 WHNF，因此它的参数在编译过程中处于严格上下文。通过这种方式，我们可以识别出一些可以安全地使用严格求值编译的表达式（仅为其中的一部分）。

  • 超级组合子定义中的表达式处于严格上下文中。

  • 如果 (op e1 e2) 处于严格上下文中（其中 op 是一个原语），那么 e1 和 e2 也处于严格上下文中。

  • 如果 (let (.....) e) 处于严格上下文中，那么 e 也处于严格上下文中（但与局部变量对应的表达式不一定是严格的，因为 e 可能不需要它们的结果）。

我们使用 compileE 函数在严格上下文中实现编译，确保_栈顶的值始终处于 WHNF_。

对于默认分支，我们仅在 compileC 的结果后添加一个 Eval 指令。

_ => compileC(self, env) + @immut/list.of([Eval])

常量被直接推入。

Num(n) => @immut/list.of([PushInt(n)])

对于 let/letrec 表达式，专门设计的 compileLet 和 compileLetrec 变得非常有用。在严格上下文中编译 let/letrec 表达式时，只需要使用 compileE 来编译它的主要表达式。

Let(rec, defs, e) => {
  if rec {
    compileLetrec(compileE, defs, e, env)
  } else {
    compileLet(compileE, defs, e, env)
  }
}

if 和 negate 函数分别需要 3 和 1 个参数，需要特殊处理。

App(App(App(Var("if"), b), e1), e2) => {
  let condition = compileE(b, env)
  let branch1 = compileE(e1, env)
  let branch2 = compileE(e2, env)
  condition +  @immut/list.of([Cond(branch1, branch2)])
}
App(Var("negate"), e) => {
  compileE(e, env) + @immut/list.of([Neg])
}

基本的二元操作可以通过查找表统一处理。首先，构建一个名为 builtinOpS 的哈希表，通过原语的名称查询相应的指令。

let builtinOpS : @hashmap.T[String, Instruction] = {
  let table  = @hashmap.new(capacity = 50)
  table["add"] = Add 
  table["mul"] = Mul
  table["sub"] = Sub
  table["div"] = Div
  table["eq"]  = Eq
  table["neq"] = Ne
  table["ge"] = Ge 
  table["gt"] = Gt
  table["le"] = Le
  table["lt"] = Lt
  table
}

其余的处理没有太大区别。

App(App(Var(op), e0), e1) => {
  match builtinOpS[op] {
    None => compileC(self, env) + @immut/list.of([Eval])
    Some(instr) => {
      let code1 = compileE(e1, env)
      let code0 = compileE(e0, argOffset(1, env))
      code1 + code0 + @immut/list.of([instr])
    }
  }
}

我们完成了吗？看起来是的，但除了整数之外，还有另一种 WHNF：部分应用函数。

部分应用是指参数数量不足的情况。这种情况在高阶函数中很常见，例如：

(map (add 1) listofnumbers)

这里，(add 1) 是一个部分应用。

为了确保新编译策略生成的代码正常工作，我们需要修改 NGlobal 分支的 Unwind 指令实现。当参数不足且转储保存了堆栈时，我们应仅保留原始的红 ex 并恢复堆栈。

NGlobal(_, n, c) => {
  let k = self.stack.length()
  if k < n {
    match self.dump {
      Nil => abort("Unwinding with too few arguments")
      Cons((i, s), rest) => {
        // a1 : ...... : ak
        // ||
        // ak : s
        self.stack = self.stack.drop(k - 1) + s
        self.dump = rest
        self.code = i
      }
    }
  } else {
    if n != 0 {
      self.rearrange(n)
    } else {
      self.put_stack(addr)
    }
    self.put_code(c)
  }
}

这种基于上下文的严格性分析技术很有用，但不能处理超级组合子调用。在这里，我们简要介绍一种基于布尔运算的严格性分析技术，它可以分析超级组合子调用的哪些参数应该使用严格模式编译。

我们首先定义一个概念：bottom，它在概念上代表一个永不终止或引发异常的值。对于一个超级组合子 f a[1] ...... a[n]，如果其中一个参数 a[i] 满足 a[i] = bottom，那么 f a[1] .... a[i] .... a[n] = bottom（其他参数不是 bottom）。这表明，无论 f 的内部控制流多么复杂，它必须需要参数 a[i] 的结果才能得到最终结果。因此，a[i] 应该被严格求值。

如果此条件不满足，并不一定意味着该参数完全不需要；它可能只在某些分支中使用，其使用在运行时确定。这样的参数是应该延迟求值的典型例子。

我们将 bottom 视为 false，非 bottom 值视为 true。这样，coref 中的所有函数都可以视为布尔函数。以 abs 为例：

(defn abs[n]
  (if (lt n 0) (negate n) n))

我们分析如何将其从上到下转换为布尔函数：

  • 对于像 (if x y z) 这样的表达式，x 必须被求值，但只需要评估 y 或 z 之一。这可以转换为 x and (y or z)。以上面的函数为例，如果 n 是 bottom，那么条件 (lt n 0) 也是 bottom，因此整个表达式的结果也是 bottom。

  • 对于原始表达式，使用 and 连接所有部分即可。

为了确定一个参数是否需要严格编译，可以将上述条件转换为布尔函数：a[i] = false 表示 f a[1] .... a[i] .... a[n] = false（其他所有参数为 true）。

这本质上是一种名为“抽象解释”的程序分析方法。

自定义数据结构#

Haskell 中的数据结构类型定义类似于 MoonBit 中的 enum。然而，由于 CoreF 是一种简单的玩具语言，用于演示懒惰求值，它不允许自定义数据类型。唯一的内置数据结构是懒惰列表。

(defn take[n l]
  (case l
    [(Nil) Nil]
    [(Cons x xs)
      (if (le n 0)
        Nil
        (Cons x (take (sub n 1) xs)))]))

如上所示，可以使用 case 表达式进行列表的简单模式匹配。

列表的对应图节点是 NConstr(Int, List[Addr])，由两部分组成：

  • 不同值构造器的标签：Nil 的标签是 0，Cons 的标签是 1。

  • 用于存储子结构的地址列表，其长度对应于值构造器的参数数量（元数）。

该图节点结构可用于实现各种数据结构，但 CoreF 没有类型系统。为了演示目的，仅实现了懒惰列表。

我们需要添加两个指令，Split 和 Pack，来解构和构建列表。

fn pack(self : GState, t : Int, n : Int) -> Unit {
  let addrs = self.stack.take(n)
  self.stack = self.stack.drop(n)
  let addr = self.heap.alloc(NConstr(t, addrs))
  self.put_stack(addr)
}

fn split(self : GState) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NConstr(_, addrs) => {
      // n == addrs.length()
      self.stack = addrs + self.stack
    }
    _ => panic()
  }
}

此外，需要一个 CaseJump 指令来实现 case 表达式。

fn casejump(self : GState, table : List[(Int, List[Instruction])]) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NConstr(t, _) => {
      match table.lookup(t) {
        None => abort("casejump")
        Some(instrs) => { 
          self.code = instrs + self.code
          self.put_stack(addr)
        }
      }
    }
    otherwise => abort("casejump(): addr = \{addr} node = \{otherwise}")
  }
}

在添加上述指令之后，我们需要修改 compileC 和 compileE 函数。由于 case 表达式匹配的对象需要被求值到 WHNF，因此只能通过 compileE 函数来编译它。

App(App(Constructor(tag = 1, arity = 2), x), xs) => {
  // Cons(x, xs)
  compileC(xs, env) + compileC(x, argOffset(1, env)) + @immut/list.of([Pack(1, 2)])
}
// Nil
Constructor(tag = 0, arity = 0) => @immut/list.of([Pack(0, 0)])

Case(e, alts) => {
  compileE(e, env) + @immut/list.of([CaseJump(compileAlts(alts, env))])
}
Constructor(tag = 0, arity = 0) => {
  // Nil
  @immut/list.of([Pack(0, 0)])
}
App(App(Constructor(tag = 1, arity = 2), x), xs) => {
  // Cons(x, xs)
  compileC(xs, env) + compileC(x, argOffset(1, env)) + @immut/list.of([Pack(1, 2)])
}

此时，出现了一个新问题。以前，打印求值结果只需要处理简单的 NNum 节点，但 NConstr 节点有子结构。当列表本身被求值到 WHNF 时，它的子结构大多是未求值的 NApp 节点。我们需要添加一个 Print 指令，它将递归地求值并将结果写入 GState 的 output 组件。

fn gprint(self : GState) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(n) => {
      self.output.write_string(n.to_string())
      self.output.write_char(' ')
    }
    NConstr(0, Nil) => self.output.write_string("Nil")
    NConstr(1, Cons(addr1, Cons(addr2, Nil))) => {
      self.code = @immut/list.of([Instruction::Eval, Print, Eval, Print]) + self.code
      self.put_stack(addr2)
      self.put_stack(addr1)
    }
    _ => panic()
  }
}

最后，将 G-Machine 的初始代码修改为：

代码：@immut/list.of([PushGlobal("main"), Eval, Print]),

现在，我们可以使用懒惰列表编写一些经典的函数式程序，例如无限斐波那契数列：

(defn fibs[] (Cons 0 (Cons 1 (zipWith add fibs (tail fibs)))))

引入数据结构后，严格性分析变得更加复杂。对于懒惰列表，有几种评估模式：

  • 完全严格（要求列表是有限的，且所有元素都不能是底值）。

  • 完全懒惰。

  • 头部严格（列表可以是无限的，但其元素不能是底值）。

  • 尾部严格（列表必须是有限的，但其元素可以是底值）。

此外，函数使用的上下文可以改变其参数的评估模式（不能孤立分析，需要跨函数分析）。这种复杂的严格性分析通常采用投影分析技术。相关文献包括：

  • Projections for Strictness Analysis

  • Static Analysis and Code Optimizations in Glasgow Haskell Compiler

  • Implementing Projection-based Strictness Analysis

  • Theory and Practice of Demand Analysis in Haskell

结语#

懒惰求值可以减少运行时冗余计算，但它也引入了一些新问题，例如：

  • 臭名昭著的副作用顺序问题。

  • 过多的冗余节点。一些未共享的计算仍然将结果存储在堆中，这不利于利用 CPU 的缓存机制。

懒惰求值语言的代表 Haskell 提出了一个有争议的解决方案来解决副作用顺序问题：单子（Monads）。这个解决方案对急切求值语言也有一定价值，但许多在线教程过于强调其数学背景，未能有效解释如何使用它。

Idris2，Haskell 的继任者（不再是懒惰语言），保留了单子并引入了另一种处理副作用的机制：代数效应（Algebraic Effects）。

由 SPJ 设计的无脊柱 G-Machine 改善了过多冗余节点的问题，它的继任者 STG 统一了不同类型节点的数据布局。

除了抽象机器模型的改进外，GHC 对 Haskell 程序的优化还大量依赖于基于内联的优化和基于投影分析的严格性分析技术。

2004 年，几位 GHC 设计者发现，之前的 push-enter 模型（参数被推入栈中，然后调用函数）比 eval-apply 模型效果差，后者将责任交给了调用者。他们发表了一篇题为《Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages》的论文。

2007 年，Simon Marlow 发现 tagless 设计中的跳转和执行代码显著影响了现代 CPU 分支预测器的性能。论文《Faster laziness using dynamic pointer tagging》描述了几种解决方案。

懒惰的纯函数式语言展现了许多有趣的可能性，但也面临着许多批评和反思。尽管如此，它无疑是一项引人入胜的技术！

目录