### Debugging Example Setup

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Sets up a basic DebugMath class and a score function with a rewrite rule for addition. This serves as a foundation for demonstrating debugging and inspection methods.

```python
from __future__ import annotations

from egglog import *


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

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


@function
def score(x: DebugMath) -> i64: ...


debug_rules = ruleset()


@debug_rules.register
def _(i: i64, j: i64):
    yield rewrite(DebugMath(i) + DebugMath(j)).to(DebugMath(i + j))
```

--------------------------------

### Example Usage: Array Manipulation and Optimization Setup

Source: https://github.com/egraphs-good/egglog-python/blob/main/python/egglog/exp/MoA.ipynb

Demonstrates the usage of `take`, `drop`, and `cat` functions with `NDArray`s. It also shows how to initialize an `EGraph` and define variables for array dimensions and shapes, preparing for optimization.

```python
shape = TupleInt.from_vec(Vec(Int(2), Int(3), Int(4)))
RAMY = NDArray.from_memory(shape, constant("RAMY", TupleInt))
AMY = NDArray.from_memory(shape, constant("AMY", TupleInt))
Amts = take(Int(2), drop(Int(2), cat(RAMY, AMY)))
Amts

```

```text
Result:
take(Int(2), drop(Int(2), cat(NDArray.from_memory(TupleInt.from_vec(Vec(Int(2), Int(3), Int(4))), RAMY), NDArray.from_memory(TupleInt.from_vec(Vec(Int(2), Int(3), Int(4))), AMY))))
```

```python
egraph = EGraph()
ndim = egraph.let("ndim", Amts.shape.length)
shape_1 = egraph.let("shape_1", Amts.shape[Int(0)])
shape_2 = egraph.let("shape_2", Amts.shape[Int(1)])
shape_3 = egraph.let("shape_3", Amts.shape[Int(2)])

```

--------------------------------

### Install anywidget for interactive widgets

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/usage.md

Install the anywidget package to enable interactive widgets.

```shell
pip install anywidget
```

--------------------------------

### Install Full Development Environment

Source: https://github.com/egraphs-good/egglog-python/blob/main/AGENTS.md

Use this command to install all necessary dependencies for the development environment.

```bash
uv sync --all-extras
```

--------------------------------

### Install egglog with array support

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/usage.md

Install egglog with optional array processing capabilities.

```shell
pip install egglog[array]
```

--------------------------------

### Install egglog and anywidget

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_11_17_pytensor.ipynb

Installs the egglog and anywidget Python packages using pip.

```python
%%capture
!pip install egglog
!pip install anywidget
```

--------------------------------

### Install egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/usage.md

Install the base egglog package using pip.

```shell
pip install egglog
```

--------------------------------

### Add lambda calculus example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/changelog.md

Includes an example demonstrating the implementation and usage of lambda calculus within egglog-python.

```python
from egglog import * 

# Example of lambda calculus implementation
e = egglog.EGraph()
# ... lambda calculus specific code ...
```

--------------------------------

### Add NDarray example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/changelog.md

Includes an example demonstrating the usage of NDarrays within the egglog-python framework.

```python
from egglog import * 

# Example usage of NDarray (specific implementation depends on egglog's NDarray support)
e = egglog.EGraph()
# ... code related to NDarray usage ...
```

--------------------------------

### Install Rust and Python Environment with uv

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/contributing.md

Install Rust using the official script and set up a Python environment with uv. This ensures compatible versions for development.

```bash
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
curl -LsSf https://astral.sh/uv/install.sh | sh
```

--------------------------------

### Test egglog Python Installation

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Verify the egglog Python installation by importing it in the Python interpreter.

```bash
python -m 'import egglog'
```

--------------------------------

### Setup Egglog and Scikit-learn Integration

Source: https://github.com/egraphs-good/egglog-python/blob/main/python/egglog/exp/any_expr_example.ipynb

Initializes the environment by setting the SciPy array API and importing necessary scikit-learn and Egglog modules. Configures scikit-learn for array API dispatch.

```python
import os

os.environ["SCIPY_ARRAY_API"] = "1"

from sklearn import set_config
from sklearn.datasets import make_classification
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

from egglog import *
from egglog.exp import any_expr
from egglog.exp.any_expr import *

set_config(array_api_dispatch=True)
```

--------------------------------

### Install mypy for Static Type Checking

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Install mypy, a static type checker, to help ensure the correctness of your egglog representations. This is recommended but not strictly required.

```bash
pip install mypy
```

--------------------------------

### Create Kronecker Product of Identity and Matrix B

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Creates an example representing the Kronecker product of an identity matrix and matrix B, then runs and extracts the result.

```python
ex1 = kron(Matrix.identity(n), B) @ kron(A, Matrix.identity(m))
egraph.run(20)
egraph.extract(ex1)
```

```result
kron(Matrix.named("A"), Matrix.named("B"))
```

--------------------------------

### Kronecker Product with Mismatched Dimensions

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Demonstrates that transformations are not applied if matrix dimensions do not align for the Kronecker product. The example is run and extracted.

```python
ex2 = kron(Matrix.identity(p), C) @ kron(A, Matrix.identity(m))
egraph.run(20)
egraph.extract(ex2)
```

```result
kron(Matrix.identity(Dim.named("p")), Matrix.named("C")) @ kron(Matrix.named("A"), Matrix.identity(Dim.named("m")))
```

--------------------------------

