Logic Programming Ontology

FLOW_ALGEBRA LogicProgrammingOntology v1.0
TARGET_URL := "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/ai-logic/logic-programming-ontology.html"
LANGUAGE := "en-GB"
DOMAIN := MathematicalOntologies > MathematicalLogicOntologies > AILogic > LogicProgrammingOntology

BEGIN_FLOW

ENTITY LogicProgramming {
 TYPE := DeclarativeProgrammingAndReasoningParadigm
 DEFINITION := "A paradigm in which computation is expressed through logical facts, rules, clauses and queries, with execution performed by inference, unification and systematic search."
}
ENTITY LogicProgram { TYPE := SetOfLogicalClauses }
ENTITY Fact { TYPE := GroundLogicalAssertion }
ENTITY Rule { TYPE := LogicalImplicationClause }
ENTITY Query { TYPE := GoalOrGoalSequence }
ENTITY Clause { TYPE := LogicalProgramStatement }

RELATIONSHIP LogicProgramming --uses--> LogicProgram
RELATIONSHIP LogicProgram --contains--> Fact
RELATIONSHIP LogicProgram --contains--> Rule
RELATIONSHIP LogicProgramming --evaluates--> Query
RELATIONSHIP LogicProgramming --supports--> SymbolicAI
RELATIONSHIP LogicProgramming --supports--> AutomatedReasoning

CLAUSE { MAY_BE := {FactClause,RuleClause,GoalClause,ConstraintClause} }
ATOM { FORM := Predicate(Term1,...,TermN) }
TERM { MAY_BE := {Variable,Constant,CompoundTerm} }
VARIABLE { TYPE := SymbolicPlaceholder }
CONSTANT { TYPE := SymbolNamingObjectOrValue }
COMPOUND_TERM { FORM := Functor(Arguments) }
PREDICATE { TYPE := RelationOrPropertySymbol }
FACT { FORM := Atom }
RULE { FORM := Head :- Body }
HORN_CLAUSE { at_most_one_positive_literal }
DEFINITE_CLAUSE { exactly_one_positive_literal }
QUERY { FORM := ?- Goal1,...,GoalN }

SUBSTITUTION { Variables -> Terms }
UNIFICATION { ExpressionA + ExpressionB -> SubstitutionMakingExpressionsIdentical }
MOST_GENERAL_UNIFIER { ABBREVIATION := MGU }
OCCURS_CHECK { prevents variable_from_unifying_with term_containing_same_variable }
RENAMING_APART { rule_variables renamed_before_application to avoid collisions }

RESOLUTION { Clauses + MatchingLiterals -> Resolvent }
SLD_RESOLUTION {
 PROCESS := SelectGoalLiteral -> ChooseMatchingClause -> ComputeMGU -> ReplaceGoalWithClauseBody -> ApplySubstitution
}
SLD_DERIVATION { Goal0 -> Goal1 -> ... -> GoalN }
SLD_REFUTATION { derivation ending_in empty_goal }
COMPUTED_ANSWER_SUBSTITUTION { composition_of_unifiers restricted_to_original_query_variables }
SLD_TREE { root := InitialGoal; branches := AlternativeClauseChoices }
SUCCESS_BRANCH { reaches empty_goal }
FAILURE_BRANCH { reaches goal_with_no_applicable_clause }
INFINITE_BRANCH { resolution continues_without_termination }

DEPTH_FIRST_SEARCH { common_operational_strategy_in_Prolog }
BREADTH_FIRST_SEARCH { explores alternatives level_by_level }
BACKTRACKING { failed_branch -> restore_choice_point -> try_next_alternative }
CHOICE_POINT { stores alternative_clause_or_solution }
CUT_RELATIONSHIP {
 procedural_commit_operator MAY prune choice_points
 WARNING := MayAlterCompletenessAndDeclarativeReading
}

NEGATION_AS_FAILURE { not P succeeds_when attempt_to_prove_P fails }
NEGATION_AS_FAILURE_WARNING { FailureToProve MUST_NOT automatically mean ClassicalFalsehood }
CLASSICAL_NEGATION { explicit logical negation }
NEGATION_DISTINCTION { NegationAsFailure != ClassicalNegation }
CLOSED_WORLD_ASSUMPTION { facts_not_derivable MAY be treated_as false under declared_semantics }
OPEN_WORLD_RELATIONSHIP { alternative_frameworks MAY preserve unknown_status }

