Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Rust로 다루는 E-그래프

· 태그: programming, rust, compilers · 원문 · 한국어 번역(원문에서 변경됨)

E-그래프(*동치 그래프(equality graph)*라고도 합니다)는 프로그래밍 언어 공학에서 가장 흥미롭고 빠르게 발전하는 분야 중 하나입니다. 1980년 Gregory Nelson의 박사 학위 논문에서 처음 고안된 E-그래프는 표현식 사이의 동치 관계를 유지하는 기반 자료 구조로 자리 잡았습니다. 처음에는 SMT 솔버를 구동하기 위해 만들어졌지만, 최근 몇 년 사이 그 응용 범위가 극적으로 넓어졌습니다.

이러한 e-그래프 응용의 부흥을 이끈 것은 동치 포화와 같은 기법으로, 이 기법을 쓰면 동치인 표현식들을 더 효율적으로 탐색할 수 있습니다. E-그래프의 핵심 혁신은 항 재작성에서 이른바 “선택 문제(choice problem)“를 해결할 수 있다는 점입니다. 전통적인 항 재작성은 파괴적입니다. 표현식을 한 번 변환하면 원래 표현식은 사라집니다. 그래서 국소적으로는 최적이지만 전역적으로는 최적이 아닐 수 있는 특정 최적화 선택을 미리 확정해야만 합니다. 예를 들어 x + x는 x * 2로 최적화할 수 있지만, 이를 (x + x) - x에 적용하면 덧셈 하나와 뺄셈이 서로 상쇄되어 그냥 x가 된다는 사실을 발견할 수 없게 됩니다.

E-그래프는 가능한 모든 동치 표현식을 압축된 형태로 동시에 유지함으로써 이 문제를 해결합니다. E-그래프는 다음으로 구성됩니다.

  • E-클래스(E-Class): 동치인 표현식들의 집합
  • E-노드(E-Node): 자식이 (다른 e-노드를 직접 가리키지 않고) e-클래스를 가리키는 연산자
  • E-클래스 ID(E-Class ID): e-클래스의 고유 식별자

E-그래프의 강력함은 두 가지 핵심 성질에서 나옵니다.

  1. 합동(Congruence): x가 y와 동치이면 f(x)도 f(y)와 동치여야 합니다. 이 성질은 동치 관계가 발견될 때마다 자동으로 유지됩니다.

  2. 압축 표현(Compact Representation): E-그래프는 비슷한 표현식 사이에서 구조를 공유하므로, 지수적으로 많은 동치 표현식을 선형 공간에 표현할 수 있습니다.

동치 포화라는 기법을 통해 E-그래프를 최적화에 사용할 때, 그 과정은 다음과 같이 진행됩니다.

  1. 초기 표현식을 E-그래프로 변환합니다
  2. 가능한 모든 재작성을 반복 적용하여 동치 관계를 발견합니다
  3. 어떤 비용 함수에 따라 최적의 표현식을 추출합니다

Rust에서 E-그래프를 시작하기 위해, E-그래프를 다루는 강력하고 사용하기 편한 API를 제공하는 egg 라이브러리를 사용하겠습니다. 먼저 Cargo.toml에 egg 크레이트를 추가하십시오.

[dependencies]
egg = "0.6"

E-그래프의 합동

E-그래프의 근본적인 성질은 단순한 동치 관계가 아니라 합동 관계를 유지한다는 점입니다. 합동이란 두 표현식 x와 y가 동치이면, x를 포함하는 더 큰 표현식은 x를 y로 바꾼 같은 표현식과 동치여야 한다는 뜻입니다. 더 형식적으로 말하면, x ≡ y이면 임의의 문맥 f에 대해 f(x) ≡ f(y)입니다.

간단한 예제로 이것이 실제로 어떻게 동작하는지 살펴봅시다.

#![allow(unused)]
fn main() {
use egg::*;

define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        Symbol(Symbol),
    }
}

fn congruence_example() {
    let mut egraph = EGraph::<SimpleLanguage, ()>::default();

    // Create expressions: (+ a x) and (+ a y)
    let a = egraph.add(SimpleLanguage::Symbol("a".into()));
    let x = egraph.add(SimpleLanguage::Symbol("x".into()));
    let y = egraph.add(SimpleLanguage::Symbol("y".into()));

    let expr1 = egraph.add(SimpleLanguage::Add([a, x]));  // (+ a x)
    let expr2 = egraph.add(SimpleLanguage::Add([a, y]));  // (+ a y)

    // Initially, these are in different e-classes
    assert_ne!(egraph.find(expr1), egraph.find(expr2));

    // When we declare x ≡ y...
    egraph.union(x, y);
    egraph.rebuild();

    // ...congruence ensures (+ a x) ≡ (+ a y)
    assert_eq!(egraph.find(expr1), egraph.find(expr2));
}
}

