|Owning Department/School:||Department of Computer Science|
|Credits:||6 [equivalent to 12 CATS credits]|
|Notional Study Hours:||120|
|Level:||Intermediate (FHEQ level 5)|
|Assessment Detail:|| |
|Requisites:||Before taking this module you must take CM10228 OR take XX10190|
To illustrate how the logical and semantic foundations of programming languages are translated into usable programming languages. To give students practical experience of using a functional programming language.
On completion of this unit, students will be able to:
1. Define and explain the syntax and semantics of the lambda-calculus, and its role as a model of computation.
2. Demonstrate the difference between reduction orders and explain their relationship with call-by-name, call-by-value and call-by-need evaluation.
3. Define and explain the simply-typed lambda calculus, Hindley-Milner polymorphism, and type inference.
4. Write programs over structured datatypes in a typed higher-order functional programming language.
Use of IT (T/F,A), Problem Solving (T/F,A).
The lambda calculus, syntax and semantics; free and bound variables; alpha conversion; beta and eta reduction. Normal form subject to a reduction scheme. Reduction order: normal and applicative; Y combinator. Programming in the lambda-calculus: Church numerals and operations (addition, subtraction, multiplication), Booleans, recursion via fixed points. The diamond property. Church-Rosser theorem.
Typed lambda calculus. Hindley-Milner polymorphism and type checking and type inference.
Programming in a typed higher-order functional programming language (e.g. Haskell.) Types and type constructors: product, sum and function types. Recursive types, especially lists. Programming with map and fold. Call-by-name, call-by-value and call-by-need; graph reduction. Relationship of functional programming to other programming styles; integration of effects in functional programming languages.
CM20256 is Compulsory on the following programmes:Department of Computer Science
CM20256 is Optional on the following programmes:Department of Mathematical Sciences