Lambda Calculus Ontology

KIRETH RESEARCH - SEMANTIC LIBRARY
AI CORE -> ONTOLOGIES -> MATHEMATICAL ONTOLOGIES -> MATHEMATICAL LOGIC ONTOLOGIES
COMPUTABILITY THEORY -> LAMBDA CALCULUS ONTOLOGY

Canonical URL:
https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/lambda-calculus-ontology.html

FLOW_ALGEBRA LambdaCalculusOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN LambdaCalculusOntology := {
    LambdaCalculus,
    ComputabilityTheory,
    LambdaTerm,
    Variable,
    Abstraction,
    Application,
    BoundVariable,
    FreeVariable,
    Binding,
    Scope,
    Substitution,
    CaptureAvoidingSubstitution,
    AlphaConversion,
    BetaReduction,
    EtaReduction,
    Reduction,
    Redex,
    NormalForm,
    BetaNormalForm,
    Normalisation,
    Confluence,
    ChurchRosserTheorem,
    LambdaDefinableFunction,
    ComputableFunction,
    TuringMachine,
    RecursiveFunction,
    ChurchTuringThesis,
    ChurchEncoding,
    ChurchNumeral,
    BooleanEncoding,
    FixedPoint,
    FixedPointCombinator,
    YCombinator,
    UntypedLambdaCalculus,
    TypedLambdaCalculus
}

DEFINE ENTITY_TYPES := {
    LAMBDA_CALCULUS,
    LAMBDA_TERM,
    VARIABLE,
    ABSTRACTION,
    APPLICATION,
    BINDING,
    SUBSTITUTION,
    REDUCTION,
    REDUCTION_RULE,
    NORMAL_FORM,
    COMBINATOR,
    ENCODING,
    COMPUTABLE_FUNCTION,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    BINDS,
    HAS_SCOPE,
    HAS_BODY,
    HAS_FUNCTION,
    HAS_ARGUMENT,
    FREE_IN,
    BOUND_IN,
    SUBSTITUTES,
    REDUCES_TO,
    ALPHA_EQUIVALENT_TO,
    BETA_EQUIVALENT_TO,
    ETA_EQUIVALENT_TO,
    NORMALISES_TO,
    ENCODES,
    COMPUTES,
    EQUIVALENT_IN_COMPUTABILITY_TO,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF,
    DEPENDS_ON
}

SET LambdaCalculus.type = LAMBDA_CALCULUS
SET LambdaCalculus.context = ComputabilityTheory
SET LambdaCalculus.role =
    "represent computation through variable binding, function abstraction, application and formal reduction of lambda terms"

RULE term_variable:
    Variable(x)
    -> LambdaTerm(x)

RULE term_abstraction:
    Variable(x)
    AND LambdaTerm(M)
    -> LambdaTerm(lambda x . M)
    AND Abstraction(lambda x . M)

RULE term_application:
    LambdaTerm(M)
    AND LambdaTerm(N)
    -> LambdaTerm(M N)
    AND Application(M,N)

RULE abstraction_binding:
    Abstraction(lambda x . M)
    -> BINDS(lambda x . M,x)
    AND HAS_BODY(lambda x . M,M)

RULE application_components:
    Application(M,N)
    -> HAS_FUNCTION(M N,M)
    AND HAS_ARGUMENT(M N,N)

RULE free_variable_variable:
    FreeVariables(x) = {x}

RULE free_variable_application:
    FreeVariables(M N)
    = FreeVariables(M) UNION FreeVariables(N)

RULE free_variable_abstraction:
    FreeVariables(lambda x . M)
    = FreeVariables(M) MINUS {x}

RULE bound_variable:
    occurrence_of x within scope_of(lambda x . M)
    -> BOUND_IN(x,lambda x . M)

RULE alpha_conversion:
    Abstraction(lambda x . M)
    AND y fresh_for M
    -> ALPHA_EQUIVALENT_TO(
        lambda x . M,
        lambda y . M[x:=y]
    )

RULE beta_reduction:
    Application(
        Abstraction(lambda x . M),
        N
    )
    -> REDUCES_TO(
        (lambda x . M) N,
        M[x:=N]
    )
       USING capture_avoiding_substitution

RULE beta_redex:
    Term((lambda x . M) N)
    -> Redex((lambda x . M) N)

RULE eta_reduction:
    Term(lambda x . (M x))
    AND x NOT_MEMBER_OF FreeVariables(M)
    -> REDUCES_TO(
        lambda x . (M x),
        M
    )

RULE substitution_variable_same:
    x[x:=N] = N

RULE substitution_variable_different:
    x != y
    -> y[x:=N] = y

RULE substitution_application:
    (M1 M2)[x:=N]
    = M1[x:=N] M2[x:=N]

RULE substitution_abstraction_safe:
    y != x
    AND y NOT_MEMBER_OF FreeVariables(N)
    -> (lambda y . M)[x:=N]
       = lambda y . (M[x:=N])

RULE substitution_capture_avoidance:
    y MEMBER_OF FreeVariables(N)
    AND substitution_under(lambda y . M) required
    -> alpha_rename_bound_variable_before_substitution

RULE beta_normal_form:
    LambdaTerm(M)
    AND no_beta_redex_occurs_in M
    -> BetaNormalForm(M)

RULE normalisation:
    LambdaTerm(M)
    AND EXISTS reduction_sequence [
        M REDUCES_TO_STAR N
        AND BetaNormalForm(N)
    ]
    -> Normalises(M)

RULE Church_Rosser:
    M REDUCES_TO_STAR N1
    AND M REDUCES_TO_STAR N2
    -> EXISTS P [
        N1 REDUCES_TO_STAR P
        AND N2 REDUCES_TO_STAR P
    ]

RULE normal_form_uniqueness:
    M has_beta_normal_form N1
    AND M has_beta_normal_form N2
    -> ALPHA_EQUIVALENT_TO(N1,N2)

RULE lambda_Turing_equivalence:
    LambdaDefinableFunction(f)
    -> TuringComputableFunction(f)

RULE Turing_lambda_equivalence:
    TuringComputableFunction(f)
    -> LambdaDefinableFunction(f)
       UNDER standard_encoding

RULE fixed_point:
    FixedPointCombinator(Y)
    AND LambdaTerm(F)
    -> Y F
       BETA_EQUIVALENT_TO
       F (Y F)

DEFINE LAMBDA_TERM_GRAMMAR := {
    syntax:
        "M ::= x | (lambda x . M) | (M M)",
    constructors: {
        Variable,
        Abstraction,
        Application
    }
}

DEFINE BINDING_MODEL := {
    abstraction:
        "lambda x . M",
    binder:
        x,
    scope:
        M,
    free_occurrence:
        "an occurrence not enclosed by a corresponding binder",
    bound_occurrence:
        "an occurrence governed by a corresponding abstraction"
}

DEFINE SUBSTITUTION_MODEL := {
    notation:
        "M[x:=N]",
    meaning:
        "replace free occurrences of x in M with N",
    mandatory_property:
        CaptureAvoidingSubstitution,
    capture_prevention:
        "alpha-rename conflicting bound variables before substitution"
}

DEFINE REDUCTION_MODEL := {
    AlphaConversion:
        "rename bound variables without changing binding structure",
    BetaReduction:
        "apply an abstraction to an argument by capture-avoiding substitution",
    EtaReduction:
        "remove extensionally redundant abstraction when side conditions hold"
}

DEFINE CHURCH_ENCODING_MODEL := {
    ChurchBoolean: {
        TRUE:
            "lambda t . lambda f . t",
        FALSE:
            "lambda t . lambda f . f"
    },
    ChurchNumeral: {
        zero:
            "lambda f . lambda x . x",
        one:
            "lambda f . lambda x . f x",
        two:
            "lambda f . lambda x . f (f x)",
        general_n:
            "apply f exactly n times to x"
    }
}

DEFINE CRITICAL_DISTINCTIONS := {
    free_vs_bound_variable: {
        free:
            "not governed by an enclosing binder",
        bound:
            "within the scope of a matching abstraction"
    },
    substitution_vs_text_replacement: {
        substitution:
            "binding-aware and capture-avoiding",
        text_replacement:
            "may incorrectly change variable binding"
    },
    alpha_vs_beta_reduction: {
        alpha:
            "renames bound variables",
        beta:
            "performs function application"
    },
    normal_form_vs_termination: {
        normal_form:
            "term contains no applicable target redex",
        termination:
            "a chosen reduction strategy reaches a stopping point",
        note:
            "some lambda terms have no normal form"
    }
}

DEFINE EXAMPLE_1 := {
    term:
        "(lambda x . x) y",
    beta_reduction:
        "y"
}

DEFINE EXAMPLE_2 := {
    term:
        "(lambda x . lambda y . x) y",
    capture_risk:
        TRUE,
    safe_process: {
        "alpha-rename inner y to z",
        "(lambda x . lambda z . x) y",
        "beta-reduce to lambda z . y"
    }
}

DEFINE EXAMPLE_3 := {
    term:
        "(lambda x . x x) (lambda x . x x)",
    behaviour:
        "reduces to itself",
    normalises:
        FALSE
}

DEFINE PARSE_PIPELINE :=
    LambdaExpression
    -> TokeniseVariablesLambdaDotsParentheses
    -> ParseVariableAbstractionApplication
    -> ConstructAbstractSyntaxTree
    -> ResolveBindingScopes
    -> AnnotateFreeAndBoundVariables
    -> ReturnTypedLambdaTerm

DEFINE SUBSTITUTION_PIPELINE :=
    Term(M)
    -> TargetVariable(x)
    -> ReplacementTerm(N)
    -> LocateFreeOccurrencesOf(x)
    -> DetectPotentialVariableCapture
    -> IF capture_risk
       THEN AlphaRenameConflictingBinders
    -> SubstituteNForFreeOccurrences
    -> ReturnCaptureSafeTerm