### Example: Matrix Dimension Calculation

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Demonstrates how to define dimensions, matrices, and register unions to set matrix dimensions, then compute the dimensions of resulting matrices after operations.

```APIDOC
## Example: Matrix Dimension Calculation

### Description
This example shows how to set up dimensions and matrices, register their relationships using `union`, and then compute the dimensions of matrices after operations.

### Setup
1. Define dimensions: `n, m, p = Dim.named("n"), Dim.named("m"), Dim.named("p")`
2. Define matrices: `A, B, C = Matrix.named("A"), Matrix.named("B"), Matrix.named("C")`
3. Register dimension unions:
   - `egraph.register(union(A.nrows()).with_(n), union(A.ncols()).with_(n))`
   - `egraph.register(union(B.nrows()).with_(m), union(B.ncols()).with_(m))`
   - `egraph.register(union(C.nrows()).with_(p), union(C.ncols()).with_(p))`

### Usage
After setting up the dimensions and matrices, operations like `A @ B` can be performed, and their dimensions can be extracted using `egraph.extract(matrix.nrows())` and `egraph.extract(matrix.ncols())`.
```

--------------------------------

### LDA fit method example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

Shows an example within a LinearDiscriminantAnalysis class where `xp.unique_counts` is used to calculate prior probabilities, demonstrating array type casting and division.

```python
class LinearDiscriminantAnalysis:
    ...  # non-negative ints
        self.priors_ = xp.astype(cnts, X.dtype) / float(y.shape[0])
```

--------------------------------

### Fork and Clone Repository using Github CLI

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/contributing.md

Use the Github CLI to fork the repository and clone it locally. Ensure you have the Github CLI installed.

```bash
brew install gh
gh repo fork egraphs-good/egglog-python --clone
cd egglog-python
```

--------------------------------

### Setup Symbolic Arrays and Run LDA

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

Initializes symbolic NumPy arrays, sets assumptions on their properties, and runs a symbolic LDA function within the egglog environment. Requires importing necessary functions from egglog.exp.array_api.

```python
from egglog.exp.array_api import *

X_arr = NDArray.var("X")
assume_dtype(X_arr, X_np.dtype)
assume_shape(X_arr, X_np.shape)
assume_isfinite(X_arr)

y_arr = NDArray.var("y")
assume_dtype(y_arr, y_np.dtype)
assume_shape(y_arr, y_np.shape)
assume_value_one_of(y_arr, tuple(map(int, np.unique(y_np))))  # type: ignore[arg-type]

egraph = EGraph()
with set_array_api_egraph(egraph):
    res = run_lda(X_arr, y_arr)
```

--------------------------------

### Egglog setup and Numba extraction

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/sklearn.ipynb

This Python code demonstrates how to set up an Egglog e-graph with Numba-specific array API rules and extract a Numba-optimized representation of a given expression.

```python
from egglog.exp.array_api_numba import array_api_numba_module

egraph = EGraph([array_api_numba_module])
egraph.register(X_r2_optimized)
egraph.run(10000)
X_r2_numba = egraph.extract(X_r2_optimized)
X_r2_numba
```

--------------------------------

### Partial Application with `functools.partial`

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Illustrates using `functools.partial` to create a partially applied function for mapping over a `MathList`. This example shows how to combine partial application with egglog's rewrite rules for functional programming patterns.

```python
from functools import partial

x = MathList.EMPTY.append(Math(1))
added_two = x.map(partial(Math.__add__, Math(2)))

check_eq(added_two, MathList.EMPTY.append(Math(2) + Math(1)), math_list_ruleset.saturate())
```

--------------------------------

### Compute Matrix Dimensions Example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Demonstrates computing the number of columns and rows of a matrix resulting from the multiplication of two identity matrices.

```python
# If we multiply two identity matrices, we should be able to get the number of columns of the result
x = Matrix.identity(Dim.named("x"))
y = Matrix.identity(Dim.named("y"))
x_mult_y = x @ y
egraph.run(10)
print(egraph.extract(x_mult_y.ncols()))
print(egraph.extract(x_mult_y.nrows()))

```

--------------------------------

### Example of Simplified Result

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

This is an example of a simplified result after optimization and extraction. It shows the expanded form of the `_mean` rewrite rule.

