High Level: `egglog`#

The top level module contains the high level API for using e-graphs in Python.

The high level API is not documented yet, because adding supporting for our custom objects requires a custom AutoDoc extension.

The high level API builds on the low level API and is designed to:

Statically type check as much as possible with MyPy
Be concise to write
Feel “pythonic”

Here is the same example using the high level API:

from __future__ import annotations

from egglog import *

egraph = EGraph()

class Math(Expr):
    def __init__(self, value: i64Like) -> None:
        ...

    @classmethod
    def var(cls, v: StringLike) -> Math:
        ...

    def __add__(self, other: Math) -> Math:
        ...

    def __mul__(self, other: Math) -> Math:
        ...

# expr1 = 2 * (x + 3)
expr1 = egraph.let("expr1", Math(2) * (Math.var("x") + Math(3)))

# expr2 = 6 + 2 * x
expr2 = egraph.let("expr2", Math(6) + Math(2) * Math.var("x"))

a, b, c = vars_("a b c", Math)
x, y = vars_("x y", i64)

egraph.register(
    rewrite(a + b).to(b + a),
    rewrite(a * (b + c)).to((a * b) + (a * c)),
    rewrite(Math(x) + Math(y)).to(Math(x + y)),
    rewrite(Math(x) * Math(y)).to(Math(x * y)),
)

egraph.run(10)

egraph.check(eq(expr1).to(expr2))

Package for creating e-graphs in Python.

class egglog.Action(__egg_decls__, action)#

Bases: object

A change to an EGraph, either unioning multiple expressions, setting the value of a function call, deleting an expression, or panicing.

Parameters:

__egg_decls__ (Declarations)
action (LetDecl | SetDecl | ExprActionDecl | ChangeDecl | UnionDecl | PanicDecl | SetCostDecl)

class egglog.BackOff(scheduler)#

Bases: object

Parameters:: scheduler (BackOffDecl)

scope(schedule)#

Defines the scheduler to be created directly before the inner schedule, instead of the default which is at the most outer scope.

Parameters:: schedule (Schedule)
Return type:: Schedule

class egglog.BaseExpr#

Bases: object

Either a builtin or a user defined expression type.

class egglog.BuiltinExpr#

Bases: BaseExpr

A builtin expr type, not an eqsort.

exception egglog.ConvertError#: Bases: Exception

class egglog.CostModel(*args, **kwargs)#

Bases: Protocol, Generic[COST]

A cost model for an e-graph. Used to determine the cost of an expression based on its structure and the costs of its sub-expressions.

Called with an expression and the costs of its children, returns the total cost of the expression.

Additionally, the cost model should guarantee that a term has a no-smaller cost than its subterms to avoid cycles in the extracted terms for common case usages. For more niche usages, a term can have a cost less than its subterms. As long as there is no negative cost cycle, the default extractor is guaranteed to terminate in computing the costs. However, the user needs to be careful to guarantee acyclicity in the extracted terms.

class egglog.EGraph(*actions, seminaive=True, save_egglog_string=False)#

Bases: object

A collection of expressions where each expression is part of a distinct equivalence class.

Can run actions, check facts, run schedules, or extract minimal cost expressions.

Parameters:

actions (Action | BaseExpr | Fact)
seminaive (bool)
save_egglog_string (bool)

all_function_sizes()#

Returns a list of all functions and their sizes.

Return type:: list[tuple[Callable[..., BaseExpr] | BaseExpr, int]]

property as_egglog_string: str#: Returns the egglog string for this module.

check(*facts)#

Check if a fact is true in the egraph.

Parameters:: facts (Fact | BaseExpr)
Return type:: None

check_bool(*facts)#

Returns true if the facts are true in the egraph.

Parameters:: facts (Fact | BaseExpr)
Return type:: bool

check_fail(*facts)#

Checks that one of the facts is not true

Parameters:: facts (Fact | BaseExpr)
Return type:: None

display(graphviz=False, **kwargs)#

Displays the e-graph.

