Package "egraph"

Title:	E-Graphs and Equality Saturation for SWI-Prolog
Rating:	Not rated. Create the first rating!
Latest version:	0.6.0
SHA1 sum:	b8c27be5ac95f44cd357a6921814c6cdb2b18e2d
Author:	Kwon-Young Choi <kwon-young.choi@hotmail.fr>
Maintainer:	Kwon-Young Choi <kwon-young.choi@hotmail.fr>
Packager:	Kwon-Young Choi <kwon-young.choi@hotmail.fr>
Home page:	https://github.com/kwon-young/egraph
Download URL:	https://github.com/kwon-young/egraph/releases/*.zip
Requires:	prolog>=9.3.23
Provides:	egraph

Reviews

No reviews. Create the first review!.

Details by download location

Version	SHA1	#Downloads	URL
0.6.0	b8c27be5ac95f44cd357a6921814c6cdb2b18e2d	2	https://github.com/kwon-young/egraph
	3545273e5e8fba017f1e1e679b3804815b5cc9ac	1	https://github.com/kwon-young/egraph
0.5.0	f0ad5f189fccc92baa3631b83d5b454319eb730a	3	https://github.com/kwon-young/egraph
0.4.0	d99b1a2db171588530c4262752e2e1c416979d60	3	https://github.com/kwon-young/egraph
0.3.0	b755b71156983a12a71e7e1fdcfc7bc12af32b09	2	https://github.com/kwon-young/egraph
0.2.0	109f5f49e26c123c63cab0c3d88ada359ce97857	4	https://github.com/kwon-young/egraph
0.1.0	da3c2c5f4b77f207b3110623e7d5d042fa5963aa	3	https://github.com/kwon-young/egraph

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,
...

Contents of pack "egraph"

Pack contains 14 files holding a total of 78.0K bytes.