```python
_NDArray_1 = NDArray.var("X")
assume_dtype(_NDArray_1, DType.float64)
assume_shape(_NDArray_1, TupleInt.from_vec(Vec[Int](Int(150), Int(4))))
assume_isfinite(_NDArray_1)
_NDArray_2 = NDArray.var("y")
assume_dtype(_NDArray_2, DType.int64)
assume_shape(_NDArray_2, TupleInt.from_vec(Vec[Int](Int(150))))
assume_value_one_of(_NDArray_2, TupleValue.from_vec(Vec[Value](Value.int(Int(0)), Value.int(Int(1)), Value.int(Int(2)))))
_NDArray_3 = astype(
    NDArray.vector(
        TupleValue.from_vec(
            Vec[Value](
                sum(_NDArray_2 == NDArray.scalar(Value.int(Int(0)))).to_value(),
                sum(_NDArray_2 == NDArray.scalar(Value.int(Int(1)))).to_value(),
                sum(_NDArray_2 == NDArray.scalar(Value.int(Int(2)))).to_value(),
            )
        )
    ),
    DType.float64,
) / NDArray.scalar(Value.float(Float.rational(BigRat(BigInt.from_string("150"), BigInt.from_string("1")))))
_NDArray_4 = zeros(TupleInt.from_vec(Vec[Int](Int(3), Int(4))), OptionalDType.some(DType.float64), OptionalDevice.some(_NDArray_1.device))
_MultiAxisIndexKeyItem_1 = MultiAxisIndexKeyItem.slice(Slice())
_IndexKey_1 = IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec[MultiAxisIndexKeyItem](MultiAxisIndexKeyItem.int(Int(0)), _MultiAxisIndexKeyItem_1)))
_NDArray_5 = _NDArray_1[IndexKey.ndarray(_NDArray_2 == NDArray.scalar(Value.int(Int(0))))]
_OptionalIntOrTuple_1 = OptionalIntOrTuple.some(IntOrTuple.int(Int(0)))
_NDArray_4[_IndexKey_1] = sum(_NDArray_5, _OptionalIntOrTuple_1) / NDArray.scalar(Value.int(_NDArray_5.shape[Int(0)]))
_IndexKey_2 = IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec[MultiAxisIndexKeyItem](MultiAxisIndexKeyItem.int(Int(1)), _MultiAxisIndexKeyItem_1)))
_NDArray_6 = _NDArray_1[IndexKey.ndarray(_NDArray_2 == NDArray.scalar(Value.int(Int(1))))]
_NDArray_4[_IndexKey_2] = sum(_NDArray_6, _OptionalIntOrTuple_1) / NDArray.scalar(Value.int(_NDArray_6.shape[Int(0)]))
_IndexKey_3 = IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec[MultiAxisIndexKeyItem](MultiAxisIndexKeyItem.int(Int(2)), _MultiAxisIndexKeyItem_1)))
_NDArray_7 = _NDArray_1[IndexKey.ndarray(_NDArray_2 == NDArray.scalar(Value.int(Int(2))))]
_NDArray_4[_IndexKey_3] = sum(_NDArray_7, _OptionalIntOrTuple_1) / NDArray.scalar(Value.int(_NDArray_7.shape[Int(0)]))
_NDArray_8 = concat(
    TupleNDArray.from_vec(Vec[NDArray](_NDArray_5 - _NDArray_4[_IndexKey_1], _NDArray_6 - _NDArray_4[_IndexKey_2], _NDArray_7 - _NDArray_4[_IndexKey_3])),
    OptionalInt.some(Int(0)),
)
_NDArray_9 = square(_NDArray_8 - expand_dims(sum(_NDArray_8, _OptionalIntOrTuple_1) / NDArray.scalar(Value.int(_NDArray_8.shape[Int(0)]))))
_NDArray_10 = sqrt(sum(_NDArray_9, _OptionalIntOrTuple_1) / NDArray.scalar(Value.int(_NDArray_9.shape[Int(0)])))
_NDArray_11 = copy(_NDArray_10)
_NDArray_11[IndexKey.ndarray(_NDArray_10 == NDArray.scalar(Value.int(Int(0))))] = NDArray.scalar(
    Value.float(Float.rational(BigRat(BigInt.from_string("1"), BigInt.from_string("1"))))
)
_TupleNDArray_1 = svd(
    sqrt(
        asarray(
            NDArray.scalar(Value.float(Float.rational(BigRat(BigInt.from_string("1"), BigInt.from_string("147"))))),
            OptionalDType.some(DType.float64),
            OptionalBool.none,
            OptionalDevice.some(_NDArray_1.device),
        )
    )
    * (_NDArray_8 / _NDArray_11),
    Boolean(False),
)
_Slice_1 = Slice(OptionalInt.none, OptionalInt.some(sum(astype(_TupleNDArray_1[Int(1)] > NDArray.scalar(Value.float(Float(0.0001))), DType.int32)).to_value().to_int))
_NDArray_12 = (
    _TupleNDArray_1[Int(2)][IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec[MultiAxisIndexKeyItem](MultiAxisIndexKeyItem.slice(_Slice_1), _MultiAxisIndexKeyItem_1)))]
    / _NDArray_11
).T / _TupleNDArray_1[Int(1)][IndexKey.slice(_Slice_1)]
_TupleNDArray_2 = svd(
    (

```

--------------------------------

### Define Relations and Rules in an Egglog File

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Define relations and rewrite rules in a separate `.egg` file for reusability. This example defines `path` and `edge` relations and rules for pathfinding.

```egglog
%%writefile path.egg
(relation path (i64 i64))
(relation edge (i64 i64))

(rule ((edge x y)) 
      ((path x y)))

(rule ((path x y) (edge y z)) 
      ((path x z)))
```

--------------------------------

### Include and Use an Egglog File in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Include an external `.egg` file using the `include` directive to reuse definitions. This example includes `path.egg` and then defines edges and checks for a path.

```egglog
%%egglog
(include "path.egg")
(edge 1 2)
(edge 2 3)
(edge 3 4)
(run 3)
(check (path 1 3))
```

--------------------------------

### Saturate EGraph with Rules

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Use `egraph.saturate` to repeatedly apply rules until the e-graph stabilizes. This example demonstrates saturation with a specific expression and a maximum number of steps.

```python
egraph = EGraph()
expr = egraph.let("expr", DebugMath(2) + DebugMath(100))
egraph.saturate(debug_rules, expr=expr, max=2, visualize=False)
```

--------------------------------

### Dynamic Cost Setting with set_cost

Source: https://context7.com/egraphs-good/egglog-python/llms.txt

Set costs dynamically based on runtime analysis using `set_cost`. This example optimizes matrix chain multiplication by reordering operations based on FLOPs.

