1. General Concepts

Logic Programming

Logic programming aims to combine logic and programming:

• Logic is used to express knowledge and describe the problem
• Inference is used to compute, manipulate knowledge, and obtain a solution

Advantages	Disadvantages
Knowledge-based programming	Ability to support efficient arithmetic and input/output operations such as file handling, are provided at the expense of declarative semantics
Declarative style of programming; what should be computed instead of how	Most logic languages are restricted to a fragment of classical first-order logic.
Precise and simple semantics
Same formalism used to specify a program, write a program, prove properties of the program
Same program can be used in many different ways

Link to original

Example of how programs can be used in many different ways: consider the following Prolog program to reverse a list of elements

reverse([], []).
reverse([H|T], List) :- reverse(T, Z), append(Z, [H], List)

And consider the output of the following three queries:

% query A
?- reverse([1, 2, 3], X).
X = [3, 2, 1]
 
% query B
?- reverse(X, [3, 2, 1]).
X = [1, 2, 3]
 
% query C
?- reverse([1, 2, 4], [3, 2, 1]).
false.

We see that variable $X$ was used in different argument positions in $A$ and $B$, and that no variables were used in $C$. Unlike functional programming, there is no intrinstic notion of “input” or “output” variables.

Prolog

Prolog

Prolog is the most popular logic programming language:

• Developed in early 1970s
• Used in natural language processing and A.I.
• Syntax - clausal fragment of classical first-order logic
• Semantics - SLD-resolution with automatic backtracking
• Impure - includes non-logical primitives

Link to original

We use SWI Prolog for this module. Load program from local file as such:

?- ['myprogram.pl'].

Syntax Basics

The set of terms is defined using:

• variables: represented by $X$, $Y$, $Z$, $\dots$
• function symbols, with fixed arities, represented by $f$, $g$, $h$, $\dots$, or $a$, $b$, $c$, $\dots$ for constants of artity zero.

A term is either a variable, or has the form $f(t_1,\dots ,t_n)$, where $f$ is a function symbol of arity $n$ and $t_1,\dots ,t_n$ are terms.

If $a$ is a constant, $f$ is a binary function, and $g$ a unary function, and $X$, $Y$ are variables, then the following are possible terms.

$X,a,g(a),f(X,g(a)),Y,f(f(X,g(a)),Y),g(f(f(X,g(a)),Y))$

Predicate symbols, atomic formulas and literals

Let $p$, $q$, $r$, $\dots$ represent predicate symbols, each with a fixed arity. If $p$ is a predicate of arity $n$ and $t_1,\dots ,t_n$ are terms, then $p(t_1,\dots ,t_n)$ is an atomic formula, $A$, $B$, $\dots$. A literal is an atomic formula $A$, or negated atomic formula, $\neg A$.

You can think of a predicate symbol as expressing a relationship between elements of the domain.

For example, the predicate father_of(peter, paul) expresses Peter is Paul’s father.

If rainy and snowy are unary predicates, temperature is a binary predicate, celsius is a unary function symbol, tuesday and zero are constants, and $X$ is a variable, then the following are possible literals:

• temperature(tuesday, celsius(zero))
• $\neg$rainy(tuesday)
• snowy(X)