Skip to main content

logicaffeine_language/semantics/
kripke.rs

1//! Kripke Semantics Lowering Pass
2//!
3//! Transforms modal operators into explicit possible world semantics:
4//! - Diamond P (force <= 0.5) → Exists w'(Accessible(w, w') And P(w'))
5//! - Box P (force > 0.5) → ForAll w'(Accessible(w, w') Implies P(w'))
6
7use crate::ast::{LogicExpr, ModalDomain, ModalVector, NeoEventData, QuantifierKind, Term};
8use crate::token::TokenType;
9use logicaffeine_base::Arena;
10use logicaffeine_base::{Interner, Symbol};
11
12/// Context for tracking world variables during Kripke lowering.
13///
14/// For hardware verification, `clock_counter` tracks discrete timesteps
15/// and `domain_hint` disambiguates temporal vs modal lowering when
16/// the context is ambiguous.
17pub struct KripkeContext {
18    world_counter: u32,
19    current_world: Symbol,
20    /// Discrete timestep counter for hardware clock cycles.
21    /// Incremented when generating Next_Temporal worlds.
22    clock_counter: u32,
23    /// Hint for the current modal domain being lowered.
24    /// Set to `Some(Temporal)` when processing temporal operators,
25    /// enabling domain-aware disambiguation.
26    domain_hint: Option<ModalDomain>,
27}
28
29impl KripkeContext {
30    pub fn new(interner: &mut Interner) -> Self {
31        Self {
32            world_counter: 0,
33            current_world: interner.intern("w0"),
34            clock_counter: 0,
35            domain_hint: None,
36        }
37    }
38
39    pub fn fresh_world(&mut self, interner: &mut Interner) -> Symbol {
40        self.world_counter += 1;
41        interner.intern(&format!("w{}", self.world_counter))
42    }
43
44    /// Get the current clock counter value (discrete timestep).
45    pub fn clock_counter(&self) -> u32 {
46        self.clock_counter
47    }
48
49    /// Get the current domain hint.
50    pub fn domain_hint(&self) -> Option<ModalDomain> {
51        self.domain_hint
52    }
53
54    /// Advance the clock counter by one tick (for Next_Temporal).
55    fn tick_clock(&mut self) {
56        self.clock_counter += 1;
57    }
58
59    /// Set the domain hint for the current lowering context.
60    fn set_domain_hint(&mut self, domain: ModalDomain) {
61        self.domain_hint = Some(domain);
62    }
63
64    /// Clear the domain hint.
65    fn clear_domain_hint(&mut self) {
66        self.domain_hint = None;
67    }
68}
69
70/// Apply Kripke lowering to transform modal operators into explicit world quantification.
71///
72/// This transforms surface modal operators (`◇`, `□`) into explicit First-Order Logic
73/// with possible world semantics, enabling Z3 verification.
74///
75/// ## Example
76/// Surface: `◇Fly(x)` (John can fly)
77/// Deep: `∃w'(Accessible(w₀, w') ∧ Fly(x, w'))` (There exists an accessible world where John flies)
78pub fn apply_kripke_lowering<'a>(
79    expr: &'a LogicExpr<'a>,
80    expr_arena: &'a Arena<LogicExpr<'a>>,
81    term_arena: &'a Arena<Term<'a>>,
82    interner: &mut Interner,
83) -> &'a LogicExpr<'a> {
84    let mut ctx = KripkeContext::new(interner);
85    lower_expr(expr, &mut ctx, expr_arena, term_arena, interner)
86}
87
88fn lower_expr<'a>(
89    expr: &'a LogicExpr<'a>,
90    ctx: &mut KripkeContext,
91    expr_arena: &'a Arena<LogicExpr<'a>>,
92    term_arena: &'a Arena<Term<'a>>,
93    interner: &mut Interner,
94) -> &'a LogicExpr<'a> {
95    match expr {
96        LogicExpr::Modal { vector, operand } => {
97            lower_modal(vector, operand, ctx, expr_arena, term_arena, interner)
98        }
99
100        LogicExpr::Predicate { name, args, world } => {
101            if world.is_none() {
102                // Add current world to predicate
103                expr_arena.alloc(LogicExpr::Predicate {
104                    name: *name,
105                    args: *args,
106                    world: Some(ctx.current_world),
107                })
108            } else {
109                expr
110            }
111        }
112
113        LogicExpr::Quantifier {
114            kind,
115            variable,
116            body,
117            island_id,
118        } => {
119            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
120            expr_arena.alloc(LogicExpr::Quantifier {
121                kind: *kind,
122                variable: *variable,
123                body: new_body,
124                island_id: *island_id,
125            })
126        }
127
128        LogicExpr::BinaryOp { left, op, right } => {
129            let new_left = lower_expr(left, ctx, expr_arena, term_arena, interner);
130            let new_right = lower_expr(right, ctx, expr_arena, term_arena, interner);
131            expr_arena.alloc(LogicExpr::BinaryOp {
132                left: new_left,
133                op: op.clone(),
134                right: new_right,
135            })
136        }
137
138        LogicExpr::UnaryOp { op, operand } => {
139            let new_operand = lower_expr(operand, ctx, expr_arena, term_arena, interner);
140            expr_arena.alloc(LogicExpr::UnaryOp {
141                op: op.clone(),
142                operand: new_operand,
143            })
144        }
145
146        LogicExpr::NeoEvent(data) => {
147            // Set the world on the event to the current world
148            if data.world.is_none() {
149                expr_arena.alloc(LogicExpr::NeoEvent(Box::new(NeoEventData {
150                    event_var: data.event_var,
151                    verb: data.verb,
152                    roles: data.roles,
153                    modifiers: data.modifiers,
154                    suppress_existential: data.suppress_existential,
155                    world: Some(ctx.current_world),
156                })))
157            } else {
158                expr
159            }
160        }
161
162        LogicExpr::Temporal { operator, body } => {
163            use crate::ast::logic::TemporalOperator;
164            // Set domain hint for temporal lowering
165            ctx.set_domain_hint(ModalDomain::Temporal);
166            let result = match operator {
167                // LTL operators → Kripke world quantification
168                TemporalOperator::Always => {
169                    // G(φ) → ∀w'(Accessible_Temporal(w, w') → φ(w'))
170                    lower_temporal_unary(
171                        body,
172                        ctx,
173                        expr_arena,
174                        term_arena,
175                        interner,
176                        "Accessible_Temporal",
177                        true,
178                    )
179                }
180                TemporalOperator::Eventually => {
181                    // F(φ) → ∃w'(Reachable_Temporal(w, w') ∧ φ(w'))
182                    lower_temporal_unary(
183                        body,
184                        ctx,
185                        expr_arena,
186                        term_arena,
187                        interner,
188                        "Reachable_Temporal",
189                        false,
190                    )
191                }
192                TemporalOperator::BoundedEventually(n) => {
193                    // F≤n(φ) — preserve bound for SVA synthesis (##[0:n])
194                    let lowered_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
195                    expr_arena.alloc(LogicExpr::Temporal {
196                        operator: TemporalOperator::BoundedEventually(*n),
197                        body: lowered_body,
198                    })
199                }
200                TemporalOperator::Next => {
201                    // X(φ) → ∀w'(Next_Temporal(w, w') → φ(w'))
202                    ctx.tick_clock();
203                    lower_temporal_unary(
204                        body,
205                        ctx,
206                        expr_arena,
207                        term_arena,
208                        interner,
209                        "Next_Temporal",
210                        true,
211                    )
212                }
213                // Priorian tense operators — pass through (linguistic, not hardware)
214                TemporalOperator::Past | TemporalOperator::Future => {
215                    let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
216                    expr_arena.alloc(LogicExpr::Temporal {
217                        operator: *operator,
218                        body: new_body,
219                    })
220                }
221            };
222            ctx.clear_domain_hint();
223            result
224        }
225
226        LogicExpr::TemporalBinary {
227            operator,
228            left,
229            right,
230        } => {
231            // φ U ψ → ψ(w) ∨ (φ(w) ∧ ∃w'(Next_Temporal(w,w') ∧ (φ U ψ)(w')))
232            // For now: lower both operands with world threading
233            let new_left = lower_expr(left, ctx, expr_arena, term_arena, interner);
234            let new_right = lower_expr(right, ctx, expr_arena, term_arena, interner);
235
236            // Generate Next_Temporal accessibility for the recursive step
237            let source_world = ctx.current_world;
238            let target_world = ctx.fresh_world(interner);
239            let next_name = interner.intern("Next_Temporal");
240            let accessibility = expr_arena.alloc(LogicExpr::Predicate {
241                name: next_name,
242                args: term_arena
243                    .alloc_slice([Term::Variable(source_world), Term::Variable(target_world)]),
244                world: None,
245            });
246
247            // Build: right(w) ∨ (left(w) ∧ ∃w'(Next_Temporal(w,w') ∧ ...))
248            let recursive_body = expr_arena.alloc(LogicExpr::BinaryOp {
249                left: accessibility,
250                op: crate::token::TokenType::And,
251                right: expr_arena.alloc(LogicExpr::TemporalBinary {
252                    operator: *operator,
253                    left: new_left,
254                    right: new_right,
255                }),
256            });
257            let existential = expr_arena.alloc(LogicExpr::Quantifier {
258                kind: QuantifierKind::Existential,
259                variable: target_world,
260                body: recursive_body,
261                island_id: 0,
262            });
263            let left_and_next = expr_arena.alloc(LogicExpr::BinaryOp {
264                left: new_left,
265                op: crate::token::TokenType::And,
266                right: existential,
267            });
268            expr_arena.alloc(LogicExpr::BinaryOp {
269                left: new_right,
270                op: crate::token::TokenType::Or,
271                right: left_and_next,
272            })
273        }
274
275        LogicExpr::Aspectual { operator, body } => {
276            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
277            expr_arena.alloc(LogicExpr::Aspectual {
278                operator: *operator,
279                body: new_body,
280            })
281        }
282
283        LogicExpr::Voice { operator, body } => {
284            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
285            expr_arena.alloc(LogicExpr::Voice {
286                operator: *operator,
287                body: new_body,
288            })
289        }
290
291        LogicExpr::Lambda { variable, body } => {
292            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
293            expr_arena.alloc(LogicExpr::Lambda {
294                variable: *variable,
295                body: new_body,
296            })
297        }
298
299        LogicExpr::App { function, argument } => {
300            let new_function = lower_expr(function, ctx, expr_arena, term_arena, interner);
301            let new_argument = lower_expr(argument, ctx, expr_arena, term_arena, interner);
302            expr_arena.alloc(LogicExpr::App {
303                function: new_function,
304                argument: new_argument,
305            })
306        }
307
308        LogicExpr::Intensional { operator, content } => {
309            let new_content = lower_expr(content, ctx, expr_arena, term_arena, interner);
310            expr_arena.alloc(LogicExpr::Intensional {
311                operator: *operator,
312                content: new_content,
313            })
314        }
315
316        LogicExpr::Control {
317            verb,
318            subject,
319            object,
320            infinitive,
321        } => {
322            let new_infinitive = lower_expr(infinitive, ctx, expr_arena, term_arena, interner);
323            expr_arena.alloc(LogicExpr::Control {
324                verb: *verb,
325                subject: *subject,
326                object: *object,
327                infinitive: new_infinitive,
328            })
329        }
330
331        LogicExpr::Scopal { operator, body } => {
332            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
333            expr_arena.alloc(LogicExpr::Scopal {
334                operator: *operator,
335                body: new_body,
336            })
337        }
338
339        LogicExpr::Question { wh_variable, body } => {
340            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
341            expr_arena.alloc(LogicExpr::Question {
342                wh_variable: *wh_variable,
343                body: new_body,
344            })
345        }
346
347        LogicExpr::YesNoQuestion { body } => {
348            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
349            expr_arena.alloc(LogicExpr::YesNoQuestion { body: new_body })
350        }
351
352        LogicExpr::Focus {
353            kind,
354            focused,
355            scope,
356        } => {
357            let new_scope = lower_expr(scope, ctx, expr_arena, term_arena, interner);
358            expr_arena.alloc(LogicExpr::Focus {
359                kind: *kind,
360                focused: *focused,
361                scope: new_scope,
362            })
363        }
364
365        LogicExpr::Distributive { predicate } => {
366            let new_predicate = lower_expr(predicate, ctx, expr_arena, term_arena, interner);
367            expr_arena.alloc(LogicExpr::Distributive {
368                predicate: new_predicate,
369            })
370        }
371
372        LogicExpr::Counterfactual {
373            antecedent,
374            consequent,
375        } => {
376            let new_antecedent = lower_expr(antecedent, ctx, expr_arena, term_arena, interner);
377            let new_consequent = lower_expr(consequent, ctx, expr_arena, term_arena, interner);
378            expr_arena.alloc(LogicExpr::Counterfactual {
379                antecedent: new_antecedent,
380                consequent: new_consequent,
381            })
382        }
383
384        LogicExpr::Event { predicate, adverbs } => {
385            let new_predicate = lower_expr(predicate, ctx, expr_arena, term_arena, interner);
386            expr_arena.alloc(LogicExpr::Event {
387                predicate: new_predicate,
388                adverbs: *adverbs,
389            })
390        }
391
392        LogicExpr::Imperative { action } => {
393            let new_action = lower_expr(action, ctx, expr_arena, term_arena, interner);
394            expr_arena.alloc(LogicExpr::Imperative { action: new_action })
395        }
396        LogicExpr::Exclamative { degree_var, body } => {
397            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
398            expr_arena.alloc(LogicExpr::Exclamative {
399                degree_var: *degree_var,
400                body: new_body,
401            })
402        }
403        LogicExpr::Optative { wish } => {
404            let new_wish = lower_expr(wish, ctx, expr_arena, term_arena, interner);
405            expr_arena.alloc(LogicExpr::Optative { wish: new_wish })
406        }
407        LogicExpr::Implicature {
408            assertion,
409            implicature,
410        } => {
411            let new_assertion = lower_expr(assertion, ctx, expr_arena, term_arena, interner);
412            let new_implicature = lower_expr(implicature, ctx, expr_arena, term_arena, interner);
413            expr_arena.alloc(LogicExpr::Implicature {
414                assertion: new_assertion,
415                implicature: new_implicature,
416            })
417        }
418
419        LogicExpr::Causal { effect, cause } => {
420            let new_effect = lower_expr(effect, ctx, expr_arena, term_arena, interner);
421            let new_cause = lower_expr(cause, ctx, expr_arena, term_arena, interner);
422            expr_arena.alloc(LogicExpr::Causal {
423                effect: new_effect,
424                cause: new_cause,
425            })
426        }
427
428        LogicExpr::Concessive { main, concession } => {
429            let new_main = lower_expr(main, ctx, expr_arena, term_arena, interner);
430            let new_concession = lower_expr(concession, ctx, expr_arena, term_arena, interner);
431            expr_arena.alloc(LogicExpr::Concessive {
432                main: new_main,
433                concession: new_concession,
434            })
435        }
436
437        LogicExpr::Presupposition {
438            assertion,
439            presupposition,
440        } => {
441            let new_assertion = lower_expr(assertion, ctx, expr_arena, term_arena, interner);
442            let new_presupposition =
443                lower_expr(presupposition, ctx, expr_arena, term_arena, interner);
444            expr_arena.alloc(LogicExpr::Presupposition {
445                assertion: new_assertion,
446                presupposition: new_presupposition,
447            })
448        }
449
450        LogicExpr::TemporalAnchor { anchor, body } => {
451            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
452            expr_arena.alloc(LogicExpr::TemporalAnchor {
453                anchor: *anchor,
454                body: new_body,
455            })
456        }
457
458        LogicExpr::GroupQuantifier {
459            group_var,
460            count,
461            member_var,
462            restriction,
463            body,
464        } => {
465            let new_restriction = lower_expr(restriction, ctx, expr_arena, term_arena, interner);
466            let new_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
467            expr_arena.alloc(LogicExpr::GroupQuantifier {
468                group_var: *group_var,
469                count: *count,
470                member_var: *member_var,
471                restriction: new_restriction,
472                body: new_body,
473            })
474        }
475
476        // Leaf nodes that don't need transformation
477        LogicExpr::Identity { .. }
478        | LogicExpr::Metaphor { .. }
479        | LogicExpr::Categorical(_)
480        | LogicExpr::Relation(_)
481        | LogicExpr::Atom(_)
482        | LogicExpr::Superlative { .. }
483        | LogicExpr::Comparative { .. }
484        | LogicExpr::SpeechAct { .. } => expr,
485    }
486}
487
488fn lower_modal<'a>(
489    vector: &ModalVector,
490    operand: &'a LogicExpr<'a>,
491    ctx: &mut KripkeContext,
492    expr_arena: &'a Arena<LogicExpr<'a>>,
493    term_arena: &'a Arena<Term<'a>>,
494    interner: &mut Interner,
495) -> &'a LogicExpr<'a> {
496    let source_world = ctx.current_world;
497    let target_world = ctx.fresh_world(interner);
498
499    // Lower operand with new current world
500    let old_world = ctx.current_world;
501    ctx.current_world = target_world;
502    let lowered_operand = lower_expr(operand, ctx, expr_arena, term_arena, interner);
503    ctx.current_world = old_world;
504
505    // Create accessibility predicate based on modal domain
506    let access_name = match vector.domain {
507        ModalDomain::Alethic => interner.intern("Accessible_Alethic"),
508        ModalDomain::Deontic => interner.intern("Accessible_Deontic"),
509        ModalDomain::Temporal => interner.intern("Accessible_Temporal"),
510    };
511
512    let accessibility = expr_arena.alloc(LogicExpr::Predicate {
513        name: access_name,
514        args: term_arena.alloc_slice([Term::Variable(source_world), Term::Variable(target_world)]),
515        world: None, // Accessibility predicate is a meta-level relation
516    });
517
518    if vector.force > 0.5 {
519        // Necessity (Box): ForAll w'(Accessible(w, w') -> P(w'))
520        let implication = expr_arena.alloc(LogicExpr::BinaryOp {
521            left: accessibility,
522            op: TokenType::Implies,
523            right: lowered_operand,
524        });
525        expr_arena.alloc(LogicExpr::Quantifier {
526            kind: QuantifierKind::Universal,
527            variable: target_world,
528            body: implication,
529            island_id: 0,
530        })
531    } else if vector.force <= 0.0 {
532        // Impossibility (force 0, e.g. "cannot" = ¬◇ = □¬):
533        // ForAll w'(Accessible(w, w') -> ¬P(w')). Lowering this as a Diamond
534        // possibility would assert the LOGICAL OPPOSITE (that P is possible).
535        let negated = expr_arena.alloc(LogicExpr::UnaryOp {
536            op: TokenType::Not,
537            operand: lowered_operand,
538        });
539        let implication = expr_arena.alloc(LogicExpr::BinaryOp {
540            left: accessibility,
541            op: TokenType::Implies,
542            right: negated,
543        });
544        expr_arena.alloc(LogicExpr::Quantifier {
545            kind: QuantifierKind::Universal,
546            variable: target_world,
547            body: implication,
548            island_id: 0,
549        })
550    } else {
551        // Possibility (Diamond): Exists w'(Accessible(w, w') ∧ P(w'))
552        let conjunction = expr_arena.alloc(LogicExpr::BinaryOp {
553            left: accessibility,
554            op: TokenType::And,
555            right: lowered_operand,
556        });
557        expr_arena.alloc(LogicExpr::Quantifier {
558            kind: QuantifierKind::Existential,
559            variable: target_world,
560            body: conjunction,
561            island_id: 0,
562        })
563    }
564}
565
566/// Lower a unary LTL temporal operator into Kripke world quantification.
567///
568/// `is_universal`: true for G/X (∀w'), false for F (∃w')
569fn lower_temporal_unary<'a>(
570    body: &'a LogicExpr<'a>,
571    ctx: &mut KripkeContext,
572    expr_arena: &'a Arena<LogicExpr<'a>>,
573    term_arena: &'a Arena<Term<'a>>,
574    interner: &mut Interner,
575    predicate_name: &str,
576    is_universal: bool,
577) -> &'a LogicExpr<'a> {
578    let source_world = ctx.current_world;
579    let target_world = ctx.fresh_world(interner);
580
581    // Lower body with new current world
582    let old_world = ctx.current_world;
583    ctx.current_world = target_world;
584    let lowered_body = lower_expr(body, ctx, expr_arena, term_arena, interner);
585    ctx.current_world = old_world;
586
587    // Create temporal accessibility predicate
588    let access_name = interner.intern(predicate_name);
589    let accessibility = expr_arena.alloc(LogicExpr::Predicate {
590        name: access_name,
591        args: term_arena.alloc_slice([Term::Variable(source_world), Term::Variable(target_world)]),
592        world: None,
593    });
594
595    if is_universal {
596        // G/X: ∀w'(Accessible_Temporal(w, w') → φ(w'))
597        let implication = expr_arena.alloc(LogicExpr::BinaryOp {
598            left: accessibility,
599            op: TokenType::Implies,
600            right: lowered_body,
601        });
602        expr_arena.alloc(LogicExpr::Quantifier {
603            kind: QuantifierKind::Universal,
604            variable: target_world,
605            body: implication,
606            island_id: 0,
607        })
608    } else {
609        // F: ∃w'(Reachable_Temporal(w, w') ∧ φ(w'))
610        let conjunction = expr_arena.alloc(LogicExpr::BinaryOp {
611            left: accessibility,
612            op: TokenType::And,
613            right: lowered_body,
614        });
615        expr_arena.alloc(LogicExpr::Quantifier {
616            kind: QuantifierKind::Existential,
617            variable: target_world,
618            body: conjunction,
619            island_id: 0,
620        })
621    }
622}