```python
from egglog import *
from collections.abc import Iterable

class Matrix(Expr):
    def __init__(self, rows: i64Like, cols: i64Like) -> None: ...
    def __matmul__(self, other: Matrix) -> Matrix: ...

    @property
    def row(self) -> i64: ...
    @property
    def col(self) -> i64: ...

egraph = EGraph()

@egraph.register
def _(x: Matrix, y: Matrix, z: Matrix, r: i64, c: i64, m: i64) -> Iterable[RewriteOrRule]:
    # Propagate dimensions
    yield rule(x == Matrix(r, c)).then(set_(x.row).to(r), set_(x.col).to(c))
    yield rule(
        x == (y @ z), r == y.row, y.col == z.row, c == z.col
    ).then(set_(x.row).to(r), set_(x.col).to(c))

    # Set cost based on matrix dimensions (FLOPs)
    yield rule(
        y @ z, r == y.row, m == y.col, c == z.col
    ).then(set_cost(y @ z, r * m * c))

    # Associativity rewrite
    yield birewrite(x @ (y @ z)).to((x @ y) @ z)

# Optimize matrix chain multiplication
expr = egraph.let("expr", (Matrix(64, 8) @ Matrix(8, 256)) @ Matrix(256, 2))
egraph.run(5)
optimized = egraph.extract(expr)
print(optimized)  # Reorders for minimal FLOPs
```

--------------------------------

### Define Types and Functions for Congruence Closure

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_12_02_congruence_closure.md

Sets up a dummy type 'T' and functions 'f' (2-argument) and 'f1' (1-argument) required for congruence closure examples in egglog.

```python
from egglog import *


class T(Expr): pass

a = constant("a", T)
b = constant("b", T)

@function
def f(x: T, y: T) -> T: pass

@function
def f1(x: T) -> T: pass
```

--------------------------------

### Array Manipulation Example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

This snippet demonstrates complex array manipulations using egglog's NDArray and IndexKey objects, involving operations like subtraction, indexing, and SVD.

```python
asarray(_NDArray_1)[IndexKey.ndarray(_NDArray_7 == _NDArray_8[IndexKey.int(Int(2))])] - _NDArray_3[_IndexKey_5],
            )
        ),
        OptionalInt.some(Int(0)),
    ),
    _OptionalIntOrTuple_1,
)
_NDArray_10 = copy(_NDArray_9)
_NDArray_10[IndexKey.ndarray(_NDArray_9 == NDArray.scalar(Value.int(Int(0))))] = NDArray.scalar(Value.float(Float(1.0)))
_NDArray_11 = astype(unique_counts(_NDArray_2)[Int(1)], DType.float64) / NDArray.scalar(Value.float(Float.rational(BigRat(BigInt.from_string("150"), BigInt.from_string("1")))))
_TupleNDArray_2 = svd(
    (
        sqrt((NDArray.scalar(Value.int(Int(150)))) * _NDArray_11) * NDArray.scalar(Value.float(Float.rational(BigRat(BigInt.from_string("1"), BigInt.from_string("2"))))))
        * (_NDArray_4 - (_NDArray_11 @ _NDArray_4)).T
    ).T
    @ (
        (
            _TupleNDArray_1[Int(2)][IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec[MultiAxisIndexKeyItem](MultiAxisIndexKeyItem.slice(_Slice_1), _MultiAxisIndexKeyItem_1)))]
            / _NDArray_6
        ).T
        / _TupleNDArray_1[Int(1)][IndexKey.slice(_Slice_1)]
    ),
    Boolean(False),
)
(
    (asarray(_NDArray_1) - ((astype(unique_counts(_NDArray_2)[Int(1)], asarray(_NDArray_1).dtype) / NDArray.scalar(Value.float(Float(150.0)))) @ _NDArray_3))
    @ (
        (
            (_TupleNDArray_1[Int(2)][IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec(MultiAxisIndexKeyItem.slice(_Slice_1), _MultiAxisIndexKeyItem_1)))] / _NDArray_10).T
            / _TupleNDArray_1[Int(1)][IndexKey.slice(_Slice_1)]
        )
        @ _TupleNDArray_2[Int(2)].T[
            IndexKey.multi_axis(
                MultiAxisIndexKey.from_vec(
                    Vec(
                        _MultiAxisIndexKeyItem_1,
                        MultiAxisIndexKeyItem.slice(
                            Slice(
                                OptionalInt.none,
                                OptionalInt.some(
                                    sum(astype(_TupleNDArray_2[Int(1)] > (NDArray.scalar(Value.float(Float(0.0001))) * _TupleNDArray_2[Int(1)][IndexKey.int(Int(0))]), DType.int32))
                                    .to_value()
                                    .to_int
                                ),
                            )
                        ),
                    )
                )
            )
        ]
    )
)[IndexKey.multi_axis(MultiAxisIndexKey.from_vec(Vec(_MultiAxisIndexKeyItem_1, MultiAxisIndexKeyItem.slice(Slice(OptionalInt.none, OptionalInt.some(Int(2)))))))]
```

--------------------------------

### Define Datalog-Style Relations and Rules

Source: https://context7.com/egraphs-good/egglog-python/llms.txt

Use relations for deductive reasoning with pattern matching and rule chaining. This example defines edge and path relations and inference rules for path discovery.

