Transcript Additional Prolog Information

Prolog
a declarative language
• A program in a declarative programming
language consists of assertions rather
than assignments and control flow
statements.
• These declarations are actually
statements or propositions in symbolic
logic.
• Program doesn’t state how a result is to be
computed but what the result is.
Prolog program composition
• Collections of statements
• Kinds of statements
– Facts
– Rules
• Statements are constructed from terms
– A term is a constant, a variable, or a structure
Prolog program elements
• Constants are
– Atoms or integers
• Atoms are
– Symbolic values of Prolog
– String of letters, digits, and underscores that
begins with a lowercase letter OR
– String of any printable ASCII characters
delimited by apostrophes
Prolog program elements
• Variables are
– any string of letters, digits, and underscores
that begins with an upper case letter
– not bound to types by declarations
– bound to values and types by instantiations
• Instantiation occurs only in resolution process
– not like variables in imperative languages
Prolog program elements
• Structures
– have the general form functor(parameter_list)
– functor is any atom & it identifies the structure
– parameter_list can be any list of atoms
variables or other structures.
– are the way to specify facts in Prolog
– can be thought of as objects
– are relations
– are predicates
Prolog facts
• Facts
– state relations explicitly
• man(paul).
• rich(joan).
– SWI-Prolog doesn’t like spaces between the name of the
relation and the left parenthesis. PDProlog doesn’t care.
– are propositions that are assumed to be true
– are the statements from which new information can
be inferred
– are headless Horn clauses
– have no intrinsic semantics
Prolog rules
• Rules
–
–
–
–
–
are headed Horn clauses
right side is the antecedent or if part
left side is the consequent or then part
consequent must be a single term,
antecedent may be either a single term or a
conjunction
•
•
•
•
•
rich(joan) :- has_money(joan).
rich(joan) :- has_health(joan),has_job(joan).
Conjunctions contain multiple terms separated by logical and
:- is read as if
, means and
Example
parent(X,Y) :- mother(X,Y).
parent(X,Y) :- father(X,Y).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
sibling(X,Y) :mother(M,X),mother(M,Y),father (F,X),
father(F,Y).
Prolog as a theorem proving model
• proposition
– is the form of the theorem that we want to prove or
disprove
– is called a goal
– is called a query
– syntactic form is that of a headless Horn clause
• man(fred).
– returns yes OR returns no
– yes means that system proved goal was true under given
database of facts and relationships
– no means either the goal was proved false OR system was
simply unable to prove it.
Sidebar 1
• The process of determining useful values
for variables is called unification.
• The temporary assigning of values to
variables to allow unification is called
instantiation.
• Resolution is an inference rule that allows
inferred propositions to be computed from
given propositions.
Sidebar 2
• Horn clauses come in two forms
– Single atomic proposition on the left side OR
– Empty left side
– Left side is called the head
– Horn clauses with left sides are called headed
Horn clauses
– Horn clauses with empty left sides are called
headless Horn clauses.
Example
Database:
p(X) :- q(X), not (r(X)).
r(X) :- w(X), not (s(X)).
q(a).
q(b).
q(c).
s(a).
s(a).
w(a).
w(b).
Queries
p(a).
p(b).
p(c).
Example
Database:
bachelor(P) :- male(P), not
(married(P)).
male(henry).
male(tom).
married(tom).
Queries:
bachelor(henry).
bachelor(tom).
bachelor(Who).
married(Who).
not(married(Who)).
Prolog operators
• relational operators
\=
=
>=
<=
>
<
• Assignment operator
is is peculiar - not like ordinary assignment
operator
Behavior of Prolog “is”
• takes an arithmetic expression as its right
operand
• takes a variable as its left operand
• all variables in the arithmetic expression must
already be instantiated
• left-side variable cannot be previously
instantiated
• Discussion Examples:
A is B / 17 + C
X is X + 1
Prolog Arithmetic Example
•
•
•
•
•
•
•
•
•
speed(ford,100).
speed(chevy,105).
speed(dodge,95).
speed(volvo,80).
time(ford,20).
time(chevy,21).
time(dodge,24).
time(volvo,24).
distance (X,Y) :- speed(X,Speed), time(X,Time),
Y is Speed * Time.
Short Prolog backtracking example
/* facts */
likes(jake,chocolate).
likes(jake,apricots).
likes(darcie,licorice).
likes(darcie,apricots).
/* query or goal */
likes(jake,What), likes(darcie,What).
Miscellanea
• parameters , arguments
• arity – number of parameters/arguments in a
parameter list
• anonymous variable – used when don’t care
mother (X, _).
likes (_, What).
• logical operators , means and
; means or
\+ means not in SWI - Prolog
not means not in PD Prolog
Miscellania
• retract( ). - can be used to delete a single
fact or relation
• forget( ). – can be used to remove a file
you have consulted
• halt. – exits gracefully from SWI-Prolog
• differences between
– listing.
– dir p.
– dir.
Prolog lists
• Lists
– are written in square brackets with commas between
the list’s element
[condor,whooping_crane, dusky_seaside_sparrow]
– can be used as the argument of a relation
rarebird([condor,whooping_crane, dusky_seaside_sparrow]).
–
–
–
–
can be queried
can take advantage of anonymous variables
have a head and a tail
can be processed recursively
List Example
Database:
rarebird([condor,whooping_crane, dusky_seaside_sparrow]).
Queries:
rarebird(condor).
rarebird(What).
List Example - continued
Database:
rarebird([condor,whooping_crane, dusky_seaside_sparrow]).
noteworthy(Bird) :- rarebird([Bird, __,__]).
noteworthy(Bird) :- rarebird([__,Bird, __]).
noteworthy(Bird) :- rarebird([__,__, Bird]).
Queries:
rarebird(condor).
rarebird(What).
noteworthy(condor).
noteworthy(Who).
List Example - continued
Database:
rarebird([condor,whooping_crane, dusky_seaside_sparrow]).
noteworthy(Bird) :- rarebird([Bird, __,__]).
noteworthy(Bird) :- rarebird([__,Bird, __]).
noteworthy(Bird) :- rarebird([__,__, Bird]).
rarebird(Bird) :- noteworthy(Bird).
Queries:
rarebird(condor).
rarebird(What).
noteworthy(condor).
noteworthy(Who).
Head | Tail examples
• Database
rarebird([condor,whooping_crane, dusky_seaside_sparrow]).
• Query
rarebird([H | T]).
P638.pro
append ([], List, List).
append([Head | List_1], List_2, [Head |
List_3]) :append (List_1, List_2, List_3).
P6382.pro
list_op_2( [],[]).
list_op_2( [Head | Tail], List) :list_op_2 (Tail, Result),
append (Result, [Head], List).
P639.pro
member (Element, [Element | _ ] ).
member (Element, [_ | List]) :- member
(Element, List
Matching a goal to a fact
• Start with facts and rules and attempt to find a
sequence of matches that lead to the goal.
– Called bottom-up resolution
– Also called forward chaining
• Start with the goal and attempt to find a
sequence of matching propositions that lead to a
set of original facts in the database.
– Called top-down resolution
– Also called backward chaining
• Prolog implementations use backward chaining.
How is solution found?
• A depth-first search finds a complete
sequence of proposition - a proof- for the
first subgoal before working on the others.
• A breadth-first search works on all
subgoals of a given goal in parallel.
• Prolog’s designers chose depth-first
approach
– uses fewer resources
Backtracking
• When a goal with multiple subgoals is being
processed and the system fails to show the truth
of one of the subgoals, the system abandons the
subgoal it could not prove.
• It then reconsiders the previous subgoal,if there
is one, and attempts to find an alternative
solution to it.
• A new solution is found by beginning the search
where the previous search for that subgoal
stopped.
• Multiple solutions to a subgoal result from
different instantiations of its variables.