chomsky-extract

Optimal program extraction from E-Graphs for the Chomsky framework.

Overview

After chomsky-rule-engine has expanded the E-Graph with equivalent forms and chomsky-cost has assigned costs, chomsky-extract is responsible for selecting the "best" representative program. It finds the lowest-cost tree from the complex cyclic E-Graph structure.

Features

• Optimal Extraction: Uses a greedy but effective extraction algorithm to find the lowest-cost IKunTree for a given E-Class.
• Backend Trait: Defines the standard interface for all backends that consume extracted trees and produce artifacts (source, binary, or assembly).
• Artifact Management: Supports multiple output formats via BackendArtifact, including binary blobs, source strings, and collections of files.
• Recursive Reconstruction: Efficiently reconstructs the program tree while respecting the cost-based decisions.

Core Concepts

IKunExtractor

The main engine for extraction. It:

1. Calculates the best cost for every E-Class in the graph based on a CostModel.
2. Recursively selects the best nodes to form an IKunTree.

Backend

The interface for code generation. A backend provides:

• A name.
• A generate method to transform an IKunTree into a BackendArtifact.
• A target-specific CostModel.

Usage

use chomsky_extract::IKunExtractor;
use chomsky_cost::DefaultCostModel;
use chomsky_uir::EGraph;

let egraph = EGraph::new();
// ... fill egraph ...

let extractor = IKunExtractor::new(&egraph, DefaultCostModel);
let best_tree = extractor.extract(root_id);