```python
from egglog import *
from collections.abc import Iterable

# Define relations (functions returning Unit)
edge = relation("edge", i64, i64)
path = relation("path", i64, i64)

egraph = EGraph()

# Insert facts
egraph.register(
    edge(i64(1), i64(2)),
    edge(i64(2), i64(3)),
    edge(i64(3), i64(4)),
)

# Define inference rules
@egraph.register
def _(a: i64, b: i64, c: i64) -> Iterable[RewriteOrRule]:
    # Base case: edge implies path
    yield rule(edge(a, b)).then(path(a, b))
    # Transitive case: path(a,b) + edge(b,c) => path(a,c)
    yield rule(path(a, b), edge(b, c)).then(path(a, c))

# Run to fixpoint
egraph.run(run().saturate())

# Check derived facts
egraph.check(path(i64(1), i64(4)))  # Passes: path exists
```

--------------------------------

### Preventing Saturation with Associativity and Zero Rules in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2026_02_containers.md

This example demonstrates how simple associativity and zero rules can prevent saturation in an e-graph. It defines an integer datatype with multiplication and zero, then applies rewrite rules to simplify expressions involving multiplication and zero.

```clojure
(datatype Int (mul Int Int) (a) (zero))

(birewrite (mul x (mul y z)) (mul (mul x y) z))
(rewrite (mul (zero) x) (zero))

(mul (zero) (a))
(run-schedule (repeat 8 (run)))
```

--------------------------------

### Build Documentation

Source: https://github.com/egraphs-good/egglog-python/blob/main/AGENTS.md

Build the project documentation using the Make command.

```bash
make docs
```

--------------------------------

### Get Function Size

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Retrieve the number of rows for a specific function using `egraph.function_size(fn)`. Call `egraph.all_function_sizes()` to get sizes for all registered functions.

```python
egraph.function_size(Math)
```

```python
egraph.all_function_sizes()
```

--------------------------------

### Basic Value Creation in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Demonstrates the creation of a simple Value object in Egglog.

```python
Value(7)
```

--------------------------------

### Egglog EGraph Initialization and Saturation

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2026_02_containers.md

Demonstrates initializing an `EGraph` and defining a new expression with a sum of numbers and variables. It then saturates the e-graph using the `set_get_i64` and `constant_fold_sum` rulesets, preparing it for extraction.

```python
egraph = EGraph()
new_expr = egraph.let("new_expr", sum_(MultiSet(Num(2), a, b, b, Num(3))))
egraph.saturate(set_get_i64.saturate() + constant_fold_sum.saturate())
egraph.extract(new_expr)
```

--------------------------------

### Numba Performance Warning Example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_11_09_portland_state.ipynb

Illustrates a Numba performance warning related to the '@' operator on non-contiguous arrays.

```python
/var/folders/xn/05ktz3056kqd9n8frgd6236h0000gn/T/egglog-9befda2c-765c-4e2c-94d5-f667be45c7eb.py:56: NumbaPerformanceWarning: '@' is faster on contiguous arrays, called on (Array(float64, 2, 'C', False, aligned=True), Array(float64, 2, 'A', False, aligned=True))
  _45 = _33 @ _40[2].T[:, :_44]
```

--------------------------------

### Prove f1(a) = a using successive assumptions

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_12_02_congruence_closure.md

Demonstrates proving f1(a) = a by first registering f1(f1(f1(a))) = a and then f1(f1(f1(f1(f1(a))))) = a. The e-graph is displayed after each registration to show the evolving equivalence classes.

```python
egraph = EGraph()
egraph.register(
    union(f1(f1(f1(a)))).with_(a),
)
egraph.display()
egraph.register(
    union(f1(f1(f1(f1(f1(a)))))).with_(a),
)
egraph.check(eq(f1(a)).to(a))
```

--------------------------------

### Get Variable Name in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Use `get_var_name(expr)` to check if an expression is a variable and retrieve its name.

```python
from egglog import var, get_var_name
v = var("x", i64)
assert get_var_name(v) == "x"
```

--------------------------------

### Get Source Code of Optimized Function

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_11_pydata_lightning_talk.ipynb

Use the `inspect` module to retrieve the source code of the optimized function.

```python
import inspect

print(inspect.getsource(optimized_fn))
```

--------------------------------

### Apply Egglog Rules to Scikit-learn Model Training

Source: https://github.com/egraphs-good/egglog-python/blob/main/python/egglog/exp/any_expr_example.ipynb

Demonstrates how to instantiate a scikit-learn model (LinearDiscriminantAnalysis), generate sample data, and then use Egglog's `AnyExpr` within a configured `EGraph` to fit the model. This allows Egglog to apply the defined rules during the model training process.

```python
lda = LinearDiscriminantAnalysis()
X_np, y_np = make_classification(random_state=0)

egraph = EGraph()
with set_any_expr_egraph(egraph):
    x = lda.fit_transform(AnyExpr(X_np), AnyExpr(y_np))
```

--------------------------------

### Prove f(f(a, b), b) = a from f(a, b) = a

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_12_02_congruence_closure.md

Uses egglog to register an initial assumption and then checks if the desired equality can be proven. The e-graph visualization helps in understanding the proof.

```python
egraph = EGraph()
# start with our initial assumption
egraph.register(
    union(f(a, b)).with_(a)
)
# Verify that we can prove the result
egraph.check(
    eq(f(f(a, b), b)).to(a)
)
egraph.display()
```

--------------------------------

### Get Callable Function from Egglog Expression

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Use `get_callable_fn(expr)` to retrieve the underlying Python function for a callable egglog expression.

