experiment API

Luna-Flow/mare_mark/experiment 承载基准测试中关于正确性的部分：参考判定器与关系判定器、输入缩减，以及把各规模上的判定结果转化为规模分界点的交叉点分析。运行器会使用这些判定器和缩减器；你也可以直接调用它们。参见 experiment 设计。

源码：src/experiment/experiment.mbt。

import {
  "Luna-Flow/mare_mark/model",
  "Luna-Flow/mare_mark/experiment",
}

判定器

ReferenceOracle

ReferenceOracle 计算每一步的期望结果，并据此判定某个实现的结果。

pub struct ReferenceOracle[Input, Expected, Output, Context] {
  id : String
  initial_context : () -> Context
  sequence_length : (Input) -> Int
  compute_expected : (Input, Int, Context) -> @model.OperationResult[Expected, Context]
  validate : (Input, Int, @model.ExecutionOutcome[Expected], @model.ExecutionOutcome[Output]) -> @model.ValidationStatus
  expected_text : (Expected) -> String
}
pub fn[Input, Expected, Output, Context] ReferenceOracle::new(String, () -> Context, (Input) -> Int, (Input, Int, Context) -> @model.OperationResult[Expected, Context], (Input, Int, @model.ExecutionOutcome[Expected], @model.ExecutionOutcome[Output]) -> @model.ValidationStatus, (Expected) -> String) -> Self[Input, Expected, Output, Context]

compute_expected(input, step, context) 返回第 step 步的期望结果以及判定器的下一个上下文；当它不再返回上下文时序列结束。validate(input, step, expected, actual) 返回判定结果。expected_text 在证据中渲染期望值。运行器使用用例的 sequence_length，而不是判定器的 sequence_length 函数。

ReferenceOracle::equal

ReferenceOracle::equal 由一个参考函数和一个相等性判断构建单步判定器。

pub fn[Input, Expected, Output] ReferenceOracle::equal(String, (Input) -> Expected, (Expected, Output) -> Bool) -> Self[Input, Expected, Output, Unit]

当两个结果都是 Value 且比较器接受它们时，判定结果为 Valid；比较器拒绝时为 Invalid("value mismatch")；其他任何结果组合则为 Invalid("outcome mismatch")。期望值渲染为 "<expected>"。

test "an equality oracle with a tolerance" {
  let oracle = @experiment.ReferenceOracle::equal(
    "sqrt",
    (x : Double) => x.sqrt(),
    (expected : Double, actual : Double) => (expected - actual).abs() <= 1.0e-12,
  )
  let ok = @experiment.validate_reference(oracle, 2.0, 0, Value(2.0.sqrt()), Value(1.4142135623731), "fast", "2")
  let bad = @experiment.validate_reference(oracle, 2.0, 0, Value(2.0.sqrt()), Value(1.5), "fast", "2")
  inspect(ok.status is Valid, content="true")
  inspect(bad.status is Invalid("value mismatch"), content="true")
}

validate_reference

validate_reference 把参考判定器应用于一步，并将判定结果包装为不带证据的 Validation。

pub fn[Input, Expected, Output, Context] validate_reference(ReferenceOracle[Input, Expected, Output, Context], Input, Int, @model.ExecutionOutcome[Expected], @model.ExecutionOutcome[Output], String, String) -> @model.Validation

参数：判定器、输入、步骤、期望结果、实际结果、实现 id、规模文本。

RelationalOracle

RelationalOracle 在没有唯一参考时让两个实现相互判定。

pub struct RelationalOracle[Input, Output] {
  id : String
  validate_pair : (Input, Int, String, @model.ExecutionOutcome[Output], String, @model.ExecutionOutcome[Output]) -> @model.ValidationStatus
}
pub fn[Input, Output] RelationalOracle::new(String, (Input, Int, String, @model.ExecutionOutcome[Output], String, @model.ExecutionOutcome[Output]) -> @model.ValidationStatus) -> Self[Input, Output]

validate_pair(input, step, left_id, left, right_id, right) 返回这一对的判定结果；运行器把它归于右侧实现。

test "a relational oracle" {
  let agree = @experiment.RelationalOracle::new("agree", (_ : Int, _, _, left : @model.ExecutionOutcome[Int], _, right) => {
    match (left, right) {
      (Value(a), Value(b)) if a == b => Valid
      (_, Unsupported(reason)) => Unsupported(reason)
      _ => Invalid("implementations disagree")
    }
  })
  inspect((agree.validate_pair)(1, 0, "a", Value(3), "b", Value(3)) is Valid, content="true")
  inspect((agree.validate_pair)(1, 0, "a", Value(3), "b", Value(4)) is Invalid(_), content="true")
}