If in IPython it will display it inline, otherwise it will write it to a file and open it.

Parameters:

graphviz (bool)
kwargs (Unpack[GraphvizKwargs])

Return type:

None

extract(expr, /, include_cost=False, cost_model=None)#

Extract the lowest cost expression from the egraph.

Parameters:

expr (TypeVar(BASE_EXPR, bound= BaseExpr))
include_cost (bool)
cost_model (Optional[CostModel[TypeVar(COST, bound= Comparable)]])

Return type:

Union[TypeVar(BASE_EXPR, bound= BaseExpr), tuple[TypeVar(BASE_EXPR, bound= BaseExpr), TypeVar(COST, bound= Comparable)]]

extract_multiple(expr, n)#

Extract multiple expressions from the egraph.

Parameters:

expr (TypeVar(BASE_EXPR, bound= BaseExpr))
n (int)

Return type:

list[TypeVar(BASE_EXPR, bound= BaseExpr)]

freeze()#

Freeze the current e-graph state for debugging.

The returned FrozenEGraph contains a snapshot of the current declarations and can be pretty-printed back into replayable high-level actions with str(...).

This is useful when debugging unexpected unions, sets, subsumptions, or costs after a run:

Return type:: FrozenEGraph

>>> from egglog import *
>>> class Math(Expr):
...     def __init__(self, value: i64Like) -> None: ...
...
>>> egraph = EGraph(Math(1))
>>> str(egraph.freeze())
'EGraph(Math(1)).freeze()'

function_size(fn)#

Returns the number of rows in a certain function

Parameters:: fn (Callable[..., BaseExpr] | BaseExpr)
Return type:: int

function_values(fn, length=None)#

Given a callable that is a “function”, meaning it returns a primitive or has a merge set, returns a mapping of the function applied with its arguments to its values

If length is specified, only the first length values will be returned.

Parameters:

fn (Union[Callable[..., TypeVar(BASE_EXPR, bound= BaseExpr)], TypeVar(BASE_EXPR, bound= BaseExpr)])
length (int | None)

Return type:

dict[TypeVar(BASE_EXPR, bound= BaseExpr), TypeVar(BASE_EXPR, bound= BaseExpr)]

has_custom_cost(fn)#

Checks if the any custom costs have been set for this expression callable.

Parameters:: fn (Callable[..., BaseExpr] | BaseExpr)
Return type:: bool

include(path)#

Include a file of rules.

Parameters:: path (str)
Return type:: None

input(fn, path)#

Loads a CSV file and sets it as *input, output of the function.

Parameters:

fn (Callable[..., RuntimeClass])
path (str)

Return type:

None

let(name, expr)#

Define a new expression in the egraph and return a reference to it.

Parameters:

name (str)
expr (TypeVar(BASE_EXPR, bound= BaseExpr))

Return type:

TypeVar(BASE_EXPR, bound= BaseExpr)

lookup_function_value(expr)#

Given an expression that is a function call, looks up the value of the function call if it exists.

Parameters:: expr (TypeVar(BASE_EXPR, bound= BaseExpr))
Return type:: Optional[TypeVar(BASE_EXPR, bound= BaseExpr)]

pop()#

Pop the current state of the egraph, reverting back to the previous state.

Return type:: None

push()#

Push the current state of the egraph, so that it can be popped later and reverted back.

Return type:: None

register(command_or_generator, *command_likes)#

Registers any number of rewrites or rules.

Parameters:

command_or_generator (Action | BaseExpr | Fact | RewriteOrRule | Callable[..., Iterable[RewriteOrRule]])
command_likes (Action | BaseExpr | Fact | RewriteOrRule)

Return type:

None

run(limit_or_schedule, /, *until, ruleset=None)#

Run the egraph until the given limit or until the given facts are true.

Parameters:

limit_or_schedule (int | Schedule)
until (Fact)
ruleset (Ruleset | None)

Return type:

RunReport

saturate(schedule=None, *, expr=None, max=1000, visualize=True, print_frozen=False, **kwargs)#

