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类似于一个关系，除了当发现一个新的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_par! 和 ascent_run_par! 生成并行化代码。自然地，列类型必须是 Send + Sync 才能在并行 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_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

聚合器甚至可以是参数化的！有关参数化聚合器的示例，请查看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);
     // ...
  }
  

  提示：如果您收到“private type ... in public interface (error E0446)”警告，您可以通过使生成的Ascent类型私有来解决它，如上面示例所示。