Ascent

Ascent는 Rust에 매크로를 통해 임베디드된 Datalog 유사 논리 프로그래밍 언어입니다.

자세한 내용은 Ascent에 관한 CC 논문을 참고하세요.

또한, 이 OOPSLA 논문은 Ascent의 “Datalog에 당신만의 자료구조를 가져오기(Bring Your Own Data Structures to Datalog, BYODS)” 측면을 설명합니다.

예제

보다 완전한 예제는 ascent/examples 디렉터리를 참고하세요.

그래프에서 모든 연결된 노드 계산하기

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. src/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

기능

격자(Lattice)

Ascent는 사용자 정의 격자의 고정점을 계산하는 기능을 지원합니다. lattice 키워드는 Ascent에서 격자를 정의합니다. lattice의 마지막 컬럼 타입은 반드시 Lattice 트레이트를 구현해야 합니다. lattice는 관계와 비슷하지만, 새 lattice 사실 (v 1, v 2, …, v(n-1), v n)이 발견되었을 때 데이터베이스에 이미 (v 1, v 2, …, 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)입니다. 최단 경로에 관심이 있으므로, 임의의 노드 쌍에 대한 두 경로 길이 l1과 l2 중 min(l1, l2)만 저장하기 위해 Dual<T>를 사용합니다.

병렬 Ascent

Ascent는 병렬 코드를 생성할 수 있습니다. 매크로 ascent_par!와 ascent_run_par!는 병렬화된 코드를 생성합니다. 당연히 컬럼 타입은 병렬 Ascent에서 동작하려면 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)] // 이 관계를 전이적으로 만듭니다
   relation path(Node, Node);
   
   path(x, y) <-- edge(x, y);
}

#[ds(trrel_uf)] 속성은 path 관계에 대해 trrel_uf 모듈에 정의된 자료구조 제공자를 사용하도록 Ascent 컴파일러에 지시합니다. 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!의 병렬 버전인 ascent_run_par!도 제공합니다.

조건과 생성 절(Generative Clauses)

문법은 Rust 사용자에게 친숙하도록 설계되었습니다. 이 예제에서 edge는 node로부터 비자기루프(non-reflexive) 간선을 채웁니다. 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는 계층화된 부정(stratified negation)과 집계를 지원합니다. 집계기는 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 매크로의 매크로에 대해 더 알고 싶다면 여기를 참고하세요.

ascent_source!와 include_source!

Ascent 코드를 ascent_source! 매크로 호출 안에 작성하고, 이후 실제 Ascent 프로그램에 포함할 수 있습니다. 이를 통해 서로 다른 Ascent 프로그램 간 Ascent 코드를 재사용하고, 서로 다른 코드 “모듈”로부터 Ascent 프로그램을 합성할 수 있습니다.

mod ascent_code {
   ascent::ascent_source! { my_awesome_analysis:
      // 나의 멋진 분석을 위한 Ascent 코드
   }
}

// 다른 위치에서:
ascent! {
   struct MyAwesomeAnalysis;
   include_source!(ascent_code::my_awesome_analysis);
}

ascent_par! {
   struct MyAwesomeAnalysisParallelized;
   include_source!(ascent_code::my_awesome_analysis);
}

기타

• #![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 타입을 비공개로 만들어 해결할 수 있습니다.