이 예제에서는 다음과 같습니다.

  1. 서로 다른 e-클래스에 있는 두 표현식 (+ a x)와 (+ a y)에서 시작합니다
  2. union을 사용해 x와 y가 동치라고 선언하면
  3. e-그래프는 (+ a x)와 (+ a y)를 포함하는 e-클래스들을 자동으로 병합합니다.

이 합동(congruence) 성질은 동치 관계가 발견될 때마다 e-그래프에 의해 자동으로 유지됩니다. e-그래프가 rebuild 연산을 수행하면 다음과 같이 동작합니다.

  1. 합동으로 인해 동치가 된 모든 e-노드를 찾습니다.
  2. 그 e-노드들을 포함하는 e-클래스들을 병합합니다.
  3. 더 이상 병합할 수 없을 때까지 반복합니다.

이처럼 합동이 자동으로 유지된다는 점이 e-그래프를 항 재작성과 프로그램 최적화에 매우 강력한 도구로 만듭니다. 이를 통해 더 큰 식 안에서의 치환을 거쳐 간접적으로 동치가 되는 경우에도 모든 동치인 식이 올바르게 식별됩니다.

Core 개념 이해하기

코드를 살펴보기 전에 egg의 주요 추상화를 이해해 봅시다.

  1. 언어 정의: egg의 define_language! 매크로를 사용하여 식 언어를 정의해야 합니다. 각 변형(variant)은 식의 연산자 또는 리프 노드를 나타냅니다.

  2. 패턴 매칭: egg는 하위 표현식을 매칭하기 위해 ?x와 같은 변수를 사용하는 간단한 패턴 언어를 사용합니다. 이 패턴들이 재작성 규칙을 구동합니다.

  3. 재작성 규칙: 규칙은 동치인 식 사이의 양방향 변환이며, rewrite! 매크로를 사용하여 정의합니다.

  4. E-클래스 분석: 사용자 정의 분석을 e-클래스에 연결하여 동치 클래스에 대한 추가 정보를 유지할 수 있습니다.

간단한 식 언어를 정의하면서 이 개념들이 실제로 어떻게 동작하는지 살펴봅시다.

#![allow(unused)]
fn main() {
use egg::*;

// Define our expression language
define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        Symbol(Symbol),
    }
}

// Define our rewrite rules
fn make_rules() -> Vec<Rewrite<SimpleLanguage, ()>> {
    vec![
        rewrite!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
        rewrite!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),
        rewrite!("add-0"; "(+ ?a 0)" => "?a"),
        rewrite!("mul-0"; "(* ?a 0)" => "0"),
        rewrite!("mul-1"; "(* ?a 1)" => "?a"),
    ]
}
}

이제 이 규칙들을 사용하여 식을 단순화하는 간단한 함수를 만들어 봅시다.

#![allow(unused)]
fn main() {
/// Simplify an expression using egg
fn simplify(s: &str) -> String {
    // Parse the expression
    let expr: RecExpr<SimpleLanguage> = s.parse().unwrap();

    // Create a Runner and apply our rules
    let runner = Runner::default()
        .with_expr(&expr)
        .run(&make_rules());

    // Extract the smallest equivalent expression
    let extractor = Extractor::new(&runner.egraph, AstSize);
    let (best_cost, best) = extractor.find_best(runner.roots[0]);

    println!("Simplified {} to {} with cost {}", expr, best, best_cost);
    best.to_string()
}

#[test]
fn simple_tests() {
    assert_eq!(simplify("(* 0 42)"), "0");
    assert_eq!(simplify("(+ 0 (* 1 foo))"), "foo");
}
}

Core 함수

E-그래프로 작업할 때 가장 자주 사용하게 될 Core 함수는 네 가지입니다:

#![allow(unused)]
fn main() {
pub fn union(&mut self, id1: Id, id2: Id) -> bool
}

union 함수는 id1과 id2를 포함하는 e-클래스들을 병합합니다. e-클래스들이 병합되었으면 true를 반환하고, 이미 같은 e-클래스에 있었으면 false를 반환합니다.

#![allow(unused)]
fn main() {
pub fn find(&self, id: Id) -> Id
}

find 함수는 id를 포함하는 e-클래스의 대표를 반환합니다. 대표는 해당 e-클래스에서 가장 작은 식입니다.

