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).
fCaOlMseS 342 Principles of Programming Languages @ Iowa State University 3
What is Logic Programming
There are many (overlapping) perspectives on logic programming: A very high level programming language
An interpretation of declarative specifications
Non-procedural programming
Algorithms minus control Computations as deduction Theorem proving
COM S 342 Principles of Programming Languages @ Iowa State University 4
A Very High Level Language
A good programming language should not encumber the programmer with non-essential details.
The development of programming languages has been toward freeing the programmer of more and more of the details
ASSEMBLY LANGUAGE: symbolic encoding of data and instructions.
FORTRAN: allocation of variables to memory locations, register saving, etc.
ML: explicit variable type declarations
JAVA: Platform specifics
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
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.
Prolog code: father(X,Y) :-
parent(X,Y), gender(X,male).
Interpret it in two slightly different ways:
declaratively – which must be true if a father relationship holds.
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
A non – procedural language one in which one specifies WHAT needs to be computed but not HOW it is to be done.
it specifies a state with constraints, objects and relations: the set of objects involved in the computation
the relationships which hold between them
the constraints which must hold for the problem to be solved
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
Nikolas Wirth (architect of Pascal) used the following slogan as the title of a book: Algorithms + Data Structures = Programs
Bob Kowalski offers a similar one to express the central theme of logic programming: Algorithms = Logic + Control
We can view the LOGIC component as: a specification of the essential logical constraints of a particular problem
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
Computation is related to logical proofs and is not restricted to functional (Church) or imperative (Turing/Von Neumann) computation models.
inductive reasoning: particular cases to general cases – inductive reasonable and proof
deductive reasoning:
All men are mortal. (First premise) Socrates is a man. (Second premise) Therefore, Socrates is mortal. (Conclusion)
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.
Current logic programming languages use first order logic (FOL)
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
Logic programming uses the notion of an automatic theorem prover as an interpreter.
The theorem prover derives a desired solution from an initial set of axioms.
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 (Alan Robinson)
1969 Theorem Proving for problem solving. (Cordell Green)
1969 PLANNER, theorem proving as programming (Carl Hewett) 1970 Micro – Planner, an implementation (Sussman, Charniak and Winograd)
1970 Prolog, an implementation (Alain Colmerauer)
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
Prolog is the only widely used logic programming language.
As a Logic Programming language, it has a number of advantages: simple, small, fast, easy to write good compilers for it.
Disadvantages
It has a fixed control strategy.
It has a strong procedural aspect
limited support parallelism or concurrency or multi-threading.
Datalog: is a subset of Prolog, fully declarative
COM S 342 Principles of Programming Languages @ Iowa State University 12
Prolog Programming
Step 1: presenting knowledge: predicate logic
fact: proposition that’s unconditional true
rule: proposition that’s conditional true; dependent on other
propositions
a fact or a rule is a statement or clause in Prolog.
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
COM S 342 Principles of Programming Languages @ Iowa State University 27
Swi-prolog Programming
Install on mac: brew install swi-prolog
Install on different machines: https://www.swi-prolog.org/build/ edit your program in any aditor and save it as test.pl
run the program using: swipl -s test.pl
stop running the program: halt.
frequently used command link
Demo: case sensitive
COM S 342 Principles of Programming Languages @ Iowa State University 28
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: [WX,Yg(Z),Zh(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
numbers: max
list: append, reverse constraint problems
language parsing
graph search problems
COM S 342 Principles of Programming Languages @ Iowa State University 45