Saturate the egraph, running the given schedule until the egraph is saturated. It serializes the egraph at each step and returns a widget to visualize the egraph.

If an expr is passed, it’s also extracted after each run and printed

Parameters:

schedule (Schedule | None)
expr (Expr | None)
max (int)
visualize (bool)
print_frozen (bool)
kwargs (Unpack[GraphvizKwargs])

Return type:

None

set_report_level(level)#: Set the level of detail recorded in subsequent run reports.

stats()#

Returns the overall run report for the egraph.

Return type:: RunReport

class egglog.Expr#

Bases: BaseExpr

Subclass this to define a custom expression type.

exception egglog.ExprValueError(expr, allowed)#

Bases: AttributeError

Raised when an expression cannot be converted to a Python value because the value is not a constructor.

Parameters:

expr (BaseExpr)
allowed (str)

class egglog.Fact(__egg_decls__, fact)#

Bases: object

A query on an EGraph, either by an expression or an equivalence between multiple expressions.

Parameters:

__egg_decls__ (Declarations)
fact (EqDecl | ExprFactDecl)

class egglog.GraphvizKwargs#: Bases: TypedDict

class egglog.GreedyDagCost(total, _costs)#

Bases: Generic[DAG_COST]

Cost of a DAG, which stores children costs. Use .total to get the underlying cost.

Parameters:

total (TypeVar(DAG_COST, bound= ComparableAddSub))
_costs (dict[TypedExprDecl, TypeVar(DAG_COST, bound= ComparableAddSub)])

class egglog.RewriteOrRule(__egg_decls__, decl, ruleset=None)#

Bases: object

Parameters:

__egg_decls__ (Declarations)
decl (RewriteDecl | BiRewriteDecl | RuleDecl | DefaultRewriteDecl)
ruleset (Ruleset | None)

class egglog.Ruleset(ident, _current_egg_decls=<factory>, deferred_rule_gens=<factory>)#

Bases: Schedule

A collection of rules, which can be run as a schedule.

Parameters:

ident (Ident | None)
_current_egg_decls (Declarations)
deferred_rule_gens (list[Callable[[], Iterable[RewriteOrRule]]])

_update_egg_decls()#

To return the egg decls, we go through our deferred rules and add any we haven’t yet

Return type:: Declarations

append(rule)#

Parameters:: rule (RewriteOrRule)
Return type:: None

register(rule_or_generator, *rules, _increase_frame=False)#

Parameters:

rule_or_generator (RewriteOrRule | Callable[..., Iterable[RewriteOrRule]])
rules (RewriteOrRule)
_increase_frame (bool)

Return type:

None

class egglog.RunReport(_decls, iterations=<factory>, updated=False, search_and_apply_time_per_rule=<factory>, num_matches_per_rule=<factory>, search_and_apply_time_per_ruleset=<factory>, merge_time_per_ruleset=<factory>, rebuild_time_per_ruleset=<factory>)#

Bases: object

Python-friendly wrapper around bindings.RunReport.

Parameters:

_decls (Declarations)
iterations (list[IterationReport])
updated (bool)
search_and_apply_time_per_rule (dict[RuleDecl | BiRewriteDecl | RewriteDecl, timedelta])
num_matches_per_rule (dict[RuleDecl | BiRewriteDecl | RewriteDecl, int])
search_and_apply_time_per_ruleset (dict[str, timedelta])
merge_time_per_ruleset (dict[str, timedelta])
rebuild_time_per_ruleset (dict[str, timedelta])

class egglog.Schedule(__egg_decls_thunk__, schedule)#

Bases: DelayedDeclarations

A composition of some rulesets, either composing them sequentially, running them repeatedly, running them till saturation, or running until some facts are met

Parameters:

__egg_decls_thunk__ (Callable[[], Declarations])
schedule (SaturateDecl | RepeatDecl | SequenceDecl | RunDecl | LetSchedulerDecl)

saturate()#

Run the schedule until the e-graph is saturated.

Return type:: Schedule

