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

simple_semantics/language/
parser.rs
