Computer Programming Languages -- Logic Programming

Computer Programming Languages -- Logic Programming

By Herbert J. Bernstein

Logic Programming or Declarative Programming defines a program by specifying facts and logical relationships among them, rather than by specifying any particular actions to be performed. It is based on the techniques of formal symbolic logic and techniques originally used in automating proofs of mathematical theorems. The most important languages of this type are variants of Prolog. Prolog lends itself naturally to object-oriented programming. See http://www.cetus-links.org/oo_prolog.html.

Logic programming
- Meaning and differences from procedural languages
  - Predicate calculus
    - predicate -- the portion of a sentence which says something about the subject of the sentence.
    - Boolean logic -- concerned with sentences which may be true or false
    - First order -- sentences constructed by applying predicates to individuals and building from there with Bollean operations and quantifiers.
      
      logical operations
      
      relationships
      
      See http://www.rbjones.com/rbjpub/logic/log050.htm
  - Theorem proving
    - A theorem is a proposition stating that certain things are true if other things are true
    - Often proven by assuming the negation of the theorem and producing a contradiction (proof by contradiction)
    - Sometimes proven directly
    - Resolution
      
      State theorem in clausal form (union of implied propositions (consequent) implied by intersection of implying propositions (antecedent))
      Horn clauses -- atomic propsition on lhs (headed Horn clause) or empty lhs (facts)
      Adjoin negation of theorem to facts
      Find circumstances in which terms on left-hand sides match terms on right-hand-sides
      Combine statements to drop matching terms
      If no matches, back up and try again
      Work to contradiction
  - Declarative semantics
    - State facts
    - State known and desired relationships among facts
    - Leave it to the computer to work out how to make those relationships hold
    - e.g. state the definition of a sorted list and leave it to the computer to figure out how to sort the list
- Prolog
  See http://www.swi.psy.uva.nl/projects/SWI-Prolog/Manual/
  - Terms, variables, instantiation
    - term -- constant, variable, structure
    - constant -- atom ('-quoted string or identifier beginning with lc letter) or integer
    - variable -- begins with upper case letter
    - structure -- functor(comma-separated parameter list)
      functor is an atomic identifier
    - instantiation -- binding values to variables, done during theorem proving
  - Facts, rules , goals
    - fact -- headless Horn clause -- fact(arg1, arg2, ...).
    - rule -- headed Horn clause
      
      consequence(carg1, carg2, ... ) :- antecedent .
      and implied by commas between structures in antecedent
      or implied by semicolon
      See https://en.wikipedia.org/wiki/Horn_clause
      goal -- a headless Horn clause submitted as a query to check
    - Reasoning strategies, backtracking and cuts
      
      forward chaining -- find the goal from given facts and rules
      backward chaining -- start at the goal
      backtracking -- undo instantiations that failed, back up and try again
      cut -- conrol over backtracking, ... !, subgoal, ... won't back up past the ! pseudo-goal if the subgoal fails
Last Updated on 27 April 2000
By Herbert J. Bernstein
Email: yaya@bernstein-plus-sons.com