```python
expr = i64(1) + i64(2)
fn = get_callable_fn(expr)
assert fn == i64.__add__
```

--------------------------------

### Get Let Variable Name in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Use `get_let_name(expr)` to check if an expression is a let value and retrieve its assigned name.

```python
x = EGraph().let("my_var", i64(1))
assert get_let_name(x) == "my_var"
```

--------------------------------

### Download Visualizer Source

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/contributing.md

Clean and build the project to download the most recent released version of the visualizer source from GitHub Actions artifacts.

```bash
make clean; make
```

--------------------------------

### Run LDA with NumPy Arrays

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_11_09_portland_state.ipynb

Performs Linear Discriminant Analysis using scikit-learn on NumPy arrays. Ensure scikit-learn and NumPy are installed.

```python
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from egglog.core import config_context
from sklearn.datasets import make_classification

def run_lda(x, y):
    with config_context(array_api_dispatch=True):
        lda = LinearDiscriminantAnalysis()
        return lda.fit(x, y).transform(x)


X_np, y_np = make_classification(random_state=0, n_samples=1000000)
run_lda(X_np, y_np)
```

--------------------------------

### Get EGraph Statistics

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Obtain overall statistics for the EGraph by calling `egraph.stats()`. This provides insights into the EGraph's current state and performance.

```python
egraph.stats()
```

--------------------------------

### Switch from define to let

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/changelog.md

Updates the syntax for defining variables from `define` to `let`, aligning with upstream changes.

```egglog
(let x 10)
```

--------------------------------

### Extract Expression from EGraph

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Use `egraph.extract` to get the lowest cost expression for a given term. Pass `include_cost=True` to also retrieve the associated cost.

```python
egraph.extract(fib(1))
```

```python
egraph.extract(fib(1), include_cost=True)
```

--------------------------------

### Python to egglog Conversion Example

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

Illustrates how Python's `unique_counts` function is converted into an egglog expression, showing the transformation of array data types and calculations.

```python
astype(unique_counts(_NDArray_3)[Int(1)], asarray(_NDArray_1).dtype) / NDArray.scalar(Value.float(Float(1000000.0)))
```

--------------------------------

### Define and Apply Rewrite Rules in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Use egglog syntax to define rewrite rules for expression simplification and then run them. The `run` command executes the rules, and `check` verifies the result.

```egglog
%%egglog graph continue
(rewrite (Add a b)
         (Add b a))
(rewrite (Mul a (Add b c))
         (Add (Mul a b) (Mul a c)))
(rewrite (Add (Num a) (Num b))
         (Num (+ a b)))
(rewrite (Mul (Num a) (Num b))
         (Num (* a b)))

(run 10)
(check (= expr1 expr2))
```

--------------------------------

### Python Slice Class Definition

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2024_03_17_community_talk.ipynb

Defines the `Slice` class in egglog, which represents slicing operations and accepts optional integer values for start, stop, and step.

```python
class Slice(Expr):
    def __init__(
        self,
        start: OptionalInt = OptionalInt.none,
        stop: OptionalInt = OptionalInt.none,
        step: OptionalInt = OptionalInt.none,
    ) -> None: ...


converter(
    slice,
    Slice,
    lambda x: Slice(
        convert(x.start, OptionalInt),
        convert(x.stop, OptionalInt),
        convert(x.step, OptionalInt),
    ),
)
```

--------------------------------

### Import egglog Library

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Imports necessary components from the `egglog` library for use in Python scripts. This is a common starting point for utilizing `egglog`'s features.

```python
from __future__ import annotations

from egglog import *

```

--------------------------------

### Initialize EGraph and Saturate Rules

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2026_02_containers.md

Initialize an empty e-graph, define two initial expressions, and then saturate the e-graph using the defined `comm_dist_fold` ruleset until no further changes occur. This process establishes all possible equivalences based on the rules.

```python
# 3. Create an empty e-graph
egraph = EGraph()

# 4. Add our two initial expressions
expr1 = egraph.let("expr1", Num(2) * (Num.var("x") + Num(3)))
expr2 = egraph.let("expr2", Num(6) + Num(2) * Num.var("x"))


# 5. Run this ruleset until it is "saturated"
# meaning that further application will be no-ops
# as well as output a visualization showing the progress
egraph.saturate(comm_dist_fold)
```

--------------------------------

### Initialize EGraph with Let and Set Actions

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Initializes an EGraph with 'let' and 'set_' actions. 'let' binds a variable, and 'set_' assigns a value to an expression, useful for setting initial conditions or rule results.

```python
egraph = EGraph(
    let("x", i64(1)),
    set_(fib(0)).to(i64(0)),
)
```

--------------------------------

### Add to/from i64 methods

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/changelog.md

Provides methods for converting between Python integers and egglog's i64 sort.

```python
from egglog import * 

ctx = egglog.EGraph().ctx

# Assuming i64 is a registered sort
value = ctx.i64(10)
python_int = value.to_i64()
```

--------------------------------

### Using Functions as First-Class Values in Egglog

Source: https://context7.com/egraphs-good/egglog-python/llms.txt

Illustrates how to use functions as first-class values in Egglog by passing them as arguments using Python's `Callable` type annotation. It defines custom `Math` and `MathList` expressions and demonstrates mapping operations with `partial` and lambda functions.

