CS 457 Functional Languages

Credit Hours:	4
Course Coordinator:	Andrew Tolmach
Course Description:	Introduction to functional notation, recursion, higher-order functions, reasoning about functions, and models for the evaluation of applicative expressions. Use of functional languages. Prerequisites: CS 202, 311.
Prerequisites:	Expected background of a senior or graduate student in CS.
Goals:	Ability to solve programming problems with a functional language; basic understanding of theoretical foundations of the functional paradigm. Upon the successful completion of this course students will be able to: Describe the key characteristics of the functional paradigm. Use a functional language to write simple programs manipulating lists and trees. Use higher order functions, including maps, folds, and composition, to perform tasks on lists. Define algebraic datatypes to model useful domains. Define and use appropriate higher order functions on arbitrary algebraic data types. Illustrate how higher-order function values can be used to store data. Convert functional abstract data type specifications into implementations. Prove properties of simple functional programs using equational reasoning and induction. Explain and use polymorphic functions and data types, and interpret type error messages. Write functional programs that perform I/O, using either monadic or direct methods. Explain the differences between eager and lazy evaluation, and their significance. Write programs using simple infinite data structures. Explain the basic implementation considerations for a functional language. Design and implement a non-trivial application program in a functional language.
Textbooks:	Haskell: The Craft of Functional Programming, 2nd ed., Simon Thompson, Addison Wesley, 1999.
References:	On-line user and reference manuals for the programming language compilers used in the course.
Major Topics:	Functional paradigm Algebraic data types and recursion Polymorphism Higher-order functions Program transformation Monads Laziness Type checking
Laboratory Exercises:	Haskell programming exercises (6, 1 week each) Large application program in Haskell (4 weeks)

CAC Category Credits	Core	Advanced
Data Structures
Algorithms
Software Design		1.0
Computer Architecture
Programming Languages		3.0

Oral and Written Communications:	None.
Social and Ethical Issues:	None.
Theoretical Content:	Lambda-calculus (0.5 week) Type systems and monads (1.5 week) Evaluation semantics (1 week)
Problem Analysis:	The large project will require students to define a computing problem (based on a suggested list or of their own invention), analyze it, and program a solution in a functional language.
Solution Design:	Many of the homework exercises, and the course project, will require students to design functional language solutions (including design of data structures and algorithms) for set problems.