Functional Programming

versión española

Objectives

Functional languages are one of the most important declarative languages. Functional languages provide the means for solving real problems by means of small, concise programs: (algebraic) polymorphic types that permit the definition of a variety of (generic) data structures; higher order functions, i.e., functions accepting functions as arguments and returning other functions as the result of the computation; lazy evaluation techniques that permit dealing with infinite data structures; a simple computational model based on the notions of reduction and evaluation, etc. Moreover, well established methods for proving properties of functional programs (correctness, efficiency, run-time behavior, etc.) are also available. This is important for reasoning about programs and implementing functional languages.

Most functional languages share a common core of concepts and techniques which are well established. In this course, we study the foundations of functional programming languages and their use in programming and implementation of such languages.

Contents

1. Introduction to functional programming
   1.1. Functional languages as programming languages
   1.2. History and evolution of functional languages
   1.3. The pros and couns of functional languages
   1.4. Aplications
   

2. Haskell: an advanced functional language
   2.1. Introducing Haskell
   2.2. Lexical level
   2.3. Expressions
   2.4. Declarations
   

3. Data structures in functional languages
   3.1. Simple and numeric types
   3.2. Algebraic datatypes and polymorphism
   3.3. Functional types: higher order and function definitions
   3.4. Lists and trees
   3.5. Abstract data types
   

4. Models of computation for functional languages
   4.1. Reduction and evaluation in functional programs
   4.2. Lambda calculus
   4.3. Combinatory logic
   4.4. Reduction strategies in lambda calculus
   

5. The meaning of functional programs
   5.1. Denotational semantics of functional languages
   5.2. Reasoning about the properties of functional programs
   5.3. Abstract interpretation of functional languages
   

6. Implementation and optimization
   6.1. Implementation techniques for functional languages
   6.2. Program transformation
   6.3. Other optimization techniques
   

Laboratory

The practices consist in writing small programs which permit the outline of the applicability of functional languages to real problems. In particular, we work on the development of multimedia applications including graphics, animations, music, etc. The working environment is Hugs, a popular implementation of Haskell (on Windows95).

Evaluation

Exam about the theoretical contents of the subject and evaluation of the practices. Personal works.

References

[Bir00] R. Bird. Introducción a la Programación Funcional con Haskell. Prentice-Hall, 2000.

[Dav92] A.J.T. Davie. An Introduction to Functional Programming Systems Using Haskell. Cambridge University Press, 1992.

[Hud00] P. Hudak. The Haskell School of Expression. Learning functional programming through multimedia. Cambridge University Press, 2000.

[PE93] R. Plasmeijer and M. van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, 1993.

[Pey87] S.L. Peyton-Jones. The implementation of Functional Programming Languages. Prentice-Hall, 1987.

[Rea93] C. Reade. Elements of Functional Programming. Addison-Wesley, 1993.

[Tho99] S. Thompson. Haskell. The Craft of Functional Programming. Addison-Wesley, 1999.

Interesting URLs

Functional programming on the network:

http://cm.bell-labs.com/cm/cs/who/wadler/guide.html

http://haskell.org/

More URLs

RWTH Aachen's functional programming group (Germany)
Glasgow's programming group (Scotland)
Functional programming at the Universidad Complutense de Madrid
Functional programming at the Universidad de Málaga
Nijmegen functional programming group (The Netherlands)
Yale's functional programming group (United States of America)