#![allow(unused)]
fn main() {
pub fn rebuild(&mut self) -> usize
}

rebuild 함수는 합동 폐포(congruence closure)를 한 차례 수행합니다. 합동으로 인해 동치가 된 모든 e-노드를 찾아 그 e-노드들을 포함하는 e-클래스들을 병합합니다. 병합된 e-클래스의 개수를 반환합니다.

고급 기능

egg 라이브러리는 몇 가지 고급 기능도 제공합니다.

  1. 사용자 정의 분석: e-클래스에 대한 추가 정보를 유지하는 사용자 정의 분석을 정의할 수 있습니다.
#![allow(unused)]
fn main() {
#[derive(Default)]
struct ConstantFolding;

impl Analysis<Math> for ConstantFolding {
    type Data = Option<i32>;

    fn merge(&mut self, a: &mut Self::Data, b: Self::Data) -> DidMerge {
        if a == &b {
            DidMerge(false, false)
        } else {
            *a = None;
            DidMerge(true, false)
        }
    }

    fn make(egraph: &EGraph<Math, Self>, enode: &Math) -> Self::Data {
        match enode {
            Math::Num(n) => Some(*n),
            Math::Add([a, b]) => {
                let a = egraph[*a].data;
                let b = egraph[*b].data;
                a.zip(b).map(|(a, b)| a + b)
            }
            // ... other operations ...
            _ => None,
        }
    }
}
}
  1. 조건부 재작성: 규칙에는 반드시 충족되어야 하는 조건을 포함할 수 있습니다.
#![allow(unused)]
fn main() {
rw!("div-cancel"; "(/ ?a ?a)" => "1" if is_not_zero("?a"))
}

Runner API 사용하기

Runner API를 사용하여 동치 포화를 수행하는 완전한 예제를 살펴봅시다:

#![allow(unused)]
fn main() {
use egg::{*, rewrite as rw};

// Define our rewrite rules
let rules: &[Rewrite<SymbolLang, ()>] = &[
    rw!("commute-add"; "(+ ?x ?y)" => "(+ ?y ?x)"),
    rw!("commute-mul"; "(* ?x ?y)" => "(* ?y ?x)"),
    rw!("add-0"; "(+ ?x 0)" => "?x"),
    rw!("mul-0"; "(* ?x 0)" => "0"),
    rw!("mul-1"; "(* ?x 1)" => "?x"),
];

// Parse the initial expression
let start = "(+ 0 (* 1 a))".parse().unwrap();

// Run equality saturation
let runner = Runner::default().with_expr(&start).run(rules);

// Extract the best expression using AstSize cost function
let extractor = Extractor::new(&runner.egraph, AstSize);
let (best_cost, best_expr) = extractor.find_best(runner.roots[0]);

// The expression simplifies to just "a" with cost 1
assert_eq!(best_expr, "a".parse().unwrap());
assert_eq!(best_cost, 1);
}

숫자처럼 보이는 것을 다루고 있지만, 실제로 SymbolLang은 모든 것을 문자열로 저장한다는 점에 유의하십시오. 이는 단지 시연을 위한 것입니다.

추출과 비용 함수

E-그래프를 포화 상태까지 실행한 후에는, 잠재적으로 많은 동치 표현식 중에서 “가장 좋은” 표현식을 추출해야 합니다. egg 라이브러리는 비용 함수에 따라 최적의 표현식을 찾을 수 있는 Extractor를 제공합니다.

다음은 추출이 실제로 동작하는 모습을 보여 주는 완전한 예제입니다:

#![allow(unused)]
fn main() {
use egg::*;

define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
    }
}

fn extraction_example() {
    let rules: &[Rewrite<SimpleLanguage, ()>] = &[
        rewrite!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
        rewrite!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),
        rewrite!("add-0"; "(+ ?a 0)" => "?a"),
        rewrite!("mul-0"; "(* ?a 0)" => "0"),
        rewrite!("mul-1"; "(* ?a 1)" => "?a"),
    ];

    // Start with (+ 0 (* 1 10))
    let start = "(+ 0 (* 1 10))".parse().unwrap();
    let runner = Runner::default().with_expr(&start).run(rules);
    let (egraph, root) = (runner.egraph, runner.roots[0]);

    // Extract the smallest equivalent expression
    let mut extractor = Extractor::new(&egraph, AstSize);
    let (best_cost, best) = extractor.find_best(root);

    // The expression simplifies to just "10" with cost 1
    assert_eq!(best_cost, 1);
    assert_eq!(best, "10".parse().unwrap());
}
}

