For students (of the BCS and BSE in particular) to learn the concepts of functional programming (reduction rules, lazy evaluation, high-order functions, type-classes, parametric polymorphic types, research in types and in parallel evaluation, relationship to denotational semantics), gain programming experience with a modern lazy, functional programming language (such as Haskell), and learn the relevance of lambda calculus to computing today. As of 2004 many of CSSE's students are mono-lingual (C/C++), and most are certainly mono-paradigm-al. Few of our students at any level have ever programmed in a lazy functional language.

(Note, that CSE3322 "programming languages and implementation" (see later) touches on the applicative (not functional) language SML, at the lecturer's discretion, and this is the closest that some of our students come to true FP. e.g.There is some overlap of this new unit with points #3, #4 and #5(b) out of points #1 to #10 of "Knowledge and Understanding" for CSE3322 as in the avatar June 2004, however overall this seems no more significant than compared with CSE2305. I would argue for neither an exclusion nor a prereuisite relationship between CSE3322 and CSE3456.

It may be argues that there should be 6-points of functional programming somewhere between level-2 and level-4 inclusive for computer science graduates. A compromise is this 3-point unit that has a quota due to resource limitations (staff availability) and is not available through the WES automated enrolment system so as to allow the lecturer the opportunity to give appropriate course advice and to manually manage the quota.

There is scope for a follow-on advanced functional programming unit should this unit be successful.

To show students another programming paradigm (FP) that is radically different from the one(!) that most of them are familiar with (imperative / OO). To teach the lambda calculus, its relationship to programming languages (not just FP languages) and their semantics, and to program specification and verification. To present modern developments in the design and implementation of FP languages including active topics in e.g. type-classes and parallel evaluation.

And very importantly, to impart a reasonable level of competence in programming techniques for a modern, still evolving, lazy functional programming language such as Haskell.

CSE3322 Programming languages and implementation tries to cover four programming paradigms but is known to be over-streched in trying to cover multiple paradigms and also implementations. The degree of overlap is not large.

The proposed FP unit would complement CSE3395 Perl Programming (3pts), CSE3393 Prolog Programming (3pts), CSE3394 Lisp Programming (3pts). A variety of paradigm/language units would be one way to offer variety in this area to BCS and BSE.

As a topic "functional programming" is proper, core, computer science material. The lambda calculus is the prototype programming language; its influence is pervasive but most of our graduates do not know what it really is. Functional programming is one of the most active and exciting research areas in computer science, influencing type theory, and the semantics of sequential, concurrent and distributed computing.

Facts: lambda calculus syntax, conversion rules, semantics, expression evaluation strategies strict- (eager-, greedy-), lenient-, speculative-, and lazy- (call by need, normal-order) -evaluation, result of Church Rosser theorem, representing ints bool and lists in pure lambda calculus, basic-, parametric-polymorphic- and existential-types, type-classes, syntax, semantics and pragmatics of a modern lazy functional language (e.g. Haskell), functional input-output (e.g. monads); programming techniques (e.g. recursion, accumulating parameters, high-order functions), examples (e.g. trees, and operations on them, parser combinators, and "embedded languages" etc.), use in denotational semantics.

The student will understand the historic importance of the lambda calculus and its relationship to representative programming languages (functional and otherwise), and to models of computation. The student will be able to read, understand, evaluate and modify existing expressions in lambda calculus and programs in a functional programming language. The student will be able to solve programming problems using a functional programming language. The student will be able to analyse the time and space complexity of functional programs. The student will also be able to apply techniques that come from functional programming to solutions in non functional languages.

The student will appreciate the genius of Church and the economical beauty of the lambda calculus. The student will be impressed by the construction of correct and powerful software (e.g. in Haskell) on these sound mathematical foundations.

The student will have to accept a new way of thinking, when it comes to solving computing problems, if (s)he is to fully absorb the functional programming paradigm; such an adjustment can be difficult. Even if this process is incomplete, FP techniques can be absorbed and applied in non-FP languages.

The student will be able to write a functional program (e.g. in Haskell) to solve a new programming problem, run the compiler (e.g. ghc), understand its error messages if any and fix the program, and produce a working program that solves the problem. The student will be able to use existing types and functions from the standard prelude and libraries, where appropriate. The student will be able to design new algebraic data-types, new type-classes and new functions as necessary. The student will be able to test and evaluate programs for correctness, and to estimate time- and space-complexity.

The student will be able to manipulate expressions in lambda calculus and formally prove things about them.

not appropriate

Facts: lambda calculus syntax, conversion rules, semantics, expression evaluation strategies strict- (eager-, greedy-), lenient-, speculative-, and lazy- (call by need, normal-order) -evaluation, result of Church Rosser theorem, representing ints bool and lists in pure lambda calculus, basic-, parametric-polymorphic- and existential-types, type-classes, syntax, semantics and pragmatics of a modern lazy functional language (e.g. Haskell), functional input-output (e.g. monads); programming techniques (e.g. recursion, accumulating parameters, high-order functions), examples (e.g. trees, and operations on them, parser combinators, and "embedded languages" etc.), use in denotational semantics.

Haskell 98 Language and Libraries, the Revised Report. (ed) S. Peyton Jones et al, CUP, 2003.

P. Hudak. The Haskell School of Expression: Learning Functional Programming through Multimedia. CUP, 2000.

Lectures: 12 hours.

Practical work -- problem solving using a modern lazy functional programming language, e.g. Haskell and the ghc compiler.

Presentation of formal material (syntax, theorems, semantics, ...), reinforcement with worked examples, student then works on similar problems.

There is an interactive lambda calculus interpreter here

Lectures will present the detailed factual material as detailed in the unit summary. The practical programming skills will be learned through programming exercises and tutorial style interaction with the lecturer.

50% examination for the formal material. 50% pracs/assignments for assessing practical functional programming skills.

Exam will cover the formal mathematical aspects of the unit. The prac work and/or prac exam will cover the more practical skills and objectives.

3

6 hours per week comprising 1 hours lecture, 3 hours prac/assignment work, and 2 hours reading/private study.

1 hi-tech lecture theatre or tutorial room for 1 hours per week. 1 computer laboratory for 3 hours per week.

Nil, except as may be bundled in the lectures or prac work.

Lectures and marking of prac work and exam will be carried out by the lecturer. There is a quota of about 15 students due to staff limitations. This unit may be taught 'over-load'.

There would be some small load on technical staff because Haskell, say, would have to be installed on the student computers. This is quite straightforward.

• Software Title:
• Vendor:
• Version:
• OS: MS Windows XP ( ) and/or LINUX ( )
• License Details: (A valid software license certificate/s or Vendor permission must be available upon request if the software is to be installed for teaching)
• Are we currently licensed: Yes ( ) or No ( ) (If unsure, please check with your local IT support )
• If (Yes), who is the contact person for this software?:
• If (No), will the software license be arranged by: Staff member requesting the software ( ) or Technical Services* ( ) ? *If the latter is selected, please discuss your requirement/s with myself ASAP, prior to finalising your request, as there could be financial or resourcing implications.
• Is the software to be installed and accessed from a: Client/Workstation ( ), or Server ( ) ?
• Type of license: Site License ( ), Freeware ( ), FOSS (Free and Open Source Software) ( ), Shareware ( ), Lab based ( ) # of Licenses needed ____
• In what week will you commence using the software in class? Semester 1 (Week ___ ) and/or Semester 2 (Week ___ ):
• Nominated Staff For Acceptance Testing Software: (Name) (Phone) (Email)
• Additional Information: Special Requirements, Software Configuration/Installation Requirements, etc:

Haskell compiler ghc (free) see http://haskell.org/

Ideally software to support automated (partial-)marking of pracs and/or prac/exam, but the proposal does not depend on this.

Suitable material available in recommended reading and on the web. No additional library resources required.

100% CSSE

Nil.

Nil.

CSE2303 Formal Methods I, and CSE2304 Algorithms and Data Structures.

Unit will not be available for enrolment through WES, so lecturer will be able to advise the students and select appropriate ones to fill the quota, initially set to 15 students.

Formal syntax, grammar, BNF. Some mathematics - logic, induction. A good grounding in fundamental (comp. sci.) algorithms and data structures.

Maturity -- e.g. experience with paradigms (e.g. logic programming) other than the usual imperative/OO paradigm would help, but this is hard to come by with the current course structures. (CSE3322 would help but would not be essential.)

Lloyd Allison, (lloyd@csse.monash.edu.au)

Lloyd Allison