Logic Programming
Logic Programming
March 17, 2021
COM S 342 Principles of Programming Languages @ Iowa State University 1
COM S 342 Principles of Programming Languages @ Iowa State University 2
?- loves(X, tom).
mary
?- loves(mary, Y).
tom
?- loves(mary, jane).
falseCOM S 342 Principles of Programming Languages @ Iowa State University 3
What is Logic Programming
There are many (overlapping) perspectives on logic programming:
I A very high level programming language
I An interpretation of declarative specifications
I Non-procedural programming
I Algorithms minus control
I Computations as deduction
I Theorem proving
COM S 342 Principles of Programming Languages @ Iowa State University 4
A Very High Level Language
I A good programming language should not encumber the
programmer with non-essential details.
I The development of programming languages has been toward freeing
the programmer of more and more of the details
I ASSEMBLY LANGUAGE: symbolic encoding of data and
instructions.
I FORTRAN: allocation of variables to memory locations, register
saving, etc.
I ML: explicit variable type declarations
I JAVA: Platform specifics
I Logic Programming Languages are a class of languages which
attempt to free us from having to worry about many aspects of
explicit control.
COM S 342 Principles of Programming Languages @ Iowa State University 5
An Interpretation of Declarative Specifications
I Logical statement: Forall X and Y, X is the father of Y if X is a
parent of Y and the gender of X is male.
I Prolog code: father(X,Y) :-
parent(X,Y), gender(X,male).
I Interpret it in two slightly different ways:
I declaratively – which must be true if a father relationship holds.
I procedurally: what to do to establish that a father relationship holds.
COM S 342 Principles of Programming Languages @ Iowa State University 6
Non-procedural Programming
I A non – procedural language one in which one specifies WHAT
needs to be computed but not HOW it is to be done.
I it specifies a state with constraints, objects and relations:
I the set of objects involved in the computation
I the relationships which hold between them
I the constraints which must hold for the problem to be solved
I the language interpreter or compiler will decide HOW to satisfy the
constraints.
COM S 342 Principles of Programming Languages @ Iowa State University 7
Algorithms Minus Control
I (architect of Pascal) used the following slogan as the
title of a book: Algorithms + Data Structures = Programs
I offers a similar one to express the central theme of
logic programming: Algorithms = Logic + Control
I We can view the LOGIC component as: a specification of the
essential logical constraints of a particular problem
I CONTROL component as: advice to an evaluation machine (e.g. an
interpreter or compiler) on how to go about satisfying the
constraints)
COM S 342 Principles of Programming Languages @ Iowa State University 8
Computation as Deduction
I Computation is related to logical proofs and is not restricted to
functional (Church) or imperative (Turing/ )
computation models.
I inductive reasoning: particular cases to general cases – inductive
reasonable and proof
I deductive reasoning:
All men are mortal. (First premise)
Socrates is a man. (Second premise)
Therefore, Socrates is mortal. (Conclusion)
I It uses the language of logic to express data and programs, e.g.,
Forall X and Y, X is the father of Y if X is a parent of Y and the
gender of X is male.
I Current logic programming languages use first order logic (FOL)
I Propositions, e.g., A is father of B, predicates, e.g., parent (X Y),
and quantifier symbols such as ∃ and ∀ on objects (more in discrete
maths books).
COM S 342 Principles of Programming Languages @ Iowa State University 9
Theorem Proving
I Logic programming uses the notion of an automatic theorem prover
as an interpreter.
I The theorem prover derives a desired solution from an initial set of
axioms.
I Note that the proof must be a ”constructive” one so that more than
a true/false answer can be obtained, e.g., the answer to exists x
such that x = sqrt(16) should be x = 4 or x = -4 rather than true
COM S 342 Principles of Programming Languages @ Iowa State University 10
A Short History
1965 Efficient theorem provers. Resolution ( )
1969 Theorem Proving for problem solving. ( )
1969 PLANNER, theorem proving as programming ( )
1970 Micro – Planner, an implementation (Sussman, Charniak and
Winograd)
1970 Prolog, an implementation ( )
1972 Book: Logic for Problem Solving. (Kowalski)
1977 DEC – 10 Prolog, an efficient interpreter/compiler (Warren and
Pereira)
1982 Japan’s 5th Generation Computer Project
1985 Datalog and deductive databases
1995 Prolog interpreter embedded in NT
COM S 342 Principles of Programming Languages @ Iowa State University 11
PROLOG is the FORTRAN of Logic Programming
I Prolog is the only widely used logic programming language.
I As a Logic Programming language, it has a number of advantages:
simple, small, fast, easy to write good compilers for it.
I Disadvantages
I It has a fixed control strategy.
I It has a strong procedural aspect
I limited support parallelism or concurrency or multi-threading.
I Datalog: is a subset of Prolog, fully declarative
COM S 342 Principles of Programming Languages @ Iowa State University 12
Prolog Programming
I Step 1: presenting knowledge: predicate logic
I fact: proposition that’s unconditional true
I rule: proposition that’s conditional true; dependent on other
propositions
I a fact or a rule is a statement or clause in Prolog.
I Step 2: ”execute a program”: make inference from a database of
facts and rules.
COM S 342 Principles of Programming Languages @ Iowa State University 13
COM S 342 Principles of Programming Languages @ Iowa State University 14
COM S 342 Principles of Programming Languages @ Iowa State University 15
COM S 342 Principles of Programming Languages @ Iowa State University 16
COM S 342 Principles of Programming Languages @ Iowa State University 17
COM S 342 Principles of Programming Languages @ Iowa State University 18
COM S 342 Principles of Programming Languages @ Iowa State University 19
COM S 342 Principles of Programming Languages @ Iowa State University 20
?-reach(a, X)
b, c
COM S 342 Principles of Programming Languages @ Iowa State University 21
COM S 342 Principles of Programming Languages @ Iowa State University 22
COM S 342 Principles of Programming Languages @ Iowa State University 23
COM S 342 Principles of Programming Languages @ Iowa State University 24
COM S 342 Principles of Programming Languages @ Iowa State University 25
COM S 342 Principles of Programming Languages @ Iowa State University 26
Result: succ(0)
COM S 342 Principles of Programming Languages @ Iowa State University 27
Swi-prolog Programming
I Install on mac: brew install swi-prolog
I Install on different machines: https://www.swi-prolog.org/build/
I edit your program in any aditor and save it as test.pl
I run the program using: swipl -s test.pl
I stop running the program: halt.
I frequently used command link
Demo: case sensitive
COM S 342 Principles of Programming Languages @ Iowa State University 28
https://www.swi-prolog.org/pldoc/man?section=cmdline
COM S 342 Principles of Programming Languages @ Iowa State University 29
COM S 342 Principles of Programming Languages @ Iowa State University 30
Recall, term can be constant, variable, functor.
COM S 342 Principles of Programming Languages @ Iowa State University 31
Soln: [W � X, Y � g(Z), Z � h(x)] MGU
Or, [W � X, Y � g(h(x)), Z � h(x)] MGU
COM S 342 Principles of Programming Languages @ Iowa State University 32
COM S 342 Principles of Programming Languages @ Iowa State University 33
COM S 342 Principles of Programming Languages @ Iowa State University 34
COM S 342 Principles of Programming Languages @ Iowa State University 35
COM S 342 Principles of Programming Languages @ Iowa State University 36
COM S 342 Principles of Programming Languages @ Iowa State University 37
COM S 342 Principles of Programming Languages @ Iowa State University 38
COM S 342 Principles of Programming Languages @ Iowa State University 39
COM S 342 Principles of Programming Languages @ Iowa State University 40
COM S 342 Principles of Programming Languages @ Iowa State University 41
Example: search on graphs
COM S 342 Principles of Programming Languages @ Iowa State University 42
Example: write a parser with Prolog
COM S 342 Principles of Programming Languages @ Iowa State University 43
Example: write a parser with Prolog
COM S 342 Principles of Programming Languages @ Iowa State University 44
Logic Programming
I numbers: max
I list: append, reverse
I constraint problems
I language parsing
I graph search problems
COM S 342 Principles of Programming Languages @ Iowa State University 45