simple_semantics/language/
enumerator.rs

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

simple_semantics/language/
enumerator.rs
