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

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[1], line 7
      3 from egglog import *
      5 egraph = EGraph()
----> 7 @egraph.class_
      8 class Math(Expr):
      9     def __init__(self, value: i64Like) -> None:
     10         ...

AttributeError: 'EGraph' object has no attribute 'class_'

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)

class egglog.BaseExpr#

Bases: object

Either a builtin or a user defined expression type.

exception egglog.BuiltinEvalError#

Bases: Exception

Raised when an builtin cannot be evaluated into a Python primitive because it is complex.

Try extracting this expression first.

class egglog.BuiltinExpr#

Bases: BaseExpr

A builtin expr type, not an eqsort.

exception egglog.ConvertError#

Bases: Exception

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

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:

  • seminaive (InitVar)

  • save_egglog_string (InitVar)

  • _state_stack (list[EGraphState])

  • _token_stack (list[EGraph])

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:
Return type:

None

extract(expr, include_cost=False)#

Extract the lowest cost expression from the egraph.

Parameters:

  • expr (TypeVar(BASE_EXPR, bound= BaseExpr))

  • include_cost (bool)

Return type:

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

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

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

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:
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:
Return type:

RunReport

saturate(schedule=None, *, expr=None, max=1000, visualize=True, **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:
Return type:

None

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

Simplifies the given expression.

Parameters:
Return type:

TypeVar(BASE_EXPR, bound= BaseExpr)

class egglog.Expr#

Bases: BaseExpr

Subclass this to define a custom expression 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.RewriteOrRule(__egg_decls__, decl, ruleset=None)#

Bases: object

Parameters:

  • __egg_decls__ (Declarations)

  • decl (RewriteDecl | BiRewriteDecl | RuleDecl | DefaultRewriteDecl)

  • 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:
_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:
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:
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:
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.birewrite(lhs, ruleset=None)#

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

Parameters:
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:
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:
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:
Return type:

TypeVar(BASE_EXPR, bound= BaseExpr)

egglog.convert(source, target)#

Convert a source object to a target type.

Parameters:
Return type:

TypeVar(V, bound= BaseExpr)

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

Register a converter from some type to an egglog type.

Parameters:
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_type_args()#

Get the type args for the type being converted.

Return type:

tuple[type, ...]

egglog.let(name, expr)#

Create a let binding.

Parameters:
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:
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:
Return type:

Callable[..., RuntimeClass]

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

Rewrite the given expression to a new expression.

Parameters:
Return type:

_RewriteBuilder[TypeVar(EXPR, bound= Expr)]

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

Create a rule with the given facts.

Parameters:
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:
Return type:

Ruleset

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

Create a run configuration.

Parameters:
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.simplify(x, schedule=None)#

Simplify an expression by running the schedule.

Parameters:
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:
Return type:

UnstableCombinedRuleset

egglog.var(name, bound)#

Create a new variable with the given name and type.

Parameters:
Return type:

TypeVar(T)

egglog.vars_(names, bound)#

Create variables with the given names and type.

Parameters:
Return type:

Iterable[TypeVar(BASE_EXPR, bound= BaseExpr)]