06-11582
Software Workshop Haskell

Dr A R Diller

10 credits in Sem1

Outline

The purpose of this module is to present the basic ideas of the pure functional programming language Haskell, to demonstrate the main elements of good programming style and to illustrate some of the used and applications of Haskell.

Aims

The aims of this module are to:

Present the basic ideas of the pure functional programming language Haskell.
Demonstrate the main elements of good programming style.
Illustrate some of the uses and applications of Haskell.

Learning Outcomes

On completion of this module, the student should be able to:	Assessed by:
Appreciate the main features of the functional programming paradigm.	Examination, Continuous assessment
Aware of the main advantages and disadvantages of functional programming languages.	Examination, Continuous assessment
Aware of some of the uses and applications of functional programming languages.	Examination, Continuous assessment
Aware of some of the connections between functional programming and other topics in computer science.	Examination, Continuous assessment
Write medium-sized programs.	Examination, Continuous assessment
Write programs to carry out arithmetical calculations.	Examination, Continuous assessment
Define functions using recursion.	Examination, Continuous assessment
Write programs to manipulate lists.	Examination, Continuous assessment
Write functions that accumulate parameters.	Examination, Continuous assessment
Use homomorphisms.	Examination, Continuous assessment
Use memoisation or tabulation techniques.	Examination, Continuous assessment
Define and use dynamic data-structures.	Examination, Continuous assessment
Use infinite data structures.	Examination, Continuous assessment
Use continuations.	Examination, Continuous assessment
Reason about programs and prove that they have various properties.	Examination, Continuous assessment
Carry out proofs using structural induction.	Examination, Continuous assessment
Recognise deductivist style and be aware of its limitations.	Examination, Continuous assessment
Source-reduce expressions in a high-level functional programming language.	Examination, Continuous assessment
Carry out simple program transformations.	Examination, Continuous assessment
Write executable specifications.	Examination, Continuous assessment
Understand straightforward formal specifications.	Examination, Continuous assessment
Animate straightforward formal specifications.	Examination, Continuous assessment
Understand how a functional language can be implemented.	Examination, Continuous assessment
Translate a functional language into a system of combinatory logic.	Examination, Continuous assessment
Apply various bracket abstraction algorithms.	Examination, Continuous assessment
Reduce terms in various lambda calculi and systems of combinatory logic.	Examination, Continuous assessment
Devise fixed-point combinators.	Examination, Continuous assessment

Restrictions, Prerequisites and Corequisites

Restrictions:

None.

Prerequisites:

None

Co-requisites:

None

Teaching Methods

Ten one-hour weekly lectures plus ten three-hour demonstrator-supervised laboratory sessions.

Assessment

2 hr examination (80%), continuous assessment (20%). Students who fail this module but achieve at least 30% will be allowed to resit, by examination only. Students whose mark is below 30% will be required to repeat the module in the following academic year.

Recommended Books

Title	Author(s)	Publisher, Date	Comments
Introduction to Functional Programming using Haskell (second edition)	Richard Bird	Prentice Hall, 1998	Haskell; the most useful book for this module
To Mock a Mockingbird	Raymond Smullyan	OUP, 1990	Combinatory logic; bracket abstraction algorithms; fixed-point combinators; fun puzzle-book
Proofs and Refutations	Imre Lakatos	CUP, 1976	Criticism of Euclidean methodology
Haskell: The Craft of Functional Programming (second edition)	Simon Thompson	Addison Wesley Longman, 1999	Haskell; an alternative and easier treatment
The Haskell School of Expression	Paul Hudak	Cambridge University Press, 2000	Haskell; alternative treatment with interesting applications
An Introduction to Functional Programming Systems Using Haskell	Antony J. T. Davie	Cambridge University Press, 1992	Haskell; rather old-fashioned book
Functional Programming with Haskell	Michael G. Hinchey and Steven A. Jarvis	McGraw-Hill, 1997	Haskell; an alternative treatment
Programming Language Theory and its Implementation	M. J. C. Gordon	Prentice Hall, 1988	Lambda-calculi; combinatory logic
Compiling Functional Languages	Antoni Diller	Wiley, 1988	Implementing functional languages; abstraction algorithms; source reduction; program transformation
Introduction to Formal Methods	A. Harry	Wiley, 1996	Formal specification
Z: An Introduction to Formal Methods (second edition)	Antoni Diller	Wiley, 1994	Formal methods; animation; specification techniques
The Z Notation: A Reference Manual (second edition)	J. M. Spivey	Prentice Hall, 1992	Comprehensive guide to the formal specification language Z
Using Z: Specification, Refinement, and Proof	Jim Woodcock and Jim Davies	Prentice Hall, 1996	Alternative treatment of the formal specification language Z

Detailed Syllabus

Introduction: aims of the module; structure and organisation of the module; assessment; teaching methods; style of presentation; useful books.
Functional language paradigm: uses; implementation; history; main features; advantages and disadvantages; languages (Lisp, Hope, ML, SASL, KRC, Miranda (tm), Orwell, Haskell); why Haskell is the best.
Haskell: various implementations (Gofer, HUGS98 and others); the HUGS98 system; system commands; sessions and scripts; fundamental ideas (higher-order functions, currying, uncurrying, sections, function composition, recursion, local definitions, Landin's off-side rule); programming style; literate scripts; the standard prelude; type systems; qualified types.
Numbers: basic operations (addition, subtraction, multiplication and so on); basic numerical types (Int, Integer, Float, Double); numerical type classes (Num, Integral, Real, Fractional).
Lists: basic operations (concatenation, concat, reverse, length, head, tail, init, last, take, drop, indexing, map, filter, zip, unzip and so on); list comprehensions.
Homomorphisms: various operators (foldr, foldl, foldr1, foldl1, scanr, scanl, scanr1, scanl1); duality theorems; fusion.
Programming techniques: executable specifications; program transformation; source reduction; partial evaluation; accumulating parameters; tupling; memoisation or tabulation; divide-and-conquer functions; continuations.
Advanced features: modules; monads; interactive programs; lazy evaluation; proving properties possessed by programs; harmful effects of deductivist style and Euclidean methodology.
Animation: executable and formal specification; representing types; implementing operations; choosing the state space.
Types: basic types (Int, Integer, Float, Double, Bool, Char); type classes (Text, Eq, Ord, Num, Integral, Real, Fractional); enumerations; recursive datatypes (trees and others).
Combinatory logic: contraction; reduction; normal forms; various systems; Church-Rosser Theorem and other useful properties; bracket abstraction algorithms; bases; fixed-point combinators; Curry-Howard isomorphism.
Type theory: design issues; systems (non-existent, monomorphic, polymorphic, other); motivation; type-free lambda-calculi; Curry-style typed lambda-calculi; Church-style typed lambda-calculi; type-inference and type-assignment; Curry-Howard isomorphism.

Relevant Links

Further information about this module, including any last-minute changes, corrections and alterations to the information contained above, can be found on my Software Workshop Haskell module web page .

Page maintained by:	Dr A R Diller , School of Computer Science
Content last updated:	29 July 2001
Source:	/resources/modules/2001/xml/11582.xml

06-11582 Software Workshop Haskell