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:

1. Statically type check as much as possible with MyPy

2. Be concise to write

3. Feel “pythonic”

Here is the same example using the high level API:

from __future__ import annotations

from egglog import *

egraph = EGraph()

@egraph.class_
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 expressing, setting the value of a function call, deleting an expression, or panicking.

Parameters:

• __egg_decls__ (Declarations)

• action (LetDecl | SetDecl | ExprActionDecl | ChangeDecl | UnionDecl | PanicDecl)

class egglog.EGraph(modules=[], seminaive=True, save_egglog_string=False, _state_stack=<factory>, _token_stack=<factory>)

Bases: _BaseModule

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:

• modules (InitVar)

• seminaive (InitVar)

• save_egglog_string (InitVar)

• _state_stack (list[EGraphState])

• _token_stack (list[Token[EGraph]])

_repr_html_()

Add a _repr_html_ to be an SVG to work with sphinx gallery.

ala xflr6/graphviz#121 until this PR is merged and released sphinx-gallery/sphinx-gallery#1138

Return type:

str

_repr_mimebundle_(*args, **kwargs)

Returns the graphviz representation of the e-graph.

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 | Expr)

Return type:

None

check_fail(*facts)

Checks that one of the facts is not true

Parameters:

facts (Fact | Expr)

Return type:

None

classmethod current()

Returns the current egraph, which is the one in the context.

Return type:

EGraph

display(**kwargs)

Displays the e-graph in the notebook.

Parameters:

kwargs (Unpack[GraphvizKwargs])

Return type:

None

eval(expr)

Evaluates the given expression (which must be a primitive type), returning the result.

Parameters:

expr (Expr)

Return type:

object

extract(expr, include_cost=False)

Extract the lowest cost expression from the egraph.

Parameters:

• expr (TypeVar(EXPR, bound= Expr))

• include_cost (bool)

Return type:

Union[TypeVar(EXPR, bound= Expr), tuple[TypeVar(EXPR, bound= Expr), int]]

extract_multiple(expr, n)

Extract multiple expressions from the egraph.

Parameters:

• expr (TypeVar(EXPR, bound= Expr))

• n (int)

Return type:

list[TypeVar(EXPR, bound= Expr)]

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(EXPR, bound= Expr))

Return type:

TypeVar(EXPR, bound= Expr)

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

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

simplify(expr, limit_or_schedule, /, *until, ruleset=None)

Simplifies the given expression.

Parameters:

• expr (TypeVar(EXPR, bound= Expr))

• limit_or_schedule (int | Schedule)

• until (Fact)

• ruleset (Ruleset | None)

Return type:

TypeVar(EXPR, bound= Expr)

class egglog.Expr

Bases: object

Either a function called with some number of argument expressions or a literal integer, float, or string, with a particular type.

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.Module(modules=[], cmds=<factory>)

Bases: _BaseModule

Parameters:

• modules (InitVar)

• cmds (list[Action | RewriteOrRule])

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

Bases: object

Parameters:

• __egg_decls__ (Declarations)

• decl (RewriteDecl | BiRewriteDecl | RuleDecl)

• ruleset (Ruleset | None)

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

Bases: Schedule

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

Parameters:

• name (str | 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)

Register a rule with the ruleset.

Parameters:

rule (RewriteOrRule)

Return type:

None

register(rule_or_generator, *rules, _increase_frame=False)

Register rewrites or rules, either as a function or as values.

Parameters:

• rule_or_generator (RewriteOrRule | Callable[..., Iterable[RewriteOrRule]])

• rules (RewriteOrRule)

• _increase_frame (bool)

Return type:

None

class egglog.Schedule(__egg_decls_thunk__, schedule)

Bases: DelayedDeclerations

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)

saturate()

Run the schedule until the e-graph is saturated.

Return type:

Schedule

class egglog._BirewriteBuilder(lhs, ruleset)

Bases: Generic[EXPR]

Parameters:

• lhs (TypeVar(EXPR, bound= Expr))

• ruleset (Ruleset | None)

class egglog._EqBuilder(expr)

Bases: Generic[EXPR]

Parameters:

expr (TypeVar(EXPR, bound= Expr))

class egglog._NeBuilder(lhs)