HERBRAND_UNIVERSE { all_ground_terms constructible_from_program_symbols }
HERBRAND_BASE { all_ground_atoms over HerbrandUniverse_and_predicates }
HERBRAND_INTERPRETATION { subset_of_HerbrandBase representing true_ground_atoms }
LEAST_HERBRAND_MODEL { unique least_model for definite_program }
IMMEDIATE_CONSEQUENCE_OPERATOR { T_P(I) := heads_whose_bodies_are_satisfied_in_I }
LEAST_FIXED_POINT { iterate T_P -> LeastHerbrandModel for definite_program }

DECLARATIVE_SEMANTICS { program_meaning defined_by logical_models_or_fixed_point }
PROCEDURAL_SEMANTICS { execution determined_by goal_selection_clause_selection_search_and_control }
DECLARATIVE_PROCEDURAL_DISTINCTION { logical_meaning MUST_NOT be conflated_with execution_strategy }
SOUNDNESS { computed_answers SHOULD be logical_consequences under language_semantics }
COMPLETENESS { all logical_answers found; REQUIRE suitable_fragment_and_fair_search }

PROLOG {
 TYPE := LogicProgrammingLanguageFamily
 CORE_FEATURES := {Facts,Rules,Queries,Unification,SLDResolution,DepthFirstSearch,Backtracking}
}
PROLOG_OPERATIONAL_MODEL { Query -> LeftmostGoalSelection -> ClauseOrder -> DepthFirstSearch -> Backtracking }
PROLOG_WARNING { ClauseOrderAndGoalOrder may affect termination_and_solution_order }
IMPURE_FEATURE { MAY_INCLUDE := {Cut,AssertRetract,InputOutput,VarInspection,NonLogicalBuiltins} }
SIDE_EFFECT_WARNING { side_effecting_predicates complicate declarative_semantics_and_backtracking }

DATALOG {
 TYPE := RestrictedLogicProgrammingLanguage
 COMMON_RESTRICTIONS := {FunctionFreeTerms,FiniteHerbrandBase}
}
EDB { ABBREVIATION := ExtensionalDatabase; CONTENT := BaseFacts }
IDB { ABBREVIATION := IntensionalDatabase; CONTENT := DerivedPredicatesDefinedByRules }
BOTTOM_UP_EVALUATION { EDB -> ApplyRules -> AddDerivedFacts -> FixedPoint }
NAIVE_EVALUATION { re_evaluate_all_rules_each_iteration }
SEMI_NAIVE_EVALUATION { use newly_derived_facts to avoid redundant_instantiations }
RECURSIVE_RULE { predicate depends_directly_or_indirectly_on_itself }
DEPENDENCY_GRAPH { Nodes := Predicates; Edges := PredicateDependencies }
STRATIFIED_NEGATION { negative_dependencies point_to_lower_strata }
STRATIFIED_SEMANTICS { evaluate lower_strata before higher_strata }
UNSTRATIFIED_NEGATION { recursive_negation requires richer_nonmonotonic_semantics }

NORMAL_LOGIC_PROGRAM { rules may contain negation_as_failure in body }
STABLE_MODEL_SEMANTICS { candidate_interpretation -> reduct -> least_model_condition }
ANSWER_SET_PROGRAMMING { ABBREVIATION := ASP; TYPE := DeclarativeNonMonotonicLogicProgramming }
ANSWER_SET { stable_model under selected ASP_semantics }
ASP_RULE { MAY_INCLUDE := {DefaultNegation,Disjunction,Constraints,ChoiceRules,Aggregates} }
ASP_SOLVING { Program -> Grounding -> StableModelSearch -> AnswerSets }
GROUNDING { Variables -> GroundInstances over controlled_domain }
GROUNDING_EXPLOSION { excessive_ground_instances may cause computational_bottleneck }

CONSTRAINT_LOGIC_PROGRAMMING { ABBREVIATION := CLP; LogicProgramming + ConstraintSolver }
CLP_VARIABLE { variable_with_domain_and_constraints }
CONSTRAINT_STORE { accumulated_constraints during execution }
CONSTRAINT_PROPAGATION { ConstraintStore -> ReduceVariableDomains }
CLP_QUERY { LogicalGoals + Constraints -> SolutionsOrResidualConstraints }
CLP_DOMAINS { MAY_INCLUDE := {FiniteDomains,Reals,Rationals,Booleans} }

