simple_semantics/
utils.rs

1use serde::{Deserialize, Serialize};
2use thiserror::Error;
3
4use crate::lambda::{
5    LambdaExpr, LambdaExprRef, LambdaLanguageOfThought, LambdaPool, RootedLambdaPool,
6};
7
8#[derive(Debug, Copy, Clone, Eq, PartialEq)]
9pub(crate) enum ArgumentIterator<A, B, C, D> {
10    A(A),
11    B(B),
12    C(C),
13    D(D),
14}
15
16impl<A, B, C, D, Item> Iterator for ArgumentIterator<A, B, C, D>
17where
18    A: Iterator<Item = Item>,
19    B: Iterator<Item = Item>,
20    C: Iterator<Item = Item>,
21    D: Iterator<Item = Item>,
22{
23    type Item = Item;
24
25    fn next(&mut self) -> Option<Self::Item> {
26        match self {
27            ArgumentIterator::A(a) => a.next(),
28            ArgumentIterator::B(b) => b.next(),
29            ArgumentIterator::C(c) => c.next(),
30            ArgumentIterator::D(d) => d.next(),
31        }
32    }
33}
34
35///A representation of an expression in a [`RootedLambdaPool`]. This is used for fancy
36///datastructures that involve breaking down a [`RootedLambdaPool`] such as
37///[tries](https://en.wikipedia.org/wiki/Trie).
38///
39///The internal content of the expression is hidden and can be reconstructed by passing it as an iterator
40///to [`RootedLambdaPool::from_beads`].
41///
42///It includes all the data necessary to reconstruct a [`RootedLambdaPool`] by putting each token as
43///a bead, along with a record of which index is the root (referred to in docs as a root bead).
44#[derive(Debug, Clone, Eq, PartialEq, Hash, PartialOrd, Ord)]
45pub struct ExpressionBead<'a, T: LambdaLanguageOfThought>(ExpressionBeadInner<'a, T>);
46
47#[derive(Debug, Clone, Eq, PartialEq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
48enum ExpressionBeadInner<'a, T: LambdaLanguageOfThought> {
49    Expr(#[serde(borrow)] LambdaExpr<'a, T>),
50    Root(LambdaExprRef),
51}
52
53///An error that arises when constructing a [`RootedLambdaPool`] from beads.
54#[derive(Error, Debug)]
55pub enum BeadError {
56    ///The iterator is missing a root.
57    #[error("This bead iterator is missing its root!")]
58    MissingRoot,
59    ///The iterator has multiple roots.
60    #[error("This bead iterator has multiple roots!")]
61    MultipleRoots,
62    ///The resulting expression is malformed.
63    #[error("This bead iterator creates a malformed RootedLambdaPool")]
64    MalformedPool,
65}
66
67impl<'a, T: LambdaLanguageOfThought> RootedLambdaPool<'a, T> {
68    ///Converts a [`RootedLambdaPool`] into beads for use in fancy data structures.
69    pub fn into_beads(self) -> impl Iterator<Item = ExpressionBead<'a, T>> {
70        std::iter::once(ExpressionBead(ExpressionBeadInner::Root(self.root))).chain(
71            self.pool
72                .0
73                .into_iter()
74                .map(|x| ExpressionBead(ExpressionBeadInner::Expr(x))),
75        )
76    }
77
78    ///Reconstruct a [`RootedLambdaPool`] from an iterator of beads.
79    ///
80    ///# Errors
81    ///
82    ///Returrns [`BeadError`] if the
83    pub fn from_beads(
84        iter: impl IntoIterator<Item = ExpressionBead<'a, T>>,
85    ) -> Result<RootedLambdaPool<'a, T>, BeadError> {
86        let mut root = None;
87        let pool = LambdaPool(
88            iter.into_iter()
89                .filter_map(|x| match x.0 {
90                    ExpressionBeadInner::Expr(lambda_expr) => Some(Ok(lambda_expr)),
91                    ExpressionBeadInner::Root(_) if root.is_some() => {
92                        Some(Err(BeadError::MultipleRoots))
93                    }
94                    ExpressionBeadInner::Root(x) => {
95                        root = Some(x);
96                        None
97                    }
98                })
99                .collect::<Result<Vec<_>, _>>()?,
100        );
101        let root = root.ok_or(BeadError::MissingRoot)?;
102        if root.0 as usize >= pool.0.len() {
103            return Err(BeadError::MalformedPool);
104        }
105        pool.get_type(root).map_err(|_| BeadError::MalformedPool)?;
106        Ok(RootedLambdaPool { pool, root })
107    }
108
109    ///Reconstruct a [`RootedLambdaPool`] from a **reversed** iterator of beads.
110    ///
111    ///# Errors
112    ///
113    ///Returrns [`BeadError`] if the
114    pub fn from_beads_rev(
115        iter: impl IntoIterator<Item = ExpressionBead<'a, T>>,
116    ) -> Result<RootedLambdaPool<'a, T>, BeadError> {
117        let mut root = None;
118        let mut pool = LambdaPool(
119            iter.into_iter()
120                .filter_map(|x| match x.0 {
121                    ExpressionBeadInner::Expr(lambda_expr) => Some(Ok(lambda_expr)),
122                    ExpressionBeadInner::Root(_) if root.is_some() => {
123                        Some(Err(BeadError::MultipleRoots))
124                    }
125                    ExpressionBeadInner::Root(x) => {
126                        root = Some(x);
127                        None
128                    }
129                })
130                .collect::<Result<Vec<_>, _>>()?,
131        );
132        pool.0.reverse();
133        let root = root.ok_or(BeadError::MissingRoot)?;
134        if root.0 as usize >= pool.0.len() {
135            return Err(BeadError::MalformedPool);
136        }
137        pool.get_type(root).map_err(|_| BeadError::MalformedPool)?;
138        Ok(RootedLambdaPool { pool, root })
139    }
140
141    ///Reconstruct a [`RootedLambdaPool`] from an iterator of beads.
142    ///
143    ///# Panics
144    ///Will panic if there is no root bead or multiple root beads.
145    ///
146    ///# Safety
147    ///This version of the function does not check if the corresponding expression is wellformed.
148    ///If the beads are not presented in the correct order, the resulting code may panic or loop
149    ///indefinitely elsewhere.
150    pub unsafe fn from_beads_unchecked(
151        iter: impl IntoIterator<Item = ExpressionBead<'a, T>>,
152    ) -> RootedLambdaPool<'a, T> {
153        let mut root = None;
154        let pool = LambdaPool(
155            iter.into_iter()
156                .filter_map(|x| match x.0 {
157                    ExpressionBeadInner::Expr(lambda_expr) => Some(lambda_expr),
158                    ExpressionBeadInner::Root(_) if root.is_some() => {
159                        panic!("RootedLambdaPool can only have one root but the beads have multiple roots!");
160                    }
161                    ExpressionBeadInner::Root(x) => {
162                        root = Some(x);
163                        None
164                    }
165                })
166                .collect::<Vec<_>>(),
167        );
168        let root = root.unwrap();
169        RootedLambdaPool { pool, root }
170    }
171
172    ///Reconstruct a [`RootedLambdaPool`] from a **reversed** iterator of beads.
173    ///
174    ///# Panics
175    ///Will panic if there is no root bead or multiple root beads.
176    ///
177    ///# Safety
178    ///This version of the function does not check if the corresponding expression is wellformed.
179    ///If the beads are not presented in the correct order, the resulting code may panic or loop
180    ///indefinitely elsewhere.
181    pub unsafe fn from_beads_rev_unchecked(
182        iter: impl IntoIterator<Item = ExpressionBead<'a, T>>,
183    ) -> RootedLambdaPool<'a, T> {
184        let mut root = None;
185        let mut pool = LambdaPool(
186            iter.into_iter()
187                .filter_map(|x| match x.0 {
188                    ExpressionBeadInner::Expr(lambda_expr) => Some(lambda_expr),
189                    ExpressionBeadInner::Root(_) if root.is_some() => {
190                        panic!("RootedLambdaPool can only have one root but the beads have multiple roots!");
191                    }
192                    ExpressionBeadInner::Root(x) => {
193                        root = Some(x);
194                        None
195                    }
196                })
197                .collect::<Vec<_>>(),
198        );
199        pool.0.reverse();
200        let root = root.unwrap();
201        RootedLambdaPool { pool, root }
202    }
203}
204
205impl<'a, T: LambdaLanguageOfThought + Clone> RootedLambdaPool<'a, T> {
206    ///Converts a [`RootedLambdaPool`] into beads for use in fancy data structures without
207    ///ownership.
208    pub fn as_beads(&self) -> impl Iterator<Item = ExpressionBead<'a, T>> {
209        std::iter::once(ExpressionBead(ExpressionBeadInner::Root(self.root))).chain(
210            self.pool
211                .0
212                .iter()
213                .map(|x| ExpressionBead(ExpressionBeadInner::Expr(x.clone()))),
214        )
215    }
216}
217#[cfg(test)]
218mod test {
219    use super::{BeadError, ExpressionBeadInner};
220    use crate::{lambda::RootedLambdaPool, language::Expr};
221
222    const TEST_EXPR: [&str; 28] = [
223        "a_john",
224        "every(x, ~pa_a(x), every_e(y, pa_a(x), pe_e(y)))",
225        "iota_e(x, ~(pa_a(a_john) | PatientOf(a_john, x)))",
226        "iota_e(x, pe_e(x) | some_e(y, pa_a(a_john), pe_e(y)))",
227        "lambda <e,a> P some(x, pa_a(a_john), pa_a(a_john))",
228        "lambda a x lambda t phi ~(phi & ~~pa_a(a_john))",
229        "iota(x, pe_e(iota_e(y, pe_e(y) | ~pa_a(x))))",
230        "iota(x, pa_a(x))",
231        "iota(x, some_e(y, ~pe_e(y), PatientOf(x, y)))",
232        "iota_e(x, pa_a(a_john) | every_e(y, pe_e(y), AgentOf(a_john, x)))",
233        "iota_e(x, pa_a(a_john) | ~pe_e(x))",
234        "iota_e(x, ~pe_e(iota_e(y, pe_e(y) | pe_e(x))))",
235        "iota_e(x, every_e(y, pe_e(x), pe_e(y)))",
236        "iota(x, ~PatientOf(x, iota_e(y, pe_e(y))))",
237        "iota_e(x, some_e(y, ~pe_e(y), ~pe_e(x)))",
238        "lambda a x lambda a y ~pa_a(x) & ~pa_a(y)",
239        "lambda a x lambda a y ~every_e(z, pa_a(y), AgentOf(x, z))",
240        "lambda a x lambda a y AgentOf(x, iota_e(z, PatientOf(y, z)))",
241        "lambda a x lambda a y ~some(z, all_a, ~pa_a(a_john))",
242        "lambda a x lambda a y pa_a(iota(z, pa_a(y)))",
243        "lambda a x lambda a y ~(pa_a(y) & pa_a(x))",
244        "lambda a x lambda a y some(z, all_a, pa_a(y))",
245        "lambda a x lambda a y AgentOf(a_john, iota_e(z, pa_a(a_john)))",
246        "lambda a x lambda a y ~~(pa_a(x) | pa_a(y))",
247        "lambda a x lambda a y ~pa_a(y) | pa_a(x) | pa_a(y)",
248        "lambda a x lambda a y some(z, ~~pa_a(z), pa_a(a_john))",
249        "lambda a x lambda a y every_e(z, pa_a(x), AgentOf(y, z))",
250        "lambda a x lambda a y AgentOf(x, iota_e(z, ~AgentOf(y, z)))",
251    ];
252
253    #[test]
254    fn bead_round_trip_into() -> Result<(), anyhow::Error> {
255        for expr_str in TEST_EXPR {
256            let original = RootedLambdaPool::parse(expr_str)?;
257            let clone = original.clone();
258            assert_eq!(clone, RootedLambdaPool::from_beads(original.into_beads())?);
259        }
260        Ok(())
261    }
262
263    #[test]
264    fn bead_round_trip_as_beads() -> Result<(), anyhow::Error> {
265        for expr_str in TEST_EXPR {
266            let original = RootedLambdaPool::parse(expr_str)?;
267            assert_eq!(original, RootedLambdaPool::from_beads(original.as_beads())?);
268        }
269        Ok(())
270    }
271
272    #[test]
273    fn bead_round_trip_unchecked() -> Result<(), anyhow::Error> {
274        for expr_str in TEST_EXPR {
275            let original = RootedLambdaPool::parse(expr_str)?;
276            let safe = RootedLambdaPool::from_beads(original.as_beads())?;
277            let unchecked = unsafe { RootedLambdaPool::from_beads_unchecked(original.as_beads()) };
278            assert_eq!(safe, unchecked);
279        }
280        Ok(())
281    }
282
283    #[test]
284    fn bead_missing_root_error() -> Result<(), anyhow::Error> {
285        for expr_str in TEST_EXPR {
286            let original = RootedLambdaPool::parse(expr_str)?;
287            let beads: Vec<_> = original
288                .into_beads()
289                .filter(|b| matches!(b.0, ExpressionBeadInner::Expr(_)))
290                .collect();
291            assert!(matches!(
292                RootedLambdaPool::from_beads(beads),
293                Err(BeadError::MissingRoot)
294            ));
295        }
296        Ok(())
297    }
298
299    #[test]
300    fn bead_multiple_roots_error() -> Result<(), anyhow::Error> {
301        for expr_str in TEST_EXPR {
302            let original = RootedLambdaPool::parse(expr_str)?;
303            let mut beads: Vec<_> = original.into_beads().collect();
304            let root_clone = beads
305                .iter()
306                .find(|b| matches!(b.0, ExpressionBeadInner::Root(_)))
307                .unwrap()
308                .clone();
309            beads.push(root_clone);
310            assert!(matches!(
311                RootedLambdaPool::from_beads(beads),
312                Err(BeadError::MultipleRoots)
313            ));
314        }
315        Ok(())
316    }
317
318    #[test]
319    fn bead_malformed_pool_error() -> Result<(), anyhow::Error> {
320        for expr_str in TEST_EXPR {
321            let original = RootedLambdaPool::parse(expr_str)?;
322            let mut beads: Vec<_> = original.into_beads().collect();
323            beads.retain(|b| matches!(b.0, ExpressionBeadInner::Root(_)));
324            let result = RootedLambdaPool::from_beads(beads);
325            if result.is_ok() {
326                continue;
327            }
328            assert!(matches!(result, Err(BeadError::MalformedPool)));
329        }
330        Ok(())
331    }
332
333    #[test]
334    fn bead_missing_root_empty_iterator() {
335        assert!(matches!(
336            RootedLambdaPool::<'static, Expr<'static>>::from_beads(std::iter::empty()),
337            Err(BeadError::MissingRoot)
338        ));
339    }
340
341    #[test]
342    fn bead_root_position_invariance() -> Result<(), anyhow::Error> {
343        for expr_str in TEST_EXPR {
344            let original = RootedLambdaPool::parse(expr_str)?;
345            let (root_beads, expr_beads): (Vec<_>, Vec<_>) = original
346                .as_beads()
347                .partition(|b| matches!(b.0, ExpressionBeadInner::Root(_)));
348            let root_bead = root_beads.into_iter().next().unwrap();
349
350            let mut end_order = expr_beads.clone();
351            end_order.push(root_bead.clone());
352
353            let mid = expr_beads.len() / 2;
354            let mut mid_order = expr_beads.clone();
355            mid_order.insert(mid, root_bead.clone());
356
357            let mut start_order = expr_beads;
358            start_order.insert(0, root_bead);
359
360            let from_start = RootedLambdaPool::from_beads(start_order)?;
361            assert_eq!(from_start, RootedLambdaPool::from_beads(mid_order)?);
362            assert_eq!(from_start, RootedLambdaPool::from_beads(end_order)?);
363        }
364        Ok(())
365    }
366
367    #[test]
368    #[should_panic(expected = "RootedLambdaPool can only have one root")]
369    fn bead_unchecked_panics_on_multiple_roots() {
370        let original = RootedLambdaPool::parse(TEST_EXPR[0]).unwrap();
371        let mut beads: Vec<_> = original.into_beads().collect();
372        let root_clone = beads
373            .iter()
374            .find(|b| matches!(b.0, ExpressionBeadInner::Root(_)))
375            .unwrap()
376            .clone();
377        beads.push(root_clone);
378        unsafe { RootedLambdaPool::from_beads_unchecked(beads) };
379    }
380}
simple_semantics/utils.rs

simple_semantics/
utils.rs
