PROgramming LOGic
A logic programming language is
a notational system for writing logical statements together with
specified algorithms for implementing inference rules.
What will be cover ?
- Simple descriptions of Prolog Syntax
- A small example program,
- Unification and Pattern Matching
- Queries and the Searching Mechanisms
- The Computational Model
What is Prolog?
- Prolog is a logical programming language.
- Prolog has a very simple syntax with dynamic type checking.
- the variable takes the type need by the context
- Prolog programs are statements of rules
and facts.
- Program execution is deduction
- can an answer be inferred from the program (known rules and facts)
- Prolog uses
- queries to initiate execution
- Horn clauses to specify rules
- unification to instantiate variables
- resolution to see if a goal succeeds
- a depth first strategy to search the solution
space
- backtracking when a goal fails
- Elements of Prolog:
- Atoms and numbers
are the elementary data objects
- Numbers
are ordinary literals and values
- Atoms
are identifiers that begin with a lower-case letter.
- Terms
that represent data objects --entities
- Clauses
are
facts
and rules that
specify relations among terms
- clauses are relations
among terms
- predicate names clauses
- and queries that ask
questions about how terms are related with respect to a collections of
facts and rules
- A Prolog program (procedure) is structured like the statement of a
Theorem
- Set of rules
- Set of facts -- database
- Interactive query -- executes the program.
Basic syntax of Edinburgh Prolog (EBNF)
<prologprog> -> <clause> { <clause> }
<clause> -> <fact> | <rule>
<fact> -> <pred> .
<pred> -> <atom> { ( <arglist> ) }
<rule> -> <head> :- <body> .
<head> -> <pred>
<body> -> <goal> { , <goal> }
<goal> -> <pred> | !
<query> -> <body>.
<arglist> -> <arg> { , <arg> }
<arg> -> <atom> | <var> | <list>
<atom> -> <lcchar> { <anychar> }
<atom> -> ' { <anychar> } '
<var> -> <ucchar> { <anychar> }
<var> -> _ { <anychar> }
<list> -> [ ]
<list> -> [ <arglist> ]
More on Syntax and Prolog terminology
- CASE sensitive
- Integers/Numbers: base 10
- facts,
rules and queries are
specified using terms
- symbolic atoms refer to specific objects
- name starts with lower case: john,
student2
- begin with upper case: Who, X
- _
{_name} can be used in place of variable name,
- Atom followed by a parenthesized sequence of sub-terms.
- The atom of structure is called a functor.
- Functors can represent name of predicate
- Structures are just relations.
- They are not functions.
- There are no inputs or outputs for the variables of the
structures.
- Sub-terms are called arguments.
- Example: student(ali,
freshman, 194).
- student is the
functor with arity 3
- NOTE: student is not a function!
- NOTE: There is no space between an atom and "("
- Compound terms can be nested.
- Nested terms allows for recursive data
structures.
binarytree(node(10,binarytree(
node(5,empty,
binarytree(
node(8,empty,empty)))) ,empty)).
- A fact expresses unconditional
relationship among terms.
- student(ali, freshman, 194).
- fact is a clause
with an empty body
- A rule similar to a fact, except they assert a truth relation
that is guaranteed only under certain condition.
- grandmother(X,Y)
:-mother(X,Z),
mother(Z,Y).
- Rule is a clause with a head
and a body.
Head: grandmother(X,Y)
Body: mother(X,Z),
mother(Z,Y).
- Informal semantics of general rule :
p :- q1, q2
, q3 .
p is true if q1 and
q2 and q3 are true.
- Lists
- In earlier
version of SWIPL, [ Head|
Tail ] was short hand
(syntactic sugar) for .( Head , Tail )
- The `cons' operator for creating list cells has changed from
./2 to '[|]'/2
- L = '[|]'(1,[]).
- ./2 is now a dictionary predicate
- Sequences and the comma operator (tuples)
- Shortest sequence has one element, longer sequences have elements
separated by commas ",".
- (a,s,d).
- (F, Rest).
- Display of values for sequence variables will not have "()"
- ?- X=(1,2,3).
X = 1, 2, 3
- = is the
unification operator.
- is is a
special symbol that evaluates arithmetic operators.
Running a program.
- likes.pl
comes with the prolog installation
- If you have a swipl window:
?- consult (likes.pl ).
% likes.pl compiled 0.00 sec, 2408 bytes
true.
or
?- [likes].
% likes compiled 0.00 sec, 2408 bytes
true.
- OR in an explorer window - double click on the file name.
Editing a program.
- You can use notepad.
- In the swipl window you can type
?- emacs('likes.pl').
The file must be in the current path and the file does not have to be
loaded yet.
Comments
- Comments are either bound by /* ,*/
or any characters following the % .
- The swipl documentation of the built-in predicates does indicate how
the variables should be used.
pred(+var1, -var2, +var3).
+ indicates input variable
- indicates output variable
- You can also consult (load) a file with a pl extension by
?- [family].
% family compiled 0.00 sec, 2,056 bytes
true.
Sample execution: family.pl
- Prolog: The order of the facts and rules (in the file) is the order of
the search and is a variation from pure logic model
2 ?- father( X, Y ).
X = mike /* BLUE represents
computer output */
Y = ann ; /* User types ; to
continue searching the data */
X = mike
Y = joe ;
X = tom
Y = mary ;
3 ?- father( X, joe).
X = mike;
false.
Spring, 2019
On Functors {in
different programming languages}
Dot
notation (cons) in Prolog
Lists are
special in Prolog