Rust 中的逻辑编程

Ascent 是一种逻辑编程语言（类似于 Datalog），通过宏嵌入 Rust。

有关 Ascent 的更多信息，请参阅 CC 论文。

此外，此 OOPSLA 论文 描述了 Ascent 的 "将用户自定义数据结构带给 Datalog" 方面。

示例

计算图中的所有连接节点

ascent! {
   relation edge(i32, i32);
   relation path(i32, i32);
   
   path(x, y) <-- edge(x, y);
   path(x, z) <-- edge(x, y), path(y, z);
}

使用 Ascent

1. 安装 Rust.
2. 创建一个新的 Rust 项目

   cargo new my-ascent-project
   cd my-ascent-project
   

3. 在 Cargo.toml 中将 ascent 添加为依赖项

   [dependencies]
   ascent = "*"
   

4. 在 main.rs 中编写一些 Ascent 代码。这里是一个完整的示例

   use ascent::ascent;
   ascent! {
      relation edge(i32, i32);
      relation path(i32, i32);
      
      path(x, y) <-- edge(x, y);
      path(x, z) <-- edge(x, y), path(y, z);
   }
   
   fn main() {
      let mut prog = AscentProgram::default();
      prog.edge = vec![(1, 2), (2, 3)];
      prog.run();
      println!("path: {:?}", prog.path);
   }
   

5. 运行程序

   cargo run
   

功能

格

Ascent 支持计算用户定义格的固定点。在 Ascent 中，lattice 关键字定义了一个格。格的最后一列的类型必须实现 Lattice 特性。一个 lattice 类似于关系，除了当发现一个新的 lattice 事实（v₁，v₂，...，v_(n-1)，v_n）时，如果数据库中已经存在一个事实（v₁，v₂，...，v_(n-1)，v'_n），则 v_n 和 v'_n 将通过 join 合并在一起，以产生一个单一的事实。

此功能允许编写在 Datalog 中无法表达的程序。例如，我们可以使用此功能来计算图中节点之间的最短路径长度。

ascent! {
   lattice shortest_path(i32, i32, Dual<u32>);
   relation edge(i32, i32, u32);

   shortest_path(x, y, Dual(*w)) <-- edge(x, y, w);

   shortest_path(x, z, Dual(w + l)) <-- 
      edge(x, y, w), 
      shortest_path(y, z, ?Dual(l));
}

在这个示例中，Dual<T> 是格 T 的对偶。我们使用 Dual<T> 是因为我们对最短路径感兴趣，对于任何给定的两个路径长度 l1 和 l2，我们只存储 min(l1, l2)。

并行 Ascent

Ascent 能够生成并行代码。宏 ascent_par! 和 ascent_run_par! 用于生成并行化代码。显然，列类型必须是 Send + Sync 才能在 Ascent 中并行运行。

并行 Ascent 使用 rayon，因此可以通过 rayon 的 ThreadPoolBuilder 或使用 RAYON_NUM_THREADS 环境变量（更多信息请见 此处）来控制并行级别。

BYODS

BYODS（代表Bring Your Own Data Structures to Datalog）是 Ascent 的一个功能，它允许关系由自定义数据结构支持。此功能可以通过优化支持关系的用于数据结构来提高 Ascent 程序的算法复杂性。例如，需要计算大型图传递闭包的程序可以通过为传递闭包关系选择基于并查集的数据结构 trrel_uf（在 ascent-byods-rels 中定义）来提高其性能

在 Cargo.toml 中

[dependencies]
ascent-byods-rels = "*"
ascent = "*"

use ascent_byods_rels::trrel_uf;
ascent! {
   relation edge(Node, Node);
   
   #[ds(trrel_uf)] // Makes the relation transitive
   relation path(Node, Node);
   
   path(x, y) <-- edge(x, y);
}

#[ds(trrel_uf)] 属性指示 Ascent 编译器使用模块 trrel_uf 中定义的数据结构提供程序为 path 关系。您可以在此处找到 BYODS 显著加快 Ascent 计算的完整示例。

有关 BYODS 的更多信息，请参阅 BYODS.MD。

ascent_run!

除了 ascent! 之外，我们还提供了 ascent_run! 宏。与 ascent! 不同，此宏在调用时评估 Ascent 程序。ascent_run! 的主要优点是本地变量在 Ascent 程序内部是有效的。例如，我们可以定义一个用于发现关系的（可选自反的）传递闭包的函数，如下所示

fn tc(r: Vec<(i32, i32)>, reflexive: bool) -> Vec<(i32, i32)> {
   ascent_run! {
      relation r(i32, i32) = r;
      relation tc(i32, i32);
      tc(x, y) <-- r(x, y);
      tc(x, z) <-- r(x, y), tc(y, z);
      tc(x, x), tc(y, y) <-- if reflexive, r(x, y);
   }.tc
}

在上面的示例中，我们直接初始化关系 r 以缩短程序。

我们还提供了 ascent_run_par!，这是 ascent_run! 的并行版本。

条件和生成子句

语法设计得与 Rust 用户熟悉。在这个例子中，edge 被填充了来自 node 的非自反边。请注意，任何实现了 Clone + Eq + Hash 的类型都可以用作关系列。

ascent! {
   relation node(i32, Rc<Vec<i32>>);
   relation edge(i32, i32);
   
   edge(x, y) <--
      node(x, neighbors),
      for &y in neighbors.iter(),
      if x != y;
}

否定和聚合

Ascent 支持分层否定和聚合。聚合器定义在 ascent::aggregators 中。您可以在那里找到 sum、min、max、count 和 mean。

在以下示例中，学生的平均成绩存储在 avg_grade

use ascent::aggregators::mean;
type Student = u32;
type Course = u32;
type Grade = u16;
ascent! {
   relation student(Student);
   relation course_grade(Student, Course, Grade);
   relation avg_grade(Student, Grade);

   avg_grade(s, avg as Grade) <--
      student(s),
      agg avg = mean(g) in course_grade(s, _, g);
}

如果提供的聚合器不足，您可以定义自己的聚合器。例如，一个用于获取列中第二高值的聚合器的签名可以是以下内容

fn second_highest<'a, N: 'a>(inp: impl Iterator<Item = (&'a N,)>) -> impl Iterator<Item = N>
where N: Ord + Clone

聚合器甚至可以参数化！有关参数化聚合器的示例，请查看这里关于 percentile 的定义。

宏定义

定义宏以展开为体项或头项可能会有用。Ascent 允许您这样做。

有关宏的更多信息，请在此处查找。

杂项

• #![measure_rule_times] 会导致测量单个规则的执行时间。示例

  ascent! {
     #![measure_rule_times]
     // ...
  }
  let mut prog = AscentProgram::default();
  prog.run();
  println!("{}", prog.scc_times_summary());
  

  请注意，scc_times_summary() 对所有 Ascent 程序都生成。使用 #![measure_rule_times]，它还会报告单个规则的执行时间。

• 使用 #![generate_run_timeout]，会生成一个 run_timeout 函数，该函数在给定时间后停止。

• wasm-bindgen 功能允许 Ascent 程序在 WASM 环境中运行。

• struct 声明可以添加到 ascent! 定义的最上面。这允许更改生成的类型的名称和可见性，以及引入类型/生命周期参数和约束。

  ascent! {
     struct GenericTC<N: Clone + Eq + Hash>;
     relation edge(N, N);
     // ...
  }
  

  提示：如果您收到“在公共接口中声明私有类型 ... (错误 E0446)”警告，您可以像上面的示例那样将生成的 Ascent 类型设为私有来修复它。