OracleSpec

OracleSpec 选择用例的判定器。

pub(all) enum OracleSpec[Input, Expected, Output, Context] {
  Reference(ReferenceOracle[Input, Expected, Output, Context])
  Relational(RelationalOracle[Input, Output])
  ReferenceAndRelational(ReferenceOracle[Input, Expected, Output, Context], RelationalOracle[Input, Output])
}

使用 ReferenceAndRelational 时，运行器执行两种检查并分别报告。

缩减

Shrinker

Shrinker 为失败的输入提出更小的变体。

pub struct Shrinker[Input] {
  candidates : (Input) -> Array[Input]
  text : (Input) -> String
  max_steps : Int
}
pub fn[Input] Shrinker::new((Input) -> Array[Input], (Input) -> String, max_steps? : Int) -> Self[Input]

candidates(x) 列出更小的输入，最激进的排在最前。text 为缩减路径渲染被接受的候选。max_steps（默认 128）限制尝试的候选数量。

shrink

shrink 在谓词持续成立的前提下最小化输入。

pub fn[Input] shrink(Input, Shrinker[Input], (Input) -> Bool) -> (Input, Array[String])

从输入开始，它反复选取第一个使谓词为真的候选，直到没有候选满足谓词或已尝试 max_steps 个候选为止。它返回最后被接受的输入，以及按顺序排列的被接受候选的文本。初始输入本身不会被测试。

test "shrink a failing size" {
  let shrinker = @experiment.Shrinker::new(
    (n : Int) => if n <= 1 { [] } else { [n / 2, n - 1] },
    n => n.to_string(),
  )
  let (smallest, path) = @experiment.shrink(64, shrinker, n => n >= 5)
  inspect(smallest, content="5")
  debug_inspect(path, content="[\"32\", \"16\", \"8\", \"7\", \"6\", \"5\"]")
}

交叉点分析

ScaleDomain

ScaleDomain 列出分析所用的规模及其顺序和文本。

pub struct ScaleDomain[Scale] {
  values : Array[Scale]
  compare : (Scale, Scale) -> Int
  text : (Scale) -> String
}
pub fn[Scale] ScaleDomain::new(Array[Scale], (Scale, Scale) -> Int, (Scale) -> String) -> Self[Scale]

crossover_from_labels 按给定顺序读取 values，不会对其排序；请传入已排序的值。

comparator_label

comparator_label 把相对差值转换为交叉点分析所用的标签。

pub fn comparator_label(Double, Double) -> String

当 $r \le -t$ 时 comparator_label(r, t) 为 "A"，当 $r \ge t$ 时为 "B"，否则为 "Unknown"。请传入以 B 为基线测得的 A 的相对差值，这样 "A" 就表示 A 更快。

crossover_from_labels

crossover_from_labels 找出首选实现发生变化的规模。

pub fn[Scale] crossover_from_labels(ScaleDomain[Scale], Array[String]) -> @model.CrossoverResult[Scale]

labels[i] 是 values[i] 处的判定结果。一次转变是指一对相邻、彼此不同且都不是 "Unknown" 的标签。

情形	结果
没有标签，或标签与值的数量不同	Inconclusive("label/domain length mismatch", labels)
没有转变	NoCrossover("no stable label transition", labels)
恰好一次转变，位于 $i-1$ 与 $i$ 之间	Found(ScaleBoundary(values[i-1], values[i]), "piecewise-confirmed", labels)
多于一次转变	NonMonotonic(labels)

test "find a crossover" {
  let domain = @experiment.ScaleDomain::new([16, 64, 256, 1024], (a, b) => a.compare(b), n => n.to_string())
  let labels = [-12.0, -4.0, 6.0, 15.0].map(r => @experiment.comparator_label(r, 3.0))
  debug_inspect(labels, content="[\"A\", \"A\", \"B\", \"B\"]")
  guard @experiment.crossover_from_labels(domain, labels) is Found(boundary, _, _) else {
    fail("expected a crossover")
  }
  inspect(boundary.below, content="64")
  inspect(boundary.at_or_above, content="256")
}