simple_semantics/language/
parser.rs

1use crate::{
2    Actor, Entity, Event,
3    lambda::{
4        Bvar, FreeVar, LambdaExpr, LambdaExprRef, LambdaPool, ReductionError, RootedLambdaPool,
5        types::{LambdaType, TypeError, core_type_parser},
6    },
7    language::{Constant, Expr, MonOp, lambda_implementation::LambdaConversionError},
8};
9use chumsky::{
10    extra::ParserExtra,
11    input::ValueInput,
12    label::LabelError,
13    pratt::{infix, left, prefix},
14    prelude::*,
15    text::{TextExpected, inline_whitespace},
16    util::MaybeRef,
17};
18use std::{
19    collections::{HashMap, VecDeque},
20    fmt::{Debug, Display},
21};
22
23use super::{ActorOrEvent, BinOp, LanguageExpression, Quantifier};
24use thiserror::Error;
25
26///Error in parsing a lambda expression
27#[derive(Debug, Error, Clone)]
28pub enum LambdaParseError {
29    ///Core error in parsing
30    #[error("ParseError({0})")]
31    ParseError(String),
32
33    ///A free variable was left untyped
34    #[error("You must provide a type for unbound free variable {0} like so \"{0}#<e,t>\"")]
35    UnTypedFreeVariable(String),
36
37    ///When the expression was reduced, it lead to an error.
38    #[error("Reduction Error: {0}")]
39    ReductionError(#[from] ReductionError),
40
41    ///There is a type error in  apply function types
42    #[error("{0}")]
43    TypeError(String),
44
45    ///Type error in lower part
46    #[error("Type error: {0}")]
47    InnerTypeError(#[from] TypeError),
48
49    ///The expression was still a lambda expression and not yet runnable.
50    #[error("{0}")]
51    ConversionError(#[from] LambdaConversionError),
52}
53
54impl<'a, T: Display> From<Vec<Rich<'a, T>>> for LambdaParseError {
55    fn from(value: Vec<Rich<'a, T>>) -> Self {
56        LambdaParseError::ParseError(
57            value
58                .into_iter()
59                .map(|x| x.to_string())
60                .collect::<Vec<_>>()
61                .join("\n"),
62        )
63    }
64}
65
66impl<'src> ParseTree<'src> {
67    #[allow(clippy::too_many_lines)]
68    fn add_to_pool(
69        &self,
70        pool: &mut LambdaPool<'src, Expr<'src>>,
71        variable_names: &mut VariableContext<'src>,
72        lambda_depth: usize,
73    ) -> Result<LambdaExprRef, LambdaParseError> {
74        let expr: LambdaExpr<'src, Expr<'src>> = match &self {
75            ParseTree::Constant(c) => LambdaExpr::LanguageOfThoughtExpr(Expr::Constant(*c)),
76            ParseTree::Entity(e) => LambdaExpr::LanguageOfThoughtExpr(match e {
77                Entity::Actor(a) => Expr::Actor(a),
78                Entity::Event(e) => Expr::Event(*e),
79            }),
80            ParseTree::Unary(m, x) => {
81                let x = x.add_to_pool(pool, variable_names, lambda_depth)?;
82                let x_type = pool.get_type(x)?;
83                if m.get_argument_type() != &x_type {
84                    return Err(LambdaParseError::TypeError(format!(
85                        "Can't apply {x_type} to {m} which takes type {}",
86                        m.get_argument_type(),
87                    )));
88                }
89                LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(*m, x.into()))
90            }
91            ParseTree::Binary(b, x, y) => {
92                let x = x.add_to_pool(pool, variable_names, lambda_depth)?;
93                let y = y.add_to_pool(pool, variable_names, lambda_depth)?;
94
95                let x_type = pool.get_type(x)?;
96                let y_type = pool.get_type(y)?;
97                let b_type = b.get_argument_type();
98                if b_type != [&x_type, &y_type] {
99                    return Err(LambdaParseError::TypeError(format!(
100                        "Can't apply [{x_type}, {y_type}] to {b} which takes type [{}, {}]",
101                        b_type[0], b_type[1]
102                    )));
103                }
104
105                LambdaExpr::LanguageOfThoughtExpr(Expr::Binary(*b, x.into(), y.into()))
106            }
107            ParseTree::Iota { t, var, body } => {
108                let lambda_type: LambdaType = (*t).into();
109                variable_names.bind_var(var, lambda_depth + 1, lambda_type);
110                let body = body.add_to_pool(pool, variable_names, lambda_depth + 1)?;
111                let body_type = pool.get_type(body)?;
112                if &body_type != LambdaType::t() {
113                    return Err(LambdaParseError::TypeError(format!(
114                        "Iota body is {t} and not of t",
115                    )));
116                }
117                variable_names.unbind(var);
118
119                LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(MonOp::Iota(*t), body.into()))
120            }
121            ParseTree::Quantifier {
122                quantifier,
123                lambda_type: var_type,
124                variable,
125                restrictor,
126                subformula,
127            } => {
128                let lambda_type: LambdaType = (*var_type).into();
129                variable_names.bind_var(variable, lambda_depth + 1, lambda_type);
130                let restrictor = restrictor.add_to_pool(pool, variable_names, lambda_depth + 1)?;
131
132                let r_type = pool.get_type(restrictor)?;
133                let required_type = match var_type {
134                    ActorOrEvent::Actor => LambdaType::at(),
135                    ActorOrEvent::Event => LambdaType::et(),
136                };
137                if &r_type != required_type && &r_type != LambdaType::t() {
138                    return Err(LambdaParseError::TypeError(format!(
139                        "Quantifier restrictor is {r_type} and not of type {required_type} or t",
140                    )));
141                }
142
143                let subformula = subformula.add_to_pool(pool, variable_names, lambda_depth + 1)?;
144                let sub_type = pool.get_type(subformula)?;
145                if &sub_type != LambdaType::t() {
146                    return Err(LambdaParseError::TypeError(format!(
147                        "Quantifier body is {sub_type} and not of t",
148                    )));
149                }
150                variable_names.unbind(variable);
151
152                LambdaExpr::LanguageOfThoughtExpr(Expr::Quantifier {
153                    quantifier: *quantifier,
154                    var_type: *var_type,
155                    restrictor: restrictor.into(),
156                    subformula: subformula.into(),
157                })
158            }
159            ParseTree::Application {
160                subformula,
161                argument,
162            } => {
163                let subformula = subformula.add_to_pool(pool, variable_names, lambda_depth)?;
164                let argument = argument.add_to_pool(pool, variable_names, lambda_depth)?;
165
166                let f = pool.get_type(subformula)?;
167                let arg = pool.get_type(argument)?;
168
169                if !f.can_apply(&arg) {
170                    return Err(LambdaParseError::TypeError(
171                        "Can't apply subformula to argument".to_string(),
172                    ));
173                }
174
175                LambdaExpr::Application {
176                    subformula,
177                    argument,
178                }
179            }
180            ParseTree::Lambda {
181                body,
182                var,
183                lambda_type,
184            } => {
185                variable_names.bind_var(var, lambda_depth + 1, lambda_type.clone());
186                let body = body.add_to_pool(pool, variable_names, lambda_depth + 1)?;
187                variable_names.unbind(var);
188                LambdaExpr::Lambda(body, lambda_type.clone())
189            }
190            ParseTree::Variable(var) => variable_names.to_expr(var, None, lambda_depth)?,
191            ParseTree::FreeVariable(var, lambda_type) => {
192                variable_names.to_expr(var, Some(lambda_type.clone()), lambda_depth)?
193            }
194        };
195        Ok(pool.add(expr))
196    }
197
198    fn to_pool(&self) -> Result<RootedLambdaPool<'src, Expr<'src>>, LambdaParseError> {
199        let mut pool = LambdaPool::new();
200
201        let mut var_labels = VariableContext::default();
202        let root = self.add_to_pool(&mut pool, &mut var_labels, 0)?;
203        Ok(RootedLambdaPool::new(pool, root))
204    }
205}
206
207#[derive(Debug, Clone, Eq, PartialEq, Default)]
208struct VariableContext<'src>(HashMap<&'src str, Vec<(Bvar, LambdaType)>>, u32);
209
210impl<'src> VariableContext<'src> {
211    fn to_expr(
212        &self,
213        variable: &'src str,
214        lambda_type: Option<LambdaType>,
215        lambda_depth: usize,
216    ) -> Result<LambdaExpr<'src, Expr<'src>>, LambdaParseError> {
217        Ok(match self.0.get(variable) {
218            Some(vars) if !vars.is_empty() => {
219                let (og_depth, lambda_type) = vars
220                    .last()
221                    .expect("There should never be an empty vec in the VariableContext");
222                LambdaExpr::BoundVariable(lambda_depth - og_depth, lambda_type.clone())
223            }
224            //Do free var
225            _ => match lambda_type {
226                Some(lambda_type) => {
227                    let free_var = variable
228                        .parse::<usize>()
229                        .map_or(FreeVar::Named(variable), FreeVar::Anonymous);
230
231                    LambdaExpr::FreeVariable(free_var, lambda_type)
232                }
233                None => {
234                    return Err(LambdaParseError::UnTypedFreeVariable(variable.to_string()));
235                }
236            },
237        })
238    }
239
240    fn bind_var(&mut self, variable: &'src str, lambda_depth: usize, lambda_type: LambdaType) {
241        self.0
242            .entry(variable)
243            .or_default()
244            .push((lambda_depth, lambda_type));
245    }
246
247    fn unbind(&mut self, variable: &'src str) {
248        self.0.get_mut(variable).unwrap().pop();
249    }
250}
251
252#[derive(Debug, Clone, Eq, PartialEq)]
253enum ParseTree<'src> {
254    Lambda {
255        body: Box<ParseTree<'src>>,
256        lambda_type: LambdaType,
257        var: &'src str,
258    },
259    Variable(&'src str),
260    FreeVariable(&'src str, LambdaType),
261    Application {
262        subformula: Box<ParseTree<'src>>,
263        argument: Box<ParseTree<'src>>,
264    },
265    Constant(Constant<'src>),
266    Unary(MonOp<'src>, Box<ParseTree<'src>>),
267    Iota {
268        t: ActorOrEvent,
269        var: &'src str,
270        body: Box<ParseTree<'src>>,
271    },
272    Binary(BinOp, Box<ParseTree<'src>>, Box<ParseTree<'src>>),
273    Quantifier {
274        quantifier: Quantifier,
275        lambda_type: ActorOrEvent,
276        variable: &'src str,
277        restrictor: Box<ParseTree<'src>>,
278        subformula: Box<ParseTree<'src>>,
279    },
280    Entity(Entity<'src>),
281}
282
283fn keyword<'src, E>() -> impl Parser<'src, &'src str, &'src str, E> + Copy
284where
285    E: ParserExtra<'src, &'src str>,
286{
287    one_of("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-")
288        .repeated()
289        .at_least(1)
290        .to_slice()
291}
292
293fn unary_op<'tokens, 'src: 'tokens, I>(
294    expr: impl Parser<'tokens, I, ParseTree<'src>, ChumskyErr<'tokens, 'src>> + Clone,
295) -> impl Parser<'tokens, I, ParseTree<'src>, ChumskyErr<'tokens, 'src>> + Clone
296where
297    I: ValueInput<'tokens, Token = Token<'src>, Span = SimpleSpan> + Clone,
298{
299    choice((
300        select! {Token::Property(s, a) => MonOp::Property(s, a) }
301            .then(
302                expr.clone()
303                    .delimited_by(just(Token::OpenDelim), just(Token::CloseDelim)),
304            )
305            .map(|(op, arg)| ParseTree::Unary(op, Box::new(arg))),
306        select! {Token::Iota(a) =>  a }
307            .then_ignore(just(Token::OpenDelim))
308            .then(select! {Token::Variable(v) => v})
309            .then_ignore(just(Token::ArgSep))
310            .then(expr.clone().map(Box::new))
311            .then_ignore(just(Token::CloseDelim))
312            .map(|((a_e, var), body)| ParseTree::Iota { t: a_e, var, body }),
313    ))
314}
315
316type ChumskyErr<'tokens, 'src> = extra::Err<Rich<'tokens, Token<'src>, Span>>;
317
318fn binary_operation<'tokens, 'src: 'tokens, I>(
319    a: impl Parser<'tokens, I, ParseTree<'src>, ChumskyErr<'tokens, 'src>> + Clone,
320    b: impl Parser<'tokens, I, ParseTree<'src>, ChumskyErr<'tokens, 'src>> + Clone,
321) -> impl Parser<'tokens, I, ParseTree<'src>, ChumskyErr<'tokens, 'src>> + Clone
322where
323    I: ValueInput<'tokens, Token = Token<'src>, Span = SimpleSpan> + Clone,
324{
325    select! { Token::BinOp(b) => b}
326        .labelled("binary operation")
327        .then_ignore(just(Token::OpenDelim))
328        .then(a)
329        .then_ignore(just(Token::ArgSep))
330        .then(b)
331        .then_ignore(just(Token::CloseDelim))
332        .map(|((binop, actor), event)| ParseTree::Binary(binop, Box::new(actor), Box::new(event)))
333}
334
335#[derive(Debug, Clone, Eq, PartialEq)]
336enum Token<'src> {
337    Bool(Constant<'src>),
338    And,
339    Or,
340    Not,
341    Actor(Actor<'src>),
342    Event(Event),
343    BinOp(BinOp),
344    OpenDelim,
345    ArgSep,
346    CloseDelim,
347    Constant(Constant<'src>),
348    Property(&'src str, ActorOrEvent),
349    Iota(ActorOrEvent),
350    Quantifier(Quantifier, ActorOrEvent),
351    Lambda(LambdaType, &'src str),
352    Variable(&'src str),
353    FreeVariable(&'src str, LambdaType),
354}
355impl Display for Token<'_> {
356    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
357        match self {
358            Token::Actor(a) => write!(f, "a_{a}"),
359            Token::Event(n) => write!(f, "e_{n}"),
360            Token::OpenDelim => write!(f, "("),
361            Token::ArgSep => write!(f, ","),
362            Token::CloseDelim => write!(f, ")"),
363            Token::And => write!(f, "&"),
364            Token::Or => write!(f, "|"),
365            Token::Not => write!(f, "~"),
366            Token::BinOp(bin_op) => write!(f, "{bin_op}"),
367            Token::Bool(constant) | Token::Constant(constant) => write!(f, "{constant}"),
368            Token::Property(k, actor_or_event) => write!(f, "p{actor_or_event}_{k}"),
369            Token::Quantifier(quantifier, actor_or_event) => write!(
370                f,
371                "{quantifier}{}",
372                match actor_or_event {
373                    ActorOrEvent::Actor => "",
374                    ActorOrEvent::Event => "_e",
375                }
376            ),
377            Token::Lambda(lambda_type, t) => write!(f, "lambda {lambda_type} {t}"),
378            Token::Variable(v) => write!(f, "{v}"),
379            Token::FreeVariable(v, lambda_type) => write!(f, "{v}#{lambda_type}"),
380            Token::Iota(ActorOrEvent::Event) => write!(f, "iota_e"),
381            Token::Iota(ActorOrEvent::Actor) => write!(f, "iota"),
382        }
383    }
384}
385
386pub type Span = SimpleSpan;
387pub type Spanned<T> = (T, Span);
388
389fn lexer<'src, E>() -> impl Parser<'src, &'src str, Vec<Spanned<Token<'src>>>, E>
390where
391    E: ParserExtra<'src, &'src str> + 'src,
392    E::Error: LabelError<'src, &'src str, TextExpected<&'src str>>
393        + LabelError<'src, &'src str, MaybeRef<'src, char>>
394        + LabelError<'src, &'src str, &'static str>
395        + LabelError<'src, &'src str, TextExpected<()>>,
396{
397    choice((
398        just(',').to(Token::ArgSep),
399        just('(').to(Token::OpenDelim),
400        just(')').to(Token::CloseDelim),
401        just("True").to(Token::Bool(Constant::Tautology)),
402        just("False").to(Token::Bool(Constant::Contradiction)),
403        just('&').to(Token::And),
404        just('|').to(Token::Or),
405        just('~').to(Token::Not),
406        just("AgentOf").to(Token::BinOp(BinOp::AgentOf)),
407        just("PatientOf").to(Token::BinOp(BinOp::PatientOf)),
408        just("iota_e").to(Token::Iota(ActorOrEvent::Event)),
409        just("iota").to(Token::Iota(ActorOrEvent::Actor)),
410        just("all_a").to(Token::Constant(Constant::Everyone)),
411        just("all_e").to(Token::Constant(Constant::EveryEvent)),
412        choice((
413            just("every").to(Quantifier::Universal),
414            just("some").to(Quantifier::Existential),
415        ))
416        .then(just("_e").or_not())
417        .map(|(q, t)| {
418            Token::Quantifier(
419                q,
420                if t.is_some() {
421                    ActorOrEvent::Event
422                } else {
423                    ActorOrEvent::Actor
424                },
425            )
426        }),
427        just("a_").ignore_then(keyword()).map(Token::Actor),
428        just("e_")
429            .ignore_then(text::int(10))
430            .map(|s: &str| Token::Event(s.parse().unwrap())),
431        just("p")
432            .ignore_then(
433                just("a")
434                    .to(ActorOrEvent::Actor)
435                    .or(just("e").to(ActorOrEvent::Event)),
436            )
437            .then_ignore(just("_"))
438            .then(keyword())
439            .map(|(t, s)| Token::Property(s, t)),
440        just("lambda")
441            .then(inline_whitespace().at_least(1))
442            .ignore_then(core_type_parser())
443            .then_ignore(inline_whitespace().at_least(1))
444            .then(keyword())
445            .then_ignore(inline_whitespace().at_least(1))
446            .map(|(t, x)| Token::Lambda(t, x)),
447        keyword()
448            .then(just("#").ignore_then(core_type_parser()).or_not())
449            .map(|(var, lambda_type)| {
450                if let Some(t) = lambda_type {
451                    Token::FreeVariable(var, t)
452                } else {
453                    Token::Variable(var)
454                }
455            }),
456    ))
457    .map_with(|t, e| (t, e.span()))
458    .padded()
459    .repeated()
460    .collect()
461}
462
463fn language_parser<'tokens, 'src: 'tokens, I>()
464-> impl Parser<'tokens, I, ParseTree<'src>, extra::Err<Rich<'tokens, Token<'src>, Span>>> + Clone
465where
466    I: ValueInput<'tokens, Token = Token<'src>, Span = SimpleSpan> + Clone,
467{
468    let var = select! {
469        Token::Variable(a) => ParseTree::Variable(a),
470        Token::FreeVariable(a, t) => ParseTree::FreeVariable(a, t)
471    }
472    .labelled("variable");
473
474    let ent = select! {
475        Token::Actor(a) => ParseTree::Entity(Entity::Actor(a)),
476        Token::Event(a) => ParseTree::Entity(Entity::Event(a)),
477    }
478    .labelled("entity");
479
480    let bool = select! {
481        Token::Bool(b) => ParseTree::Constant(b)
482    }
483    .labelled("boolean");
484
485    let sets = select! {
486        Token::Constant(c) => ParseTree::Constant(c),
487        Token::Property(s, a) => ParseTree::Constant(Constant::Property(s,a))
488    }
489    .labelled("constant set");
490    recursive(|expr| {
491        let bin_op = binary_operation(expr.clone(), expr.clone());
492        let mon_op = unary_op(expr.clone());
493
494        let application = choice((
495            var,
496            expr.clone()
497                .delimited_by(just(Token::OpenDelim), just(Token::CloseDelim)),
498        ))
499        .then_ignore(just(Token::OpenDelim))
500        .then(
501            expr.clone()
502                .separated_by(just(Token::ArgSep))
503                .at_least(1)
504                .collect::<VecDeque<_>>(),
505        )
506        .then_ignore(just(Token::CloseDelim))
507        .map(|(t, mut args)| {
508            let mut tree = ParseTree::Application {
509                subformula: Box::new(t),
510                argument: Box::new(args.pop_front().expect("previous primitive has at least 1")),
511            };
512            while let Some(x) = args.pop_front() {
513                tree = ParseTree::Application {
514                    subformula: Box::new(tree),
515                    argument: Box::new(x),
516                };
517            }
518
519            tree
520        });
521
522        let quantified = select!(Token::Quantifier(q, a) => (q,a))
523            .then_ignore(just(Token::OpenDelim))
524            .then(select! {Token::Variable(v) => v})
525            .then_ignore(just(Token::ArgSep))
526            .then(expr.clone())
527            .then_ignore(just(Token::ArgSep))
528            .then(expr.clone())
529            .then_ignore(just(Token::CloseDelim))
530            .map(
531                |((((quantifier, lambda_type), variable), restrictor), subformula)| {
532                    ParseTree::Quantifier {
533                        quantifier,
534                        variable,
535                        lambda_type,
536                        restrictor: Box::new(restrictor),
537                        subformula: Box::new(subformula),
538                    }
539                },
540            );
541
542        let atom = choice((
543            application,
544            ent,
545            var,
546            bin_op,
547            mon_op,
548            quantified,
549            bool,
550            sets,
551            expr.delimited_by(just(Token::OpenDelim), just(Token::CloseDelim)),
552        ));
553        atom.pratt((
554            prefix(2, just(Token::Not), |_, r, _| {
555                ParseTree::Unary(MonOp::Not, Box::new(r))
556            }),
557            prefix(
558                0,
559                select! {Token::Lambda(t, var) => (t, var)},
560                |(lambda_type, var), r, _| ParseTree::Lambda {
561                    body: Box::new(r),
562                    var,
563                    lambda_type,
564                },
565            ),
566            infix(left(1), just(Token::And), |l, _, r, _| {
567                ParseTree::Binary(BinOp::And, Box::new(l), Box::new(r))
568            }),
569            infix(left(1), just(Token::Or), |l, _, r, _| {
570                ParseTree::Binary(BinOp::Or, Box::new(l), Box::new(r))
571            }),
572        ))
573    })
574}
575
576///A function which maps strings to language of thought expressions. Crucially, it automatically performs all lambda reductions.
577pub fn parse_lot(s: &str) -> Result<RootedLambdaPool<'_, Expr<'_>>, LambdaParseError> {
578    let tokens = lexer::<extra::Err<Rich<char>>>()
579        .then_ignore(end())
580        .parse(s)
581        .into_result()?;
582
583    language_parser()
584        .parse(
585            tokens
586                .as_slice()
587                .map((s.len()..s.len()).into(), |(t, s)| (t, s)),
588        )
589        .into_result()?
590        .to_pool()
591}
592
593///A function which maps strings to language of thought expressions. Crucially, it automatically performs all lambda reductions.
594///
595///# Errors
596///Will panic if the expression is malformed, or if not all lambda terms can be reduced.
597pub fn parse_executable(s: &str) -> Result<LanguageExpression<'_>, LambdaParseError> {
598    let mut pool = parse_lot(s)?;
599    pool.reduce()?;
600    Ok(pool.into_pool()?)
601}
602
603#[cfg(test)]
604mod tests {
605    use super::*;
606    use crate::language::{ExprRef, LanguageResult};
607    use crate::{Scenario, ThetaRoles};
608    use std::collections::BTreeMap;
609
610    #[test]
611    fn parse_entity() {
612        for n in [1, 6, 3, 4, 5, 100, 40] {
613            let str = format!("e_{n}");
614            assert_eq!(
615                parse_lot(&str).unwrap(),
616                RootedLambdaPool::new(
617                    LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Event(n))]),
618                    LambdaExprRef(0)
619                )
620            );
621        }
622        for keyword in ["john", "mary", "phil", "Anna"] {
623            let str = format!("a_{keyword}");
624            assert_eq!(
625                parse_lot(&str).unwrap(),
626                RootedLambdaPool::new(
627                    LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Actor(
628                        keyword
629                    ))]),
630                    LambdaExprRef(0)
631                )
632            );
633        }
634    }
635
636    #[test]
637    fn parse_sets() {
638        assert_eq!(
639            parse_lot("all_e").unwrap(),
640            RootedLambdaPool::new(
641                LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Constant(
642                    Constant::EveryEvent
643                ))]),
644                LambdaExprRef(0)
645            )
646        );
647        assert_eq!(
648            parse_lot("all_a").unwrap(),
649            RootedLambdaPool::new(
650                LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Constant(
651                    Constant::Everyone
652                ))]),
653                LambdaExprRef(0)
654            )
655        );
656        for keyword in ["john", "mary", "phil", "Anna"] {
657            let str = format!("pa_{keyword}");
658            assert_eq!(
659                parse_lot(&str).unwrap(),
660                RootedLambdaPool::new(
661                    LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Constant(
662                        Constant::Property(keyword, ActorOrEvent::Actor)
663                    ))]),
664                    LambdaExprRef(0)
665                )
666            );
667            let str = format!("pe_{keyword}");
668            assert_eq!(
669                parse_lot(&str).unwrap(),
670                RootedLambdaPool::new(
671                    LambdaPool(vec![LambdaExpr::LanguageOfThoughtExpr(Expr::Constant(
672                        Constant::Property(keyword, ActorOrEvent::Event)
673                    ))]),
674                    LambdaExprRef(0)
675                )
676            );
677        }
678    }
679
680    fn get_parse<'a>(
681        s: &'a str,
682        simple_scenario: &'a Scenario,
683    ) -> anyhow::Result<LanguageResult<'a>> {
684        let pool = LanguageExpression::parse(s)?;
685        Ok(pool.run(simple_scenario, None)?)
686    }
687
688    fn check_lambdas(
689        statement: &str,
690        lambda_type: &str,
691        gold_pool: RootedLambdaPool<Expr>,
692    ) -> anyhow::Result<()> {
693        println!("{statement}");
694        let pool = parse_lot(statement)?;
695
696        assert_eq!(
697            pool.get_type()?,
698            LambdaType::from_string(lambda_type).map_err(|e| anyhow::anyhow!(e.to_string()))?
699        );
700        assert_eq!(pool, gold_pool);
701
702        Ok(())
703    }
704
705    #[test]
706    fn parse_lambda() -> anyhow::Result<()> {
707        check_lambdas(
708            "lambda e x (pe_Red(x))",
709            "<e,t>",
710            RootedLambdaPool::new(
711                LambdaPool::from(vec![
712                    LambdaExpr::BoundVariable(0, LambdaType::e().clone()),
713                    LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(
714                        MonOp::Property("Red", ActorOrEvent::Event),
715                        ExprRef(0),
716                    )),
717                    LambdaExpr::Lambda(LambdaExprRef(1), LambdaType::e().clone()),
718                ]),
719                LambdaExprRef(2),
720            ),
721        )?;
722        check_lambdas(
723            "lambda  <e,t> P  (lambda e x (P(x)))",
724            "<<e,t>, <e,t>>",
725            RootedLambdaPool::new(
726                LambdaPool::from(vec![
727                    LambdaExpr::BoundVariable(1, LambdaType::et().clone()),
728                    LambdaExpr::BoundVariable(0, LambdaType::e().clone()),
729                    LambdaExpr::Application {
730                        subformula: LambdaExprRef(0),
731                        argument: LambdaExprRef(1),
732                    },
733                    LambdaExpr::Lambda(LambdaExprRef(2), LambdaType::e().clone()),
734                    LambdaExpr::Lambda(LambdaExprRef(3), LambdaType::et().clone()),
735                ]),
736                LambdaExprRef(4),
737            ),
738        )?;
739        check_lambdas(
740            "lambda <a,t> P (P(a_0))",
741            "<<a,t>,t>",
742            RootedLambdaPool::new(
743                LambdaPool::from(vec![
744                    LambdaExpr::BoundVariable(0, LambdaType::at().clone()),
745                    LambdaExpr::LanguageOfThoughtExpr(Expr::Actor("0")),
746                    LambdaExpr::Application {
747                        subformula: LambdaExprRef(0),
748                        argument: LambdaExprRef(1),
749                    },
750                    LambdaExpr::Lambda(LambdaExprRef(2), LambdaType::at().clone()),
751                ]),
752                LambdaExprRef(3),
753            ),
754        )?;
755        check_lambdas(
756            "~hey#<e,t>(lol#e)",
757            "t",
758            RootedLambdaPool::new(
759                LambdaPool::from(vec![
760                    LambdaExpr::FreeVariable("hey".into(), LambdaType::et().clone()),
761                    LambdaExpr::FreeVariable("lol".into(), LambdaType::e().clone()),
762                    LambdaExpr::Application {
763                        subformula: LambdaExprRef(0),
764                        argument: LambdaExprRef(1),
765                    },
766                    LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(MonOp::Not, ExprRef(2))),
767                ]),
768                LambdaExprRef(3),
769            ),
770        )?;
771
772        check_lambdas(
773            "(lambda <a,t> P (P(a_0)))(lambda a x (pa_Red(x)))",
774            "t",
775            RootedLambdaPool::new(
776                LambdaPool::from(vec![
777                    LambdaExpr::BoundVariable(0, LambdaType::at().clone()),
778                    LambdaExpr::LanguageOfThoughtExpr(Expr::Actor("0")),
779                    LambdaExpr::Application {
780                        subformula: LambdaExprRef(0),
781                        argument: LambdaExprRef(1),
782                    },
783                    LambdaExpr::Lambda(LambdaExprRef(2), LambdaType::at().clone()),
784                    LambdaExpr::BoundVariable(0, LambdaType::a().clone()),
785                    LambdaExpr::LanguageOfThoughtExpr(Expr::Unary(
786                        MonOp::Property("Red", ActorOrEvent::Actor),
787                        ExprRef(4),
788                    )),
789                    LambdaExpr::Lambda(LambdaExprRef(5), LambdaType::a().clone()),
790                    LambdaExpr::Application {
791                        subformula: LambdaExprRef(3),
792                        argument: LambdaExprRef(6),
793                    },
794                ]),
795                LambdaExprRef(7),
796            ),
797        )?;
798        check_lambdas(
799            "lambda t phi (lambda t psi (phi & psi))",
800            "<t,<t,t>>",
801            RootedLambdaPool::new(
802                LambdaPool::from(vec![
803                    LambdaExpr::BoundVariable(1, LambdaType::t().clone()),
804                    LambdaExpr::BoundVariable(0, LambdaType::t().clone()),
805                    LambdaExpr::LanguageOfThoughtExpr(Expr::Binary(
806                        BinOp::And,
807                        ExprRef(0),
808                        ExprRef(1),
809                    )),
810                    LambdaExpr::Lambda(LambdaExprRef(2), LambdaType::t().clone()),
811                    LambdaExpr::Lambda(LambdaExprRef(3), LambdaType::t().clone()),
812                ]),
813                LambdaExprRef(4),
814            ),
815        )?;
816
817        Ok(())
818    }
819
820    #[test]
821    fn test_parse_with_beta_reduction() -> anyhow::Result<()> {
822        parse_executable("(lambda <a,t> P (P(a_0)))(lambda a x (pa_Red(x)))")?;
823        Ok(())
824    }
825
826    #[test]
827    fn parse_with_keywords() -> anyhow::Result<()> {
828        let mut properties = BTreeMap::default();
829
830        properties.insert("Red", vec![Entity::Actor("John")]);
831        properties.insert("Blue", vec![Entity::Actor("Mary"), Entity::Actor("John")]);
832
833        let scenario = Scenario {
834            question: vec![],
835            actors: vec!["Mary", "John"],
836            thematic_relations: vec![
837                ThetaRoles {
838                    agent: Some("Mary"),
839                    patient: Some("Mary"),
840                },
841                ThetaRoles {
842                    agent: Some("John"),
843                    patient: Some("Mary"),
844                },
845            ],
846            properties,
847        };
848
849        for statement in [
850            "~AgentOf(a_John, e_0)",
851            "pa_Red(a_John) & ~pa_Red(a_Mary)",
852            "pa_Red(a_John) & ~pa_Red(a_Mary) & pa_Red(a_John)",
853            "~(pa_Red(a_John) & ~(True & pa_Red(a_John)))",
854            "every(x0, all_a, pa_Blue(x0))",
855            "every(x0, pa_Blue, pa_Blue(x0))",
856            "every(x, pa_Red, pa_Blue(x))",
857            "every(x0, pa_Red, pa_Blue(x0))",
858            "every_e(x0, all_e, (some(x1, all_a, AgentOf(x1, x0))))",
859            "every_e(x0, all_e, (some(x1, all_a, PatientOf(x1, x0))))",
860            "every_e(x0, all_e, PatientOf(a_Mary, x0))",
861            "some(x0, (PatientOf(x0, e_0) & PatientOf(x0, e_1)), pa_Blue(x0))",
862        ] {
863            println!("{statement}");
864            let expression = parse_executable(statement)?;
865            assert_eq!(expression.run(&scenario, None)?, LanguageResult::Bool(true));
866        }
867
868        for (statement, result) in [
869            ("a_Mary", LanguageResult::Actor("Mary")),
870            ("pa_Red", LanguageResult::ActorSet(vec!["John"])),
871            ("pa_Blue", LanguageResult::ActorSet(vec!["Mary", "John"])),
872        ] {
873            println!("{statement}");
874            let expression = parse_executable(statement)?;
875            assert_eq!(expression.run(&scenario, None)?, result);
876        }
877
878        Ok(())
879    }
880
881    #[test]
882    fn parse_test() -> anyhow::Result<()> {
883        let mut properties = BTreeMap::default();
884
885        properties.insert("Red", vec![Entity::Actor("John")]);
886        properties.insert("Blue", vec![Entity::Actor("Mary"), Entity::Actor("John")]);
887
888        let scenario = Scenario {
889            question: vec![],
890            actors: vec!["Mary", "John"],
891            thematic_relations: vec![
892                ThetaRoles {
893                    agent: Some("Mary"),
894                    patient: Some("Mary"),
895                },
896                ThetaRoles {
897                    agent: Some("John"),
898                    patient: Some("Mary"),
899                },
900            ],
901            properties,
902        };
903
904        for statement in [
905            "True",
906            "~~~False",
907            "~AgentOf(a_John, e_0)",
908            "~(True & False)",
909            "True | False",
910            "(True & False) | True",
911            "~(True & False) | False",
912            "pa_Red(a_John) & ~pa_Red(a_Mary)",
913            "pa_Red(a_John) & ~pa_Red(a_Mary) & pa_Red(a_John)",
914            "~(pa_Red(a_John) & ~(True & pa_Red(a_John)))",
915            "every(x0, all_a, pa_Blue(x0))",
916            "every(x0, pa_Blue, pa_Blue(x0))",
917            "every_e(x0, all_e, (some(x1, all_a, AgentOf(x1, x0))))",
918            "every_e(x0, all_e, (some(x1, all_a, PatientOf(x1, x0))))",
919            "every_e(x0, all_e, PatientOf(a_Mary, x0))",
920            "some(x0, (PatientOf(x0, e_0) & PatientOf(x0, e_1)), pa_Blue(x0))",
921        ] {
922            println!("{statement}");
923            assert_eq!(get_parse(statement, &scenario)?, LanguageResult::Bool(true));
924        }
925        for (statement, result) in [
926            ("a_Mary", LanguageResult::Actor("Mary")),
927            ("e_0", LanguageResult::Event(0)),
928            ("all_e", LanguageResult::EventSet(vec![0, 1])),
929            ("all_a", LanguageResult::ActorSet(vec!["Mary", "John"])),
930            ("pa_Red", LanguageResult::ActorSet(vec!["John"])),
931            ("pa_Blue", LanguageResult::ActorSet(vec!["Mary", "John"])),
932        ] {
933            println!("{statement}");
934            assert_eq!(get_parse(statement, &scenario)?, result);
935        }
936
937        Ok(())
938    }
939
940    #[test]
941    fn parse_errors_test() -> anyhow::Result<()> {
942        for statement in [
943            "(wow#<a,<e,t>>(nice#a))(cool#e)",
944            "every(x,lambda a y pa_John(y), pa_Blue(y#a))",
945            "pa_cool(iota(x, pa_man(x)))",
946            "pe_cool(iota_e(x, pe_man(x)))",
947            "pa_cool(iota(x, (lambda a x pa_man(x))(x)))",
948        ] {
949            RootedLambdaPool::parse(statement)?;
950        }
951
952        for statement in [
953            "wow#<e,t>(nice#a)",
954            "(wow#<a,<e,t>>(nice#a))(cool#a)",
955            "every(x,lambda a y pa_John(y), pa_Blue(y))",
956        ] {
957            let p = RootedLambdaPool::parse(statement);
958            assert!(p.is_err());
959        }
960        Ok(())
961    }
962}
simple_semantics/language/parser.rs

simple_semantics/language/
parser.rs
