simple_semantics/language/
enumerator.rs

1use std::{fmt::Debug, hash::Hash};
2
3use ahash::{HashMap, HashMapExt, HashSet};
4use itertools::{Either, repeat_n};
5use thiserror::Error;
6
7use crate::{
8    lambda::{
9        LambdaExpr, LambdaExprRef, LambdaLanguageOfThought, LambdaPool, RootedLambdaPool,
10        types::LambdaType,
11    },
12    language::{Expr, MonOp, PossibleExpressions},
13};
14
15#[derive(Debug, Clone, PartialEq, Eq, Hash)]
16enum FinishedOrType<'src, T: LambdaLanguageOfThought> {
17    Type(LambdaType),
18    PartiallyExpanded(ExprWrapper<'src, T>),
19    Expr(FinishedExpr<'src, T>),
20}
21
22impl<'src, T: LambdaLanguageOfThought + Clone + Hash + Eq + PartialEq + Debug + Ord>
23    FinishedOrType<'src, T>
24{
25    fn mark_finished(&mut self) {
26        let temp = std::mem::replace(self, FinishedOrType::Type(LambdaType::A));
27        let FinishedOrType::PartiallyExpanded(ExprWrapper { h, .. }) = temp else {
28            panic!()
29        };
30
31        let h: FinishedExpr<'src, T> = h.try_into().unwrap();
32        *self = FinishedOrType::Expr(h);
33    }
34}
35
36#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
37struct FinishedExpr<'src, T: LambdaLanguageOfThought> {
38    expr: LambdaExpr<'src, T>,
39    constant_function: bool,
40    children: Vec<FinishedExpr<'src, T>>,
41}
42
43#[derive(Debug, Clone, PartialEq, Eq, Hash)]
44struct HashedExpr<'src, T: LambdaLanguageOfThought> {
45    expr: LambdaExpr<'src, T>,
46    children: Vec<FinishedOrType<'src, T>>,
47}
48
49#[derive(Debug, Clone, PartialEq, Eq, Hash)]
50struct ExprWrapper<'src, T: LambdaLanguageOfThought> {
51    h: HashedExpr<'src, T>,
52    variables: Vec<LambdaType>,
53}
54
55#[derive(Debug, Clone, Eq, PartialEq)]
56struct Node<'src>(usize, ExprWrapper<'src, Expr<'src>>);
57
58impl PartialOrd for Node<'_> {
59    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
60        Some(self.cmp(other))
61    }
62}
63
64impl Ord for Node<'_> {
65    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
66        other.0.cmp(&self.0)
67    }
68}
69
70#[derive(Debug, Clone)]
71pub struct Enumerator<'a, 'src> {
72    max_length: usize,
73    simples: Vec<RootedLambdaPool<'src, Expr<'src>>>,
74    stack: Vec<Node<'src>>,
75    done: HashSet<FinishedExpr<'src, Expr<'src>>>,
76    possibles: &'a PossibleExpressions<'src, Expr<'src>>,
77}
78
79impl<'src> Iterator for Enumerator<'_, 'src> {
80    type Item = RootedLambdaPool<'src, Expr<'src>>;
81
82    fn next(&mut self) -> Option<Self::Item> {
83        if !self.simples.is_empty() {
84            return self.simples.pop();
85        }
86
87        while let Some(Node(n, x)) = self.stack.pop() {
88            if let Some(new) = x.expand(vec![], self.possibles, &mut self.stack, self.max_length, n)
89            {
90                let h = new.clone();
91                if self.done.insert(new) {
92                    return Some(h.into());
93                }
94            }
95        }
96        None
97    }
98}
99
100impl<'src> PossibleExpressions<'src, Expr<'src>> {
101    ///Enumerate over all possible expressions of type [`t`]
102    #[must_use]
103    #[allow(clippy::missing_panics_doc)]
104    pub fn enumerator<'a>(&'a self, t: &LambdaType, max_length: usize) -> Enumerator<'a, 'src> {
105        let mut stack: Vec<HashedExpr<_>> = self
106            .terms(
107                t,
108                true,
109                std::iter::empty(),
110                possible_applications(t, std::iter::empty()),
111            )
112            .into_iter()
113            .map(|x| {
114                let (e, a) = x.into_expr();
115                let mut h: HashedExpr<_> = e.into();
116                if let LambdaExpr::Lambda(_, _) = h.expr {
117                    h.children = vec![FinishedOrType::Type(t.rhs().unwrap().clone())];
118                } else if let LambdaExpr::Application { .. } = h.expr {
119                    let (arg, func) = a.unwrap();
120                    h.children = vec![FinishedOrType::Type(arg), FinishedOrType::Type(func)];
121                }
122                h
123            })
124            .collect();
125
126        let done: HashSet<FinishedExpr<_>> = stack
127            .extract_if(.., |x| x.is_done())
128            .map(|x| x.try_into().unwrap())
129            .collect();
130
131        let simples = done.iter().map(|x| (*x).clone().into()).collect::<Vec<_>>();
132
133        let stack = stack
134            .into_iter()
135            .map(|h| {
136                Node(
137                    1 + h.children.len(),
138                    ExprWrapper {
139                        variables: std::iter::once(h.expr.var_type().cloned())
140                            .flatten()
141                            .collect(),
142                        h,
143                    },
144                )
145            })
146            .collect();
147
148        Enumerator {
149            max_length,
150            simples,
151            stack,
152            possibles: self,
153            done,
154        }
155    }
156}
157
158fn get_this<'a, 'src, T: LambdaLanguageOfThought + Debug>(
159    x: &'a mut ExprWrapper<'src, T>,
160    path: &[usize],
161) -> &'a mut ExprWrapper<'src, T> {
162    let mut this = x;
163    for i in path.iter().copied() {
164        match &mut this.h.children[i] {
165            FinishedOrType::PartiallyExpanded(expr_wrapper) => {
166                this = expr_wrapper;
167            }
168            _ => panic!(),
169        }
170    }
171    this
172}
173
174fn possible_applications<'a>(
175    t: &'a LambdaType,
176    variables: impl Iterator<Item = &'a LambdaType>,
177) -> impl Iterator<Item = (LambdaType, LambdaType)> + 'a {
178    let mut possible_types: HashMap<LambdaType, HashSet<LambdaType>> = HashMap::new();
179    let mut new_types: HashSet<(&LambdaType, &LambdaType)> = HashSet::default();
180    let mut base_types: HashSet<_> = variables.collect();
181    base_types.insert(LambdaType::a());
182    base_types.insert(LambdaType::e());
183    base_types.insert(LambdaType::t());
184    base_types.insert(LambdaType::at());
185    base_types.insert(LambdaType::et());
186
187    loop {
188        for subformula in &base_types {
189            if let Ok((argument, result_type)) = subformula.split() {
190                let already_has_type = possible_types
191                    .get(result_type)
192                    .is_some_and(|x| x.contains(argument));
193
194                if base_types.contains(argument) && !already_has_type {
195                    new_types.insert((result_type, argument));
196                }
197            }
198        }
199        if new_types.is_empty() {
200            break;
201        }
202        for (result, argument) in &new_types {
203            possible_types
204                .entry((*result).clone())
205                .or_default()
206                .insert((*argument).clone());
207        }
208        base_types.extend(new_types.drain().map(|(result, _arg)| result));
209    }
210
211    match possible_types.remove(t) {
212        Some(x) => Either::Left(
213            x.into_iter()
214                .map(|x| (LambdaType::compose(x.clone(), t.clone()), x.clone())),
215        ),
216        None => Either::Right(std::iter::empty()),
217    }
218}
219
220impl<'src> ExprWrapper<'src, Expr<'src>> {
221    fn percolate_up(&mut self, path: &[usize]) {
222        if let Some((this_i, path)) = path.split_last() {
223            let parent_of_path = get_this(self, path);
224            if parent_of_path.h.children[*this_i].is_ready_to_be_marked_done() {
225                parent_of_path.h.children[*this_i].mark_finished();
226            }
227            if parent_of_path.h.is_done() {
228                self.percolate_up(path);
229            }
230        }
231    }
232
233    fn is_constant(&self) -> bool {
234        self.h
235            .children
236            .iter()
237            .filter_map(|x| match x {
238                FinishedOrType::Expr(e) => Some(e.constant_function),
239                FinishedOrType::PartiallyExpanded(e) => Some(e.is_constant()),
240                FinishedOrType::Type(_) => None,
241            })
242            .any(|x| x)
243    }
244
245    fn expand(
246        mut self,
247        mut path: Vec<usize>,
248        possibles: &PossibleExpressions<'src, Expr<'src>>,
249        stack: &mut Vec<Node<'src>>,
250        max_length: usize,
251        n: usize,
252    ) -> Option<FinishedExpr<'src, Expr<'src>>> {
253        let this = get_this(&mut self, &path);
254
255        //Initialize any types that haven't been started.
256        if let Some((i, typ)) = this
257            .h
258            .children
259            .iter()
260            .enumerate()
261            .find_map(|(i, x)| match x {
262                FinishedOrType::Type(lambda_type) => Some((i, lambda_type)),
263                _ => None,
264            })
265        {
266            let mut terms = possibles.terms(
267                typ,
268                //the function of a application shouldn't have lambdas, since otherwise we could just
269                //apply the argument there.
270                i != 0 || !matches!(this.h.expr, LambdaExpr::Application { .. }),
271                this.variables
272                    .iter()
273                    .rev()
274                    .enumerate()
275                    .filter(|(_, x)| x == &typ)
276                    .map(|(i, x)| LambdaExpr::BoundVariable(i, x.clone())),
277                possible_applications(typ, this.variables.iter()),
278            );
279
280            terms.retain(|x| {
281                (x.expr().n_children() + n
282                    - usize::from(matches!(x.expr(), LambdaExpr::Application { .. })))
283                    <= max_length
284                    && !(matches!(
285                        this.h.expr,
286                        LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(MonOp::Not, _))
287                    ) && matches!(
288                        x.expr(),
289                        LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(MonOp::Not, _))
290                    ))
291            });
292
293            let terms = terms
294                .into_iter()
295                .map(|x| {
296                    let (e, a) = x.into_expr();
297                    let mut h = HashedExpr::from(e);
298                    if let LambdaExpr::Lambda(_, _) = h.expr {
299                        h.children = vec![FinishedOrType::Type(typ.rhs().unwrap().clone())];
300                    } else if let LambdaExpr::Application { .. } = h.expr {
301                        let (arg, func) = a.unwrap();
302                        h.children = vec![FinishedOrType::Type(arg), FinishedOrType::Type(func)];
303                    }
304
305                    h
306                })
307                .collect::<Vec<_>>();
308
309            let this_variables = this.variables.clone();
310            for (mut parent, h) in repeat_n(self, terms.len()).zip(terms) {
311                if h.is_done() {
312                    let this = get_this(&mut parent, &path);
313                    this.h.children[i] = FinishedOrType::Expr(h.try_into().unwrap());
314                    if i == this.h.children.len() - 1 {
315                        parent.percolate_up(&path);
316                    }
317
318                    if !parent.is_constant() {
319                        stack.push(Node(n, parent));
320                    }
321                } else {
322                    let mut variables = this_variables.clone();
323                    if let Some(t) = h.expr.var_type() {
324                        variables.push(t.clone());
325                    }
326
327                    let this = get_this(&mut parent, &path);
328
329                    let n = n + h.children.len()
330                        - usize::from(matches!(h.expr, LambdaExpr::Application { .. }));
331                    let e = ExprWrapper { h, variables };
332                    this.h.children[i] = FinishedOrType::PartiallyExpanded(e);
333
334                    if !parent.is_constant() {
335                        stack.push(Node(n, parent));
336                    }
337                }
338            }
339        } else if let Some(i) = this
340            .h
341            .children
342            .iter()
343            .position(|x| matches!(x, FinishedOrType::PartiallyExpanded(_)))
344        {
345            path.push(i);
346            self.expand(path, possibles, stack, max_length, n);
347        } else if path.is_empty() {
348            let x: FinishedExpr<'src, Expr<'src>> = self.h.try_into().unwrap();
349            if !x.constant_function {
350                return Some(x);
351            }
352        } else {
353            panic!("this path should never occur");
354        }
355        None
356    }
357}
358
359impl<'src, T: LambdaLanguageOfThought + Clone> FinishedExpr<'src, T> {
360    fn has_variable(&self, typ: &LambdaType, depth: usize) -> bool {
361        if let LambdaExpr::BoundVariable(d, x) = &self.expr
362            && d == &depth
363            && x == typ
364        {
365            true
366        } else {
367            self.children
368                .iter()
369                .any(|x| x.has_variable(typ, depth + usize::from(self.expr.inc_depth())))
370        }
371    }
372
373    fn convert(pool: &RootedLambdaPool<'src, T>, i: LambdaExprRef) -> FinishedExpr<'src, T> {
374        let expr = pool.get(i).clone();
375        let children = expr
376            .get_children()
377            .map(|i| FinishedExpr::convert(pool, i))
378            .collect::<Vec<_>>();
379
380        let constant_function = if children.iter().any(|x| x.constant_function) {
381            true
382        } else if let Some(t) = expr.var_type() {
383            !children.iter().any(|x| x.has_variable(t, 0))
384        } else {
385            false
386        };
387
388        FinishedExpr {
389            expr,
390            constant_function,
391            children,
392        }
393    }
394}
395
396impl<T: LambdaLanguageOfThought + Clone> HashedExpr<'_, T> {
397    fn is_done(&self) -> bool {
398        self.children.iter().all(|x| match x {
399            FinishedOrType::Expr(_) => true,
400            FinishedOrType::PartiallyExpanded(_) | FinishedOrType::Type(_) => false,
401        })
402    }
403}
404
405impl<T: LambdaLanguageOfThought + Clone> FinishedOrType<'_, T> {
406    fn is_ready_to_be_marked_done(&self) -> bool {
407        match self {
408            FinishedOrType::PartiallyExpanded(e) => e.h.is_done(),
409            FinishedOrType::Expr(_) | FinishedOrType::Type(_) => false,
410        }
411    }
412}
413
414#[derive(Debug, Error)]
415#[error("This HashedExpr isn't done!")]
416struct FinishingError;
417
418impl<'src, T: LambdaLanguageOfThought + Clone + Debug + PartialOrd + Ord>
419    TryFrom<HashedExpr<'src, T>> for FinishedExpr<'src, T>
420{
421    type Error = FinishingError;
422    fn try_from(value: HashedExpr<'src, T>) -> Result<FinishedExpr<'src, T>, FinishingError> {
423        let mut children: Vec<_> = value
424            .children
425            .into_iter()
426            .map(|x| match x {
427                FinishedOrType::Expr(e) => Ok(e),
428                _ => Err(FinishingError),
429            })
430            .collect::<Result<_, _>>()?;
431
432        let constant_function = if children.iter().any(|x| x.constant_function) {
433            true
434        } else if let Some(t) = value.expr.var_type() {
435            !children.iter().any(|x| x.has_variable(t, 0))
436        } else {
437            false
438        };
439
440        if value.expr.commutative() {
441            children.sort();
442        }
443
444        Ok(FinishedExpr {
445            expr: value.expr,
446            constant_function,
447            children,
448        })
449    }
450}
451
452impl<'src, T: LambdaLanguageOfThought + Clone + Debug> From<LambdaExpr<'src, T>>
453    for HashedExpr<'src, T>
454{
455    fn from(value: LambdaExpr<'src, T>) -> Self {
456        let children = match &value {
457            LambdaExpr::LanguageOfThoughtExpr(e) => {
458                e.get_arguments().map(FinishedOrType::Type).collect()
459            }
460            LambdaExpr::BoundVariable(..) | LambdaExpr::FreeVariable(..) => vec![],
461            LambdaExpr::Lambda(_, t) => {
462                //not quite right but we need this here otherwise it will falsely get considered
463                //"done"
464                vec![FinishedOrType::Type(t.clone())]
465            }
466            LambdaExpr::Application { .. } => {
467                vec![
468                    FinishedOrType::Type(LambdaType::A),
469                    FinishedOrType::Type(LambdaType::T),
470                ]
471            }
472        };
473
474        HashedExpr {
475            children,
476            expr: value,
477        }
478    }
479}
480
481impl<'src, T: LambdaLanguageOfThought + Clone> From<RootedLambdaPool<'src, T>>
482    for FinishedExpr<'src, T>
483{
484    fn from(value: RootedLambdaPool<'src, T>) -> Self {
485        FinishedExpr::convert(&value, value.root)
486    }
487}
488
489impl<'src, T: LambdaLanguageOfThought + Clone> From<FinishedExpr<'src, T>>
490    for RootedLambdaPool<'src, T>
491{
492    fn from(value: FinishedExpr<'src, T>) -> Self {
493        let mut pool = vec![None];
494        let mut stack = vec![(value, LambdaExprRef(0))];
495        while let Some((x, i)) = stack.pop() {
496            for x in x.children.iter().cloned() {
497                stack.push((x, LambdaExprRef::new(pool.len())));
498                pool.push(None);
499            }
500            let mut e = x.expr.clone();
501            e.change_children(
502                (0..e.n_children())
503                    .rev()
504                    .map(|i| LambdaExprRef::new(pool.len() - i - 1)),
505            );
506            pool[i.0 as usize] = Some(e);
507        }
508
509        RootedLambdaPool {
510            pool: LambdaPool(pool.into_iter().collect::<Option<_>>().unwrap()),
511            root: LambdaExprRef(0),
512        }
513    }
514}
515
516#[cfg(test)]
517mod test {
518    use ahash::HashSetExt;
519
520    use super::*;
521
522    #[test]
523    fn convert_to_weak() -> anyhow::Result<()> {
524        let x = RootedLambdaPool::parse("lambda a x some_e(e, pe_run(e), AgentOf(x, e))")?;
525        let y: FinishedExpr<_> = x.clone().into();
526        let x2: RootedLambdaPool<_> = y.into();
527        println!("{x2:?}");
528        assert_eq!(x.to_string(), x2.to_string());
529
530        Ok(())
531    }
532
533    #[test]
534    fn new_enumerate() -> anyhow::Result<()> {
535        let actors = ["john"]; //, "mary", "phil", "sue"];
536        let actor_properties = ["a"];
537        let event_properties = ["e"];
538        let possibles = PossibleExpressions::new(&actors, &actor_properties, &event_properties);
539        let t = vec![
540            (LambdaType::A, 19),
541            (LambdaType::E, 22),
542            (LambdaType::T, 96),
543            (LambdaType::at().clone(), 18),
544            (LambdaType::et().clone(), 22),
545            (LambdaType::from_string("<<a,t>,t>").unwrap(), 37),
546        ];
547        for (t, how_many) in t {
548            println!("{t}");
549            let mut count = 0;
550            let mut pool_set = HashSet::new();
551            let mut reduced_pool_set = HashSet::new();
552
553            for mut x in possibles.enumerator(&t, 6) {
554                println!("{x}");
555                let o = x.get_type()?;
556                assert_eq!(o, t);
557                count += 1;
558                pool_set.insert(x.clone());
559                x.reduce()?;
560                x.cleanup();
561                reduced_pool_set.insert(x);
562            }
563            assert_eq!(count, how_many);
564            println!("{t} {count}");
565            assert_eq!(pool_set.len(), count);
566            assert_eq!(pool_set.len(), reduced_pool_set.len());
567        }
568        Ok(())
569    }
570}
simple_semantics/language/enumerator.rs

simple_semantics/language/
enumerator.rs
