meta_language/grammar/inference/
minimize.rs

1//! MDL/Occam minimization for inferred grammars.
2//!
3//! The minimizer is deterministic and conservative. It greedily accepts
4//! transformations that reduce a two-part MDL score while preserving recall on
5//! the supplied positive examples and rejecting sampled strings that the input
6//! grammar did not accept beyond the configured precision budget.
7
8mod cost;
9mod transform;
10
11use super::eval::{sample, GrammarOracle, SampleConfig};
12use crate::grammar::Grammar;
13use transform::{apply_candidate, enumerate_candidates, Candidate, CandidateKind};
14
15const DEFAULT_PRECISION_BUDGET: f64 = 0.0;
16const DEFAULT_SAMPLE_BUDGET: usize = 256;
17const DEFAULT_MAX_ITERATIONS: usize = 64;
18const COST_EPSILON: f64 = 1e-9;
19
20/// Two-part Minimum Description Length cost in bits. Lower is better.
21#[derive(Clone, Copy, Debug, PartialEq)]
22pub struct Mdl {
23    /// `L(G)`: bits to encode the grammar itself.
24    pub grammar_bits: f64,
25    /// `L(D | G)`: bits to encode the examples given the grammar.
26    pub data_bits: f64,
27}
28
29impl Mdl {
30    /// Returns `grammar_bits + data_bits`.
31    #[must_use]
32    pub fn total(self) -> f64 {
33        self.grammar_bits + self.data_bits
34    }
35}
36
37/// Options for [`minimize`].
38#[derive(Clone, Copy, Debug, PartialEq)]
39pub struct MinimizeOptions {
40    /// Maximum sampled precision drop tolerated by the D1 gate.
41    pub precision_budget: f64,
42    /// Number of deterministic samples used by the precision gate.
43    pub sample_budget: usize,
44    /// Defensive cap for greedy minimization iterations and sampler depth.
45    pub max_iterations: usize,
46}
47
48impl Default for MinimizeOptions {
49    fn default() -> Self {
50        Self {
51            precision_budget: DEFAULT_PRECISION_BUDGET,
52            sample_budget: DEFAULT_SAMPLE_BUDGET,
53            max_iterations: DEFAULT_MAX_ITERATIONS,
54        }
55    }
56}
57
58/// Counts and rejection reasons recorded during minimization.
59#[derive(Clone, Debug, Default, PartialEq, Eq)]
60pub struct MinimizeReport {
61    /// Number of non-terminal merge candidates accepted.
62    pub merges_applied: usize,
63    /// Number of single-use inlining candidates accepted.
64    pub inlines_applied: usize,
65    /// Number of local choice factoring or deduplication candidates accepted.
66    pub factorings_applied: usize,
67    /// Number of unreachable-rule pruning candidates accepted.
68    pub prunes_applied: usize,
69    /// Number of candidates rejected because they did not strictly reduce MDL.
70    pub candidates_rejected_by_mdl: usize,
71    /// Number of cost-reducing candidates rejected by recall or precision gates.
72    pub candidates_rejected_by_gate: usize,
73}
74
75/// Minimized grammar and before/after accounting.
76#[derive(Clone, Debug, PartialEq)]
77pub struct MinimizeResult {
78    /// The minimized grammar.
79    pub grammar: Grammar,
80    /// MDL cost of the input grammar.
81    pub before: Mdl,
82    /// MDL cost of the minimized grammar.
83    pub after: Mdl,
84    /// Deterministic transform report.
85    pub report: MinimizeReport,
86}
87
88/// Computes deterministic two-part MDL for `grammar` on `examples`.
89///
90/// The total matches the D1 [`super::eval::mdl`] encoding: `L(G)` is the public
91/// grammar symbol count multiplied by a deterministic alphabet code width, and
92/// `L(D | G)` charges accepted examples by emitted Unicode scalars plus a stop
93/// bit while rejected examples use a UTF-8 escape penalty.
94#[must_use]
95pub fn mdl_cost(grammar: &Grammar, examples: &[String]) -> Mdl {
96    cost::mdl_cost(grammar, examples)
97}
98
99/// Generalises and minimises an inferred grammar under an MDL objective.
100///
101/// The search is greedy and deterministic: candidates are enumerated in rule
102/// order, scored by strict MDL decrease, gated by positive-example recall and a
103/// sampled precision proxy against the input grammar, then the best admissible
104/// candidate is applied until fixpoint or `opts.max_iterations`.
105#[must_use]
106pub fn minimize(grammar: &Grammar, examples: &[String], opts: MinimizeOptions) -> MinimizeResult {
107    let before = mdl_cost(grammar, examples);
108    let mut current = grammar.clone();
109    let mut current_cost = before;
110    let mut report = MinimizeReport::default();
111
112    for _ in 0..opts.max_iterations {
113        let candidates = enumerate_candidates(&current);
114        if candidates.is_empty() {
115            break;
116        }
117
118        let mut best: Option<ScoredCandidate> = None;
119        for (order, candidate) in candidates.into_iter().enumerate() {
120            let trial = apply_candidate(&current, candidate);
121            if trial == current {
122                report.candidates_rejected_by_mdl =
123                    report.candidates_rejected_by_mdl.saturating_add(1);
124                continue;
125            }
126
127            let trial_cost = mdl_cost(&trial, examples);
128            let delta = trial_cost.total() - current_cost.total();
129            if delta >= -COST_EPSILON {
130                report.candidates_rejected_by_mdl =
131                    report.candidates_rejected_by_mdl.saturating_add(1);
132                continue;
133            }
134
135            if !passes_gate(grammar, &trial, examples, opts) {
136                report.candidates_rejected_by_gate =
137                    report.candidates_rejected_by_gate.saturating_add(1);
138                continue;
139            }
140
141            let scored = ScoredCandidate {
142                order,
143                candidate,
144                grammar: trial,
145                cost: trial_cost,
146                delta,
147            };
148            if best
149                .as_ref()
150                .map_or(true, |best| scored.is_better_than(best))
151            {
152                best = Some(scored);
153            }
154        }
155
156        let Some(best) = best else {
157            break;
158        };
159
160        record_acceptance(&mut report, best.candidate.kind());
161        current = best.grammar;
162        current_cost = best.cost;
163    }
164
165    MinimizeResult {
166        grammar: current,
167        before,
168        after: current_cost,
169        report,
170    }
171}
172
173#[derive(Clone, Debug, PartialEq)]
174struct ScoredCandidate {
175    order: usize,
176    candidate: Candidate,
177    grammar: Grammar,
178    cost: Mdl,
179    delta: f64,
180}
181
182impl ScoredCandidate {
183    fn is_better_than(&self, other: &Self) -> bool {
184        self.delta < other.delta - COST_EPSILON
185            || ((self.delta - other.delta).abs() <= COST_EPSILON && self.order < other.order)
186    }
187}
188
189fn record_acceptance(report: &mut MinimizeReport, kind: CandidateKind) {
190    match kind {
191        CandidateKind::Merge => {
192            report.merges_applied = report.merges_applied.saturating_add(1);
193        }
194        CandidateKind::Inline => {
195            report.inlines_applied = report.inlines_applied.saturating_add(1);
196        }
197        CandidateKind::Factor => {
198            report.factorings_applied = report.factorings_applied.saturating_add(1);
199        }
200        CandidateKind::Prune => {
201            report.prunes_applied = report.prunes_applied.saturating_add(1);
202        }
203    }
204}
205
206fn passes_gate(
207    baseline: &Grammar,
208    trial: &Grammar,
209    examples: &[String],
210    opts: MinimizeOptions,
211) -> bool {
212    let trial_oracle = GrammarOracle::new(trial);
213    if !examples.iter().all(|example| trial_oracle.accepts(example)) {
214        return false;
215    }
216
217    if opts.sample_budget == 0 {
218        return true;
219    }
220
221    let config = SampleConfig {
222        count: opts.sample_budget.max(1),
223        max_depth: opts.max_iterations.max(1),
224        ..SampleConfig::default()
225    };
226    let Ok(samples) = sample(trial, &config) else {
227        return false;
228    };
229    if samples.is_empty() {
230        return false;
231    }
232
233    let baseline_oracle = GrammarOracle::new(baseline);
234    let accepted = samples
235        .iter()
236        .filter(|sample| baseline_oracle.accepts(sample))
237        .count();
238    let precision = ratio(accepted, samples.len());
239    let budget = if opts.precision_budget.is_finite() {
240        opts.precision_budget.max(0.0)
241    } else {
242        DEFAULT_PRECISION_BUDGET
243    };
244
245    precision + budget + COST_EPSILON >= 1.0
246}
247
248fn ratio(numerator: usize, denominator: usize) -> f64 {
249    debug_assert!(denominator > 0);
250    usize_to_f64(numerator) / usize_to_f64(denominator)
251}
252
253#[allow(clippy::cast_precision_loss)]
254const fn usize_to_f64(value: usize) -> f64 {
255    value as f64
256}
meta_language/grammar/inference/minimize.rs

meta_language/grammar/inference/
minimize.rs
