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.
• 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
• 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