numeric_expr 教程

本教程介绍如何将一次计算描述为一棵 numeric_expr 树，并通过提供两个回调在任意数值类型上运行它：一个读取字面量，一个执行运算。学完本教程，你将能够在 Int 上、在带 IEEE 标志的 BinFloat 上对表达式求值，并在源代码行处报告失败。符合性前端（frontend/gda_expr 等）正是用这一机制来运行测试语料的。

快速入门

将该包添加到 moon.pkg：

import {
  "Luna-Flow/floating/numeric_expr",
}

构建 1 + 2 并在 Int 上求值：

///|
test "quick start" {
  let one_plus_two = @numeric_expr.Expr::invoke(
    @numeric_expr.Operation::new("add"),
    [
      @numeric_expr.Expr::literal(@numeric_expr.Literal::new("1")),
      @numeric_expr.Expr::literal(@numeric_expr.Literal::new("2")),
    ],
  )
  let result : Result[Int, @numeric_expr.EvalError[String]] = @numeric_expr.evaluate(
    one_plus_two,
    literal => if literal.raw() == "1" { Ok(1) } else { Ok(2) },
    (_, arguments) => Ok(arguments[0] + arguments[1]),
  )
  inspect(result is Ok(3), content="true")
}

evaluate 先解码两个字面量，然后以解码后的参数 [1, 2] 调用运算回调。

日常任务

编写一个小型解释器

大多数调用方会对运算名和参数数组做模式匹配。匹配数组模式还会检查元数，而 numeric_expr 本身并不做这一检查：

///|
fn int_literal(literal : @numeric_expr.Literal) -> Result[Int, String] {
  match literal.raw() {
    "0" => Ok(0)
    "1" => Ok(1)
    "2" => Ok(2)
    "3" => Ok(3)
    "10" => Ok(10)
    other => Err("not a small integer: " + other)
  }
}

///|
fn int_operation(
  operation : @numeric_expr.Operation,
  arguments : Array[Int],
) -> Result[Int, String] {
  match (operation.name(), arguments) {
    ("add", [a, b]) => Ok(a + b)
    ("mul", [a, b]) => Ok(a * b)
    ("neg", [a]) => Ok(-a)
    ("sum", values) => Ok(values.fold(init=0, (acc, x) => acc + x))
    (name, values) =>
      Err(name + " does not take " + values.length().to_string() + " arguments")
  }
}

///|
fn lit(raw : String) -> @numeric_expr.Expr {
  @numeric_expr.Expr::literal(@numeric_expr.Literal::new(raw))
}

///|
fn call(name : String, arguments : Array[@numeric_expr.Expr]) -> @numeric_expr.Expr {
  @numeric_expr.Expr::invoke(@numeric_expr.Operation::new(name), arguments)
}

///|
test "small interpreter" {
  // -(2 * 3) + sum(1, 2, 3, 10)
  let expression = call("add", [
    call("neg", [call("mul", [lit("2"), lit("3")])]),
    call("sum", [lit("1"), lit("2"), lit("3"), lit("10")]),
  ])
  let result = @numeric_expr.evaluate(expression, int_literal, int_operation)
  inspect(result is Ok(10), content="true")
}

sum 表明一个运算可以接受任意数量的参数；由回调决定。

在 BinFloat 上求值并收集 IEEE 标志

值类型 V 可以携带的不只是一个数。这里每个值都是一个 BinFloat 加上迄今为止引发的 IEEE 标志，每个运算都会把其参数的标志与自身的标志合并：

///|
fn binary_literal(
  literal : @numeric_expr.Literal,
) -> Result[(@bin_float.BinFloat, @bin_float.BinaryFlags), String] {
  match
    @bin_float.BinFloat::from_string_ctx(
      literal.raw(),
      @bin_float.BinaryContext::binary64(),
    ) {
    Ok(pair) => Ok(pair)
    Err(_) => Err("not a number: " + literal.raw())
  }
}

///|
fn binary_operation(
  operation : @numeric_expr.Operation,
  arguments : Array[(@bin_float.BinFloat, @bin_float.BinaryFlags)],
) -> Result[(@bin_float.BinFloat, @bin_float.BinaryFlags), String] {
  let context = @bin_float.BinaryContext::binary64()
  match (operation.name(), arguments) {
    ("add", [(a, fa), (b, fb)]) => {
      let (value, flags) = a.add_ctx(b, context)
      Ok((value, fa.combine(fb).combine(flags)))
    }
    ("div", [(a, fa), (b, fb)]) => {
      let (value, flags) = a.div_ctx(b, context)
      Ok((value, fa.combine(fb).combine(flags)))
    }
    _ => Err("unsupported " + operation.name())
  }
}