```python
from egglog import *
from collections.abc import Callable
from functools import partial
from typing import ClassVar

class Math(Expr):
    def __init__(self, x: i64Like) -> None: ...
    def __add__(self, other: Math) -> Math: ...
    def __mul__(self, other: Math) -> Math: ...

class MathList(Expr):
    EMPTY: ClassVar[MathList]
    def append(self, x: Math) -> MathList: ...
    def map(self, fn: Callable[[Math], Math]) -> MathList: ...

converter(i64, Math, Math)

# Define mapping rules
@ruleset
def list_rules(xs: MathList, x: Math, f: Callable[[Math], Math]):
    yield rewrite(MathList.EMPTY.map(f)).to(MathList.EMPTY)
    yield rewrite(xs.append(x).map(f)).to(xs.map(f).append(f(x)))

# Use partial application
my_list = MathList.EMPTY.append(Math(1)).append(Math(2))
doubled = my_list.map(partial(Math.__mul__, Math(2)))

# Or use lambda functions
added_ten = my_list.map(lambda x: x + Math(10))

egraph = EGraph()
egraph.register(doubled)
egraph.run(list_rules.saturate())
```

--------------------------------

### Equivalent of Top-Level Simplify

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/changelog.md

Demonstrates the equivalent EGraph instantiation and simplification process for the top-level simplify command.

```python
EGraph().simplify(<expr>, [<schedule>])
```

--------------------------------

### Use Modules and Run Commands in Python

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Instantiate an `EGraph` with defined modules and register commands like edges. The `run` command executes the commands, and `check` verifies the results, allowing for distributed and reusable code.

```python
egraph = EGraph([mod])
egraph.register(edge(1, 2), edge(2, 3), edge(3, 4))
egraph.run(3)
egraph.check(path(1, 3))
```

--------------------------------

### Egglog EGraph Initialization and Extraction

Source: https://github.com/egraphs-good/egglog-python/blob/main/python/egglog/exp/any_expr_example.ipynb

Initializes an EGraph, registers an expression, runs saturation, and extracts the expression's value.

```python
# egraph = EGraph()
# # x = given(given(10, 100), 1000)
# egraph.register(x)
# egraph.run(given_ruleset.saturate())
# # egraph.display()
# print(str(egraph.extract(x)))  # $, cost_model=greedy_dag_cost_model())))

# a
```

--------------------------------

### Define Functions with Merge Semantics

Source: https://context7.com/egraphs-good/egglog-python/llms.txt

Define functions that compute values with merge semantics for handling multiple mappings. This example uses a `shortest_path` function that keeps the minimum value on conflict.

```python
from egglog import *
from collections.abc import Iterable

# Function without merge - expects unique mappings
@function
def edge_len(from_: i64Like, to: i64Like) -> i64: ...

# Function with merge - keeps minimum value on conflict
@function(merge=lambda old, new: old.min(new))
def shortest_path(from_: i64Like, to: i64Like) -> i64: ...

egraph = EGraph()

# Set function values
egraph.register(
    set_(edge_len(1, 2)).to(i64(10)),
    set_(edge_len(2, 3)).to(i64(5)),
    set_(edge_len(1, 3)).to(i64(20)),
)

# Define path computation rules
@egraph.register
def _(a: i64, b: i64, c: i64, ab: i64, bc: i64) -> Iterable[RewriteOrRule]:
    yield rule(edge_len(a, b) == ab).then(set_(shortest_path(a, b)).to(ab))
    yield rule(
        shortest_path(a, b) == ab,
        edge_len(b, c) == bc
    ).then(set_(shortest_path(a, c)).to(ab + bc))

egraph.run(run().saturate())
egraph.check(eq(shortest_path(1, 3)).to(15))  # Shortest: 1->2->3 = 10+5
```

--------------------------------

### Get Callable Arguments in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/python-integration.md

Use `get_callable_args(expr)` to retrieve the arguments of a callable expression. Optionally, provide a specific function `fn` to match against, returning `None` if the callable does not match.

```python
assert get_callable_args(expr) == (i64(1), i64(2))
```

```python
assert get_callable_args(expr, i64.__add__) == (i64(1), i64(2))
assert get_callable_args(expr, i64.__sub__) == None
```

--------------------------------

### Demonstrate Demand Rules with Matrix Multiplication

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/tutorials/getting-started.ipynb

Illustrates the effect of demand rules by adding a matrix multiplication to the e-graph and displaying its state before and after running one iteration.

```python
with egraph:
    egraph.register(Matrix.named("X") @ Matrix.named("Y"))
    egraph.display()
    egraph.run(1)
    egraph.display()

```

--------------------------------

### Registering a let-bound variable in EGraph

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_07_presentation.ipynb

This example shows how to use `egraph.let` to bind a variable, `f4`, to the result of calling the `fib` function with the argument `4`. This is useful for defining and referencing computed values within the EGraph.

```python
f4 = egraph.let("f4", fib(4))
egraph
```

--------------------------------

### Import egglog and utilities

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_11_17_pytensor.ipynb

Imports necessary components from the egglog library and functools.

```python
from __future__ import annotations

from functools import partial

from egglog import *

```

--------------------------------

### JIT Compile Application with Third-Party Library

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/pldi_2023_presentation.ipynb

Integrate a third-party library (e.g., for cross product) into an e-graph for lazy compilation without modifying the library itself. This enables seamless interoperability.

```python
egraph = EGraph([cross_mod, py_mod])
egraph.simplify(my_special_app(py_value("x")), 10)
```