Bases: Generic[EXPR]

Parameters:

lhs (TypeVar(EXPR, bound= Expr))

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[EXPR]

Parameters:

lhs (TypeVar(EXPR, bound= Expr))

class egglog._UnionBuilder(lhs)

Bases: Generic[EXPR]

Parameters:

lhs (TypeVar(EXPR, bound= Expr))

egglog.birewrite(lhs, ruleset=None)

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

Parameters:

• lhs (TypeVar(EXPR, bound= Expr))

• ruleset (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 | Expr)

• schedule (Schedule | None)

• given (Action | Expr)

Return type:

None

egglog.check_eq(x, y, schedule=None)

Verifies that two expressions are equal after running the schedule.

Parameters:

• x (TypeVar(EXPR, bound= Expr))

• y (TypeVar(EXPR, bound= Expr))

• schedule (Schedule | None)

Return type:

EGraph

egglog.constant(name, tp, egg_name=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(EXPR, bound= Expr)])

• egg_name (str | None)

Return type:

TypeVar(EXPR, bound= Expr)

egglog.convert(source, target)

Convert a source object to a target type.

Parameters:

• source (object)

• target (type[TypeVar(V, bound= Expr)])

Return type:

TypeVar(V, bound= Expr)

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

Register a converter from some type to an egglog type.

Parameters:

• from_type (type[TypeVar(T)])

• to_type (type[TypeVar(V, bound= Expr)])

• fn (Callable[[TypeVar(T)], TypeVar(V, bound= Expr)])

• cost (int)

Return type:

None

egglog.delete(expr)

Create a delete expression.

Parameters:

expr (Expr)

Return type:

Action

egglog.eq(expr)

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

Parameters:

expr (TypeVar(EXPR, bound= Expr))

Return type:

_EqBuilder[TypeVar(EXPR, bound= Expr)]

egglog.expr_parts(expr)

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

Parameters:

expr (Expr)

Return type:

TypedExprDecl

egglog.function(*args, **kwargs)

Defined by a unique name and a typing relation that will specify the return type based on the types of the argument expressions.

Return type:

Any

egglog.let(name, expr)

Create a let binding.

Parameters:

• name (str)

• expr (Expr)

Return type:

Action

egglog.method(*, egg_fn=None, cost=None, default=None, merge=None, on_merge=None, preserve=False, mutates_self=False, unextractable=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)

• default (Optional[TypeVar(EXPR, bound= Expr)])

• merge (Callable[[TypeVar(EXPR, bound= Expr), TypeVar(EXPR, bound= Expr)], TypeVar(EXPR, bound= Expr)] | None)

• on_merge (Callable[[TypeVar(EXPR, bound= Expr), TypeVar(EXPR, bound= Expr)], Iterable[Action | Expr]] | None)

• preserve (bool)

• mutates_self (bool)

• unextractable (bool)

Return type:

Callable[[Callable[[ParamSpec(P, bound= None)], TypeVar(EXPR, bound= Expr)]], Callable[[ParamSpec(P, bound= None)], TypeVar(EXPR, bound= Expr)]]

egglog.ne(expr)

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

Parameters:

expr (TypeVar(EXPR, bound= Expr))

Return type:

_NeBuilder[TypeVar(EXPR, bound= Expr)]

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 (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 | Expr)

• ruleset (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)

Create a run configuration.

Parameters:

• ruleset (Ruleset | None)

• until (Fact | Expr)

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(EXPR, bound= Expr))

Return type:

_SetBuilder[TypeVar(EXPR, bound= Expr)]

egglog.simplify(x, schedule=None)

Simplify an expression by running the schedule.

Parameters:

• x (TypeVar(EXPR, bound= Expr))

• schedule (Schedule | None)

Return type:

TypeVar(EXPR, bound= Expr)

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)

Create a new variable with the given name and type.

Parameters:

• name (str)

• bound (type[TypeVar(EXPR, bound= Expr)])

Return type:

TypeVar(EXPR, bound= Expr)

egglog.vars_(names, bound)

Create variables with the given names and type.

Parameters:

• names (str)

• bound (type[TypeVar(EXPR, bound= Expr)])

Return type:

Iterable[TypeVar(EXPR, bound= Expr)]