///|
test "binary64 evaluation with flags" {
  // 1/3 + 1/3 in binary64
  let third = call("div", [lit("1"), lit("3")])
  let result = @numeric_expr.evaluate(
    call("add", [third, third]),
    binary_literal,
    binary_operation,
  )
  match result {
    Ok((value, flags)) => {
      inspect(value.to_hex(), content="0x15555555555555p-53")
      inspect(flags.inexact(), content="true")
    }
    Err(_) => fail("expected a value")
  }
}

只需替换两个回调，同一棵树就可以在 @decimal_gda.Decimal 上求值；表达式中没有任何内容依赖于数值类型。

在源头报告错误

为每个节点赋予其来源文本的区间（span）。当回调失败时，EvalError 会返回失败的节点，从而可以借助该区间定位错误：

///|
test "locate a bad operand" {
  let span = @numeric_expr.SourceSpan::new("rows.txt", line=42, column=9)
  let expression = @numeric_expr.Expr::invoke(
    @numeric_expr.Operation::new("add", span~),
    [
      @numeric_expr.Expr::literal(@numeric_expr.Literal::new("2", span~)),
      @numeric_expr.Expr::literal(@numeric_expr.Literal::new("two", span~)),
    ],
  )
  let message = match
    @numeric_expr.evaluate(expression, int_literal, int_operation) {
    Ok(_) => "ok"
    Err(@numeric_expr.LiteralFailure(literal, error)) =>
      literal.span().source() +
      ":" +
      literal.span().line().to_string() +
      ": " +
      error
    Err(@numeric_expr.OperationFailure(operation, error)) =>
      operation.name() + ": " + error
    Err(@numeric_expr.UnsupportedExpression(_)) => "unsupported"
  }
  inspect(message, content="rows.txt:42: not a small integer: two")
}

观察求值顺序

回调按后序、从左到右运行，并在第一次失败时停止求值。跟踪记录可以直观地展示这一点：

///|
test "post-order with early stop" {
  let trace : Array[String] = []
  let expression = call("add", [
    call("mul", [lit("2"), lit("3")]),
    call("add", [lit("bad"), lit("1")]),
  ])
  let _ = @numeric_expr.evaluate(
    expression,
    literal => {
      trace.push(literal.raw())
      int_literal(literal)
    },
    (operation, arguments) => {
      trace.push(operation.name())
      int_operation(operation, arguments)
    },
  )
  inspect(trace.join(" "), content="2 3 mul bad")
}

字面量 1 和两个 add 节点都从未被访问，因为 bad 先失败了。

深入了解

• 语料前端。 frontend/gda_expr 把每个 .decTest 行 id operation operands -> expected conditions 降低为 Expr::invoke(Operation::new(op), operands.map(Expr::literal))，并用基于 @decimal_gda 的回调对其求值。完整的模式示例请阅读 gda_expr。
• 更丰富的值。 当运算返回不同种类的结果（数值、布尔值、字符串）时，V 可以是一个枚举，gda_expr 对 compare、class 和 isnan 就是这样做的。
• 带类型的错误。 E 可以是你自己的枚举而不是 String；EvalError[E] 会原样保留它。
• checked 流水线。 如果希望定义域错误作为值保留而不是终止求值，可让 V 为 checked 类型（如 @bin_float_checked.BinFloatResult），并让回调始终返回 Ok。

常见陷阱

• 没有元数检查。 Expr::invoke 接受任意数量的参数。请在 invoke 中检查元数（数组模式即可做到），并在不匹配时返回 Err。
• 提前停止。 第一次失败之后不再运行任何回调。不要依赖失败节点右侧节点的回调所产生的副作用。
• 深层树。 求值是递归的，栈深度等于树高。非常深的左倾树（例如以嵌套 add 构建的一百万项之和）可能耗尽栈空间；请改为构建一个扁平的 sum 节点。
• 默认区间。 没有显式区间的节点报告 SourceSpan::new("")，其行号和列号均为 0。
• 这里不解析字面量。 Literal 只存储原始文本。转换时的舍入、精度和标志完全由你的 decode 回调决定。

后续步骤

• numeric_expr API 列出了每个条目。
• numeric_expr 设计 阐述了求值语义及其不变式。
• gda_expr 教程 通过此包运行真实的十进制测试行。