```python
@egraph.register
def _(l: String, r: String):
    yield rewrite(cross(py_ndarray(l), py_ndarray(r))).to(py_ndarray(join("np.multiply.outer(", l, ", ", r, ")")))
```

```python
egraph.run(20)
egraph.graphviz().render(outfile="big_graph.svg", format="svg")
```

--------------------------------

### Define Helper Function to Get i64 from Num

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2026_02_containers.md

Defines a helper function `get_i64` that returns an `i64` if the input `Num` is a constant. This is used in conjunction with the `set_get_i64` ruleset to establish a mapping from `Num(i)` to its `i64` value.

```python
@function
def get_i64(x: Num) -> i64: ...


@ruleset
def set_get_i64(i: i64):
    yield rule(Num(i)).then(set_(get_i64(Num(i))).to(i))
```

--------------------------------

### Run EGraph and Render Graphviz

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_07_presentation.ipynb

Executes the EGraph's simplification rules and renders the resulting graph using Graphviz. This is useful for analyzing the optimization process.

```python
egraph.run(20)
egraph.graphviz().render(outfile="big_graph.svg", format="svg")
```

--------------------------------

### Initialize EGraph and Run Sequential Schedules

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Initializes an EGraph and registers initial facts. Runs a schedule composed of saturating 'step_right' and 'step_left' rulesets, repeated 10 times.

```python
step_egraph = EGraph()
step_egraph.register(left(i64(0)), right(i64(0)))
step_egraph.run(
    seq(
        step_right.saturate(),
        step_left.saturate(),
    ) * 10
)
```

--------------------------------

### Define Pathfinding Rules in Egglog

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_07_presentation.ipynb

This Egglog code defines `path` and `edge` relations and rules for transitive pathfinding, then includes the file and runs the rules.

```egglog
%%writefile path.egg
(relation path (i64 i64))
(relation edge (i64 i64))

(rule ((edge x y)) 
      ((path x y)))

(rule ((path x y) (edge y z)) 
      ((path x z)))
```

```egglog
%%egglog
(include "path.egg")
(edge 1 2)
(edge 2 3)
(edge 3 4)
(run 3)
(check (path 1 3))
```

--------------------------------

### Get Function Values

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/reference/egglog-translation.md

Retrieve the values of a specific function using `egraph.function_values(fn, length=?)`. The function must return a primitive or be created with a merge function. An optional `length` parameter can limit the number of values returned.

```python
egraph.function_values(fib, length=3)
```

--------------------------------

### Convert Python bool to egglog Bool

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2023_07_presentation.ipynb

Use the `converter` function to map Python types to egglog types. This example shows the conversion of a Python boolean to an egglog `Bool` type, using a lambda function for the conversion logic.

```python
converter(bool, Bool, lambda x: TRUE if x else FALSE)

TRUE | False
```

--------------------------------

### Basic List Manipulation and Assertions

Source: https://github.com/egraphs-good/egglog-python/blob/main/python/egglog/exp/any_expr_example.ipynb

Demonstrates fundamental list operations and assertions in a Python-like syntax, likely for testing or intermediate steps within Egglog.

```python
_0 = list((*(), 42))
del _0[0]
assert (list((*(), 42)) != 10)
assert (not (_0 == 1))
-_0
```

--------------------------------

### Extract Optimal Expressions with Custom Cost Models

Source: https://context7.com/egraphs-good/egglog-python/llms.txt

Extract optimal expressions from the egraph using built-in or custom cost models. This example demonstrates extraction with default costs and a custom cost model prioritizing small constants.

```python
from egglog import *
from collections.abc import Iterable

class Num(Expr):
    def __init__(self, value: i64Like) -> None: ...
    @classmethod
    def var(cls, name: StringLike) -> Num: ...

    @method(cost=2)   # Addition costs 2
    def __add__(self, other: Num) -> Num: ...

    @method(cost=10)  # Multiplication costs 10
    def __mul__(self, other: Num) -> Num: ...

converter(i64, Num, Num)

egraph = EGraph()
expr = egraph.let("expr", Num.var("x") * 2)

# Extract with cost
result, cost = egraph.extract(expr, include_cost=True)
print(f"Before: {result}, cost={cost}")  # Cost includes multiplication

# Add rewrite to avoid multiplication
@egraph.register
def _(x: Num):
    yield rewrite(x * 2).to(x + x)

egraph.run(1)
result, cost = egraph.extract(expr, include_cost=True)
print(f"After: {result}, cost={cost}")  # Lower cost with addition

# Custom cost model
def prefer_small_constants(egraph: EGraph, expr: Expr, children_costs: list[int]) -> int:
    from egglog import i64
    match expr:
        case i64(i):
            return abs(i)  # Prefer small constants
    return 1 + sum(children_costs)

small_expr = EGraph().extract(i64(100), cost_model=prefer_small_constants, include_cost=True)
```

--------------------------------

### EGraph Initialization and Saturation

Source: https://github.com/egraphs-good/egglog-python/blob/main/docs/explanation/2026_02_containers.md

Initializes an EGraph, defines variables, and sets an expression. It then saturates the e-graph using specified rules (associativity, commutativity, distributivity, and folding) and extracts the optimized expression.

```python
egraph = EGraph()
a, b = Num.var("a"), Num.var("b")
new_expr = egraph.let("new_expr", Num(2) + a + b + b + Num(3))

# run both the associativity and commutativity/distributivity
# rules together
egraph.saturate(assoc | comm_dist_fold)
egraph.extract(new_expr)
```