Transcript Logic Programming and Prolog

Logic Programming
and Prolog
Danielle and Joseph Bennett
24 April 2007
What is Logic Programming?
What is Logic Programming?

“The use of mathematical logic for computer
programming.” (Wikipedia)

“A declarative, relational style of
programming based on first-order logic.”
(Dictionary.com)
History of Logic Programming

Came about in 1960s and 1970s due to
debates about using declarative or
procedural representations in AI

Stanford and Edinburgh – declarative

MIT - procedural

Developed Planner in 1969 (first language in the
proceduralistic paradigm).
Systems for Logic Programming














ALF
CLP
ECLiPSe
Elf
Fish
Flang
Gödel
KLIC
LIFE
MONA
Oz System
RELFUN
SAMPLE
XSB
Just to name a few….
Systems for Logic Programming, cont.

Prolog is the most common system

Prolog has many variations:











&-Prolog, And-parallel Prolog.
ACE, And-Or-parallel Prolog.
Actor Prolog
Andorra-I, an Or- and (deterministic) and-parallel Prolog.
Aurora, Or-parallel Prolog.
cu-Prolog, a constraint logic programming language
lambda Prolog
LeanTaP, a small theorem prover written in SICStus Prolog.
Logtalk, an extension for Object-Oriented Programming in Prolog.
Mixtus, an automatic partial evaluator for full Prolog.
Muse, Or-parallel Prolog.
All About Prolog
All About Prolog

Developed in 1972 by Alain Colmerauer and
Philippe Roussel

Name comes from “PROgramming in LOGic”

A solution to the debate about which kinds of
logic to use
Prolog Structure

Prolog facts – a database of predicates and
associations.

Prolog rules – define new predicates by using
Prolog facts.

Note: Prolog considers capital letters to
denote variables, not predicates.
Prolog Structure – Queries

A query searches the database for the first
fact that satisfies its goal.

If a fact is found it either unifies the variable
with a constant or returns yes.

If a fact is not found that meets that condition
it returns no.
Prolog Structure – Queries, cont.

Use a semi-colon to request subsequent
answers.

In other words, a semi-colon signifies
disjunction.

A comma signifies conjunction.
Prolog Structure - Unification




A query resolves by unifying all of its
elements.
A constant unifies with itself and any variable.
Scope is limited to the rule in which a variable
occurs.
When a variable is unified with a constant in
a rule, all instances of that variable in that
rule are unified to that constant.
Prolog Structure - Backtracking




In more complex examples, Prolog uses
backtracking to find possible solutions.
Prolog will attempt to resolve the first fact of its rule,
unifying any variables with the first constant that
satisfies that fact
It then attempts to resolve the rest of that rules
facts.
If it is unable to do so under those conditions it
“backs up” and tries again with the next available
unifying constant.
More Than Just Information



Prolog rules can also be used write programs that
do more than find the answers to simple database
queries.
append([], L, L).
append([H|T], L, [H|L1]):-append(T, L, L1).
This will append a list to another list recursively.
A binary tree can be defined as follows
tree(nil).
tree(node(_, Left, Right):-tree(left), tree(right).
How Prolog Works
Example from pages 45-46 of our text:
instructor (bebis, cs365)
instructor (looney, cs311)
instructor (yuksel, cs446)
enrolled (joseph, cs311)
enrolled (joseph, cs365)
enrolled (joseph, cs446)
enrolled (danielle, cs365)
enrolled (danielle, cs446)
This is the database of Prolog facts.
How Prolog Works, cont.
Prolog rules:
teaches (P,S) :- instructor (P,C), enrolled
(S,C)
This is to say that an instructor only teaches if
he teaches a class and students are enrolled
in that class.
How Prolog Works, cont.

Prolog answers queries based off of the database
that has been given.
?enrolled (joseph, cs365)
yes
?enrolled (X, cs365)
joseph
danielle
?teaches (X, joseph)
bebis
looney
yuksel
How Prolog Works, cont.
Imagine what happens if we expand the database:
























instructor (bebis, cs365)
instructor (looney, cs311)
instructor (yuksel, cs446)
instructor (helfand, cs493)
instructor (quint, math486)
enrolled (ben, cs365)
enrolled (bill, cs365)
enrolled (bill, cs446)
enrolled (brian, cs311)
enrolled (brian, cs365)
enrolled (brittney, cs311)
enrolled (brittney, cs365)
enrolled (brittney, cs446)
enrolled (cody, cs311)
enrolled (cody, cs365)
enrolled (danielle, cs365)
enrolled (danielle, cs446)
enrolled (danielle, cs493)
enrolled (david, cs365)
enrolled (javier, cs365)
enrolled (jeffrey, cs365)
enrolled (jessica, cs311)
enrolled (jessica, cs446)
enrolled (jessica, math486)





















enrolled (joel, cs365)
enrolled (joseph, cs311)
enrolled (joseph, cs365)
enrolled (joseph, cs446)
enrolled (joseph, cs493)
enrolled (joseph, math486)
enrolled (kellen, cs365)
enrolled (matts, cs311)
enrolled (matts, cs365)
enrolled (mattw, cs311)
enrolled (mattw, cs365)
enrolled (mattw, cs446)
enrolled (miran, cs365)
enrolled (ryan, cs365)
enrolled (samuel, cs365)
enrolled (shane, cs311)
enrolled (shane, cs365)
enrolled (shane, cs446)
enrolled (tiffany, cs311)
enrolled (tiffany, cs365)
enrolled (tiffany, cs446)
How Prolog Works, cont.
?enrolled (X, cs365)
ben
bill
brian
brittney
cody
danielle
david
javier
jeffrey
joel
joseph
kellen
matts
mattw
miran
ryan
samuel
shane
tiffany

This list now gives us the entire
roster of students in CS 365.
How Prolog Works, cont.
Queries can be more complicated to compare more data:
classmates (S1, S2) :- enrolled (S1, C), enrolled (S2, C)
?classmates (joseph, danielle)
yes
?classmates (joseph, jessica)
yes
?classmates (jessica, danielle)
no
How Prolog Works, cont.
classmates (S1, S2, C) :- enrolled (S1, C), enrolled (S2, C)
?classmates (joseph, danielle, C)
cs365
cs446
cs493
no
?classmates (joseph, jessica, C)
math
?classmates (jessica, danielle, C)
no
Free Prolog Access



SWI-Prolog
http://www.swi-prolog.org/
YAProlog
http://www.ncc.up.pt/~vsc/Yap/
Strawberry Prolog
http://www.dobrev.com/
Sources





http://www.afm.sbu.ac.uk/logic-prog/
http://en.wikipedia.org/wiki/Logic_programming
http://dictionary.reference.com/browse/logic%20program
ming
Pages 45-46 of our textbook
CS 326 lectures on Prolog (written by Dr. Mircea
Nicolescu)