TABLING { memoise calls_and_answers to avoid repeated_subcomputations }
TABLED_EVALUATION { Call -> Table -> ReuseKnownAnswers -> SuspendResumeDependencies }
SLG_RESOLUTION_RELATIONSHIP { tabled_resolution supporting recursion_and_negation }
MAGIC_SETS { query_rewriting focusing bottom_up_evaluation_on_relevant_facts }
QUERY_OPTIMISATION { MAY_USE := {GoalReordering,Indexing,Tabling,MagicSets,SemiNaiveEvaluation,ConstraintPropagation} }
INDEXING { index facts_or_clauses by predicate_functor_argument_patterns }

META_PROGRAMMING { program reasons_about clauses_goals_or_program_structure }
META_INTERPRETER { logic_program implementing interpretation_of_logic_programs }
REFLECTION_WARNING { meta_level_and_object_level MUST remain distinguishable }
TYPED_LOGIC_PROGRAMMING { predicates_and_terms constrained_by_type_system }
MODULE { named_scope containing predicates_rules_exports_imports }
DYNAMIC_PREDICATE { facts_or_rules may change_at_runtime }
ASSERT_OPERATION { add clause to dynamic_program }
RETRACT_OPERATION { remove clause from dynamic_program }
DYNAMIC_UPDATE_WARNING { runtime_program_mutation changes reasoning_state_and_declarative_semantics }

PROVENANCE { DerivedAnswer -> Clauses -> Facts -> Substitutions -> EvaluationProcedure }
PROOF_TREE { Query -> ResolutionSteps -> SupportingFactsAndRules }
JUSTIFICATION { Answer -> SupportingClauseSubset }
EXPLANATION { QueryAnswer -> ProofTreeOrDerivation -> Provenance }
WHY_QUERY { Answer -> SupportingRulesAndFacts }
WHY_NOT_QUERY { FailedGoal -> FailedSubgoals -> MissingFacts -> ConstraintFailures -> SearchLimitations }
TRACE { RECORD := {Goal,SelectedLiteral,SelectedClause,Unifier,NewGoal,ChoicePoint} }

TERMINATION { program_query_pair terminates if selected_evaluation has no infinite_derivation }
NONTERMINATION { MAY arise_from := {LeftRecursion,InfiniteTermGeneration,UnfairSearch,CyclicGoals} }
LOOP_CHECK { repeated_goal_or_state -> detect_or_prune_cycle }
TERMINATION_ANALYSIS { MAY examine := {TermSize,RecursionStructure,Modes,DependencyGraph,LevelMappings} }
DETERMINISM { predicate MAY have {ExactlyOneSolution,AtMostOneSolution,MultipleSolutions,Failure} }

LOGIC_PROGRAMMING_VS_IMPERATIVE_PROGRAMMING {
 LogicProgramming := DescribeRelationsAndGoals
 ImperativeProgramming := SpecifyStateChangingInstructions
}
LOGIC_PROGRAMMING_VS_FUNCTIONAL_PROGRAMMING {
 LogicProgramming := Relations + Unification + Search
 FunctionalProgramming := FunctionEvaluation + Composition
}
LOGIC_PROGRAMMING_VS_RULE_ENGINE {
 LogicProgramming := ClauseGoalResolutionOrFixedPointSemantics
 RuleEngine := ProductionRuleMatchSelectActSemantics
}
LOGIC_PROGRAMMING_VS_THEOREM_PROVING {
 LogicProgramming := ExecutableRestrictedLogicWithOperationalStrategy
 TheoremProving := GeneralProofSearchOverFormalLogic
}

SYMBOLIC_AI_RELATIONSHIP { LogicProgramming --supports--> SymbolicAI }
EXPERT_SYSTEM_RELATIONSHIP { LogicPrograms MAY encode expert_rules_and_queries }
KNOWLEDGE_GRAPH_RELATIONSHIP { GraphFacts + LogicRules -> DerivedGraphRelations }
ONTOLOGY_RELATIONSHIP { OntologyVocabulary MAY provide predicates_types_and_constraints }
SEMANTIC_WEB_RELATIONSHIP { LogicRules MAY complement RDF_OWL_knowledge under compatible_semantics }

