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类似于一个关系，但当一个新的事实（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 程序。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 的定义。

宏定义

定义宏以扩展到主体项或头部项可能会有用。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 类型私有来修复它，就像上面示例中做的那样。