Changelog

This project uses semantic versioning

UNRELEASED

fix using f64Like when not importing star (also properly includes removal of Callable special case from previous release).

10.0.1 (2025-04-06)

Fix bug on resolving types if not all imported to your module #286
- Also stops special casing including Callable as a global. So if you previously included this in a TYPE_CHECKING block so it wasn't available at runtime you will have to move this to a runtime import if used in a type alias.

10.0.0 (2025-03-28)

Change builtins to not evaluate values in egraph and changes facts to compare structural equality instead of using an egraph when converting to a boolean, removing magic context (EGraph.current and Schedule.current) that was added in release 9.0.0.
Fix bug that improperly upcasted values for ==

9.0.1 (2025-03-20)

Add missing i64.log2 method to the bindings

9.0.0 (2025-03-20)

Evaluating Primitives

Previously, if you had an egglog primitive object like an i64, you would have to call egraph.eval(i) to get back an int. Now you can just call int(i). This will implicitly create an e-graph and use it to extract the int value of the expression. This also means you can use this to evaluate compound expressions, like int(i64(1) + 10).

This is also supported for container types, like vecs and sets. You can also use the .eval() method on any primitive to get the Python object.

For example:

>>> from egglog import *
>>> Vec(i64(1), i64(2))[0]
Vec(1, 2)[0]
>>> int(Vec(i64(1), i64(2))[0])
1
>>> list(Vec(i64(1), i64(2)))
[i64(1), i64(2)]
>>> Rational(1, 2).eval()
Fraction(1, 2)
>>>


You can also manually set the e-graph to use, instead of it having to create a new one, with the `egraph.set_current` context manager:

```python
>>> egraph = EGraph()
>>> x = egraph.let("x", i64(1))
>>> x + 2
x + 2
>>> (x + 2).eval()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/saul/p/egg-smol-python/python/egglog/builtins.py", line 134, in eval
    value = _extract_lit(self)
            ^^^^^^^^^^^^^^^^^^
  File "/Users/saul/p/egg-smol-python/python/egglog/builtins.py", line 1031, in _extract_lit
    report = (EGraph.current or EGraph())._run_extract(cast("RuntimeExpr", e), 0)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/saul/p/egg-smol-python/python/egglog/egraph.py", line 1047, in _run_extract
    self._egraph.run_program(
EggSmolError: At 0:0 of
Unbound symbol %x
When running commands:
(extract (+ %x 2) 0)

Extracting: (+ %x 2)
>>> with egraph.set_current():
...     print((x + 2).eval())
...
3

There is a tradeoff here for more ease of use at the expense of some added implicit behavior using global state.

Equal and Not Equal operators

Previously, if you wanted to create an equality fact, you would have to do eq(x).to(y). And similarly, if you wanted to create a not equal expression, you would have to do ne(x).to(y). I had set it up this way so that you could implement __eq__ and __ne__ on your custom data types to provide other functions (for monkeytyping purposes) and still be able to use the equality operators from egglog.

However, ergonmically this was a bit painful, so with this release, the == and != methods are now supported on all egglog expressions. If you override them for your types, you can still use the functions:

>>> i64(1) == i64(2)
eq(i64(1)).to(i64(2))
>>> i64(1) != i64(2)
ne(i64(1)).to(i64(2))
>>> class A(Expr):
...     def __init__(self) -> None: ...
...     def __eq__(self, other: "A") -> "A": ...
...
>>> A() == A()
A() == A()
>>> eq(A()).to(A())
eq(A()).to(A())

Evaluating Facts

Similar to the above with primitives, you can now evaluate facts and see if they are true. This will implicitly create and run them on the e-graph. For example:

>>> i64(10) == i64(9) + 1
eq(i64(10)).to(i64(9) + 1)
>>> bool(i64(10) == i64(9) + 1)
True

Again, you can set the current e-graph with the context manager to use that instead:

>>> egraph = EGraph()
>>> s = egraph.let("s", MultiSet(i64(1), 2))
>>> with egraph.set_current():
...     assert s.contains(1)

Experimental Array API Support

This release also continues to experiment with a proof of concept array API implementation that allows deferred optimization and analysis. It is still very much a work in progress, but open to collaboration and feedback. The goal is to see egglog might be possible to be used as an end to end array compiler.

The changes in this release allow more functional programming constructrs to be used to create arrays, and then allow their properties to be optimized. For example, we can create a linalg function (in an example inspired by Siu):

from egglog.exp.array_api import *

@function(ruleset=array_api_ruleset, subsume=True)
def linalg_norm(X: NDArrayLike, axis: TupleIntLike) -> NDArray:
    X = cast(NDArray, X)
    return NDArray(
        X.shape.deselect(axis),
        X.dtype,
        lambda k: ndindex(X.shape.select(axis))
        .foldl_value(lambda carry, i: carry + ((x := X.index(i + k)).conj() * x).real(), init=0.0)
        .sqrt(),
    )

Then we are able to check the shape of the output based on the input:

>>> X = constant("X", NDArray)
>>> assume_shape(X, (3, 2, 3, 4))
>>> res = linalg_norm(X, (0, 1))
>>> assert res.shape.eval() == (Int(3), Int(4))

As well as see the symbolic form of it's output:

>>> i = constant("i", Int)
>>> j = constant("j", Int)
>>> idxed = res.index((i, j))
>>> EGraph().simplify(idxed, array_api_schedule)
(
    (
        (
            (
                (
                    (X.index(TupleInt.from_vec(Vec[Int](Int(0), Int(0), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(0), Int(0), i, j)))).real()
                    + (X.index(TupleInt.from_vec(Vec[Int](Int(0), Int(1), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(0), Int(1), i, j)))).real()
                )
                + (X.index(TupleInt.from_vec(Vec[Int](Int(1), Int(0), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(1), Int(0), i, j)))).real()
            )
            + (X.index(TupleInt.from_vec(Vec[Int](Int(1), Int(1), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(1), Int(1), i, j)))).real()
        )
        + (X.index(TupleInt.from_vec(Vec[Int](Int(2), Int(0), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(2), Int(0), i, j)))).real()
    )
    + (X.index(TupleInt.from_vec(Vec[Int](Int(2), Int(1), i, j))).conj() * X.index(TupleInt.from_vec(Vec[Int](Int(2), Int(1), i, j)))).real()
).sqrt()

All changes

Fix pretty printing of lambda functions
Add support for subsuming rewrite generated by default function and method definitions
Add better error message when using @function in class (thanks @shinawy)
Add error method if @method decorator is in wrong place
Subsumes lambda functions after replacing
Add working loopnest test and rewrite array api suport to be more general
Improve tracebacks on failing conversions.
Use add_note for exception to add more context, instead of raising a new exception, to make it easier to debug.
Add conversions from generic types to be supported at runtime and typing level (so can go from (1, 2, 3) to TupleInt)
Open files with webbrowser instead of internal graphviz util for better support
Add support for not visualizing when using .saturate() method #254
Upgrade [egglog](https://github.com/egraphs-good/egglog/compare/b0d b06832264c9b22694bd3de2bdacd55bbe9e32...saulshanabrook:egg-smol:889ca7635368d7e382e16a93b2883aba82f1078f) #258
- This includes a few big changes to the underlying bindings, which I won't go over in full detail here. See the pyi diff for all public changes.
- Creates seperate parent classes for BuiltinExpr vs Expr (aka eqsort aka user defined expressions). This is to allow us statically to differentiate between the two, to be more precise about what behavior is allowed. For example, union can only take Expr and not BuiltinExpr.
- Removes deprecated support for modules and building functions off of the e-egraph.
- Updates function constructor to remove default and on_merge. You also can't set a cost when you use a merge function or return a primitive.
- eq now only takes two args, instead of being able to compare any number of values.
Removes eval method from EGraph and moves primitive evaluation to methods on each builtin and support int(...) type conversions on primitives. #265
Change how to set global EGraph context with with egraph.set_current() and EGraph.current and add support for setting global schedule as well with with schedule.set_current() and Schedule.current. #265
Adds support for using == and != directly on values instead of eq and ne functions. #265
Add multiset, bigint, and bigrat builtins

8.0.1 (2024-10-24)

Upgrade dependencies including egglog
Fix bug with non glob star import
Fix bug extracting functions

8.0.0 (2024-10-17)

Adds ability to use anonymous functions where callables are needed. These are automatically transformed to egglog functions with default rewrites.
Upgrade egglog
- Adds source annotations to expressions for tracebacks
- Adds ability to inline other functions besides primitives in serialized output
Adds remove and set methods to Vec
Upgrades to use the new egraph-visualizer so we can have interactive visualizations

7.2.0 (2024-05-23)

Adds ability to use function bodies as default rewrites (#167)
Fixed bug with creating empty maps and adding to maps (#168)

7.1.0 (2024-05-03)

New Feaatures

Upgrade egglog (#143)
- Adds bindings.UnstableCombinedRulset to commands
- Adds UnstableFn sort
Adds support for first class functions as values using Python's built in Callable syntax and partial.
Adds way to combine ruleset with r1 | r2 syntax or the experimental unstable_combine_rulesets(*rs, name=None) function.

Minor improvements

Fixes a bug where you could not write binary dunder methods (like __add__) that didn't have symetric arguments
Use function name as ruleset name by default when creating ruleset from function
Adds ability to refer to methods and property off of classes instead of only off of instances (i.e. Math.__add__(x, y))

7.0.0 (2024-04-27)

Defers adding rules in functions until they are used, so that you can use types that are not present yet.
Removes ability to set custom default ruleset for egraph. Either just use the empty default ruleset or explicitly set it for every run
Automatically mark Python builtin operators as preserved if they must return a real Python value
Properly pretty print all items (rewrites, actions, exprs, etc) so that expressions are de-duplicated and state is handled correctly.
Add automatic releases from github manual action

6.1.0 (2024-03-06)

Upgrade egglog
- Adds subsume action
Makes all objects besides EGraphs "sendable" aka threadsafe (#129)

6.0.1 (2024-02-28)

Upgrade dependencies, including egglog
Fix bug where saturate wasn't properly getting translated.

6.0.0 (2024-02-06)

Remove modules / Auto register functions/classes

You can now create classes and functions without an EGraph! They will be automatically registered on any EGraph if they are used in any of the rules or commands. This means the methods to add functions/classes on an EGraph are deprecated and moved to the top level module:

egraph.class_ -> Removed, simply subclass from egglog.Expr
egraph.method -> egglog.method
egraph.function -> egglog.function
egraph.relation -> egglog.relation
egraph.ruleset -> egglog.Ruleset
egraph.Module -> Removed

The goal of this change is to remove the complexity of Modules and remove the need to think about what functions/classes need to be registered for each EGraph.

In turn, if you want to collect a set of rules, you can do that with a ruleset. Whenever you now run a ruleset or schedule, the ruleset will be automatically registered on the EGraph.

For backwards compatability, the existing methods and functions are preserved, to make this easier to adopt. They will all now raise deprication warnings.

Allow future type references in classes

Classes can now reference types that have not been defined yet, as long as they are defined before the class is used in a rule or expression. For example:

class A(Expr):
    def __init__(self, b: B) -> None: ...

class B(Expr):
    ...

Top level commands

We can now simplify and check expressions without explicity making an EGraph:

check(<fact>, [<schedule>], *[<actions>])
# is equivalent to
e = EGraph()
e.register(*<actions>)
e.run(<schedule>)
e.check(<fact>)

simplify(<expr>, [<schedule>])
# is equivalent to
EGraph().simplify(<expr>, [<schedule>])

5.0.0 (2024-01-16)

Move egglog != function to be called with ne(x).to(y) instead of x != y so that user defined expressions can

4.0.1 (2023-11-27)

Fix keyword args for __init__ methods (#96)[#96].

4.0.0 (2023-11-24)

Fix as_egglog_string proprety.
Move EGraph.eval_fn to py_eval_fn since it doesn't need the EGraph anymore.

3.1.0 (2023-11-21)

Update graphs to include more compact Python names of functions (#79)[#79].
Add as_egglog_string property to get egglog source from e-graph (#82)[#82].
Add include_cost flag to egraph.extract to return the integer cost as well as an expression (#86)[#86].
Automatically try converting arguments to eq, rewrite, set_, and union to the correct type (#84)[#84].
Update RTD name to new project name of egglog-python from egg-smol-python (#18)[#18].
Move project to egraphs-good org!

3.0.0 (2023-11-19)

Add support for outputing the serialization e-graph from the low level bindings. Note that this is not yet exposed a the high level yet.

This removes the existing to graphviz function on the EGraph low level binding and moves it to a method on the serialized EGraph.

See (#78)[#78] for more details.

2.0.0 (2023-11-17)

Simplify accessing primitives

Previously, there was no public way of turning an egglog primitive, i.e. i64(10), into a Python primitive, i.e. int(10). Now there is a egraph.eval(...) method which will evaluate a primitive expression and return a Python object.

We also change the PyObject primitive to behave similarly. Instead of calling egraph.load_object(pyobj) you can now call egraph.eval(pyobj) to get the underlying Python object. Also, to unify it with the other objects, you can create a PyObject by using the constructor instead of egraph.save_object(pyobj).

Bug fixes

Properly expose birewrite at top level (#72)[#72].
Fix generation of graphviz interactive SVGs in docs.

Enhancements

Added PyData lighting talk and Portland state talk to explanations.
Add experimental jit decorator to wrap all ndarray/numba functionality together.
Switch to Ruff for linting

1.0.1 (2023-10-26)

Adds youtube video to presentation slides.

1.0.0 (2023-10-26)

Breaking Changes

Test on Python 3.9 - 3.11, stop testing on 3.8 to follow Scientific Python versioning policy
Bump egglog dep
- Adds Bool builtin
- Rename PrintTable command to PrintFunction
- Change extract command back to taking an expression instead of a fact
- Adds numer and denom functions to Rational sort.
- Adds terms_encoding boolean flag for creating an EGraph
- Allow print size command to be called with no args to print all sizes
- Add rebuild method for sets, maps, and vecs.

New Features

Add ability to print egglog string of module with .as_egglog_string
Add ability to visualize changes in egraph as it runs with .saturate()
Add ability to make functions and module unextractable as well as increase the cost of a whole module.
Convert reflected methods based on both types
Allow specifying custom costs for conversions
In py_exec make a temporary file with source for tracebacks
Add an experimental Array API implementation with a scikit-learn test

0.7.0 (2023-10-04)

Bump egglog dep

New Features

Adds ability for custom user defined types in a union for proper static typing with conversions #49
Adds py_eval function to EGraph as a helper to eval Python code. #49
Adds on hover behavior for edges in graphviz SVG output to make them easier to trace #49
Adds egglog.exp.program_gen module that will compile expressions into Python statements/functions #49
Adds py_exec primitive function for executing Python code #49

Bug fixes

Clean up example in tutorial with demand based expression generation #49

0.6.0 (2023-09-20)

Bump egglog dep

Breaking Changes

Switches RunReport to include more granular timings

New Features

Add ability to pass seminaive flag to Egraph to replicate --naive CLI flag #48
Add ability to inline leaves $n$ times instead of just once for visualization #48
Add Relation and PrintOverallStatistics low level commands #46
Adds count-matches and replace string commands #46

Uncategorized

Added initial supported for Python objects #31
- Renamed BaseExpr to Expr for succinctness
- Add slides for zoom presentation with Open Teams
- Started adding tutorial for using with array API and sklearn], using this to drive the support for more Python integration
- Added a PyObject sort with the save_object and load_object egraphs methods and the exec
- Added more general mechanism to upcast Python arguments into egglog expressions, by registering converters
- Added support for default arguments (this required refactoring declerations so that pretty printing can lookup expressions)
- Added support for properties
- Added support for passing args as keywords
- Add support for pure Python methods, using the preserve kwarg to implement functions like __bool__ on expressions.
- Fix __str__ method when pretty printing breaks.
- Added to/from i64 to i64 methods.
- Upgraded egg-smol dependency (changes)
Add support for functions which mutates their args, like __setitem__ #35
Makes conversions transitive #38
Add support for reflective operators #39
- Make reflective operators map directly to non-reflective #40
Includes latest egglog changes #42
- Switches to termdag introduced in egglog #176
- Removes custom fork of egglog now that visualizations are in core
- Adds int and float to string functions
- Switches define to let
Tidy up notebook appearence #43
- Display expressions as code in Jupyter notebook
- Display all expressions when graphing
Start adding to string support #45
- Fix adding rules for sorts defined in other modules
- Split out array API into multiple module
- tidy up docs homepage

0.5.1 (2023-07-18)

Added support for negation on f64 sort
Upgraded egg-smol dependency (changes)

0.5.0 (2023-05-03)

Renamed config() to run() to better match egglog command
Fixed relation type signature
Added default limit of 1 to run() to match egglog command and moved to second arg
Upgraded egglog dependency (changes)
- Added Set sort and removed set method from Map
- Added Vec sort
- Added support for variable args for builtin functions, to use in creation of Vec and Set sorts.
- Added suport for joining Strings
Switch generated egg names to use . as seperate (i.e. Math.__add__) instead of _ (i.e. Math___add__)
Adds support for modules to define functions/sorts/rules without executing them, for reuse in other modules
- Moved simplifying and running rulesets to the run and simplify methods on the EGraph from those methods on the Ruleset since we can now create Rulsets for modules which don't have an EGraph attached and can't be run
Fixed extracting classmethods which required generic args to cls
Added support for alternative way of creating variables using functions
Add NDarray example
Render EGraphs with graphviz in the notebook (used in progress egglog PR).
- Add images to doc examples
Add %%egglog magic to the notebook

0.4.0 (2023-05-03)

Change name to egglog from egg-smol, to mirror upstream change. Note that all previous versions are published under the egg-smol PyPi package while this and later are under egglog.

0.3.1 (2023-05-02)

Fix bug calling methods on paramterized types (e.g. Map[i64, i64].empty().insert(i64(0), i64(1)))
Fix bug for Unit type (egg name is Unit not unit)
Use @class_ decorator to force subclassing Expr
Workaround extracting definitions until upstream is fixed
Rename Map.map_remove to Map.remove.
Add lambda calculus example

0.3.0 (2023-04-26)

Upgrade egglog from 08a6e8fecdb77e6ba72a1b1d9ff4aff33229912c to 6f2633a5fa379487fb389b80fc1225866f8b8c1a.

0.2.0 (2023-03-27)

This release adds support for a high level API for e-graphs.

There is an examples of the high level API in the tutorials.

Uh oh!

FilesExpand file tree

changelog.md

Latest commit

History

changelog.md

File metadata and controls

Changelog

UNRELEASED

10.0.1 (2025-04-06)

10.0.0 (2025-03-28)

9.0.1 (2025-03-20)

9.0.0 (2025-03-20)

Evaluating Primitives

Equal and Not Equal operators

Evaluating Facts

Experimental Array API Support

All changes

8.0.1 (2024-10-24)

8.0.0 (2024-10-17)

7.2.0 (2024-05-23)

7.1.0 (2024-05-03)

New Feaatures

Minor improvements

7.0.0 (2024-04-27)

6.1.0 (2024-03-06)

6.0.1 (2024-02-28)

6.0.0 (2024-02-06)

Remove modules / Auto register functions/classes

Allow future type references in classes

Top level commands

5.0.0 (2024-01-16)

4.0.1 (2023-11-27)

4.0.0 (2023-11-24)

3.1.0 (2023-11-21)

3.0.0 (2023-11-19)

2.0.0 (2023-11-17)

Simplify accessing primitives

Bug fixes

Enhancements

1.0.1 (2023-10-26)

1.0.0 (2023-10-26)

Breaking Changes

New Features

0.7.0 (2023-10-04)

New Features

Bug fixes

0.6.0 (2023-09-20)

Breaking Changes

New Features

Uncategorized

0.5.1 (2023-07-18)

0.5.0 (2023-05-03)

0.4.0 (2023-05-03)

0.3.1 (2023-05-02)

0.3.0 (2023-04-26)

0.2.0 (2023-03-27)