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()
@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.
- check_fail(*facts)#
Checks that one of the facts is not true
- classmethod current()#
Returns the current egraph, which is the one in the context.
- Return type:
- 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.
- 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
)
- 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.
- egglog.check_eq(x, y, schedule=None)#
Verifies that two expressions are equal after running the schedule.
- 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.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.
- 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:
- 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.
- 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:
- egglog.run(ruleset=None, *until)#
Create a run configuration.
- egglog.seq(*schedules)#
Run a sequence of schedules.
- 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
- 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)]