Module 11582 (2005)
Syllabus page 2005/2006
06-11582
Software Workshop Haskell
Level 2/I
Antoni Diller
10 credits in Semester 1
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus
The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
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
.
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 successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | appreciate the main features of the functional programming paradigm | Examination, Continuous assessment |
| 2 | aware of the main advantages and disadvantages of functional programming languages | Examination, Continuous assessment |
| 3 | aware of some of the uses and applications of functional programming languages | Examination, Continuous assessment |
| 4 | aware of some of the connections between functional programming and other topics in computer science | Examination, Continuous assessment |
| 5 | write medium-sized programs | Examination, Continuous assessment |
| 6 | write programs to carry out arithmetical calculations | Examination, Continuous assessment |
| 7 | define functions using recursion | Examination, Continuous assessment |
| 8 | write programs to manipulate lists | Examination, Continuous assessment |
| 9 | write functions that accumulate parameters | Examination, Continuous assessment |
| 10 | use homomorphisms | Examination, Continuous assessment |
| 11 | use memoisation or tabulation techniques | Examination, Continuous assessment |
| 12 | define and use dynamic data-structures | Examination, Continuous assessment |
| 13 | use infinite data structures | Examination, Continuous assessment |
| 14 | use continuations | Examination, Continuous assessment |
| 15 | reason about programs and prove that they have various properties | Examination, Continuous assessment |
| 16 | carry out proofs using structural induction | Examination, Continuous assessment |
| 17 | recognise deductivist style and be aware of its limitations | Examination, Continuous assessment |
| 18 | source-reduce expressions in a high-level functional programming language | Examination, Continuous assessment |
| 19 | carry out simple program transformations | Examination, Continuous assessment |
| 20 | write executable specifications | Examination, Continuous assessment |
| 21 | understand straightforward formal specifications | Examination, Continuous assessment |
| 22 | animate straightforward formal specifications | Examination, Continuous assessment |
| 23 | understand how a functional language can be implemented | Examination, Continuous assessment |
| 24 | translate a functional language into a system of combinatory logic | Examination, Continuous assessment |
| 25 | apply various bracket abstraction algorithms | Examination, Continuous assessment |
| 26 | reduce terms in various lambda calculi and systems of combinatory logic | Examination, Continuous assessment |
| 27 | devise fixed-point combinators | Examination, Continuous assessment |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
None
Teaching
Teaching Methods:
Ten one-hour weekly lectures plus ten three-hour demonstrator-supervised laboratory sessions.
Contact Hours:
Assessment
- Supplementary (where allowed): As the sessional assessment
- 1.5 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 |
| Introduction to Functional Programming using Haskell (second edition) | Richard Bird | Prentice Hall , 1998 |
| To Mock a Mockingbird | Raymond Smullyan | OUP , 1990 |
| Proofs and Refutations | Imre Lakatos | CUP , 1976 |
| Haskell: The Craft of Functional Programming (second edition) | Simon Thompson | Addison Wesley Longman , 1999 |
| The Haskell School of Expression | Paul Hudak | Cambridge University Press , 2000 |
| An Introduction to Functional Programming Systems Using Haskell | Antony J. T. Davie | Cambridge University Press , 1992 |
| Functional Programming with Haskell | Michael G. Hinchey and Steven A. Jarvis | McGraw-Hill , 1997 |
| Programming Language Theory and its Implementation | M. J. C. Gordon | Prentice Hall , 1988 |
| Compiling Functional Languages | Antoni Diller | Wiley , 1988 |
| Introduction to Formal Methods | A. Harry | Wiley , 1996 |
| Z: An Introduction to Formal Methods (second edition) | Antoni Diller | Wiley , 1994 |
| The Z Notation: A Reference Manual (second edition) | J. M. Spivey | Prentice Hall , 1992 |
| Using Z: Specification, Refinement, and Proof | Jim Woodcock and Jim Davies | Prentice Hall , 1996 |
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.
Last updated: 13 May 2005
Source file: /internal/modules/COMSCI/2005/xml/11582.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus