代写COMP30020、Java/C++/Python程序代写

日期：2022-12-01 08:32

Declarative Programming

Lecture 0

Subject Introduction

Copyright 2022 The University of Melbourne

COMP30020 Declarative Programming

Subject Introduction

Welcome to Declarative Programming

Lecturer: Peter Schachte

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 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 Declarative Programming Lecture 0 – 16 / 16

Introduction to Logic Programming

The University of Melbourne

School of Computing and Information Systems

COMP30020

Declarative Programming

Lecture 1

Introduction to

Logic Programming

Copyright ? 2022 The University of Melbourne

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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.

COMP30020 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 ;

...

COMP30020 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.

COMP30020 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.

COMP30020 Declarative Programming Lecture 1 – 10 / 20

Introduction to Logic Programming

Recursion