Declarative Programming
Lecture 0
Subject Introduction
Copyright c 2023 The University of Melbourne
COMP90048 Declarative Programming
Subject Introduction
Welcome to Declarative Programming
Contact information is available from the LMS.
There will be two pre-recorded one-hour lectures per week, plus one live
one-hour practical meeting for questions, discussion, and demonstrations.
There will be eleven one-hour workshops (labs), starting in week 2.
You should have already been allocated a workshop. Please check your
personal timetable after the lecture.
COMP90048 Declarative Programming Lecture 0 – 1 / 16
Subject Introduction
Grok
We use Grok to provide added self-paced instructional material, exercises,
and self-assessment for both Haskell and Prolog.
You can access Grok by following the link from the subject LMS page.
If you are unable to access Grok or find that it is not working correctly,
please email
Grok University Support
from your university email account and explain the problem.
If you have questions regarding the Grok lessons or exercises, please post a
message to the subject LMS discussion forum.
COMP90048 Declarative Programming Lecture 0 – 2 / 16
Subject Introduction
Workshops
The workshops will reinforce the material from lectures, partly by asking
you to apply it to small scale programming tasks.
To get the most out of each workshop, you should read and attempt the
exercises before your workshop. You are encouraged to ask questions,
discuss, and actively engage in workshops. The more you put into
workshops, the more you will get out of them.
Workshop exercises will be available through Grok, so they can be
undertaken even if you are not present in Australia. Sample solutions for
each set of workshop exercises will also be available through Grok.
Most programming questions have more than one correct answer; your
answer may be correct even if it differs from the sample solution.
NOTE
If your laptop can access the building’s wireless network, you will be able
to use Grok, giving you access to Prolog and Haskell. If your laptop
cannot access the building’s wireless network, then you will be able to test
your Haskell or Prolog code if you install the implementations of those
languages on your machine yourself. For both languages this is typically
fast and simple.
COMP90048 Declarative Programming Lecture 0 – 3 / 16
Subject Introduction
Resources
The lecture notes contain copies of the slides presented in lectures, plus
some additional material.
All subject materials (lecture notes, workshop exercises, project
specifications etc) will be available online through the LMS.
The recommended text (which is available online)is
Bryan O’Sullivan, John Goerzen and Don Stewart: Real world Haskell.
Other recommended resources are listed on the LMS.
COMP90048 Declarative Programming Lecture 0 – 4 / 16
Subject Introduction
Academic Integrity
All assessment for this subject is individual; what you submit for
assessment must be your work and your work alone.
It is important to distinguish project work (which is assessed) from
tutorials and other unassessed exercises.
We are well aware that there are many online sources of material for
subjects like this one; you are encouraged to learn from any online sources,
and from other students, but do not submit for assessment anything that
is not your work alone.
Do not provide or show your project work to any other student.
Do not store your project work in a public Github or other repository.
We use sophisticated software to find code that is similar to other
submissions this year or in past years. Students who submit another
person’s work as their own or provide their work for another student to
submit in whole or in part will be subject to disciplinary action.
COMP90048 Declarative Programming Lecture 0 – 5 / 16
Subject Introduction
How to succeed
Declarative programming is substantially different from imperative
programming.
Even after you can understand declarative code, it can take a while before
you can master writing your own.
If you have been writing imperative code all your programming life, you will
probably try to write imperative code even in a declarative language. This
often does not work, and when it does work, it usually does not work well.
Writing declarative code requires a different mindset, which takes a while
to acquire.
This is why attending the workshops, and practicing, practicing and
practicing some more are essential for passing the subject.
COMP90048 Declarative Programming Lecture 0 – 6 / 16
Subject Introduction
Sources of help
During contact hours:
Ask me during or after a lecture (not before).
Ask the demonstrator in your workshop.
Outside contact hours:
The LMS discussion board (preferred: everyone can see it)
Email (if not of interest to everyone)
Attend my consultation hours (see LMS for schedule)
Email to schedule an appointment
Subject announcements will be made on the LMS.
Please monitor the LMS for announcements, and the discussion forum for
detailed information. Read the discussion forum before asking questions;
questions that have already been answered will not be answered again.
COMP90048 Declarative Programming Lecture 0 – 7 / 16
Subject Introduction
Objectives
On completion of this subject, students should be able to:
apply declarative programming techniques;
write medium size programs in a declarative language;
write programs in which different components use different languages;
select appropriate languages for each component task in a project.
These objectives are not all of equal weight; we will spend almost all of
our time on the first two objectives.
COMP90048 Declarative Programming Lecture 0 – 8 / 16
Subject Introduction
Content
Introduction to logic programming and Prolog
Introduction to constraint programming
Introduction to functional programming and Haskell
Declarative programming techniques
Tools for declarative programming, such as debuggers
Interfacing to imperative language code
This subject will teach you Haskell and Prolog, with an emphasis on
Haskell.
For logistical reasons, we will begin with Prolog.
COMP90048 Declarative Programming Lecture 0 – 9 / 16
Subject Introduction
Why Declarative Programming
Declarative programming languages are quite different from imperative and
object oriented languages.
They give you a different perspective: a focus on what is to be done,
rather than how.
They work at a higher level of abstraction.
They make it easier to use some powerful programming techniques.
Their clean semantics means you can do things with declarative
programs that you can’t do with conventional programs.
The ultimate objective of this subject is to widen your horizons and thus
to make you better programmers, and not just when using declarative
programming languages.
COMP90048 Declarative Programming Lecture 0 – 10 / 16
Subject Introduction
Imperative vs logic vs functional programming
Imperative languages are based on commands, in the form of instructions
and statements.
Commands are executed.
Commands have an effect, such as to update the computation state,
and later code may depend on this update.
Logic programming languages are based on finding values that satisfy a set
of constraints.
Constraints may have multiple solutions or none at all.
Constraints do not have an effect.
Functional languages are based on evaluating expressions.
Expressions are evaluated.
Expressions do not have an effect.
COMP90048 Declarative Programming Lecture 0 – 11 / 16
Subject Introduction
Side effects
Code is said to have a side effect if, in addition to producing a value, it
also modifies some state or has an observable interaction with calling
functions or the outside world. For example, a function might
modify a global or a static variable,
modify one of its arguments,
raise an exception (e.g. divide by zero),
write data to a display, file or network,
read data from a keyboard, mouse, file or network, or
call other side-effecting functions.
NOTE
Reading from a file is a side effect because it moves the current position in
the file being read, so that the next read from that file will get something
else.
COMP90048 Declarative Programming Lecture 0 – 12 / 16
Subject Introduction
An example: destructive update
In imperative languages, the natural way to insert a new entry into a table
is to modify the table in place: a side-effect. This effectively destroys the
old table.
In declarative languages, you would instead create a new version of the
table, but the old version (without the new entry) would still be there.
The price is that the language implementation has to work harder to
recover memory and to ensure efficiency.
The benefit is that you don’t need to worry what other code will be
affected by the change. It also allows you to keep previous versions, for
purposes of comparison, or for implementing undo.
The immutability of data structures also makes parallel programming
much easier. Some people think that programming the dozens of cores
that CPUs will have in future is the killer application of declarative
programming languages.
COMP90048 Declarative Programming Lecture 0 – 13 / 16
Subject Introduction
Guarantees
If you pass a pointer to a data structure to a function, can you
guarantee that the function does not update the data structure?
If not, you will need to make a copy of the data structure, and pass a
pointer to that.
You add a new field to a structure. Can you guarantee that every
piece of code that handles the structure has been updated to handle
the new field?
If not, you will need many more test cases, and will need to find and
fix more bugs.
Can you guarantee that this function does not read or write global
variables? Can you guarantee that this function does no I/O?
If the answer to either question is “no”, you will have much more
work to do during testing and debugging, and parallelising the
program will be a lot harder.
COMP90048 Declarative Programming Lecture 0 – 14 / 16
Subject Introduction
Some uses of declarative languages
In a US Navy study in which several teams wrote code for the same
task in several languages, declarative languages like Haskell were
much more productive than imperative languages.
Mission Critical used Mercury to build an insurance application in one
third the time and cost of the next best quote (which used Java).
Ericsson, one of the largest manufacturers of phone network switches,
uses Erlang in some of their switches.
The statistical machine learning algorithms behind Bing’s advertising
system are written in F#.
Facebook used Haskell to build the system they use to fight spam.
Haskell allowed them to increase power and performance over their
previous system.
NOTE
Erlang, F# and Lisp are of course declarative languages.
For a whole bunch of essays about programming, including some about the
use of Lisp in Yahoo! Store, see paulgraham.com.
COMP90048 Declarative Programming Lecture 0 – 15 / 16
Subject Introduction
The Blub paradox
Consider Blub, a hypothetical average programming language right in the
middle of the power continuum.
When a Blub programmer looks down the power continuum, he knows he
is looking down. Languages below Blub are obviously less powerful,
because they are missing some features he is used to.
But when a Blub programmer looks up the power continuum, he does not
realize he is looking up. What he sees are merely weird languages. He
thinks they are about equivalent in power to Blub, but with some extra
hairy stuff. Blub is good enough for him, since he thinks in Blub.
When we switch to the point of view of a programmer using a language
higher up the power continuum, however, we find that she in turn looks
down upon Blub, because it is missing some things she is used to.
Therefore understanding the differences in power between languages
requires understanding the most powerful ones.
NOTE
This slide is itself paraphrased from one of Paul Graham’s essays. (The full
quotation is too big to fit on one slide.)
The least abstract and therefore least powerful language is machine code.
One step above that is assembler, and one step above that are the lowest
level imperative languages, like C and Fortran. Everyone agrees on that.
Most people (but not all) would also agree that modern object-oriented
languages like Java and C#, scripting languages like awk and Perl and
multi-paradigm languages like Python and Ruby are more abstract and
more powerful than C and Fortran, but there is no general agreement on
their relative position on the continuum. However, almost everyone who
knows declarative programming languages agrees that they are more
abstract and more powerful than Java, C#, awk, Perl, Python and Ruby.
A large part of that extra power is the ability to offer many more
guarantees.
COMP90048 Declarative Programming Lecture 0 – 16 / 16
Introduction to Logic Programming
The University of Melbourne
School of Computing and Information Systems
COMP90048
Declarative Programming
Lecture 1
Introduction to
Logic Programming
Copyright c? 2023 The University of Melbourne
COMP90048 Declarative Programming
Introduction to Logic Programming
Logic programming
Imperative programming languages are based on the machine architecture
of John von Neumann, which executes a set of instructions step by step.
Functional programming languages are based on the lambda calculus of
Alonzo Church, in which functions map inputs to outputs.
Logic programming languages are based on the predicate calculus of
Gottlob Frege and the concept of a relation, which captures a relationship
among a number of individuals, and the predicate that relates them.
A function is a special kind of relation that can only be used in one
direction (inputs to outputs), and can only have one result. Relations do
not have these limitations.
While the first functional programming language was Lisp, implemented by
John McCarthy’s group at MIT in 1958, the first logic programming
language was Prolog, implemented by Alain Colmerauer’s group at
Marseille in 1971.
NOTE
Since the early 1980s, the University of Melbourne has been one of the
world’s top centers for research in logic programming.
Lee Naish designed and implemented MU-Prolog, and led the development
of its successor, NU-Prolog.
Zoltan Somogyi led the development of Mercury, and was one of its main
implementors.
NOTE
The name “Prolog” was chosen by Philippe Roussel as an abbreviation for
“programmation en logique”, which is French for “programming in logic”.
MU-Prolog and NU-Prolog are two closely-related dialects of Prolog.
There are many others, since most centers of logic programming research
in the 1980s implemented their own versions of the language.
The other main centers of logic programming research are in Leuven,
Belgium; Uppsala, Sweden; Madrid, Spain; and Las Cruces, New Mexico,
USA.
COMP90048 Declarative Programming Lecture 1 – 1 / 20
Introduction to Logic Programming
Relations
A relation specifies a relationship; for example, a family relationship. In
Prolog syntax,
parent(queen_elizabeth, prince_charles).
specifies (a small part of the) parenthood relation, which relates parents to
their children. This says that Queen Elizabeth is a parent of Prince
Charles.
The name of a relation is called a predicate. Predicates have no
directionality: it makes just as much sense to ask of whom is Queen
Elizabeth a parent as to ask who is Prince Charles’s parent. There is also
no promise that there is a unique answer to either of these questions.
COMP90048 Declarative Programming Lecture 1 – 2 / 20
Introduction to Logic Programming
Facts
A statement such as:
parent(queen_elizabeth, prince_charles).
is called a fact. It may take many facts to define a relation:
% (A small part of) the British Royal family
parent(queen_elizabeth, prince_charles).
parent(prince_philip, prince_charles).
parent(prince_charles, prince_william).
parent(prince_charles, prince_harry).
parent(princess_diana, prince_william).
parent(princess_diana, prince_harry).
...
Text between a percent sign (%) and end-of-line is treated as a comment.
COMP90048 Declarative Programming Lecture 1 – 3 / 20
Introduction to Logic Programming
Using Prolog
Most Prolog systems have an environment similar to GHCi. A file
containing facts like this should be written in a file whose name begins
with a lower-case letter and contains only letters, digits, and underscores,
and ends with “.pl”.
A source file can be loaded into Prolog by typing its filename (without the
.pl extension) between square brackets at the Prolog prompt (?-). Prolog
prints a message to say the file was compiled, and true to indicate it was
successful (user input looks like this):
?- [royals].
% royals compiled 0.00 sec, 8 clauses
true.
?-
NOTE
Some Prolog GUI environments provide other, more convenient, ways to
load code, such as menu items or drag-and-drop.
COMP90048 Declarative Programming Lecture 1 – 4 / 20
Introduction to Logic Programming
Queries
Once your code is loaded, you can use or test it by issuing queries at the
Prolog prompt. A Prolog query looks just like a fact. When written in a
source file and loaded into Prolog, it is treated as a true statement. At the
Prolog prompt, it is treated as a query, asking if the statement is true.
?- parent(prince_charles, prince_william).
true .
?- parent(prince_william, prince_charles).
false.
COMP90048 Declarative Programming Lecture 1 – 5 / 20
Introduction to Logic Programming
Variables
Each predicate argument may be a variable, which in Prolog begins with a
capital letter or underscore and follows with letters, digits, and underscores.
A query containing a variable asks if there exists a value for that variable
that makes that query true, and prints the value that makes it true.
If there is more than one answer to the query, Prolog prints them one at a
time, pausing to see if more solutions are wanted. Typing semicolon asks
for more solutions; just hitting enter (return) finishes without more
solutions.
This query asks: of whom Prince Charles is a parent?
?- parent(prince_charles, X).
X = prince_william ;
X = prince_harry.
COMP90048 Declarative Programming Lecture 1 – 6 / 20
Introduction to Logic Programming
Multiple modes
The same parenthood relation can be used just as easily to ask who is a
parent of Prince Charles or even who is a parent of whom. Each of these is
a different mode, based on which arguments are bound (inputs;
non-variables) and which are unbound (outputs; variables).
- parent(X, prince_charles).
X = queen_elizabeth ;
X = prince_philip.
- parent(X, Y).
X = queen_elizabeth,
Y = prince_charles ;
X = prince_philip,
Y = prince_charles ;
...
COMP90048 Declarative Programming Lecture 1 – 7 / 20
Introduction to Logic Programming
Compound queries
Queries may use multiple predicate applications (called goals in Prolog and
atoms in predicate logic). The simplest way to combine multiple goals is
to separate them with a comma. This asks Prolog for all bindings for the
variables that satisfy both (or all) of the goals. The comma can be read as
“and”. In relational algebra, this is called an inner join (but do not worry if
you do not know what that is).
- parent(queen_elizabeth, X), parent(X, Y).
X = prince_charles,
Y = prince_william ;
X = prince_charles,
Y = prince_harry.
COMP90048 Declarative Programming Lecture 1 – 8 / 20
Introduction to Logic Programming
Rules
Predicates can be defined using rules as well as facts. A rule has the form
Head :- Body,
where Head has the form of a fact and Body has the form of a (possibly
compound) query. The :- is read “if”, and the clause means that the
Head is true if the Body is. For example
grandparent(X,Z) :- parent(X, Y), parent(Y, Z).
means “X is grandparent of Z if X is parent of Y and Y is parent of Z .”
Rules and facts are the two different kinds of clauses. A predicate can be
defined with any number of clauses of either or both kinds, intermixed in
any order.
COMP90048 Declarative Programming Lecture 1 – 10 / 20
Introduction to Logic Programming
Recursion
Rules can be recursive. Prolog has no looping constructs, so recursion is
widely used. Prolog does not have a well-developed a library of
higher-order operations, so recursion is used more in Prolog than in
Haskell, as you will see.
A person’s ancestors are their parents and the ancestors of their parents.
ancestor(Anc, Desc) :-
parent(Anc, Desc).
ancestor(Anc, Desc) :-
parent(Parent, Desc),
ancestor(Anc, Parent).
COMP90048 Declarative Programming Lecture 1 – 11 / 20
Introduction to Logic Programming
Equality
Equality in Prolog, written “=” and used as an infix operator, can be used
both to bind variables and to check for equality. Prolog is a
single-assignment language: once bound, a variable cannot be reassigned.
- X = 7.
X = 7.
- a = b.
false.
- X = 7, X = a.
false.
- X = 7, Y = 8, X = Y.
false.
COMP90048 Declarative Programming Lecture 1 – 12 / 20
Introduction to Logic Programming
Disjunction
Goals can be combined with disjunction (or) as well as conjunction (and).
Disjunction is written “;” and used as an infix operator. Conjunction
(“,”) has higher precedence (binds tighter) than disjunction, but
parentheses can be used to achieve the desired precedence.
Who are the children of Queen Elizabeth or Princess Diana?
?- parent(queen_elizabeth, X) ; parent(princess_diana, X).
X = prince_charles ;
X = prince_william ;
X = prince_harry.
COMP90048 Declarative Programming Lecture 1 – 13 / 20
Introduction to Logic Programming
Negation
Negation in Prolog is written “\+” and used as a prefix operator. Negation
has higher (tighter) precedence than both conjunction and disjunction. Be
sure to leave a space between the \+ and an open parenthesis.
Who are the parents of Prince William other than Prince Charles?
- parent(X, prince_william), \+ X = prince_charles.
X = princess_diana.
Disequality in Prolog is written as an infix “\=”. So X \= Y is the same as
\+ X = Y.
- parent(X, prince_william), X \= prince_charles.
X = princess_diana.
COMP90048 Declarative Programming Lecture 1 – 14 / 20
Introduction to Logic Programming
The Closed World Assumption
Prolog assumes that all true things can be derived from the program. This
is called the closed world assumption. Of course, this is not true for our
parent relation (that would require tens of billions of clauses!).
- \+ parent(queen_elizabeth, princess_anne).
true.
but Princess Anne is a daughter of Queen Elizabeth. Our program simply
does not know about her.
So use negation with great care on predicates that are not complete, such
as parent.
COMP90048 Declarative Programming Lecture 1 – 16 / 20
Introduction to Logic Programming
Negation as failure
Prolog executes \+ G by first trying to prove G. If this fails, then \+ G
succeeds; if it succeeds, then \+ G fails. This is called negation as failure.
In Prolog, failing goals can never bind variables, so any variable bindings
made in solving G are thrown away when \+ G fails. Therefore, \+ G cannot
solve for any variables, and goals such as these cannot work properly.
Is there anyone of whom Queen Elizabeth is not a parent?
Is there anyone who is not Queen Elizabeth?
- \+ parent(queen_elizabeth, X).
false.
- X \= queen_elizabeth.
false.
COMP90048 Declarative Programming Lecture 1 – 17 / 20
Introduction to Logic Programming
Execution Order
The solution to this problem is simple: ensure all variables in a negated
goal are bound before the goal is executed.
Prolog executes goals in a query (and the body of a clause) from first to
last, so put the goals that will bind the variables in a negation before the
negation (or \=).
In this case, we can generate all people who are either parents or children,
and ask whether any of them is different from Queen Elizabeth.
- (parent(X,_) ; parent(_,X)), X \= queen_elizabeth.
X = prince_philip ;
...
COMP90048 Declarative Programming Lecture 1 – 18 / 20
Introduction to Logic Programming
Datalog
The fragment of Prolog discussed so far, which omits data structures, is
called Datalog. It is a generalisation of what is provided by relational
databases. Many modern databases now provide Datalog features or use
Datalog implementation techniques.
capital(australia, canberra).
capital(france, paris).
...
continent(australia, australia).
continent(france, europe).
...
population(australia, 22_680_000).
population(france, 65_700_000).
...
COMP90048 Declarative Programming Lecture 1 – 19 / 20
Introduction to Logic Programming
Datalog Queries
What is the capital of France?
- capital(france, Capital).
Capital = paris.
What are capitals of European countries?
- continent(Country, europe), capital(Country, Capital).
Country = france,
Capital = paris.
What European countries have populations > 50,000,000?
- continent(Country, europe), population(Country, Pop),
| Pop > 50_000_000.
Country = france,
Pop = 65700000.
COMP90048 Declarative Programming Lecture 1 – 20 / 20
Beyond Datalog
The University of Melbourne
School of Computing and Information Systems
COMP90048
Declarative Programming
Lecture 2
Beyond Datalog
Copyright c? 2023 The University of Melbourne
COMP90048 Declarative Programming
Beyond Datalog
Terms
In Prolog, all data structures are called terms. A term can be atomic or
compound, or it can be a variable. Datalog has only atomic terms and
variables.
Atomic terms include integers and floating point numbers, written as you
would expect, and atoms.
An atom begins with a lower case letter and follows with letters, digits and
underscores, for example a, queen_elizabeth, or banana.
An atom can also be written beginning and ending with a single quote,
and have any intervening characters. The usual character escapes can be
used, for example \n for newline, \t for tab, and \’ for a single quote.
For example: ’Queen Elizabeth’ or ’Hello, World!\n’.
COMP90048 Declarative Programming Lecture 2 – 1 / 21
Beyond Datalog
Compound Terms
In the syntax of Prolog, each compound term is a functor (sometimes
called function symbol) followed by zero or more arguments; if there are
any arguments, they are shown in parentheses, separated by commas.
Functors are Prolog’s equivalent of what Haskell calls data constructors,
and have the same syntax as atoms.
For example, a small tree with 1 at the root, an empty left branch, and 2
in the right branch, could be written as:
node(leaf, 1, node(leaf, 2, leaf))
Because Prolog is dynamically typed, each argument of a term can be any
term, and there is no need to declare types.
Prolog has special syntax for some functors, such as infix notation.
COMP90048 Declarative Programming Lecture 2 – 2 / 21
Beyond Datalog
Variables
A variable is also a term. It denotes a single unknown term.
A variable name begins with an upper case letter or underscore, followed
by any number of letters, digits, and underscores.
A single underscore _ is special: it specifies a different variable each time it
appears.
Prolog is a single-assignment language: a variable can only be bound
(assigned) once.
Because the arguments of a compound term can be any terms, and
variables are terms, variables can appear in terms.
For example f(A,A) denotes a term whose functor is f and whose two
arguments can be anything, as long as they are the same; f(_,_) denotes
a term whose functor is f and has any two arguments.
COMP90048 Declarative Programming Lecture 2 – 3 / 21
Beyond Datalog
List syntax
Prolog has a special syntax for lists.
The empty list is denoted by [].
A non-empty list is denoted by [H | T], where H is the head element of
the list and T is the tail.
For example, the list containing 1, 2 and 3 can be denoted by
[1 | [2 | [3 | []]]].
If multiple head elements are known, this can be shortened to
[1, 2 | [3 | []]].
If all elements are known, then this can be shortened to [1, 2, 3]
COMP90048 Declarative Programming Lecture 2 – 4 / 21
Beyond Datalog
Ground vs nonground terms
A term is a ground term if it contains no variables, and it is a nonground
term if it contains at least one variable.
3 and f(a, b) are ground terms.
Since Name and f(a, X) each contain at least one variable, they are
nonground terms.
If a variable occurs more than once in a term, then, just as in Algebra,
each occurrance must be bound to an identical term.
COMP90048 Declarative Programming Lecture 2 – 5 / 21
Beyond Datalog
Substitutions
A substitution is a mapping from variables to terms.
Applying a substitution to a term means consistently replacing all
occurrences of each variable in the map with the term it is mapped to.
Note that a substitution only replaces variables, never atomic or
compound terms.
For example, applying the substitution {X1 7→ leaf, X2 7→ 1, X3 7→ leaf}
to the term node(X1,X2,X3) yields the term node(leaf,1,leaf).
Since you can get node(leaf,1,leaf) from node(X1,X2,X3) by
applying a substitution to it, node(leaf,1,leaf) is an instance of
node(X1,X2,X3).
Any ground Prolog term has only one instance, while a nonground Prolog
terms has an infinite number of instances.
COMP90048 Declarative Programming Lecture 2 – 6 / 21
Beyond Datalog
Unification
The term that results from applying a substitution θ to a term t is
denoted tθ.
A term u is therefore an instance of term t if there is some substitution θ
such that u = tθ.
A substitution θ unifies two terms t and u if tθ = uθ.
Consider the terms f(X, b) and f(a, Y).
Applying a substitution {X 7→ a} to those two terms yields f(a, b) and
f(a, Y), which are not syntactically identical, so this substitution is not a
unifier.
On the other hand, applying the substitution {X 7→ a, Y 7→ b} to those
terms yields f(a, b) in both cases, so this substitution is a unifier.
COMP90048 Declarative Programming Lecture 2 – 7 / 21
Beyond Datalog
Recognising proper lists
A proper list is either empty ([]) or not ([X|Y]), in which case, the tail of
the list must be a proper list. We can define a predicate to recognise these.
proper_list([]).
proper_list([Head|Tail]) :-
proper_list(Tail).
- [list].
Warning: list.pl:3:
Singleton variables: [Head]
% list compiled 0.00 sec, 2 clauses
true.
COMP90048 Declarative Programming Lecture 2 – 9 / 21
Beyond Datalog
Detour: singleton variables
Warning: list.pl:3:
Singleton variables: [Head]
The variable Head appears only once in this clause:
proper_list([Head|Tail]) :-
proper_list(Tail).
This often indicates a typo in the source code. For example, if Tail were
spelled Tial in one place, this would be easy to miss. But Prolog’s
singleton warning would alert us to the problem.
COMP90048 Declarative Programming Lecture 2 – 10 / 21
Beyond Datalog
Detour: singleton variables
In this case, there is no problem; to avoid the warning, we should begin
the variable name Head with an underscore, or just name the variable _.
proper_list([]).
proper_list([_Head|Tail]) :-
proper_list(Tail).
- [list].
% list compiled 0.00 sec, 2 clauses
true.
General programming advice: always fix compiler warnings (if possible).
Some warnings may indicate a real problem, and you will not see them if
they’re lost in a sea of unimportant warnings. It is easier to fix a problem
when the compiler points it out than when you have to find it yourself.
COMP90048 Declarative Programming Lecture 2 – 11 / 21
Beyond Datalog
Append
Appending two lists is a common operation in Prolog. This is a built in
predicate in most Prolog systems, but could easily be implemented as:
append([], C, C).
append([A|B], C, [A|BC]) :-
append(B, C, BC).
- append([a,b,c],[d,e],List).
List = [a, b, c, d, e].
COMP90048 Declarative Programming Lecture 2 – 12 / 21
Beyond Datalog
append is like proper_list
Compare the code for proper_list to the code for append:
proper_list([]).
proper_list([Head|Tail]) :-
proper_list(Tail).
append([], C, C).
append([A|B], C, [A|BC]) :-
append(B, C, BC).
This is common: code for a predicate that handles a term often follows
the structure of that term (as we will see in Haskell).
While the proper_list predicate is not very useful itself, it was worth
designing, as it gives a hint at the structure of other code that traverses
lists. Since types are not declared in Prolog, predicates like proper_list
can serve to indicate the notional type.
COMP90048 Declarative Programming Lecture 2 – 13 / 21
Beyond Datalog
Appending backwards
Unlike ++ in Haskell, append in Prolog can work in other modes:
- append([1,2,3], Rest, [1,2,3,4,5]).
Rest = [4, 5].
- append(Front, [3,4], [1,2,3,4]).
Front = [1, 2] ;
false.
- append(Front,Back,[a,b,c]).
Front = [],
Back = [a, b, c] ;
Front = [a],
Back = [b, c] ;
Front = [a, b],
Back = [c] ;
Front = [a, b, c],
Back = [] ;
false.
COMP90048 Declarative Programming Lecture 2 – 14 / 21
Beyond Datalog
Length
The length/2 built-in predicate relates a list to its length:
- length([a,b,c], Len).
Len = 3.
- length(List, 3).
List = [_2956, _2962, _2968].
The _. . . terms are how Prolog prints out unbound variables. The number
reflects when the variable was created; because these variables are all
printed differently, we can tell they are all distinct variables.
[_2956, _2962, _2968] is a list of three distinct unbound variables, and
each unbound variable can be any term, so this can be any three-element
list, as specified by the query.
COMP90048 Declarative Programming Lecture 2 – 15 / 21
Beyond Datalog
Putting them together
How would we implement a predicate to take the front n elements of a
list in Prolog?
take(N,List,Front) should hold if Front is the first N elements of
List. So length(Front,N) should hold.
Also, append(Front, _, List) should hold. Then:
take(N, List, Front) :-
length(Front,N),
append(Front, _, List).
Prolog coding hint: think about checking if the result is correct rather
than computing it. That is, think of what instead of how.
Then you need to think about whether your code will work the ways you
want it to. We will return to that.
COMP90048 Declarative Programming Lecture 2 – 16 / 21
Beyond Datalog
Member
Here is list membership, two ways:
member1(Elt, List) :- append(_,[Elt|_], List).
member2(Elt, [Elt|_]).
member2(Elt, [_|Rest]) :- member2(Elt, Rest).
These behave the same, but the second is a bit more efficient because the
first builds and ignores the list of elements before Elt in List, and the
second does not.
Note the recursive version does not exactly match the structure of our
earlier proper_list predicate. This is because Elt is never a member of
the empty list, so we do not need a clause for []. In Prolog, we do not
need to specify when a predicate should fail; only when it should succeed.
We also have two cases to consider when the list is non-empty (like
Haskell in this respect).
COMP90048 Declarative Programming Lecture 2 – 18 / 21
Beyond Datalog
Arithmetic
In Prolog, terms like 6 * 7 are just data structures, and = does not
evaluate them, it just unifies them.
The built-in predicate is/2 (an infix operator) evaluates expressions.
- X = 6 * 7.
X = 6*7.
- X is 6 * 7.
X = 42.
COMP90048 Declarative Programming Lecture 2 – 19 / 21
Beyond Datalog
Arithmetic modes
Use is/2 to evaluate expression
square(N, N2) :- N2 is N * N.
Unfortunately, square only works when the first argument is bound. This
is because is/2 only works if its second argument is ground.
- square(5, X).
X = 25.
- square(X, 25).
ERROR: is/2: Arguments are not sufficiently instantiated
- 25 is X * X.
ERROR: is/2: Arguments are not sufficiently instantiated
Later we shall see how to write code to do arithmetic in different modes.
COMP90048 Declarative Programming Lecture 2 – 20 / 21
Beyond Datalog
Arithmetic
Prolog provides the usual arithmetic operators, including:
+ - * add, subtract, multiply
/ division (may return a float)
// integer division (rounds toward 0)
mod modulo (result has same sign as second argument)
- unary minus (negation)
integer float coersions (not operators)
More arithmetic predicates (infix operators; both arguments must be
ground expressions):
< =< less, less or equal (note!)
> >= greater, greater or equal
=:= =\= equal, not equal (only numbers)
COMP90048 Declarative Programming Lecture 2 – 21 / 21
Logic and Resolution
The University of Melbourne
School of Computing and Information Systems
COMP90048
Declarative Programming
Lecture 3
Logic and Resolution
Copyright c? 2023 The University of Melbourne
COMP90048 Declarative Programming
Logic and Resolution
Interpretations
In the mind of the person writing a logic program,
each constant (atomic term) stands for an entity in the “domain of
discourse” (world of the program);
each functor (function symbol of arity n where n > 0) stands for a
function from n entities to one entity in the domain of discourse; and
each predicate of arity n stands for a particular relationship between n
entities in the domain of discourse.
This mapping from the symbols in the program to the world of the
program (which may be the real world or some imagined world) is called
an interpretation.
The obvious interpretation of the atomic formula
parent(queen_elizabeth, prince_charles) is that Queen Elizabeth
II is a parent of Prince Charles, but other interpretations are also possible.
NOTE
Another interpretation would use the function symbol queen_elizabeth
to refer to George W Bush, the function symbol prince_charles to refer
to Barack Obama, and the predicate symbol parent to refer to the notion
“succeeded by as US President”. However, any programmer using this
interpretation, or pretty much any interpretation other than the obvious
one, would be guilty of using a horribly misleading programming style.
Terms using non-meaningful names such as f(g, h) do not lead readers
to expect a particular interpretation, so these can have many different
non-misleading interpretations.
COMP90048 Declarative Programming Lecture 3 – 1 / 21
Logic and Resolution
Two views of predicates
As the name implies, the main focus of the predicate calculus is on
predicates.
You can think of a predicate with n arguments in two equivalent ways.
You can view the predicate as a function from all possible
combinations of n terms to a truth value (i.e. true or false).
You can view the predicate as a set of tuples of n terms. Every tuple
in this set is implicitly mapped to true, while every tuple not in this
set is implicitly mapped to false.
The task of a predicate definition is to define the mapping in the first
view, or equivalently, to define the set of tuples in the second view.
COMP90048 Declarative Programming Lecture 3 – 2 / 21
Logic and Resolution
The meaning of clauses
The meaning of the clause
grandparent(A, C) :- parent(A, B), parent(B, C).
is: for all the terms that A and C may stand for, A is a grandparent of C if
there is a term B such that A is a parent of B and B is a parent of C.
In mathematical notation:
?A?C : grandparent(A,C)← ?B : parent(A,B) ∧ parent(B,C)
The variables appearing in the head are universally quantified over the
entire clause, while variables appearing only in the body are existentially
quantified over the body.
NOTE
is “forall”, the universal quantifier, while ? is “there exists”, the
existential quantifier. The sign ∧ denotes the logical “and” operation,
while the sign ∨ denotes the logical “or” operation, and the sign ? denotes
the logical “not” operation.
COMP90048 Declarative Programming Lecture 3 – 3 / 21
Logic and Resolution
The meaning of predicate definitions
A predicate is defined by a finite number of clauses, each of which is in the
form of an implication. A fact such as parent(queen_elizabeth,
prince_charles) represents this implication:
AB : parent(A,B)←
(A = queen_elizabeth ∧ B = prince_charles)
To represent the meaning of the predicate, create a disjunction of the
bodies of all the clauses:
?A?B : parent(A,B)←
(A = queen_elizabeth ∧ B = prince_charles) ∨
(A = prince_philip ∧ B = prince_charles) ∨
(A = prince_charles ∧ B = prince_william) ∨
(A = prince_charles ∧ B = prince_harry) ∨
(A = princess_diana ∧ B = prince_william) ∨
(A = princess_diana ∧ B = prince_harry)
NOTE
Obviously, this definition of the parent relationship is the correct one only
if you restrict the universe of discourse to this small set of people.
COMP90048 Declarative Programming Lecture 3 – 4 / 21
Logic and Resolution
The closed world assumption
To implement the closed world assumption, we only need to make the
implication arrow go both ways (if and only if):
(A = queen_elizabeth ∧ B = prince_charles) ∨
(A = prince_philip ∧ B = prince_charles) ∨
(A = prince_charles ∧ B = prince_william) ∨
(A = prince_charles ∧ B = prince_harry) ∨
(A = princess_diana ∧ B = prince_william) ∨
(A = princess_diana ∧ B = prince_harry)
This means that A is not a parent of B unless they are one of the listed
cases.
Adding the reverse implication this way creates the Clark completion of
the program.
COMP90048 Declarative Programming Lecture 3 – 5 / 21
Logic and Resolution
Semantics of logic programs
A logic program P consists of a set of predicate definitions. The semantics
of this program (its meaning) is the set of its logical consequences as
ground atomic formulas.
A ground atomic formula a is a logical consequence of a program P if P
makes a true.
A negated ground atomic formula ?a, written in Prolog as \+a, is a logical
consequence of P if a is not a logical consequence of P.
For most logic programs, the set of ground atomic formulas it entails is
infinite (as is the set it does not entail). As logicians, we do not worry
about this any more than a mathematician worries that there are an
infinite number of solutions to a + b = c.
COMP90048 Declarative Programming Lecture 3 – 6 / 21
Logic and Resolution
Finding the semantics
版权所有：编程辅导网 2021 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
