Computer Programming Languages -- Logic Programming

By Herbert J. Bernstein

© Copyright 2000 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

- logical operations

- predicate -- the portion of a sentence which says something
- 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

- Predicate calculus
- 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

- Terms, variables, instantiation

Last Updated on 27 April 2000

By Herbert J. Bernstein*Email: yaya@bernstein-plus-sons.com* - Meaning and differences from procedural languages