Did you know ... Search Documentation:
Pack egraph -- README.md

Prolog E-Graph

An SWI-Prolog implementation of an E-graph (Equivalence Graph) data structure for term rewriting, congruence closure, and e-matching.

E-graphs represent equivalence classes of expressions, allowing rewrite rules to be applied non-destructively before extracting representations based on cost.

Dependencies

This package relies on the following SWI-Prolog standard libraries:

  • library(dcg/high_order)
  • library(ordsets)
  • library(rbtrees)
  • library(heaps)

Installation

This package requires SWI-Prolog version 9.3.23 or later.

To install as a pack (if published) or run locally:

?- pack_install(egraph).

Defining Rewrite Rules

Rules are defined via the egraph:rewrite multifile predicate. During compilation, these rules generate the underlying DCG predicates that manipulate the E-graph.

Rule Syntax Forms

  • egraph:rewrite(Name, Lhs, Rhs)
  • egraph:rewrite(Name, Lhs, Rhs, RhsOptions)
  • egraph:rewrite(Name, Lhs, LhsOptions, Rhs, RhsOptions)
  • egraph:rewrite(Name, Lhs, LhsOptions, Rhs, RhsOptions) :- Body
  • egraph:analyze(Name, Lhs, RhsOptions)
  • egraph:analyze(Name, Lhs, LhsOptions, RhsOptions)
  • egraph:analyze(Name, Lhs, LhsOptions, RhsOptions) :- Body
  • egraph:merge_property(Name, V1, V2, Merged)
  • egraph:merge_property(Name, V1, V2, Merged) :- Body
  • egraph:rule(Name, LhsPatterns, RhsPatterns)
  • egraph:rule(Name, LhsPatterns, RhsPatterns) :- Body
  • egraph:rule(Name, LhsPatterns, RhsPatterns, RhsOptions)
  • egraph:rule(Name, LhsPatterns, RhsPatterns, RhsOptions) :- Body
  • egraph:rule(Name, LhsPatterns, LhsOptions, RhsPatterns, RhsOptions)
  • egraph:rule(Name, LhsPatterns, LhsOptions, RhsPatterns, RhsOptions) :- Body Note on Signatures:
  • For egraph:rewrite and egraph:analyze, Lhs and Rhs are single structural terms.
  • For egraph:rule, LhsPatterns and RhsPatterns must be a list of Pattern-Id pairs (e.g., [f(A)-Id1, g(B)-Id2]). Shared class Ids between left and right patterns are automatically unified.
  • Options (both Lhs and Rhs) are a list of property compounds in the form `Name(Key, Value)`. For egraph:rewrite and egraph:analyze rules, a shorthand `Name(Value)` can be used, which implicitly uses the pattern's class Id as the Key.
    • Lhs options will "get" the property and can be prefixed by \+ to negate the lookup.
    • Rhs options will "set" the property.
    • cost(Cost) is a special option that sets the structural cost of the node.

Examples

:- use_module(library(egraph)).

% Algebraic rules
egraph:rewrite(comm_add, A+B, B+A).
egraph:rewrite(assoc_add, A+(B+C), (A+B)+C).

% Rules with custom cost
egraph:rewrite(factorize_aa, A+A, 2*A, [cost(9r10)]).

% Rules with left-hand side conditions
egraph:rewrite(reduce_add0, A+B, [const(B, 0)], A, []).

% Rules with a Prolog body
egraph:rewrite(constant_folding, A+B, [const(A, VA), const(B, VB)], VC, [const(VC)]) :-
   VC is VA + VB.

% Node Analysis (e.g., constant detection)
egraph:analyze(is_const, '$NODE'(A), [const(A)]) :-
   number(A).

% Property merging when e-classes are unioned
egraph:merge_property(const, V1, V2, Merged) :-
   (  V1 =:= V2
   -> Merged = V1
   ;  domain_error(V1, V2)
   ).

% Dict support
egraph:rewrite(operator_fusion, array{op: array{op: A+B}+C}, array{op: A+B+C}).

Usage

The interface uses Prolog's DCGs to thread the E-graph state. The E-graph itself is represented as a sorted list of pairs with the specific shape Node-node(Id, Cost):

  • Node: The structural term, literal value, or variable representation (e.g., A+B, 1, '$NODE'(X)).
  • Id: The equivalence class identifier (typically a Prolog variable).
  • Cost: The structural cost of this specific node.

Core Predicates

  • `add_term(+Term, -Id)//` Recursively adds a term (and its subterms) to the E-graph, unifying Id with its equivalence class.
  • `union(+Id1, +Id2)//` Merges two equivalence classes by their IDs.
  • `saturate(+Rules)//` / `saturate(+Rules, +MaxIterations)//` Applies a list of compiled rewrite rule names iteratively until the E-graph is saturated or the iteration limit is reached.
  • `extract(+Id, -Extracted)//` Extracts the optimal term from the E-graph based on term costs.
  • `extract_all(+Id, -Extracted)//` Extracts all optimal terms from the E-graph based on term costs.
  • lookup(+Pair, +SortedPairs) Retrieves an e-class node from a sorted list of E-graph nodes.
  • `query(?Pattern)//` Queries the E-graph and dynamically binds pattern variables. On backtracking, yields all representations in increasing order of cost.

Example Workflow

?- use_module(library(egraph)).
true.

?- phrase((
       add_term(a+0, Id),
       saturate([is_const, reduce_add0]),
       extract(Id, Optimized)
   ), [], _Graph).
Optimized = a,
...