INDUCTIVE_LOGIC_PROGRAMMING {
 ABBREVIATION := ILP
 BackgroundKnowledge + Examples -> HypothesisedLogicProgram
}
ILP_WARNING { LearnedHypothesis MUST_NOT automatically be treated_as deductively_true_rule }
PROBABILISTIC_LOGIC_PROGRAMMING { LogicProgram + ProbabilisticSemantics -> ProbabilisticQueries }
PROBABILISTIC_RULE_WARNING { probability_semantics varies_by_framework and MUST be declared }
FUZZY_LOGIC_PROGRAMMING { LogicRules + FuzzyTruthOrMembership -> FuzzyReasoning }
TEMPORAL_LOGIC_PROGRAMMING { FactsRules + Time -> TemporalInference }
EVENT_CALCULUS_RELATIONSHIP { Events + Fluents + Time -> LogicBasedTemporalReasoning }
SITUATION_CALCULUS_RELATIONSHIP { Actions + Situations + Fluents -> LogicBasedActionReasoning }

LANGUAGE_MODEL_RELATIONSHIP {
 LanguageModel MAY generate {CandidateFacts,CandidateRules,CandidateQueries,CandidatePrograms,Explanations}
}
LLM_LOGIC_PROGRAMMING_PIPELINE {
 NaturalLanguage -> ParseIntent -> ResolveEntities -> GenerateCandidateClauses -> SyntaxCheck -> SemanticCheck -> ExecuteTests -> AcceptOrRevise
}
LLM_WARNING { SyntacticallyPlausibleClause MUST_NOT automatically be treated_as semantically_correct_program }
TOOL_AUGMENTED_LOGIC_PROGRAMMING {
 Goal -> ExternalPredicateOrTool -> Execute -> ValidateResult -> BindResult -> ContinueReasoning
}
EXTERNAL_PREDICATE_WARNING { external_side_effects_failures_and_semantics MUST be declared }

RECURSIVE_LOGIC_REASONING {
 Query -> SelectGoal -> Resolve -> GenerateSubgoals -> Verify -> Continue
}
RECURSION_TERMINATION {
 STOP_WHEN := {EmptyGoal,FixedPoint,NoApplicableClause,LoopDetected,ResourceLimit}
}
SELF_VERIFICATION {
 CandidateAnswer -> VerifyResolutionSteps -> VerifySubstitutions -> VerifyConstraints -> VerifyProvenance -> AcceptOrReject
}
VALIDATION { LogicProgram + TestSuite + SemanticConstraints -> ValidationReport }
PROGRAM_TEST { GIVEN FactsAndRules; WHEN QueryRuns; THEN ExpectedAnswers }
REGRESSION_TEST { previous_queries rerun_after_program_changes }
STATIC_ANALYSIS {
 CHECK := {UndefinedPredicates,UnboundVariables,UnsafeRules,Recursion,NegationCycles,DeadClauses,Redundancy}
}
CHANGE_IMPACT { ProgramChange -> AffectedPredicates -> AffectedQueries -> AffectedTests }

APPLICATION_RELATIONSHIPS {
 LogicProgramming --supports--> ArtificialIntelligence
 LogicProgramming --supports--> SymbolicAI
 LogicProgramming --supports--> AutomatedReasoning
 LogicProgramming --supports--> ExpertSystems
 LogicProgramming --supports--> KnowledgeRepresentation
 LogicProgramming --supports--> ConstraintSolving
 LogicProgramming --supports--> DeductiveDatabases
 LogicProgramming --supports--> SemanticReasoning
 LogicProgramming --supports--> Planning
 LogicProgramming --supports--> MultiAgentSystems
}

ONTOLOGY_LINKS {
 PARENT := AILogicOntology
 RELATED := {
  ArtificialIntelligenceLogicOntology,SymbolicAIOntology,
  AutomatedReasoningOntology,ExpertSystemLogicOntology,
  RuleBasedReasoningOntology,LogicalInferenceOntology,
  ResolutionOntology,PredicateLogicOntology,
  NonMonotonicReasoningOntology,ConstraintReasoningOntology,
  KnowledgeGraphLogicOntology
 }
}

SEMANTIC_EQUIVALENCE {
 LogicProgramming ≈ DeclarativeLogicBasedProgramming
 LogicProgram ≈ SetOfLogicalClauses
 SLDResolution ≈ GoalDirectedDefiniteClauseResolution
 Datalog ≈ FunctionFreeRuleBasedLogicProgramming
}