Extractor는 비용 함수를 사용하여 어떤 표현식을 선택할지 결정합니다. 이 예제에서는 표현식의 노드 수를 단순히 세는 AstSize를 사용합니다. 표현식 (+ 0 (* 1 10))은 단지 10으로 단순화되며, 이것의 비용은 1(단일 숫자 노드)입니다.

CostFunction 트레이트를 구현하여 사용자 정의 비용 함수를 정의할 수도 있습니다:

#![allow(unused)]
fn main() {
#[derive(Clone)]
struct CustomCost;

impl CostFunction<SimpleLanguage> for CustomCost {
    type Cost = usize;

    fn cost<C>(&mut self, enode: &SimpleLanguage, mut costs: C) -> Self::Cost
    where C: FnMut(Id) -> Self::Cost
    {
        match enode {
            SimpleLanguage::Num(_) => 1,
            SimpleLanguage::Add([a, b]) => costs(*a) + costs(*b) + 2, // penalize additions more
            SimpleLanguage::Mul([a, b]) => costs(*a) + costs(*b) + 1,
        }
    }
}
}

이 사용자 정의 비용 함수는 덧셈에 곱셈보다 더 큰 페널티를 부여하며, 이는 대상 플랫폼에서 곱셈이 더 저렴한 경우에 유용할 수 있습니다.

설명 이해하기

egg의 강력한 기능 중 하나는 e-그래프에서 두 항이 왜 동치인지 설명할 수 있는 능력입니다. 이는 재작성 규칙을 디버깅하거나 변환을 검증할 때 특히 유용합니다. 설명 API는 한 표현식을 다른 표현식으로 변환하는 재작성의 정확한 순서를 보여 줄 수 있습니다.

설명 기능을 활성화하려면, 러너를 생성할 때 with_explanations_enabled() 메서드를 사용하십시오:

#![allow(unused)]
fn main() {
use egg::*;

fn explanation_example() {
    let rules: &[Rewrite<SymbolLang, ()>] = &[
        rewrite!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
        rewrite!("add-0"; "(+ ?a 0)" => "?a"),
    ];

    let start = "(+ (+ a 0) b)".parse().unwrap();
    let end = "(+ b a)".parse().unwrap();

    let mut runner = Runner::default()
        .with_explanations_enabled()
        .with_expr(&start)
        .run(rules);

    // Get explanation of how start transforms to end
    println!("{}", runner.explain_equivalence(&start, &end).get_flat_string());
}
}

설명 출력은 변환의 각 단계를 어떤 재작성 규칙이 적용되었는지 나타내는 주석과 함께 보여 줍니다:

(+ (+ a 0) b)
(+ (Rewrite=> add-0 a) b)
(Rewrite=> commute-add (+ b a))

설명에는 두 가지 형태가 있습니다:

  1. FlatExplanation: 재작성의 선형 순서(위에 표시됨)로, 사람이 읽기에 가장 쉽습니다
  2. TreeExplanation: 공통 하위 설명을 공유할 수 있는 더 간결한 표현입니다

트리 형식은 공유되는 하위 항이 많은 큰 표현식을 다룰 때 특히 유용합니다. 다음은 트리 설명의 예입니다:

#![allow(unused)]
fn main() {
let tree_explanation = runner.explain_equivalence(&start, &end);
println!("{}", tree_explanation.get_tree_string());
}

explain_existence()를 사용하여 특정 항이 e-그래프에 왜 존재하는지 이해할 수도 있습니다:

#![allow(unused)]
fn main() {
// Find out how a specific term came to exist
let term = "(+ a b)".parse().unwrap();
if let Some(explanation) = runner.explain_existence(&term) {
    println!("Term exists because: {}", explanation.get_flat_string());
}
}

이는 예상치 못한 동치를 디버깅하거나 최적화가 의도한 대로 동작하는지 검증할 때 특히 유용합니다.

원문 © Stephen Diehl, stephendiehl.com · 글 CC BY-SA 4.0, 코드 MIT · Stephen Diehl은 런던의 소프트웨어 엔지니어이자 작가입니다(저자가 정한 소개 문구). 이 글은 저자가 개인 자격으로 쓴 것이며 어떤 조직과의 연관도 밝히거나 암시해서는 안 됩니다 (라이선스와 고지).
이 페이지는 원문을 한국어로 옮기며 변경한 비공식 번역이며 같은 CC BY-SA 4.0으로 제공합니다 · yeokja 한국어 번역 · Anthropic 사의 claude-opus-5-5 모델을 활용하여 번역되었으며 학습을 모두 비허용한 상태로 작업하였습니다.