[SOLVED] CS COMP30020 / COMP90048 Declarative Programming

Subject Introduction
The University of Melbourne
School of Computing and Information Systems
COMP30020 / COMP90048 Declarative Programming

Copyright By Assignmentchef assignmentchef

Section 0 Subject Introduction
Copyright c 2020 The University of Melbourne
COMP30020 / COMP90048 Declarative Programming October 30, 2020 1 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 2 / 419

Subject Introduction
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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 3 / 419

Subject Introduction
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 exerciese 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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 4 / 419

Subject Introduction
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
Sullivan, and: Real world Haskell.
Other recommended resources are listed on the LMS.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 5 / 419

Subject Introduction
Assessment
The subject has the following assessment components:
0% short Prolog project, due in Week 4 (optional) 15% larger Prolog project, due in Week 6 or 7
0% short Haskell project, is due in Week 8 or 9 (optional) 15% larger Haskell project, due in Week 11 or 12
70% two-hour written final examination
To pass the subject (get 50%), you must pass both the project component and the exam component.
The exam is closed book, and will be held during the usual examination period after the end of the semester. Practice versions of the final exam are available on the LMS.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 6 / 419

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 persons work as their own or provide their work for another student to submit in whole or in part will be subject to disciplinary action.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 7 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 8 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 9 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 10 / 419

Subject Introduction
Introduction to logic programming and Prolog Introduction to constraint programming Introduction to functional programming and 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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 11 / 419

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 cant 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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 12 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 13 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 14 / 419

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 dont 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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 15 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 16 / 419

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 Bings 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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 17 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 18 / 419

Introduction to Logic Programming
The University of Melbourne
School of Computing and Information Systems
COMP30020 / COMP90048 Declarative Programming
Introduction to Logic Programming
Copyright c 2020 The University of Melbourne
COMP30020 / COMP90048 Declarative Programming October 30, 2020 19 / 419

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, in which functions map inputs to outputs.
Logic programming languages are based on the predicate calculus of 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 byCarthys group at MIT in 1958, the first logic programming language was Prolog, implemented bys group at Marseille in 1971.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 20 / 419

Introduction to Logic Programming
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 Charless parent. There is also no promise that there is a unique answer to either of these questions.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 21 / 419

Introduction to Logic Programming
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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 22 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 23 / 419

Introduction to Logic Programming
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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 24 / 419

Introduction to Logic Programming
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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 25 / 419

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 ; .
COMP30020 / COMP90048 Declarative Programming October 30, 2020 26 / 419

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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 27 / 419

Introduction to Logic Programming
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.
COMP30020 / COMP90048 Declarative Programming October 30, 2020 28 / 419

Introduction to Logic Programming
Rules can be recursive. Like Haskell, Prolog has no looping constructs, so recursion is widely used. Prolog does not have as well-developed a library of higher-order operations as Haskell, so recursion is used more in Prolog than in Haskell.
A persons 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).
COMP30020 / COMP90048 Declarative Programming October 30, 2020 29 / 419

Introduction to Logic Programming
Equality in Prolog, written = and used as an infix operator, can be used both to bind variables and to check for equality. Like Haskell, Prolog is a single-assignment language: once bound, a variable cannot be reassigned.
?- X = 7. X = 7.

CS: assignmentchef QQ: 1823890830 Email: [email protected]