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::{GrammarOracle, SampleConfig, sample};
12use crate::grammar::Grammar;
13use transform::{Candidate, CandidateKind, apply_candidate, enumerate_candidates};
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.as_ref().is_none_or(|best| scored.is_better_than(best)) {
149                best = Some(scored);
150            }
151        }
152
153        let Some(best) = best else {
154            break;
155        };
156
157        record_acceptance(&mut report, best.candidate.kind());
158        current = best.grammar;
159        current_cost = best.cost;
160    }
161
162    MinimizeResult {
163        grammar: current,
164        before,
165        after: current_cost,
166        report,
167    }
168}
169
170#[derive(Clone, Debug, PartialEq)]
171struct ScoredCandidate {
172    order: usize,
173    candidate: Candidate,
174    grammar: Grammar,
175    cost: Mdl,
176    delta: f64,
177}
178
179impl ScoredCandidate {
180    fn is_better_than(&self, other: &Self) -> bool {
181        self.delta < other.delta - COST_EPSILON
182            || ((self.delta - other.delta).abs() <= COST_EPSILON && self.order < other.order)
183    }
184}
185
186const fn record_acceptance(report: &mut MinimizeReport, kind: CandidateKind) {
187    match kind {
188        CandidateKind::Merge => {
189            report.merges_applied = report.merges_applied.saturating_add(1);
190        }
191        CandidateKind::Inline => {
192            report.inlines_applied = report.inlines_applied.saturating_add(1);
193        }
194        CandidateKind::Factor => {
195            report.factorings_applied = report.factorings_applied.saturating_add(1);
196        }
197        CandidateKind::Prune => {
198            report.prunes_applied = report.prunes_applied.saturating_add(1);
199        }
200    }
201}
202
203fn passes_gate(
204    baseline: &Grammar,
205    trial: &Grammar,
206    examples: &[String],
207    opts: MinimizeOptions,
208) -> bool {
209    let trial_oracle = GrammarOracle::new(trial);
210    if !examples.iter().all(|example| trial_oracle.accepts(example)) {
211        return false;
212    }
213
214    if opts.sample_budget == 0 {
215        return true;
216    }
217
218    let config = SampleConfig {
219        count: opts.sample_budget.max(1),
220        max_depth: opts.max_iterations.max(1),
221        ..SampleConfig::default()
222    };
223    let Ok(samples) = sample(trial, &config) else {
224        return false;
225    };
226    if samples.is_empty() {
227        return false;
228    }
229
230    let baseline_oracle = GrammarOracle::new(baseline);
231    let accepted = samples
232        .iter()
233        .filter(|sample| baseline_oracle.accepts(sample))
234        .count();
235    let precision = ratio(accepted, samples.len());
236    let budget = if opts.precision_budget.is_finite() {
237        opts.precision_budget.max(0.0)
238    } else {
239        DEFAULT_PRECISION_BUDGET
240    };
241
242    precision + budget + COST_EPSILON >= 1.0
243}
244
245fn ratio(numerator: usize, denominator: usize) -> f64 {
246    debug_assert!(denominator > 0);
247    usize_to_f64(numerator) / usize_to_f64(denominator)
248}
249
250#[allow(clippy::cast_precision_loss)]
251const fn usize_to_f64(value: usize) -> f64 {
252    value as f64
253}
meta_language/grammar/inference/minimize.rs

meta_language/grammar/inference/
minimize.rs
