simple_semantics/language/
parser.rs

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

simple_semantics/language/
parser.rs