class egglog.Unit(*args: object, **kwargs: object)#

Bases: object

The unit type. This is used to represent if a value exists in the e-graph or not.

class egglog._BirewriteBuilder(lhs, ruleset)#

Bases: Generic[EXPR]

Parameters:

lhs (TypeVar(EXPR, bound= Expr))
ruleset (Ruleset | None)

class egglog._EqBuilder(expr)#

Bases: Generic[BASE_EXPR]

Parameters:: expr (TypeVar(BASE_EXPR, bound= BaseExpr))

class egglog._NeBuilder(lhs)#

Bases: Generic[BASE_EXPR]

Parameters:: lhs (TypeVar(BASE_EXPR, bound= BaseExpr))

class egglog._RewriteBuilder(lhs, ruleset, subsume)#

Bases: Generic[EXPR]

Parameters:

lhs (TypeVar(EXPR, bound= Expr))
ruleset (Ruleset | None)
subsume (bool)

class egglog._SetBuilder(lhs)#

Bases: Generic[BASE_EXPR]

Parameters:: lhs (TypeVar(BASE_EXPR, bound= BaseExpr))

class egglog._UnionBuilder(lhs)#

Bases: Generic[EXPR]

Parameters:: lhs (TypeVar(EXPR, bound= Expr))

egglog.back_off(match_limit=None, ban_length=None)#

Create a backoff scheduler configuration.

`python schedule = run(analysis_ruleset).saturate() + run(ruleset, scheduler=back_off(match_limit=1000, ban_length=5)) * 10 ` This will run the analysis_ruleset until saturation, then run ruleset 10 times, using a backoff scheduler.

Parameters:

match_limit (None | int)
ban_length (None | int)

Return type:

BackOff

egglog.birewrite(lhs, ruleset=None)#

Rewrite the given expression to a new expression and vice versa.

Parameters:

lhs (TypeVar(EXPR, bound= Expr))
ruleset (None)

Return type:

_BirewriteBuilder[TypeVar(EXPR, bound= Expr)]

egglog.check(x, schedule=None, *given)#

Verifies that the fact is true given some assumptions and after running the schedule.

Parameters:

x (Fact | BaseExpr)
schedule (Schedule | None)
given (Action | BaseExpr | Fact)

Return type:

None

egglog.check_eq(x, y, schedule=None, *, add_second=True, display=False)#

Verifies that two expressions are equal after running the schedule.

If add_second is true, then the second expression is added to the egraph before running the schedule.

Parameters:

x (TypeVar(BASE_EXPR, bound= BaseExpr))
y (TypeVar(BASE_EXPR, bound= BaseExpr))
schedule (Schedule | None)

Return type:

EGraph

egglog.constant(name, tp, default_replacement=None, /, *, egg_name=None, ruleset=None)#

A “constant” is implemented as the instantiation of a value that takes no args. This creates a function with name and return type tp and returns a value of it being called.

Parameters:

name (str)
tp (type[TypeVar(BASE_EXPR, bound= BaseExpr)])
default_replacement (Optional[TypeVar(BASE_EXPR, bound= BaseExpr)])
egg_name (str | None)
ruleset (Ruleset | None)

Return type:

TypeVar(BASE_EXPR, bound= BaseExpr)

egglog.convert(source, target)#

Convert a source object to a target type.

Parameters:

source (object)
target (type[TypeVar(V, bound= BaseExpr)])

Return type:

TypeVar(V, bound= BaseExpr)

egglog.converter(from_type, to_type, fn, cost=1)#

Parameters:

from_type (type[TypeVar(T)])
to_type (type[TypeVar(V, bound= BaseExpr)])
fn (Callable[[TypeVar(T)], TypeVar(V, bound= BaseExpr)])
cost (int)

Return type:

None

egglog.default_cost_model(egraph, expr, children_costs)#

A default cost model for an e-graph, which looks up costs set on function calls, or uses 1 as the default cost.

Parameters:

egraph (EGraph)
expr (BaseExpr)
children_costs (list[int])