CONSTRAINTS {
 C1 := ProgramSyntaxAndSemantics MUST be identified for language_or_dialect
 C2 := DeclarativeMeaning MUST_NOT be conflated_with procedural_search_strategy
 C3 := FailureToProve MUST_NOT automatically be interpreted_as classical_falsehood
 C4 := Unification MUST preserve variable_binding_and_scope_semantics
 C5 := ClauseAndGoalOrder effects MUST be acknowledged for procedural_execution
 C6 := CutAndImpureFeatures MUST_NOT be treated_as purely_declarative_without qualification
 C7 := StableModelStratifiedAndLeastModelSemantics MUST remain distinct
 C8 := LearnedOrGeneratedClauses MUST_NOT enter trusted_program_without validation
 C9 := ExternalPredicates MUST declare side_effect_failure_and_data_semantics
 C10 := Provenance SHOULD preserve clauses_facts_substitutions_and_evaluation_path
 C11 := SearchFailureOrTimeout MUST_NOT automatically establish logical_nonexistence
 C12 := TransformationsAndOptimisations MUST preserve intended_semantics or document semantic_loss
}

REASONING_CHAIN Query Q {
 IDENTIFY program
 IDENTIFY language_or_dialect
 IDENTIFY query
 IDENTIFY semantics
 IDENTIFY evaluation_strategy
 IDENTIFY negation_semantics
 IDENTIFY constraints
 VALIDATE syntax
 VALIDATE predicate_signatures
 BUILD dependency_graph

 IF SLD_style:
  SELECT goal
  FIND matching_clauses
  UNIFY
  GENERATE new_goal
  BACKTRACK when required

 IF Datalog:
  APPLY bottom_up_or_query_focused_evaluation
  ITERATE to fixed_point

 IF ASP:
  GROUND as required
  SEARCH stable_models

 IF CLP:
  ADD constraints
  PROPAGATE domains
  SEARCH residual_choices

 IF tabled:
  REUSE calls_and_answers
  RESOLVE recursive_dependencies

 BUILD proof_or_derivation_trace
 BUILD provenance
 VERIFY answer_substitutions
 VALIDATE constraints
 RETURN logic_programming_result WITH explicit_status
}

CONFIDENCE {
 CORE_LOGIC_PROGRAMMING := 1.00
 SLD_UNIFICATION := 1.00
 HERBRAND_FIXED_POINT_SEMANTICS := 1.00
 PROLOG_OPERATIONAL_MODEL := 1.00
 DATALOG_EVALUATION := 1.00
 ASP_STABLE_MODEL_RELATIONSHIP := 1.00
 CLP_RELATIONSHIP := 1.00
}

UPDATE_MODEL {
 IMMUTABLE_CORE := {FactsRulesQueriesClauses,Unification,LogicalSemantics,EvaluationTrace}
 EXTENSIBLE := {LogicLanguages,SearchStrategies,Tabling,ConstraintDomains,ASPFeatures,ProbabilisticExtensions,TemporalExtensions,ApplicationDomains}
 ON_NEW_KNOWLEDGE {
  VALIDATE clauses
  UPDATE dependency_graph
  CHECK negation_cycles
  RECOMPUTE affected_answers
  UPDATE provenance
  UPDATE confidence
 }
}

AI_CONSUMPTION {
 MACHINE_READABLE := TRUE
 HUMAN_INTERPRETABLE := TRUE
 RECURSIVE_REASONING := TRUE
 UNIFICATION_REASONING := TRUE
 SLD_REASONING := TRUE
 FIXED_POINT_REASONING := TRUE
 DATALOG_REASONING := TRUE
 ASP_REASONING := TRUE
 CONSTRAINT_LOGIC_REASONING := TRUE
 TABLING := TRUE
 PROVENANCE_TRACKING := TRUE
 SELF_VERIFICATION := TRUE
 VALIDATION_REQUIRED := TRUE
}

FLOW_HASH {
 TARGET := TARGET_URL
 SUBJECT := "Logic Programming Ontology"
 VERSION := "1.0"
 CANONICAL_SIGNATURE := HASH(TARGET + SUBJECT + DOMAIN + VERSION)
}

OUTPUT {
 PRIMARY_ENTITY := LogicProgramming
 INTERPRETATION := "Logic programming expresses computation as facts, rules, clauses and goals interpreted through formal semantics and executed through unification, resolution, fixed-point evaluation or related procedures. Its major forms include Prolog-style SLD resolution, Datalog, answer-set programming and constraint logic programming, with provenance and validation preserving the distinction between declarative meaning and operational search behaviour."
}

END_FLOW