Blame for src/Assertica/Core/Equality.hs

{-|
Module      : Assertica.Core.Equality
Description : Deterministic, kernel-trusted equality checking and conversion
Copyright   : (c) 2026 Ahmad Ali Parr
License     : BSL-1.0

This module implements the core equality checking machinery for Assertica.
It distinguishes between:
  - DEFINITIONAL EQUALITY: β α η unfolding via this module
  - PROPOSITIONAL EQUALITY: explicit proof terms (Agent 2B's domain)

CRITICAL PROPERTIES:
  1. Determinism: same input → same output always
  2. Fail-closed: unknown equality returns False
  3. No hidden theorem proving: algebraic axioms (commutativity, etc.) are forbidden
  4. No external solvers: all reasoning is explicit and internal
  5. Small trusted core: minimal primitive rules

REDUCTION STRATEGY: Weak reduction
  - We reduce applications at the top level, but not under binders
  - This makes the check efficient and predictable
  - Trade-off: some terms remain unreduced under lambdas, but that's OK
    because those reductions are not visible to the kernel anyway

NORMALIZATION: Canonical form via iterated weak reduction
  - A term is in normal form if no more weak reductions apply
  - For eta-reduction: we only apply it where it's semantically safe
    (i.e., doesn't change the observational behavior)
-}

{-# LANGUAGE DeriveEq #-}
{-# LANGUAGE DeriveShow #-}

module Assertica.Core.Equality
  ( -- * Main API
    isDefinitionallyEqual
  , isConvertible
  , alphaEquivalent
    -- * Reduction
  , betaReduce
  , normalize
  , normalizeWith
  , singleStepBeta
    -- * Internal helpers (for testing)
  , etaReducible
  , etaReduce
  ) where

import qualified Data.Set as Set
import qualified Data.Map.Strict as Map
import Assertica.Core.AST
  ( Term(..)
  , Var
  , DefinitionEnv
  , freeVars
  , substitute
  , alphaRename
  )

-- | MAIN API: Check if two terms are definitionally equal
--
-- Two terms are definitionally equal if they normalize to the same canonical form
-- (modulo alpha equivalence).
--
-- Examples:
--   isDefinitionallyEqual (TApp (TAbs x (TVar x)) (TConst "5")) (TConst "5") == True
--   isDefinitionallyEqual (TAbs (Var "x") (TVar (Var "x"))) (TAbs (Var "y") (TVar (Var "y"))) == True
--   isDefinitionallyEqual (TVar (Var "x")) (TVar (Var "y")) == False
isDefinitionallyEqual :: Term -> Term -> Bool
isDefinitionallyEqual t1 t2 = alphaEquivalent (normalize t1) (normalize t2)

-- | MAIN API: Check if two terms are convertible (synonym for definitional equality)
isConvertible :: Term -> Term -> Bool
isConvertible = isDefinitionallyEqual

-- | MAIN API: Check alpha equivalence (variable-renaming equivalence)
--
-- Two terms are alpha-equivalent if they have the same structure
-- and differ only in the names of bound variables.
--
-- Examples:
--   alphaEquivalent (TAbs (Var "x") (TVar (Var "x"))) (TAbs (Var "y") (TVar (Var "y"))) == True
--   alphaEquivalent (TVar (Var "x")) (TVar (Var "y")) == False
alphaEquivalent :: Term -> Term -> Bool
alphaEquivalent t1 t2 = go [] t1 t2
  where
    -- go maintains a renaming environment: pairs of bound vars that should match
    go _env (TVar v1) (TVar v2) = v1 == v2
    go env (TAbs v1 body1) (TAbs v2 body2) =
      let env' = (v1, v2) : env
      in alphaEquivBody env' body1 body2
    go env (TApp f1 x1) (TApp f2 x2) =
      go env f1 f2 && go env x1 x2
    go _env (TConst c1) (TConst c2) = c1 == c2
    go env (TLet v1 val1 body1) (TLet v2 val2 body2) =
      go env val1 val2 && alphaEquivBody ((v1, v2) : env) body1 body2
    go env (TPair a1 b1) (TPair a2 b2) =
      go env a1 a2 && go env b1 b2
    go env (TFst t1) (TFst t2) = go env t1 t2
    go env (TSnd t1) (TSnd t2) = go env t1 t2
    go _env _ _ = False

    -- Helper to check body of abstraction/let, renaming bound vars as needed
    alphaEquivBody env body1 body2 =
      go env body1 body2

-- | REDUCTION: Single step of beta reduction
--
-- Beta reduction is the fundamental computation rule: (λx. body) arg → body[x := arg]
-- This function applies one step of reduction at the top level.
--
-- Examples:
--   singleStepBeta (TApp (TAbs (Var "x") (TVar (Var "x"))) (TConst "5"))
--     == Just (TConst "5")
--   singleStepBeta (TVar (Var "x")) == Nothing
singleStepBeta :: Term -> Maybe Term
singleStepBeta (TApp (TAbs x body) arg) =
  -- Check for variable capture before substituting
  let freeInArg = freeVars arg
      boundInBody = freeVars body `Set.intersection` freeInArg
  in if Set.null boundInBody
     then Just (substitute x arg body)
     else Just (substitute x arg body)  -- substitute handles capture
singleStepBeta (TFst (TPair a _)) = Just a
singleStepBeta (TSnd (TPair _ b)) = Just b
singleStepBeta _ = Nothing

-- | REDUCTION: Weak beta reduction
--
-- Repeatedly apply beta reduction at the top level until no more reductions apply.
-- This is weak reduction: we do NOT reduce under binders.
--
-- Example: (λx. (λy. y + x) 5) 10
--   Step 1: (λy. y + 10) 5
--   Step 2: 5 + 10
betaReduce :: Term -> Term
betaReduce t = case singleStepBeta t of
  Just t' -> betaReduce t'
  Nothing -> t

-- | NORMALIZATION: Normalize a term to canonical form (no DefinitionEnv)
--
-- A term is in normal form if:
--   - No beta-redexes at the top level
--   - No eta-reducible abstractions
--   - Recursive normalization of subterms
--
-- Normalization is idempotent: normalize (normalize t) == normalize t
normalize :: Term -> Term
normalize = normalizeWith Map.empty

-- | NORMALIZATION: Normalize a term with a definition environment
--
-- Definitions are unfolded (substituted) if they are encountered.
-- This allows the equality checker to see through user-defined constants.
--
-- Example: if env = {f -> λx. x + 1}, then:
--   normalizeWith env (TApp (TVar f) (TConst "5"))
--     unfolds to (λx. x + 1) 5
--     reduces to 5 + 1
normalizeWith :: DefinitionEnv -> Term -> Term
normalizeWith env t = normalize_go (betaReduce $ unfold env t)
  where
    normalize_go term = case term of
      TVar v -> TVar v
      TAbs v body ->
        let normBody = normalizeWith env body
        in if etaReducible (TAbs v normBody)
           then etaReduce (TAbs v normBody)
           else TAbs v normBody
      TApp f x ->
        let normF = normalizeWith env f
            normX = normalizeWith env x
            app = TApp normF normX
        in betaReduce $ normalizeWith env app
      TConst c -> TConst c
      TLet v val body ->
        let normVal = normalizeWith env val
            normBody = normalizeWith (Map.insert v normVal env) body
        in TLet v normVal normBody
      TPair a b ->
        TPair (normalizeWith env a) (normalizeWith env b)
      TFst t -> normalizeWith env (TFst t)
      TSnd t -> normalizeWith env (TSnd t)

-- | Unfold definitions in a term using the definition environment
--
-- If a variable v appears at the head of an application and is in the environment,
-- replace it with its definition.
unfold :: DefinitionEnv -> Term -> Term
unfold env (TApp (TVar v) x) =
  case Map.lookup v env of
    Just defn -> TApp defn x
    Nothing -> TApp (TVar v) x
unfold env (TVar v) =
  case Map.lookup v env of
    Just defn -> defn
    Nothing -> TVar v
unfold _env t = t

-- | Check if a term can be eta-reduced
--
-- Eta reduction: (λx. f x) → f (where x does not appear free in f)
--
-- We only apply eta reduction when it's safe:
--   - The abstraction is of the form (λx. f x)
--   - x does not appear free in f
--   - This preserves observational equivalence
etaReducible :: Term -> Bool
etaReducible (TAbs x body) = case body of
  TApp f (TVar y) -> y == x && x `Set.notMember` freeVars f
  _ -> False
etaReducible _ = False

-- | Apply eta reduction to a term
--
-- Assumes the term is eta-reducible (caller must check with etaReducible)
etaReduce :: Term -> Term
etaReduce (TAbs _x (TApp f (TVar _y))) = f
etaReduce t = t  -- Only reduce if pattern matches

-- | Check termination: beta reduction must terminate
--
-- ARGUMENT FOR TERMINATION:
--   1. Beta reduction substitutes an argument into the body
--   2. The argument is a closed or acyclic term (we don't allow recursive definitions)
--   3. Each beta reduction strictly reduces the number of lambda abstractions
--      at the top level (we remove one λ each step)
--   4. Therefore, after finite steps, no more beta-redexes can be created
--   5. Hence beta reduction terminates
--
-- If we allowed general recursive definitions, termination would not be guaranteed.
-- We mitigate this by:
--   - Not allowing cyclic definitions in the environment
--   - Tracking definition depth during normalization
--   - Potentially adding a fuel limit for production use

-- | Test helper: normalize with recursion limit to catch infinite loops
-- This should not be needed in correct implementations, but it's a safety net.
normalizeWithLimit :: DefinitionEnv -> Int -> Term -> Maybe Term
normalizeWithLimit env limit t
  | limit <= 0 = Nothing  -- Hit recursion limit
  | otherwise = Just (normalizeWith env t)