Return type:

int

egglog.define_expr_method(name)#

Given the name of a method, explicitly defines it on the runtime type that holds Expr objects as a method.

Call this if you need a method to be defined on the type itself where overriding with __getattr__ does not suffice, like for NumPy’s __array_ufunc__.

Parameters:: name (str)
Return type:: None

egglog.delete(expr)#

Create a delete expression.

Parameters:: expr (BaseExpr)
Return type:: Action

egglog.eq(expr)#

Check if the given expression is equal to the given value.

Parameters:: expr (TypeVar(BASE_EXPR, bound= BaseExpr))
Return type:: _EqBuilder[TypeVar(BASE_EXPR, bound= BaseExpr)]

egglog.expr_parts(expr)#

Returns the underlying type and decleration of the expression. Useful for testing structural equality or debugging.

Parameters:: expr (BaseExpr)
Return type:: TypedExprDecl

egglog.function(*args, **kwargs)#

Decorate a function typing stub to create an egglog function for it.

If a body is included, it will be added to the ruleset passed in as a default rewrite.

This will default to creating a “constructor” in egglog, unless a merge function is passed in or the return type is a primtive, then it will be a “function”.

Return type:: Any

egglog.get_callable_args(x, fn=None)#

Gets all the arguments of an expression. If a function is provided, it will only return the arguments if the expression is a call to that function.

Note that recursively calling the arguments is the safe way to walk the expression tree.

Parameters:

x (TypeVar(T, bound= BaseExpr))
fn (Callable[[Unpack[TypeVarTuple]], TypeVar(T, bound= BaseExpr)] | None)

Return type:

tuple[Unpack[TypeVarTuple]] | None

egglog.get_callable_fn(x)#

Gets the function of an expression, or if it’s a constant or classvar, return that.

Parameters:: x (TypeVar(T, bound= BaseExpr))
Return type:: Union[Callable[..., TypeVar(T, bound= BaseExpr)], TypeVar(T, bound= BaseExpr), None]

egglog.get_constant_name(x)#

Check if the expression is a constant and return its name. If it is not a constant, return None.

Parameters:: x (BaseExpr)
Return type:: Ident | None

egglog.get_cost(expr)#

Return a lookup of the cost of an expression. If not set, won’t match.

Parameters:: expr (BaseExpr)
Return type:: RuntimeClass

egglog.get_let_name(x)#

Check if the expression is a let expression and return the name of the variable. If it is not a let expression, return None.

Parameters:: x (BaseExpr)
Return type:: str | None

egglog.get_literal_value(x)#

Returns the literal value of an expression if it is a literal. If it is not a literal, returns None.

Parameters:: x (object)
Return type:: object

egglog.get_type_args()#

Get the type args for the type being converted.

Return type:: tuple[type, ...]

egglog.get_var_name(x)#

Check if the expression is a variable and return its name. If it is not a variable, return None.

Parameters:: x (BaseExpr)
Return type:: str | None

egglog.greedy_dag_cost_model(base=<function default_cost_model>)#

Creates a greedy dag cost model from a base cost model.

Parameters:: base (CostModel[Any])
Return type:: CostModel[GreedyDagCost[Any]]

egglog.let(name, expr)#

Create a let binding.

Parameters:

name (str)
expr (BaseExpr)

Return type:

Action

egglog.method(*, egg_fn=None, cost=None, merge=None, preserve=False, mutates_self=False, unextractable=False, subsume=False, reverse_args=False)#

Any method can be decorated with this to customize it’s behavior. This is only supported in classes which subclass Expr.

Parameters:

egg_fn (str | None)
cost (int | None)
merge (Callable[[TypeVar(BASE_EXPR, bound= BaseExpr), TypeVar(BASE_EXPR, bound= BaseExpr)], TypeVar(BASE_EXPR, bound= BaseExpr)] | None)
preserve (bool)
mutates_self (bool)
unextractable (bool)
subsume (bool)
reverse_args (bool)

Return type:

Callable[[Callable[[ParamSpec(P, bound= None)], TypeVar(BASE_EXPR_NONE, bound= BaseExpr | None)]], Callable[[ParamSpec(P, bound= None)], TypeVar(BASE_EXPR_NONE, bound= BaseExpr | None)]]

egglog.ne(expr)#

Check if the given expression is not equal to the given value.

Parameters:: expr (TypeVar(BASE_EXPR, bound= BaseExpr))
Return type:: _NeBuilder[TypeVar(BASE_EXPR, bound= BaseExpr)]

egglog.panic(message)#

Raise an error with the given message.

Parameters:: message (str)
Return type:: Action

egglog.py_eval_fn(fn)#

Takes a python callable and maps it to a callable which takes and returns PyObjects.

It translates it to a call which uses py_eval to call the function, passing in the args as locals, and using the globals from function.

Parameters:: fn (Callable)
Return type:: PyObjectFunction

egglog.relation(name, /, *tps, egg_fn=None)#

Creates a function whose return type is Unit and has a default value.

Parameters:

name (str)
tps (type)
egg_fn (str | None)

Return type:

Callable[..., RuntimeClass]

egglog.rewrite(lhs, ruleset=None, *, subsume=False)#

Rewrite the given expression to a new expression.

Parameters:

lhs (TypeVar(EXPR, bound= Expr))
ruleset (None)
subsume (bool)

Return type:

_RewriteBuilder[TypeVar(EXPR, bound= Expr)]

egglog.rule(*facts, ruleset=None, name=None)#

Create a rule with the given facts.

Parameters:

facts (Fact | BaseExpr)
ruleset (None)
name (str | None)

Return type:

_RuleBuilder

egglog.ruleset(rule_or_generator=None, *rules, name=None)#

Creates a ruleset with the following rules.

If no name is provided, try using the name of the funciton.

Parameters:

rule_or_generator (RewriteOrRule | Callable[..., Iterable[RewriteOrRule]] | None)
rules (RewriteOrRule)
name (None | str)

Return type:

Ruleset

egglog.run(ruleset=None, *until, scheduler=None)#

Create a run configuration.

Parameters:

ruleset (Ruleset | None)
until (Fact | BaseExpr)
scheduler (BackOff | None)

Return type:

Schedule

egglog.seq(*schedules)#

Run a sequence of schedules.

Parameters:: schedules (Schedule)
Return type:: Schedule

egglog.set_(lhs)#

Create a set of the given expression.

Parameters:: lhs (TypeVar(BASE_EXPR, bound= BaseExpr))
Return type:: _SetBuilder[TypeVar(BASE_EXPR, bound= BaseExpr)]

egglog.set_cost(expr, cost)#

Set the cost of the given expression.

Parameters:

expr (BaseExpr)
cost (Union[RuntimeClass, int])

Return type:

Action

egglog.subsume(expr)#

Subsume an expression so it cannot be matched against or extracted

Parameters:: expr (Expr)
Return type:: Action

egglog.union(lhs)#

Create a union of the given expression.

Parameters:: lhs (TypeVar(EXPR, bound= Expr))
Return type:: _UnionBuilder[TypeVar(EXPR, bound= Expr)]

egglog.unstable_combine_rulesets(*rulesets, name=None)#

Combine multiple rulesets into a single ruleset.

Parameters:

rulesets (Ruleset | UnstableCombinedRuleset)
name (str | None)

Return type:

UnstableCombinedRuleset

egglog.var(name, bound, egg_name=None)#

Create a new variable with the given name and type.

Parameters:

name (str)
bound (type[TypeVar(T)])
egg_name (str | None)

Return type:

TypeVar(T)

egglog.vars_(names, bound)#

Create variables with the given names and type.

Parameters:

names (str)
bound (type[TypeVar(BASE_EXPR, bound= BaseExpr)])

Return type:

Iterable[TypeVar(BASE_EXPR, bound= BaseExpr)]

High Level: egglog#

This Page

High Level: `egglog`#