Next: MC211 Automata, Languages and
Up: Year 2
Previous: MC206 Software Engineering and
MC208 Functional Programming
Credits: 20 |
Convenor: Dr. N. Ghani |
Semester: 1 |
Prerequisites: |
essential: MC103, MC104 |
desirable: MC111 |
Assessment: |
Continual assessment: 40% |
Three hour exam in January: 60% |
Lectures: |
36 |
Classes: |
none |
Tutorials: |
12 |
Private Study: |
78 |
Labs: |
24 |
Seminars: |
none |
Project: |
none |
Other: |
none |
Total: |
150 |
|
|
Explanation of Pre-requisites
It is essential that students have taken a first course in basic
(imperative) programming, which includes skills involving both coding
and design, to a level which includes file handling and data
structures such as lists and trees.
A grounding in the basic mathematical concepts of
sets, functions and relations, and graphs is required, but detailed
knowledge of other areas of elementary discrete mathematics and logic
is not essential.
Course Description
Many of the ideas used in imperative programming arose through
necessity in the early days of computing when machines were much
slower and had far less memory than they do today. Languages such as
C(++) and Pascal carry a substantial legacy from the past. Even Java,
despite its OO features, has been devised to look `a bit like C'. If
one were to start again and design a programming language from scratch
what would it look like?
For many applications, the chief concern should be to produce a
language which is concise and elegant. It should be expressive enough
for a programmer to work productively and efficiently but simple
enough to minimize the chance of making serious errors. Rapid
development requires the programmer to be able to write algorithms and
data structures at a high level without worrying about the details of
their machine-level implementation. These are some of the criteria
which have led researchers to develop the functional programming
language Haskell.
The flavour of programming in Haskell is very different from that in
an imperative language. Much of the irrelevant detail has been swept
away. For example, there are at least three different uses for a
variable in Pascal: as a storage location, as parameter in a function
or procedure, as a temporary name for another variable (a `var
parameter'). There is only one use for a variable in Haskell: it
stands for a quantity that you don't yet know, as is standard in
mathematical practice. The constructs in Pascal include expressions,
commands, functions and procedures (the last two are confused in C);
whereas in Haskell there are only expressions and functions.
The meaning of a program in Pascal or C is understood by the effect it
has on the `state' of the machine as it runs.
Haskell does away with the idea of `state' -- the meaning of a program
is understood by the values it computes.
On the other hand, Haskell is a very expressive language. The type
system allows functions to be written polymorphically so that
the same code can be re-used on data of different types, e.g. the same
length function works equally well on lists of integers as on
lists of reals or lists of strings. Futhermore, it allows one to write
functions which take other functions as parameters. These are known
as higher order functions and they give a second form of code
re-use. There are powerful mechanisms for introducing user-defined
datatypes such as trees, sets, graphic objects, etc. Haskell also
makes a great deal of use of recursion. The combination of these
features makes for very clean, short programs, which, with some
experience, are easier to understand than many imperative programs.
In this course you will learn how to program in Haskell, which
exemplifies the functional style, and also learn a little of the ideas
on which functional programming is founded.
Aims
The module is intended to give the student a thorough grounding for
programming in the functional style using the language Haskell. The
emphasis is on using the language to solve problems and implement
their solution on a machine. The concepts are built up in a stepwise
fashion and related to programming practice. The student will learn
the basic types and functions; the idea of higher order types and
functions; different sorts of polymorphism and code re-use; the
concept of user-defined (recursive) datatypes; inductive proof
techniques; and evaluation strategies. At the end of the module the
student will apply these tools in the solution of a substantial
programming task.
Objectives
- To develop skilled use of basic functions and techniques to solve
problems in practical applications;
- to understand and use polymorphism in designing functions which allow
code re-use;
- to understand and use the key ideas of eager and lazy reduction systems,
along with equational reasoning, to calculate the expected results of a
functional program;
- to be able use mathematical and list induction to prove simple program
properties;
- design and implement a functional parser for an imperative language.
Transferable Skills
- The ability to program with a large core of any functional programming
language;
- the formal understanding of eager and lazy parameter passing;
- understanding of the concepts of higher order functions and polymorphism;
- inductive proof techniques;
- the basic design of lexical analysers, combinatory parsers and simple
pretty printers.
Syllabus
Basic types, such as Int, Float, String, Bool; examples of expressions
of these types. Functions and declarations, with a high level
explanation of a function with general type a1
a2
a3 ...
an. Booleans and guards;
correspondence of guards with if-then-else expressions. Pairs and
n-tuples; fst and snd functions for dismantling pairs and
tuples. Pattern matching and cases, especially defining functions on
lists and tuples. Numeric calculation. Simple recursion, with
examples on the natural numbers and lists; list comprehension; list
processing examples which use patterns, recursion and comprehensions.
Evaluation, reduction strategies (such as eager and lazy), equational
reasoning. Type inference, basic types, higher types and type
variables; informal explanation of the Milner/Damas type inference
algorithm; methods for calculating types of expressions and declared
functions. Higher-order functions, polymorphism and code re-use;
examples such as the reversal of a list. Mathematical induction and
list induction: explanation of the basic principles, together with
examples of their application. New datatypes such as error types and
exception handling and declared datatypes; recursively defined
datatypes. Examples such as lists and trees. An introduction to
lexical analysis, parsing and pretty printing. Use of datatypes in
defining parsing tools and the (syntax tree) expressions of a
programming language. In depth account of parsing combinators. An
example parser.
Reading list
Essential:
S. Thompson,
Haskell: The Craft of Functional Programming,
Addison-Wesley 1996.
Recommended:
R. Bird and P. Wadler,
Introduction to Functional Programming,
Prentice Hall 1988.
Background:
L. Paulson,
ML for the Working Programmer, 2nd Edition,
CUP 1997.
Details of Assessment
The coursework for the continual assessment consists of six
worksheets containing both programming and pencil and paper
problems. The final three weeks of the module are devoted to the sixth
worksheet, which consists of a substantial programming task.
The written January examination contains six questions, and candidates
can obtain full marks from four good questions. The examination will
test both the theoretical aspects of the course, as well as the
ability to understand, analyse and write small programs.
Next: MC211 Automata, Languages and
Up: Year 2
Previous: MC206 Software Engineering and
S. J. Ambler
11/20/1999