Skip to main content

logicaffeine_language/
lambda.rs

1//! Lambda calculus transformations for Montague-style compositional semantics.
2//!
3//! This module provides functions for manipulating logical expressions using
4//! lambda abstraction and application. It supports:
5//!
6//! - **Quantifier raising** via type-lifting (proper names → generalized quantifiers)
7//! - **Beta reduction** for applying lambda abstractions
8//! - **Scope enumeration** to generate all possible quantifier scopings
9//! - **Intensional contexts** for opaque verbs (believes, seeks, wants)
10//! - **Event semantics** transformation (Davidson-style)
11//!
12//! # Key Functions
13//!
14//! | Function | Purpose |
15//! |----------|---------|
16//! | [`lift_proper_name`] | Lifts a proper name to a generalized quantifier |
17//! | [`lift_quantifier`] | Creates a quantifier lambda term |
18//! | [`beta_reduce`] | Performs beta reduction on applications |
19//! | [`enumerate_scopings`] | Generates all scope permutations respecting islands |
20//! | [`enumerate_intensional_readings`] | Generates de re / de dicto readings |
21//! | [`to_event_semantics`] | Converts predicate to neo-Davidsonian event form |
22//!
23//! # Scope Islands
24//!
25//! Quantifiers are assigned an `island_id` during parsing. The scoping algorithm
26//! only permutes quantifiers within the same island. This prevents:
27//! - Wh-extraction from relative clauses
28//! - Quantifier raising out of adjuncts
29//! - Other island constraint violations
30//!
31//! # Intensionality
32//!
33//! Opaque verbs create intensional contexts where substitution of co-referential
34//! terms may change truth value. The module provides:
35//! - `make_intensional`: Wraps an expression in an intensional operator
36//! - `substitute_respecting_opacity`: Blocks substitution inside intensional contexts
37
38use crate::ast::{LogicExpr, QuantifierKind, Term};
39use crate::lexicon;
40use crate::token::TokenType;
41use logicaffeine_base::Arena;
42use logicaffeine_base::{Interner, Symbol};
43
44fn clone_term<'a>(term: &Term<'a>, arena: &'a Arena<Term<'a>>) -> Term<'a> {
45    match term {
46        Term::Constant(s) => Term::Constant(*s),
47        Term::Variable(s) => Term::Variable(*s),
48        Term::Function(name, args) => {
49            let cloned_args: Vec<Term<'a>> = args.iter().map(|t| clone_term(t, arena)).collect();
50            Term::Function(*name, arena.alloc_slice(cloned_args))
51        }
52        Term::Group(members) => {
53            let cloned: Vec<Term<'a>> = members.iter().map(|t| clone_term(t, arena)).collect();
54            Term::Group(arena.alloc_slice(cloned))
55        }
56        Term::Possessed {
57            possessor,
58            possessed,
59        } => Term::Possessed {
60            possessor: arena.alloc(clone_term(possessor, arena)),
61            possessed: *possessed,
62        },
63        Term::Sigma(predicate) => Term::Sigma(*predicate),
64        Term::Intension(predicate) => Term::Intension(*predicate),
65        Term::Kind(kind) => Term::Kind(*kind),
66        Term::Proposition(expr) => Term::Proposition(*expr),
67        Term::Value {
68            kind,
69            unit,
70            dimension,
71        } => Term::Value {
72            kind: *kind,
73            unit: *unit,
74            dimension: *dimension,
75        },
76    }
77}
78
79/// Checks if a verb creates an opaque (intensional) context.
80///
81/// Opaque verbs like "believes", "wants", "seeks" block substitution
82/// of co-referential terms. For example:
83/// - "John believes Clark Kent flies" ≠ "John believes Superman flies"
84pub fn is_opaque_verb(verb: Symbol, interner: &Interner) -> bool {
85    let verb_str = interner.resolve(verb);
86    let lower = verb_str.to_lowercase();
87    lexicon::is_opaque_verb(&lower)
88}
89
90/// Wraps an expression in an intensional operator.
91///
92/// Creates `operator[content]` for de dicto readings of intensional verbs.
93pub fn make_intensional<'a>(
94    operator: Symbol,
95    content: &'a LogicExpr<'a>,
96    arena: &'a Arena<LogicExpr<'a>>,
97) -> &'a LogicExpr<'a> {
98    arena.alloc(LogicExpr::Intensional { operator, content })
99}
100
101/// Substitutes a variable with a replacement, respecting opacity boundaries.
102///
103/// Unlike standard substitution, this function does NOT substitute inside
104/// intensional contexts, preserving the opacity of verbs like "believes".
105pub fn substitute_respecting_opacity<'a>(
106    expr: &'a LogicExpr<'a>,
107    var: Symbol,
108    replacement: &'a LogicExpr<'a>,
109    expr_arena: &'a Arena<LogicExpr<'a>>,
110    term_arena: &'a Arena<Term<'a>>,
111) -> &'a LogicExpr<'a> {
112    match expr {
113        LogicExpr::Intensional { operator, content } => expr_arena.alloc(LogicExpr::Intensional {
114            operator: *operator,
115            content: *content,
116        }),
117
118        LogicExpr::Predicate { name, args, .. } => {
119            let new_args: Vec<Term<'a>> = args
120                .iter()
121                .map(|arg| substitute_term_for_opacity(arg, var, replacement, term_arena))
122                .collect();
123            expr_arena.alloc(LogicExpr::Predicate {
124                name: *name,
125                args: term_arena.alloc_slice(new_args),
126                world: None,
127            })
128        }
129
130        LogicExpr::BinaryOp { left, op, right } => expr_arena.alloc(LogicExpr::BinaryOp {
131            left: substitute_respecting_opacity(left, var, replacement, expr_arena, term_arena),
132            op: op.clone(),
133            right: substitute_respecting_opacity(right, var, replacement, expr_arena, term_arena),
134        }),
135
136        LogicExpr::UnaryOp { op, operand } => expr_arena.alloc(LogicExpr::UnaryOp {
137            op: op.clone(),
138            operand: substitute_respecting_opacity(
139                operand,
140                var,
141                replacement,
142                expr_arena,
143                term_arena,
144            ),
145        }),
146
147        LogicExpr::Quantifier {
148            kind,
149            variable,
150            body,
151            island_id,
152        } => {
153            if *variable == var {
154                expr
155            } else {
156                expr_arena.alloc(LogicExpr::Quantifier {
157                    kind: *kind,
158                    variable: *variable,
159                    body: substitute_respecting_opacity(
160                        body,
161                        var,
162                        replacement,
163                        expr_arena,
164                        term_arena,
165                    ),
166                    island_id: *island_id,
167                })
168            }
169        }
170
171        LogicExpr::Lambda { variable, body } => {
172            if *variable == var {
173                expr
174            } else {
175                expr_arena.alloc(LogicExpr::Lambda {
176                    variable: *variable,
177                    body: substitute_respecting_opacity(
178                        body,
179                        var,
180                        replacement,
181                        expr_arena,
182                        term_arena,
183                    ),
184                })
185            }
186        }
187
188        LogicExpr::App { function, argument } => expr_arena.alloc(LogicExpr::App {
189            function: substitute_respecting_opacity(
190                function,
191                var,
192                replacement,
193                expr_arena,
194                term_arena,
195            ),
196            argument: substitute_respecting_opacity(
197                argument,
198                var,
199                replacement,
200                expr_arena,
201                term_arena,
202            ),
203        }),
204
205        LogicExpr::Atom(s) => {
206            if *s == var {
207                replacement
208            } else {
209                expr
210            }
211        }
212
213        _ => expr,
214    }
215}
216
217fn substitute_term_for_opacity<'a>(
218    term: &Term<'a>,
219    var: Symbol,
220    replacement: &LogicExpr<'a>,
221    arena: &'a Arena<Term<'a>>,
222) -> Term<'a> {
223    match term {
224        Term::Constant(c) if *c == var => match replacement {
225            LogicExpr::Atom(s) => Term::Constant(*s),
226            _ => clone_term(term, arena),
227        },
228        Term::Variable(v) if *v == var => match replacement {
229            LogicExpr::Atom(s) => Term::Constant(*s),
230            _ => clone_term(term, arena),
231        },
232        _ => clone_term(term, arena),
233    }
234}
235
236/// Converts a predicate to Neo-Davidsonian event semantics.
237///
238/// Transforms `P(x, y)` into `∃e(P(e) ∧ Agent(e, x) ∧ Theme(e, y))`.
239/// This reification of events enables reasoning about event modification.
240pub fn to_event_semantics<'a>(
241    expr: &'a LogicExpr<'a>,
242    interner: &mut Interner,
243    expr_arena: &'a Arena<LogicExpr<'a>>,
244    term_arena: &'a Arena<Term<'a>>,
245) -> &'a LogicExpr<'a> {
246    match expr {
247        LogicExpr::Predicate { name, args, .. } => {
248            let e_sym = interner.intern("e");
249            let _event_var = term_arena.alloc(Term::Variable(e_sym));
250
251            let event_pred = expr_arena.alloc(LogicExpr::Predicate {
252                name: *name,
253                args: term_arena.alloc_slice([Term::Variable(e_sym)]),
254                world: None,
255            });
256
257            let mut body = event_pred;
258
259            if !args.is_empty() {
260                let agent_args = term_arena
261                    .alloc_slice([Term::Variable(e_sym), clone_term(&args[0], term_arena)]);
262                let agent_pred = expr_arena.alloc(LogicExpr::Predicate {
263                    name: interner.intern("Agent"),
264                    args: agent_args,
265                    world: None,
266                });
267                body = expr_arena.alloc(LogicExpr::BinaryOp {
268                    left: body,
269                    op: TokenType::And,
270                    right: agent_pred,
271                });
272            }
273
274            if args.len() > 1 {
275                let theme_args = term_arena
276                    .alloc_slice([Term::Variable(e_sym), clone_term(&args[1], term_arena)]);
277                let theme_pred = expr_arena.alloc(LogicExpr::Predicate {
278                    name: interner.intern("Theme"),
279                    args: theme_args,
280                    world: None,
281                });
282                body = expr_arena.alloc(LogicExpr::BinaryOp {
283                    left: body,
284                    op: TokenType::And,
285                    right: theme_pred,
286                });
287            }
288
289            if args.len() > 2 {
290                let goal_args = term_arena
291                    .alloc_slice([Term::Variable(e_sym), clone_term(&args[2], term_arena)]);
292                let goal_pred = expr_arena.alloc(LogicExpr::Predicate {
293                    name: interner.intern("Goal"),
294                    args: goal_args,
295                    world: None,
296                });
297                body = expr_arena.alloc(LogicExpr::BinaryOp {
298                    left: body,
299                    op: TokenType::And,
300                    right: goal_pred,
301                });
302            }
303
304            expr_arena.alloc(LogicExpr::Quantifier {
305                kind: QuantifierKind::Existential,
306                variable: e_sym,
307                body,
308                island_id: 0,
309            })
310        }
311        _ => expr,
312    }
313}
314
315/// Adds an adverbial modifier to an event.
316///
317/// Transforms `∃e(P(e) ∧ ...)` into `∃e(P(e) ∧ Adverb(e) ∧ ...)`.
318pub fn apply_adverb<'a>(
319    expr: &'a LogicExpr<'a>,
320    adverb: Symbol,
321    interner: &mut Interner,
322    expr_arena: &'a Arena<LogicExpr<'a>>,
323    term_arena: &'a Arena<Term<'a>>,
324) -> &'a LogicExpr<'a> {
325    let e_sym = interner.intern("e");
326    match expr {
327        LogicExpr::Quantifier {
328            kind,
329            variable,
330            body,
331            island_id,
332        } if *variable == e_sym => {
333            let adverb_str = interner.resolve(adverb);
334            let capitalized = capitalize(adverb_str);
335            let adverb_pred = expr_arena.alloc(LogicExpr::Predicate {
336                name: interner.intern(&capitalized),
337                args: term_arena.alloc_slice([Term::Variable(*variable)]),
338                world: None,
339            });
340
341            let new_body = expr_arena.alloc(LogicExpr::BinaryOp {
342                left: *body,
343                op: TokenType::And,
344                right: adverb_pred,
345            });
346
347            expr_arena.alloc(LogicExpr::Quantifier {
348                kind: *kind,
349                variable: *variable,
350                body: new_body,
351                island_id: *island_id,
352            })
353        }
354        _ => expr,
355    }
356}
357
358fn capitalize(s: &str) -> String {
359    let mut chars = s.chars();
360    match chars.next() {
361        None => String::new(),
362        Some(first) => first.to_uppercase().collect::<String>() + chars.as_str(),
363    }
364}
365
366fn factorial(n: usize) -> u64 {
367    (1..=n as u64).product()
368}
369
370pub struct ScopeIterator<'a> {
371    expr_arena: &'a Arena<LogicExpr<'a>>,
372    islands: Vec<Vec<ScopalElement<'a>>>,
373    core: &'a LogicExpr<'a>,
374    current_index: u64,
375    total: u64,
376    single_result: Option<&'a LogicExpr<'a>>,
377    returned_single: bool,
378}
379
380impl<'a> ScopeIterator<'a> {
381    fn nth_island_aware_permutation(&self, n: u64) -> Vec<ScopalElement<'a>> {
382        let mut result = Vec::new();
383        let mut remainder = n;
384
385        for island in &self.islands {
386            let island_perms = factorial(island.len());
387            let island_index = remainder % island_perms;
388            remainder /= island_perms;
389
390            let perm = nth_permutation_of_slice(island, island_index);
391            result.extend(perm);
392        }
393
394        result
395    }
396}
397
398fn nth_permutation_of_slice<T: Clone>(items: &[T], n: u64) -> Vec<T> {
399    let len = items.len();
400    let mut available: Vec<usize> = (0..len).collect();
401    let mut result = Vec::with_capacity(len);
402    let mut remainder = n;
403
404    for i in 0..len {
405        let divisor = factorial(len - i - 1);
406        let index = (remainder / divisor) as usize;
407        remainder %= divisor;
408        result.push(items[available.remove(index)].clone());
409    }
410    result
411}
412
413impl<'a> Iterator for ScopeIterator<'a> {
414    type Item = &'a LogicExpr<'a>;
415
416    fn next(&mut self) -> Option<Self::Item> {
417        if let Some(single) = self.single_result {
418            if self.returned_single {
419                return None;
420            }
421            self.returned_single = true;
422            return Some(single);
423        }
424
425        if self.current_index >= self.total {
426            return None;
427        }
428        let ordered = self.nth_island_aware_permutation(self.current_index);
429        self.current_index += 1;
430        Some(rebuild_with_scopal_elements(
431            &ordered,
432            self.core,
433            self.expr_arena,
434        ))
435    }
436
437    fn size_hint(&self) -> (usize, Option<usize>) {
438        if self.single_result.is_some() {
439            let remaining = if self.returned_single { 0 } else { 1 };
440            return (remaining, Some(remaining));
441        }
442        let remaining = (self.total - self.current_index) as usize;
443        (remaining, Some(remaining))
444    }
445}
446
447impl<'a> ExactSizeIterator for ScopeIterator<'a> {}
448
449#[derive(Clone, Debug)]
450struct QuantifierInfo<'a> {
451    kind: QuantifierKind,
452    variable: Symbol,
453    restrictor: &'a LogicExpr<'a>,
454    island_id: u32,
455}
456
457#[derive(Clone, Debug)]
458enum ScopalElement<'a> {
459    Quantifier(QuantifierInfo<'a>),
460    Negation { island_id: u32 },
461}
462
463impl<'a> ScopalElement<'a> {
464    fn island_id(&self) -> u32 {
465        match self {
466            ScopalElement::Quantifier(q) => q.island_id,
467            ScopalElement::Negation { island_id } => *island_id,
468        }
469    }
470}
471
472/// Generates all possible quantifier scopings for an expression.
473///
474/// Returns an iterator over all scope-permuted versions of the expression,
475/// respecting scope island constraints. Quantifiers with the same `island_id`
476/// can be permuted; quantifiers in different islands maintain relative order.
477///
478/// # Example
479///
480/// "Every man loves a woman" has two readings:
481/// - Surface scope: ∀x(Man(x) → ∃y(Woman(y) ∧ Love(x,y)))
482/// - Inverse scope: ∃y(Woman(y) ∧ ∀x(Man(x) → Love(x,y)))
483pub fn enumerate_scopings<'a>(
484    expr: &'a LogicExpr<'a>,
485    interner: &mut Interner,
486    expr_arena: &'a Arena<LogicExpr<'a>>,
487    _term_arena: &'a Arena<Term<'a>>,
488) -> ScopeIterator<'a> {
489    let mut elements = Vec::new();
490    let core = extract_scopal_elements(expr, &mut elements, interner, expr_arena);
491
492    if elements.is_empty() || elements.len() == 1 {
493        return ScopeIterator {
494            expr_arena,
495            islands: Vec::new(),
496            core,
497            current_index: 0,
498            total: 0,
499            single_result: Some(expr),
500            returned_single: false,
501        };
502    }
503
504    let islands = group_scopal_by_island(elements);
505    let total: u64 = islands
506        .iter()
507        .map(|island| factorial(island.len()))
508        .product();
509
510    ScopeIterator {
511        expr_arena,
512        islands,
513        core,
514        current_index: 0,
515        total,
516        single_result: None,
517        returned_single: false,
518    }
519}
520
521fn group_scopal_by_island<'a>(elements: Vec<ScopalElement<'a>>) -> Vec<Vec<ScopalElement<'a>>> {
522    use std::collections::BTreeMap;
523
524    let mut by_island: BTreeMap<u32, Vec<ScopalElement<'a>>> = BTreeMap::new();
525    for elem in elements {
526        by_island.entry(elem.island_id()).or_default().push(elem);
527    }
528
529    by_island.into_values().collect()
530}
531
532/// Builds the CUMULATIVE reading (Scha 1981) for a two-cardinal transitive
533/// sentence — the reading irreducible to either nesting:
534///   "Three boys lifted five boxes." →
535///     ∃=3 x(Boy(x) ∧ ∃y(Box(y) ∧ Lift(x,y))) ∧ ∃=5 y(Box(y) ∧ ∃x(Boy(x) ∧ Lift(x,y)))
536/// i.e. exactly 3 boys each lifted some box AND exactly 5 boxes were each lifted
537/// by some boy. This is first-order over the Link lattice (no ⊕ term needed). It
538/// is produced only when there are exactly two cardinal quantifiers in the same
539/// island over a shared nucleus; otherwise returns `None`.
540pub fn cumulative_reading<'a>(
541    expr: &'a LogicExpr<'a>,
542    interner: &mut Interner,
543    expr_arena: &'a Arena<LogicExpr<'a>>,
544) -> Option<&'a LogicExpr<'a>> {
545    let mut elements = Vec::new();
546    let core = extract_scopal_elements(expr, &mut elements, interner, expr_arena);
547    if elements.len() != 2 {
548        return None;
549    }
550    let (q1, q2) = match (&elements[0], &elements[1]) {
551        (ScopalElement::Quantifier(a), ScopalElement::Quantifier(b)) => (a.clone(), b.clone()),
552        _ => return None,
553    };
554    // Both must be cardinal counts in the same island (cumulative is a relation
555    // between two counted groups, not a nesting).
556    if !matches!(q1.kind, QuantifierKind::Cardinal(_))
557        || !matches!(q2.kind, QuantifierKind::Cardinal(_))
558        || q1.island_id != q2.island_id
559    {
560        return None;
561    }
562
563    let and = |l: &'a LogicExpr<'a>, r: &'a LogicExpr<'a>| -> &'a LogicExpr<'a> {
564        expr_arena.alloc(LogicExpr::BinaryOp {
565            left: l,
566            op: TokenType::And,
567            right: r,
568        })
569    };
570
571    // Conjunct 1: q1 x ( R1(x) ∧ ∃y( R2(y) ∧ core ) )
572    let exists_y = expr_arena.alloc(LogicExpr::Quantifier {
573        kind: QuantifierKind::Existential,
574        variable: q2.variable,
575        body: and(q2.restrictor, core),
576        island_id: q1.island_id,
577    });
578    let c1 = expr_arena.alloc(LogicExpr::Quantifier {
579        kind: q1.kind,
580        variable: q1.variable,
581        body: and(q1.restrictor, exists_y),
582        island_id: q1.island_id,
583    });
584
585    // Conjunct 2: q2 y ( R2(y) ∧ ∃x( R1(x) ∧ core ) )
586    let exists_x = expr_arena.alloc(LogicExpr::Quantifier {
587        kind: QuantifierKind::Existential,
588        variable: q1.variable,
589        body: and(q1.restrictor, core),
590        island_id: q2.island_id,
591    });
592    let c2 = expr_arena.alloc(LogicExpr::Quantifier {
593        kind: q2.kind,
594        variable: q2.variable,
595        body: and(q2.restrictor, exists_x),
596        island_id: q2.island_id,
597    });
598
599    Some(and(c1, c2))
600}
601
602fn extract_scopal_elements<'a>(
603    expr: &'a LogicExpr<'a>,
604    elements: &mut Vec<ScopalElement<'a>>,
605    interner: &mut Interner,
606    expr_arena: &'a Arena<LogicExpr<'a>>,
607) -> &'a LogicExpr<'a> {
608    match expr {
609        LogicExpr::Quantifier {
610            kind,
611            variable,
612            body,
613            island_id,
614        } => {
615            if let LogicExpr::BinaryOp { left, op, right } = body {
616                if matches!(op, TokenType::If | TokenType::Implies | TokenType::And) {
617                    // Check if right side has a negation at the top level
618                    if let LogicExpr::UnaryOp {
619                        op: TokenType::Not,
620                        operand,
621                    } = right
622                    {
623                        // Pattern: ∀x(R(x) → ¬P(x)) or ∃x(R(x) ∧ ¬P(x))
624                        // Extract both quantifier and negation
625                        elements.push(ScopalElement::Quantifier(QuantifierInfo {
626                            kind: *kind,
627                            variable: *variable,
628                            restrictor: *left,
629                            island_id: *island_id,
630                        }));
631                        elements.push(ScopalElement::Negation {
632                            island_id: *island_id,
633                        });
634                        return extract_scopal_elements(operand, elements, interner, expr_arena);
635                    }
636                    // No negation in right side, just extract quantifier
637                    elements.push(ScopalElement::Quantifier(QuantifierInfo {
638                        kind: *kind,
639                        variable: *variable,
640                        restrictor: *left,
641                        island_id: *island_id,
642                    }));
643                    return extract_scopal_elements(right, elements, interner, expr_arena);
644                }
645            }
646            // No binary op body, use a true restrictor
647            elements.push(ScopalElement::Quantifier(QuantifierInfo {
648                kind: *kind,
649                variable: *variable,
650                restrictor: expr_arena.alloc(LogicExpr::Atom(interner.intern("T"))),
651                island_id: *island_id,
652            }));
653            extract_scopal_elements(body, elements, interner, expr_arena)
654        }
655        LogicExpr::UnaryOp {
656            op: TokenType::Not,
657            operand,
658        } => {
659            // Standalone negation (not inside a quantifier body)
660            elements.push(ScopalElement::Negation { island_id: 0 });
661            extract_scopal_elements(operand, elements, interner, expr_arena)
662        }
663        _ => expr,
664    }
665}
666
667fn rebuild_with_scopal_elements<'a>(
668    elements: &[ScopalElement<'a>],
669    core: &'a LogicExpr<'a>,
670    arena: &'a Arena<LogicExpr<'a>>,
671) -> &'a LogicExpr<'a> {
672    let mut result = core;
673
674    for elem in elements.iter().rev() {
675        match elem {
676            ScopalElement::Quantifier(q) => {
677                let connective = match q.kind {
678                    QuantifierKind::Universal => TokenType::Implies,
679                    _ => TokenType::And,
680                };
681
682                let body = arena.alloc(LogicExpr::BinaryOp {
683                    left: q.restrictor,
684                    op: connective,
685                    right: result,
686                });
687
688                result = arena.alloc(LogicExpr::Quantifier {
689                    kind: q.kind,
690                    variable: q.variable,
691                    body,
692                    island_id: q.island_id,
693                });
694            }
695            ScopalElement::Negation { .. } => {
696                result = arena.alloc(LogicExpr::UnaryOp {
697                    op: TokenType::Not,
698                    operand: result,
699                });
700            }
701        }
702    }
703
704    result
705}
706
707pub fn lift_proper_name<'a>(
708    name: Symbol,
709    interner: &mut Interner,
710    arena: &'a Arena<LogicExpr<'a>>,
711) -> &'a LogicExpr<'a> {
712    let p_sym = interner.intern("P");
713    let inner_app = arena.alloc(LogicExpr::App {
714        function: arena.alloc(LogicExpr::Atom(p_sym)),
715        argument: arena.alloc(LogicExpr::Atom(name)),
716    });
717    arena.alloc(LogicExpr::Lambda {
718        variable: p_sym,
719        body: inner_app,
720    })
721}
722
723pub fn lift_quantifier<'a>(
724    kind: QuantifierKind,
725    restrictor: Symbol,
726    interner: &mut Interner,
727    expr_arena: &'a Arena<LogicExpr<'a>>,
728    term_arena: &'a Arena<Term<'a>>,
729) -> &'a LogicExpr<'a> {
730    let x_sym = interner.intern("x");
731    let q_sym = interner.intern("Q");
732
733    let restrictor_pred = expr_arena.alloc(LogicExpr::Predicate {
734        name: restrictor,
735        args: term_arena.alloc_slice([Term::Variable(x_sym)]),
736        world: None,
737    });
738
739    let q_of_x = expr_arena.alloc(LogicExpr::App {
740        function: expr_arena.alloc(LogicExpr::Atom(q_sym)),
741        argument: expr_arena.alloc(LogicExpr::Atom(x_sym)),
742    });
743
744    let connective = match kind {
745        QuantifierKind::Universal => TokenType::Implies,
746        _ => TokenType::And,
747    };
748
749    let body = expr_arena.alloc(LogicExpr::BinaryOp {
750        left: restrictor_pred,
751        op: connective,
752        right: q_of_x,
753    });
754
755    let quantifier = expr_arena.alloc(LogicExpr::Quantifier {
756        kind,
757        variable: x_sym,
758        body,
759        island_id: 0,
760    });
761
762    expr_arena.alloc(LogicExpr::Lambda {
763        variable: q_sym,
764        body: quantifier,
765    })
766}
767
768/// Performs beta reduction on lambda applications.
769///
770/// Reduces `(λx.body)(arg)` to `body[x := arg]` by substituting
771/// the argument for the bound variable in the body.
772pub fn beta_reduce<'a>(
773    expr: &'a LogicExpr<'a>,
774    expr_arena: &'a Arena<LogicExpr<'a>>,
775    term_arena: &'a Arena<Term<'a>>,
776) -> &'a LogicExpr<'a> {
777    match expr {
778        LogicExpr::App { function, argument } => {
779            if let LogicExpr::Lambda { variable, body } = function {
780                substitute(body, *variable, argument, expr_arena, term_arena)
781            } else {
782                expr_arena.alloc(LogicExpr::App {
783                    function: beta_reduce(function, expr_arena, term_arena),
784                    argument: beta_reduce(argument, expr_arena, term_arena),
785                })
786            }
787        }
788        LogicExpr::Lambda { variable, body } => expr_arena.alloc(LogicExpr::Lambda {
789            variable: *variable,
790            body: beta_reduce(body, expr_arena, term_arena),
791        }),
792        _ => expr,
793    }
794}
795
796fn substitute<'a>(
797    expr: &'a LogicExpr<'a>,
798    var: Symbol,
799    replacement: &'a LogicExpr<'a>,
800    expr_arena: &'a Arena<LogicExpr<'a>>,
801    term_arena: &'a Arena<Term<'a>>,
802) -> &'a LogicExpr<'a> {
803    match expr {
804        LogicExpr::Predicate { name, args, .. } => {
805            let new_args: Vec<Term<'a>> = args
806                .iter()
807                .map(|arg| substitute_term(arg, var, replacement, term_arena))
808                .collect();
809            expr_arena.alloc(LogicExpr::Predicate {
810                name: *name,
811                args: term_arena.alloc_slice(new_args),
812                world: None,
813            })
814        }
815
816        LogicExpr::Lambda { variable, body } => {
817            if *variable == var {
818                expr
819            } else {
820                expr_arena.alloc(LogicExpr::Lambda {
821                    variable: *variable,
822                    body: substitute(body, var, replacement, expr_arena, term_arena),
823                })
824            }
825        }
826
827        LogicExpr::App { function, argument } => expr_arena.alloc(LogicExpr::App {
828            function: substitute(function, var, replacement, expr_arena, term_arena),
829            argument: substitute(argument, var, replacement, expr_arena, term_arena),
830        }),
831
832        LogicExpr::BinaryOp { left, op, right } => expr_arena.alloc(LogicExpr::BinaryOp {
833            left: substitute(left, var, replacement, expr_arena, term_arena),
834            op: op.clone(),
835            right: substitute(right, var, replacement, expr_arena, term_arena),
836        }),
837
838        LogicExpr::UnaryOp { op, operand } => expr_arena.alloc(LogicExpr::UnaryOp {
839            op: op.clone(),
840            operand: substitute(operand, var, replacement, expr_arena, term_arena),
841        }),
842
843        LogicExpr::Quantifier {
844            kind,
845            variable,
846            body,
847            island_id,
848        } => {
849            if *variable == var {
850                expr
851            } else {
852                expr_arena.alloc(LogicExpr::Quantifier {
853                    kind: *kind,
854                    variable: *variable,
855                    body: substitute(body, var, replacement, expr_arena, term_arena),
856                    island_id: *island_id,
857                })
858            }
859        }
860
861        LogicExpr::Atom(s) => {
862            if *s == var {
863                replacement
864            } else {
865                expr
866            }
867        }
868
869        _ => expr,
870    }
871}
872
873fn substitute_term<'a>(
874    term: &Term<'a>,
875    var: Symbol,
876    replacement: &LogicExpr<'a>,
877    term_arena: &'a Arena<Term<'a>>,
878) -> Term<'a> {
879    match term {
880        Term::Variable(v) if *v == var => match replacement {
881            LogicExpr::Atom(s) => Term::Constant(*s),
882            LogicExpr::Predicate { name, .. } => Term::Constant(*name),
883            _ => clone_term(term, term_arena),
884        },
885        _ => clone_term(term, term_arena),
886    }
887}
888
889// ═══════════════════════════════════════════════════════════════════
890// Intensional Reading Generation (De Re / De Dicto)
891// ═══════════════════════════════════════════════════════════════════
892
893#[derive(Debug)]
894struct IntensionalContext {
895    quantifier_var: Symbol,
896    restrictor: Symbol,
897}
898
899fn find_opaque_verb_context<'a>(
900    expr: &'a LogicExpr<'a>,
901    interner: &Interner,
902) -> Option<IntensionalContext> {
903    match expr {
904        LogicExpr::Quantifier {
905            kind: QuantifierKind::Existential,
906            variable,
907            body,
908            ..
909        } => {
910            if let LogicExpr::BinaryOp {
911                left,
912                op: TokenType::And,
913                right,
914            } = body
915            {
916                if let LogicExpr::Predicate {
917                    name: restrictor,
918                    args,
919                    ..
920                } = left
921                {
922                    if args.len() == 1 {
923                        if let Term::Variable(v) = &args[0] {
924                            if *v == *variable {
925                                if find_opaque_verb_in_scope(right, *variable, interner).is_some() {
926                                    return Some(IntensionalContext {
927                                        quantifier_var: *variable,
928                                        restrictor: *restrictor,
929                                    });
930                                }
931                            }
932                        }
933                    }
934                }
935            }
936            None
937        }
938        _ => None,
939    }
940}
941
942fn find_opaque_verb_in_scope<'a>(
943    expr: &'a LogicExpr<'a>,
944    theme_var: Symbol,
945    interner: &Interner,
946) -> Option<Symbol> {
947    match expr {
948        LogicExpr::Quantifier { body, .. } => find_opaque_verb_in_scope(body, theme_var, interner),
949        LogicExpr::BinaryOp { left, right, .. } => {
950            find_opaque_verb_in_scope(left, theme_var, interner)
951                .or_else(|| find_opaque_verb_in_scope(right, theme_var, interner))
952        }
953        LogicExpr::NeoEvent(data) => {
954            if is_opaque_verb(data.verb, interner) {
955                for (role, term) in data.roles.iter() {
956                    if matches!(role, crate::ast::ThematicRole::Theme) {
957                        if let Term::Variable(v) = term {
958                            if *v == theme_var {
959                                return Some(data.verb);
960                            }
961                        }
962                    }
963                }
964            }
965            None
966        }
967        LogicExpr::Predicate { name, args, .. } => {
968            if is_opaque_verb(*name, interner) && args.len() >= 2 {
969                if let Term::Variable(v) = &args[1] {
970                    if *v == theme_var {
971                        return Some(*name);
972                    }
973                }
974            }
975            None
976        }
977        _ => None,
978    }
979}
980
981fn build_de_dicto_reading<'a>(
982    expr: &'a LogicExpr<'a>,
983    ctx: &IntensionalContext,
984    expr_arena: &'a Arena<LogicExpr<'a>>,
985    term_arena: &'a Arena<Term<'a>>,
986    role_arena: &'a Arena<(crate::ast::ThematicRole, Term<'a>)>,
987) -> &'a LogicExpr<'a> {
988    match expr {
989        LogicExpr::Quantifier {
990            kind: QuantifierKind::Existential,
991            variable,
992            body,
993            ..
994        } if *variable == ctx.quantifier_var => {
995            if let LogicExpr::BinaryOp { right, .. } = body {
996                replace_theme_with_intension(right, ctx, expr_arena, term_arena, role_arena)
997            } else {
998                expr
999            }
1000        }
1001        _ => expr,
1002    }
1003}
1004
1005fn replace_theme_with_intension<'a>(
1006    expr: &'a LogicExpr<'a>,
1007    ctx: &IntensionalContext,
1008    expr_arena: &'a Arena<LogicExpr<'a>>,
1009    term_arena: &'a Arena<Term<'a>>,
1010    role_arena: &'a Arena<(crate::ast::ThematicRole, Term<'a>)>,
1011) -> &'a LogicExpr<'a> {
1012    match expr {
1013        LogicExpr::Quantifier {
1014            kind,
1015            variable,
1016            body,
1017            island_id,
1018        } => {
1019            let new_body =
1020                replace_theme_with_intension(body, ctx, expr_arena, term_arena, role_arena);
1021            expr_arena.alloc(LogicExpr::Quantifier {
1022                kind: *kind,
1023                variable: *variable,
1024                body: new_body,
1025                island_id: *island_id,
1026            })
1027        }
1028        LogicExpr::BinaryOp { left, op, right } => {
1029            let new_left =
1030                replace_theme_with_intension(left, ctx, expr_arena, term_arena, role_arena);
1031            let new_right =
1032                replace_theme_with_intension(right, ctx, expr_arena, term_arena, role_arena);
1033            expr_arena.alloc(LogicExpr::BinaryOp {
1034                left: new_left,
1035                op: op.clone(),
1036                right: new_right,
1037            })
1038        }
1039        LogicExpr::NeoEvent(data) => {
1040            let new_roles: Vec<_> = data
1041                .roles
1042                .iter()
1043                .map(|(role, term)| {
1044                    if matches!(role, crate::ast::ThematicRole::Theme) {
1045                        if let Term::Variable(v) = term {
1046                            if *v == ctx.quantifier_var {
1047                                return (*role, Term::Intension(ctx.restrictor));
1048                            }
1049                        }
1050                    }
1051                    (*role, clone_term(term, term_arena))
1052                })
1053                .collect();
1054
1055            expr_arena.alloc(LogicExpr::NeoEvent(Box::new(crate::ast::NeoEventData {
1056                event_var: data.event_var,
1057                verb: data.verb,
1058                roles: role_arena.alloc_slice(new_roles),
1059                modifiers: data.modifiers,
1060                suppress_existential: false,
1061                world: None,
1062            })))
1063        }
1064        LogicExpr::Predicate { name, args, .. } => {
1065            let new_args: Vec<_> = args
1066                .iter()
1067                .map(|arg| {
1068                    if let Term::Variable(v) = arg {
1069                        if *v == ctx.quantifier_var {
1070                            return Term::Intension(ctx.restrictor);
1071                        }
1072                    }
1073                    clone_term(arg, term_arena)
1074                })
1075                .collect();
1076
1077            expr_arena.alloc(LogicExpr::Predicate {
1078                name: *name,
1079                args: term_arena.alloc_slice(new_args),
1080                world: None,
1081            })
1082        }
1083        _ => expr,
1084    }
1085}
1086
1087pub fn enumerate_intensional_readings<'a>(
1088    expr: &'a LogicExpr<'a>,
1089    interner: &mut Interner,
1090    expr_arena: &'a Arena<LogicExpr<'a>>,
1091    term_arena: &'a Arena<Term<'a>>,
1092    role_arena: &'a Arena<(crate::ast::ThematicRole, Term<'a>)>,
1093) -> Vec<&'a LogicExpr<'a>> {
1094    // Check if expression already has intensional terms (de dicto from parser)
1095    if let Some(de_re) =
1096        build_de_re_from_de_dicto(expr, interner, expr_arena, term_arena, role_arena)
1097    {
1098        // Return both: de re first (existential), de dicto second (intension)
1099        return vec![de_re, expr];
1100    }
1101
1102    // Clausal attitude complement with an embedded existential
1103    // ("believes ⟨∃x(Spy(x) ∧ Exist(x))⟩"): the de re reading raises the
1104    // existential over the attitude — ∃x(Spy(x) ∧ Believe(s, ⟨Exist(x)⟩)).
1105    if let Some(de_re) = raise_existential_from_proposition(expr, expr_arena, term_arena) {
1106        return vec![expr, de_re];
1107    }
1108
1109    // Original logic: check for de re that can be converted to de dicto
1110    if let Some(ctx) = find_opaque_verb_context(expr, interner) {
1111        let de_dicto = build_de_dicto_reading(expr, &ctx, expr_arena, term_arena, role_arena);
1112        vec![expr, de_dicto]
1113    } else {
1114        vec![expr]
1115    }
1116}
1117
1118/// De re quantifier raising out of a clausal attitude complement:
1119/// `V(s, ⟨∃x(R(x) ∧ P(x))⟩)` → `∃x(R(x) ∧ V(s, ⟨P(x)⟩))`. A `Temporal`
1120/// wrapper on the attitude stays on the attitude.
1121fn raise_existential_from_proposition<'a>(
1122    expr: &'a LogicExpr<'a>,
1123    expr_arena: &'a Arena<LogicExpr<'a>>,
1124    term_arena: &'a Arena<Term<'a>>,
1125) -> Option<&'a LogicExpr<'a>> {
1126    use crate::token::TokenType;
1127
1128    let (temporal_op, attitude) = match expr {
1129        LogicExpr::Temporal { operator, body } => (Some(*operator), *body),
1130        other => (None, other),
1131    };
1132
1133    let LogicExpr::Predicate { name, args, world } = attitude else {
1134        return None;
1135    };
1136    if args.len() != 2 {
1137        return None;
1138    }
1139    let Term::Proposition(LogicExpr::Quantifier {
1140        kind: crate::ast::QuantifierKind::Existential,
1141        variable,
1142        body,
1143        island_id,
1144    }) = &args[1]
1145    else {
1146        return None;
1147    };
1148    let LogicExpr::BinaryOp {
1149        left: restriction,
1150        op: TokenType::And,
1151        right: inner,
1152    } = body
1153    else {
1154        return None;
1155    };
1156
1157    let raised_attitude = expr_arena.alloc(LogicExpr::Predicate {
1158        name: *name,
1159        args: term_arena.alloc_slice([args[0].clone(), Term::Proposition(inner)]),
1160        world: world.clone(),
1161    });
1162    let raised_attitude = match temporal_op {
1163        Some(operator) => expr_arena.alloc(LogicExpr::Temporal {
1164            operator,
1165            body: raised_attitude,
1166        }),
1167        None => raised_attitude,
1168    };
1169    let raised_body = expr_arena.alloc(LogicExpr::BinaryOp {
1170        left: restriction,
1171        op: TokenType::And,
1172        right: raised_attitude,
1173    });
1174    Some(expr_arena.alloc(LogicExpr::Quantifier {
1175        kind: crate::ast::QuantifierKind::Existential,
1176        variable: *variable,
1177        body: raised_body,
1178        island_id: *island_id,
1179    }))
1180}
1181
1182fn build_de_re_from_de_dicto<'a>(
1183    expr: &'a LogicExpr<'a>,
1184    interner: &mut Interner,
1185    expr_arena: &'a Arena<LogicExpr<'a>>,
1186    term_arena: &'a Arena<Term<'a>>,
1187    role_arena: &'a Arena<(crate::ast::ThematicRole, Term<'a>)>,
1188) -> Option<&'a LogicExpr<'a>> {
1189    // Find Term::Intension in NeoEvent themes and expand to existential
1190    match expr {
1191        LogicExpr::NeoEvent(data) => {
1192            // Check if any role has an Intension term
1193            for (role, term) in data.roles.iter() {
1194                if matches!(role, crate::ast::ThematicRole::Theme) {
1195                    if let Term::Intension(noun) = term {
1196                        // Build de re: ∃x(Noun(x) ∧ Event[Theme=x])
1197                        let var = interner.intern("x");
1198
1199                        // Build noun predicate: Noun(x)
1200                        let noun_pred = expr_arena.alloc(LogicExpr::Predicate {
1201                            name: *noun,
1202                            args: term_arena.alloc_slice([Term::Variable(var)]),
1203                            world: None,
1204                        });
1205
1206                        // Build new roles with variable instead of intension
1207                        let new_roles: Vec<_> = data
1208                            .roles
1209                            .iter()
1210                            .map(|(r, t)| {
1211                                if matches!(r, crate::ast::ThematicRole::Theme) {
1212                                    (*r, Term::Variable(var))
1213                                } else {
1214                                    (*r, t.clone())
1215                                }
1216                            })
1217                            .collect();
1218
1219                        let new_event = expr_arena.alloc(LogicExpr::NeoEvent(Box::new(
1220                            crate::ast::NeoEventData {
1221                                event_var: data.event_var,
1222                                verb: data.verb,
1223                                roles: role_arena.alloc_slice(new_roles),
1224                                modifiers: data.modifiers,
1225                                suppress_existential: false,
1226                                world: None,
1227                            },
1228                        )));
1229
1230                        // Build: ∃x(Noun(x) ∧ Event)
1231                        let body = expr_arena.alloc(LogicExpr::BinaryOp {
1232                            left: noun_pred,
1233                            op: crate::token::TokenType::And,
1234                            right: new_event,
1235                        });
1236
1237                        return Some(expr_arena.alloc(LogicExpr::Quantifier {
1238                            kind: crate::ast::QuantifierKind::Existential,
1239                            variable: var,
1240                            body,
1241                            island_id: 0,
1242                        }));
1243                    }
1244                }
1245            }
1246            None
1247        }
1248        _ => None,
1249    }
1250}
1251
1252#[cfg(test)]
1253#[path = "../../logicaffeine_tests/unit/logicaffeine_language/lambda/tests.rs"]
1254mod tests;