Transcript Term

CS4026
Formal Models of Computation
Part II
The Logic Model
Lecture 3 – Prolog syntax and operation
Prolog
• An implementation of logic programming.
• There are others, but Prolog is by far the most successful.
• It is a programming language with its own style and
pragmatics.
• We will explore Prolog from a programming perspective
(and not primarily logic-theoretic);
formal models of computation
2
Prolog: Syntax
• A Prolog program is a sequence of facts and rules
• The logical symbols must get an ASCII representation:
– The “neck” of a clause is “:-”
– Conjunction indicated by “,” and disjunction indicated by “;”
– All clauses (fact, rules and queries) must end with “.” (to inform the
interpreter it is indeed the end)
– Variables, predicate names, constants, etc. also have their
representation, as we’ll see…
• Prolog programs can be compiled or interpreted, but Prolog
systems support the following basic functionality:
– Edit your program in a file and load it in Prolog
– Run the program by entering a query
formal models of computation
3
Variables
• Variables in Prolog are represented by
–
–
–
–
Any string starting with a capital letter (A-Z)
Any string starting with “_” (underscore)
Examples: X, X1, X_1, ThisIsAVariable, _23
Also, the anonymous variable “_” (underscore)
• Once a variable gets a value, there is no way to change it!
(no destructive assignments!)
• Variables can be aliased (just like in Java) thus sharing their
values with other variables.
• We say a variable is instantiated when it has a value,
otherwise it is uninstantiated.
formal models of computation
4
Variables in Haskell vs Prolog
• As in Haskell, every time a definition (Haskell)/
clause (Prolog) is used the variables in the
definition can have a new value
• As in Haskell, for a particular use of a definition/
clause a variable always denotes the same value
• As in Haskell, there is no way to destructively
assign a value to a variable
• Unlike Haskell, a variable can be used when it has
not yet been assigned a value, and two such
variables can be aliased
• In Prolog, variables obtain their values primarily
through the effects of unification
formal models of computation
5
Constants
• Constants (or atoms) are
–
–
–
–
Any string starting with a non-capital letter (a-z)
Any string within ’…’ (single quotes)
Numbers (integers, reals, scientific notation)
Examples:
anAtom
’AnotherConstant’ 123.4
true false thisIsAVeryLongAtom
formal models of computation
6
Terms
• Terms are means to structure information.
• Terms are
FunctorName(SubTerm1,…,SubTermn)
• FunctorName must be a constant (not numbers!)
• SubTermi is a
– constant, or
– a variable, or
– another (nested) term
• Examples:
has(john,jaguar)
s(s(s(s(s(0)))))
date(15,Month,2003)
p(q(X,123),a45)
formal models of computation
7
Terms (Cont’d)
• Term: functor and arguments
FunctorName(SubTerm1,…,SubTermn)
functor
arguments
• Terms are stored internally as trees.
• Examples:
has
john
jaguar
date
15
Month
formal models of computation
2003
8
Matching Terms (Unification)
• Terms can be matched, that is, compared.
• Two terms match if
– They are identical, or
– If their variables can be assigned values so that the terms become
identical.
• Two terms are matched by traversing their trees comparing
their nodes and assigning values to variables (if needed).
• Terms are matched when a goal is matched against the
head of a clause.
• Terms can also be matched via the built-in “=” operator – it
compares and, if possible, assigns values to variables.
[NB remember that a variable can only be assigned a value if
it doesn’t yet have one (is uninstantiated)]
formal models of computation
9
Matching Terms (Cont’d)
• Example:
date(2,april,Year) matches date(Day,Month,2003)
date
2
april
date
Year
Day Month
2003
Day is instantiated to 2
Month is instantiated to april
Year is instantiated to 2003
• The terms below don’t match – why?
p(1,s(X,a),foo)
p(A,s(1,A),B)
formal models of computation
10
Matching in Haskell vs Prolog
• We have seen pattern matching in Haskell – used:
– to test whether a case of a definition is appropriate
– to transfer values from actual parameters to formal
parameters (local variables)
• In Haskell, it is one-way matching – information
flows from the call to the function body, not the
reverse:
tail (_:xs) = xs
Main> tail 4:3:2:1:[]
• In Prolog, it is two-way matching – information can
pass out to the caller:
p(X,f(X)).
:- p(a,Y), q(Y)…
formal models of computation
11
Facts
• Facts are terms which must end with “.”
• Examples:
has(john,car(jaguar)).
has(john,book(’AnimalFarm’)).
date(23,april,2003).
• Facts establish what is true about something.
• Facts represent what is important to the problem we want
to solve.
• As programmers, we create facts and their meaning:
loves(ann,bob).
(who loves whom?)
formal models of computation
12
Rules
• Rules are of the form
Term :- Term, Term, …, Term.
• N.B.: rules must end with “.” !!
• We refer head
to the head and body of a rule:
Term :- Term, Term, …, Term.
body
• A fact is a rule with an empty body (so, no “:-”)
• The terms of a rule are also called (sub-)goals.
• Examples:
rich(X):- has(X,jaguar).
goodPC(Cf):- ram(Cf,256), processor(Cf,pIII).
formal models of computation
13
Prolog Programs
•
•
•
•
Programs are sequences of facts and rules.
There is no restriction on the layout of programs.
To improve visualisation, write facts in separate lines.
Rules can be split into different lines if too big:
grandfather(X,Y):father(X,Z),
father(Z,Y).
• Humans (you!) will read your program – make their life
easier and COMMENT YOUR CODE!!
grandfather(X,Z):father(X,Y),
father(Y,Z).
% X is a grandfather of Y if
% - X is the father of Z and
% - Z is the father of Y
formal models of computation
14
Prolog Programs
• Sometimes we have different rules with the same head goal
– these are the distinct cases.
• Rules with the same head goal should be written together.
• The rules that have the same head goal are said to define a
predicate;
• As programmers, we can equate a predicate with a
procedure.
formal models of computation
15
Type Checking in Haskell and Prolog
• In Haskell, every function has a single type (either
inferred, or explicitly given by the programmer)
• The type information can be used to detect silly
errors in programs
• Prolog has no typing – any predicate or functor can
apply to any kinds of Prolog terms
formal models of computation
16
Queries
• Queries are of the form
:- Term, Term, …, Term.
•
•
•
•
N.B.: queries must end with “.” !!
The terms of a query are also called (sub-)goals.
A query is a clause without a head term.
Prolog offers a prompt for us to enter queries, so we don’t
need to type “:-” (it is assumed).
• However, the period at the end is essential!
• Example:
?- rich(X).
prompt
formal models of computation
17
Queries (Cont’d)
• A Prolog program is run/executed when we pose
queries.
• An execution is a proof of a query:
– If the query is true Prolog will say “yes”;
– If not Prolog will say “no”.
• We use `execution` & `proof` as synonyms in
the context of Prolog programs.
formal models of computation
18
Haskell vs Prolog: Interaction loop
• Haskell systems operate a “read - evaluate - print”
loop:
Main> fac 3
6
• Prolog systems operate a “read - satisfy –print”
loop:
?- fac(3,X).
X = 6?
• There may be more than one answer to a Prolog
query. Responding to the “?” with “;” asks for
alternative solutions; responding <return> returns
to the main loop. In this context, “no” from Prolog
means “no more solutions”.
formal models of computation
19