rusty_alto/algebras/
mod.rs

1//! Algebra interfaces and decomposition automata.
2
3mod feature;
4mod string;
5mod string_astar;
6mod tag_string;
7mod tag_tree;
8mod tree;
9
10use crate::{BottomUpTa, DetBottomUpTa, Signature, Symbol, VisualRepresentation};
11use packed_term_arena::tree::{Tree, TreeArena};
12use std::hash::Hash;
13
14pub use string::{
15    SentenceSxHeuristic, Span, StringAlgebra, StringDecompositionAutomaton, UniversalSxHeuristic,
16};
17pub(crate) use string::{SpanProductSibling, SpanProductSiblingFinder};
18pub(crate) use string_astar::{
19    SpanAstarLeftIndex, SpanBinarySiblingGroup, SpanInterner, StringAstarSource,
20    string_fallback_rules,
21};
22pub use tag_string::{
23    CONC11, CONC12, CONC21, TAG_E, TAG_EE, TagSpan, TagStringAlgebra,
24    TagStringDecompositionAutomaton, TagStringValue, WRAP21, WRAP22,
25};
26pub use tag_tree::{
27    BinarizedTagTreeDecompositionAutomaton, BinarizedTagTreeState, TAG_HOLE, TAG_SUBSTITUTE,
28    TagTreeAlgebra, TagTreeContext, TagTreeDecompositionAutomaton,
29};
30pub use tree::{APPEND_SYMBOL, Binarizing, TreeAlgebra, TreeValue};
31
32/// Algebra over a domain of values.
33///
34/// An algebra distinguishes two value types:
35/// - [`InternalValue`](Self::InternalValue): the efficient, ID/handle-based representation the
36///   algebra uses internally (for [`evaluate`](Self::evaluate) and decomposition);
37/// - [`Value`](Self::Value): the standalone *public* value produced by
38///   [`evaluate_term`](Self::evaluate_term) for output (e.g. `Vec<String>` rather than
39///   `Vec<Symbol>`), hiding the auxiliary interners from consumers.
40///
41/// The default decomposition automaton uses internal values as states and computes parent
42/// states by applying the algebra operation bottom-up.
43pub trait Algebra {
44    /// Efficient internal value domain used by [`evaluate`](Self::evaluate) and decomposition.
45    type InternalValue: Clone + Eq + Hash;
46
47    /// Standalone public value produced for output by [`evaluate_term`](Self::evaluate_term).
48    type Value;
49
50    /// Error returned when parsing a textual object representation.
51    type ParseError;
52
53    /// Return the operation signature used by this algebra.
54    fn signature(&self) -> &Signature;
55
56    /// Evaluate an operation over child internal values.
57    ///
58    /// Return `None` when the operation is undefined for the given children.
59    fn evaluate(
60        &self,
61        symbol: Symbol,
62        children: &[Self::InternalValue],
63    ) -> Option<Self::InternalValue>;
64
65    /// Parse a textual representation into an internal value.
66    fn parse_object(&mut self, input: &str) -> Result<Self::InternalValue, Self::ParseError>;
67
68    /// Map an internal value to its standalone public form.
69    fn to_external(&self, value: &Self::InternalValue) -> Self::Value;
70
71    /// Convert a public value into this algebra's preferred GUI-neutral representation.
72    fn visualize(&self, value: &Self::Value) -> VisualRepresentation;
73
74    /// Evaluate a term tree bottom-up to an internal value, applying [`evaluate`](Self::evaluate)
75    /// at every node (e.g. a homomorphic image produced from a derivation tree).
76    ///
77    /// Returns `None` if any node's operation is undefined for its children.
78    fn evaluate_term_internal(
79        &self,
80        arena: &TreeArena<Symbol>,
81        root: Tree,
82    ) -> Option<Self::InternalValue> {
83        let children: Vec<Self::InternalValue> = arena
84            .get_children(root)
85            .iter()
86            .map(|&child| self.evaluate_term_internal(arena, child))
87            .collect::<Option<_>>()?;
88        self.evaluate(*arena.get_label(root), &children)
89    }
90
91    /// Evaluate a term tree to its public value (bottom-up [`evaluate`](Self::evaluate), then
92    /// [`to_external`](Self::to_external)).
93    fn evaluate_term(&self, arena: &TreeArena<Symbol>, root: Tree) -> Option<Self::Value> {
94        Some(self.to_external(&self.evaluate_term_internal(arena, root)?))
95    }
96
97    /// Return whether `value` is a valid internal value.
98    fn is_valid_value(&self, _value: &Self::InternalValue) -> bool {
99        true
100    }
101
102    /// Build the default evaluating decomposition automaton for `value`.
103    fn decompose_default(
104        &self,
105        value: Self::InternalValue,
106    ) -> EvaluatingDecompositionAutomaton<'_, Self>
107    where
108        Self: Sized,
109    {
110        EvaluatingDecompositionAutomaton::new(self, value)
111    }
112}
113
114/// Default decomposition automaton for an [`Algebra`].
115pub struct EvaluatingDecompositionAutomaton<'a, A: Algebra> {
116    algebra: &'a A,
117    accepting: A::InternalValue,
118}
119
120impl<'a, A: Algebra> EvaluatingDecompositionAutomaton<'a, A> {
121    /// Create a decomposition automaton accepting terms that evaluate to
122    /// `accepting`.
123    pub fn new(algebra: &'a A, accepting: A::InternalValue) -> Self {
124        Self { algebra, accepting }
125    }
126}
127
128impl<A: Algebra> BottomUpTa for EvaluatingDecompositionAutomaton<'_, A> {
129    type State = A::InternalValue;
130
131    fn step(&self, f: Symbol, children: &[Self::State], out: &mut dyn FnMut(Self::State)) {
132        if self.algebra.signature().arity(f) != children.len() {
133            return;
134        }
135        let Some(value) = self.algebra.evaluate(f, children) else {
136            return;
137        };
138        if self.algebra.is_valid_value(&value) {
139            out(value);
140        }
141    }
142
143    fn is_accepting(&self, q: &Self::State) -> bool {
144        q == &self.accepting
145    }
146}
147
148impl<A: Algebra> DetBottomUpTa for EvaluatingDecompositionAutomaton<'_, A> {
149    fn step_det(&self, f: Symbol, children: &[Self::State]) -> Option<Self::State> {
150        if self.algebra.signature().arity(f) != children.len() {
151            return None;
152        }
153        let value = self.algebra.evaluate(f, children)?;
154        self.algebra.is_valid_value(&value).then_some(value)
155    }
156}
157
158pub use feature::{
159    FS_EMBED_PREFIX, FS_PROJECT_PREFIX, FS_REMAP_PREFIX, FS_UNIFY, FeatureStructure,
160    FeatureStructureAlgebra, FeatureStructureAttribute, FeatureStructureFilter,
161    FeatureStructureNode, FeatureStructureNodeId, FeatureStructureParseError,
162};
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167    use packed_term_arena::tree::TreeArena;
168
169    #[derive(Clone)]
170    struct Tiny {
171        signature: Signature,
172        zero: Symbol,
173        inc: Symbol,
174    }
175
176    impl Tiny {
177        fn new() -> Self {
178            let mut signature = Signature::new();
179            let zero = signature.intern("zero".to_owned(), 0).unwrap();
180            let inc = signature.intern("inc".to_owned(), 1).unwrap();
181            Self {
182                signature,
183                zero,
184                inc,
185            }
186        }
187    }
188
189    impl Algebra for Tiny {
190        type InternalValue = u8;
191        type Value = u8;
192        type ParseError = std::num::ParseIntError;
193
194        fn signature(&self) -> &Signature {
195            &self.signature
196        }
197
198        fn evaluate(
199            &self,
200            symbol: Symbol,
201            children: &[Self::InternalValue],
202        ) -> Option<Self::InternalValue> {
203            match (symbol, children) {
204                (s, []) if s == self.zero => Some(0),
205                (s, [x]) if s == self.inc => Some(x + 1),
206                _ => None,
207            }
208        }
209
210        fn parse_object(&mut self, input: &str) -> Result<Self::InternalValue, Self::ParseError> {
211            input.parse()
212        }
213
214        fn to_external(&self, value: &Self::InternalValue) -> Self::Value {
215            *value
216        }
217
218        fn visualize(&self, value: &Self::Value) -> VisualRepresentation {
219            VisualRepresentation::Text(value.to_string())
220        }
221    }
222
223    #[test]
224    fn default_decomposition_evaluates_bottom_up() {
225        let algebra = Tiny::new();
226        let decomp = algebra.decompose_default(2);
227
228        let zero = decomp.step_det(algebra.zero, &[]).unwrap();
229        let one = decomp.step_det(algebra.inc, &[zero]).unwrap();
230        let two = decomp.step_det(algebra.inc, &[one]).unwrap();
231
232        assert!(!decomp.is_accepting(&one));
233        assert!(decomp.is_accepting(&two));
234        assert_eq!(decomp.step_det(algebra.zero, &[two]), None);
235    }
236
237    #[test]
238    fn built_in_algebras_choose_structured_or_text_visualizations() {
239        let string = StringAlgebra::new();
240        assert!(matches!(
241            string.visualize(&vec!["hello".to_owned(), "world".to_owned()]),
242            VisualRepresentation::Text(text) if text == "hello world"
243        ));
244
245        let tree = TreeAlgebra::tree(Signature::new());
246        let mut arena = TreeArena::new();
247        let root = arena.add_node("root".to_owned(), Vec::new());
248        let value = TreeValue::new(arena, root);
249        assert!(matches!(
250            tree.visualize(&value),
251            VisualRepresentation::Tree(_)
252        ));
253
254        let feature = FeatureStructureAlgebra::with_signature(Signature::new());
255        let value = FeatureStructure::parse("[number: singular]").unwrap();
256        assert!(matches!(
257            feature.visualize(&value),
258            VisualRepresentation::FeatureStructure(_)
259        ));
260    }
261}
rusty_alto/algebras/mod.rs

rusty_alto/algebras/
mod.rs
