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/examples 目录中的更完整示例集。

功能

格

Ascent 支持计算用户定义格的固定点。在 Ascent 中，lattice 关键字定义了一个格。一个 lattice 的最后一列的类型必须实现 Lattice trait。一个 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_par! 和 ascent_run_par! 生成并行化代码。自然地，列类型必须是 Send + Sync 才能在并行上升中工作。

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

BYODS

BYODS（代表 Bring Your Own Data Structures to Datalog）是上升的一个功能，它允许关系由自定义数据结构支持。此功能通过优化用于支持关系的数据结构来改进上升程序的算法复杂度。例如，需要计算大型图的传递闭包的程序可以通过为传递闭包关系选择基于并查集的数据结构 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)] 属性指示上升编译器使用模块 trrel_uf 中定义的数据结构提供者来为 path 关系。您可以在此处找到 BYODS 显著加快上升计算的完整示例。

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

ascent_run!

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

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

聚合器甚至可以参数化！有关参数化聚合器的示例，请查阅ascent::aggregators中的percentile定义。

宏定义

定义扩展为正文项或头部项的宏可能很有用。Ascent允许您这样做。

有关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类型私有来修复它，如上述示例所示。