DEFINE REDUCTION_PIPELINE :=
    LambdaTerm(M)
    -> DetectRedexes
    -> SelectReductionStrategy
    -> ApplyAlphaConversionWhenRequired
    -> ApplyBetaReduction
    -> ApplyEtaReductionWhenRequestedAndValid
    -> RepeatUntilNormalFormOrDivergenceEvidence
    -> ReturnReductionSequence

DEFINE COMPUTABILITY_PIPELINE :=
    MathematicalFunction(f)
    -> SearchForLambdaEncoding
    -> ConstructLambdaTermComputing(f)
    -> VerifyInputOutputBehaviour
    -> EstablishLambdaDefinability
    -> MapToTuringComputability
    -> ReturnComputabilityRelation

DEFINE LAMBDA_GRAPH := {
    node_types: {
        VariableNode,
        AbstractionNode,
        ApplicationNode,
        BinderNode,
        ReductionNode,
        EncodingNode
    },
    edge_types: {
        BINDS,
        HAS_SCOPE,
        HAS_BODY,
        HAS_FUNCTION,
        HAS_ARGUMENT,
        REDUCES_TO,
        ALPHA_EQUIVALENT_TO
    },
    binding_scope_preserved: TRUE
}

DEFINE ONTOLOGY_RELATIONS := {
    LambdaCalculus IS_COMPONENT_OF ComputabilityTheory,
    LambdaTerm IS_CONSTRUCTED_FROM VariableOrAbstractionOrApplication,
    Abstraction BINDS Variable,
    Application HAS_FUNCTION LambdaTerm,
    Application HAS_ARGUMENT LambdaTerm,
    BetaReduction USES CaptureAvoidingSubstitution,
    AlphaConversion PRESERVES BindingStructure,
    ChurchNumeral ENCODES NaturalNumber,
    FixedPointCombinator ENABLES RecursiveDefinitions,
    LambdaDefinableFunction EQUIVALENT_IN_COMPUTABILITY_TO TuringComputableFunction,
    ChurchTuringThesis RELATES LambdaCalculus TO EffectiveCalculability
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "lambda calculus" <=> LambdaCalculus,
    "lambda term" <=> LambdaTerm,
    "lambda abstraction" <=> Abstraction,
    "function application" <=> Application WHEN lambda_context=TRUE,
    "beta reduction" <=> BetaReduction,
    "alpha conversion" <=> AlphaConversion,
    "capture-avoiding substitution" <=> CaptureAvoidingSubstitution,
    "Church numeral" <=> ChurchNumeral,
    "fixed-point combinator" <=> FixedPointCombinator
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation, parsing and reduction of lambda-calculus expressions",
    preserve_term_identity: TRUE,
    preserve_abstract_syntax_tree: TRUE,
    preserve_binding_scope: TRUE,
    distinguish_free_from_bound_variables: TRUE,
    require_capture_avoiding_substitution: TRUE,
    support_alpha_conversion: TRUE,
    support_beta_reduction: TRUE,
    support_eta_reduction: TRUE,
    detect_beta_normal_form: TRUE,
    detect_obvious_reduction_cycles: TRUE,
    support_Church_encodings: TRUE,
    support_fixed_point_reasoning: TRUE,
    support_Turing_equivalence_reasoning: TRUE,
    reasoning_mode: "symbolic + binding-aware + substitution-safe + reduction-based"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    lambda_term_parsing: 0.99,
    binding_scope_resolution: 0.99,
    free_variable_analysis: 0.99,
    capture_avoiding_substitution: 0.99,
    beta_reduction: 1.00,
    alpha_conversion: 0.99,
    arbitrary_normalisation_prediction: undecidable_in_general
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        variable_abstraction_application,
        lexical_binding,
        free_bound_distinction,
        capture_avoiding_substitution,
        alpha_conversion,
        beta_reduction,
        lambda_Turing_equivalence
    },
    extensible_layers: {
        eta_conversion,
        Church_encodings,
        fixed_point_combinators,
        evaluation_strategies,
        simply_typed_lambda_calculus,
        polymorphic_lambda_calculus,
        dependent_type_theory,
        lambda_machine_implementations
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + LAMBDA_TERM_GRAMMAR
    + BINDING_MODEL
    + SUBSTITUTION_MODEL
    + REDUCTION_MODEL
    + CHURCH_ENCODING_MODEL
    + CRITICAL_DISTINCTIONS
    + PARSE_PIPELINE
    + SUBSTITUTION_PIPELINE
    + REDUCTION_PIPELINE
    + COMPUTABILITY_PIPELINE
    + LAMBDA_GRAPH
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: LambdaCalculusOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/lambda-calculus-ontology.html",
    parent_domain: ComputabilityTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: LambdaCalculus,
    binding_reasoning_enabled: TRUE,
    capture_avoiding_substitution_enabled: TRUE,
    reduction_reasoning_enabled: TRUE,
    Church_encoding_reasoning_enabled: TRUE,
    Turing_equivalence_reasoning_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    database_safe_unicode: TRUE,
    flow_complete: TRUE
}

END_FLOW