CS 613: Design and
Implementation of Functional Programming Languages
Instructor
: Amitabha Sanyal
That's
me, in xfig
Last
updated on: 7th March 2007.
Schedule for the semester
- Problem sheet
for introductory lab session. This is on 20th January, Saturday, from 2:30-4:30.
- The
first assignment. Announcement on
22nd January 28th January .
Submission
on 5th February 11th
February .
- Quiz 1 on 15th February.
- Midsemester on 25th February. The question paper and its solution.
- The second assignment.
Announcement 26th
February 4th March.
Submission on 12th March
26th March.
- The third assignment.
Announcement on 12th March
26th March.
Submission on 26th March
9th April.
- The fourth
assignment.
Announcement on 26th March.
Submission on 9th April.
- Quiz 2 on 12th April.
Introduction
Welcome to the course on
Functional Programming Languages. I shall use this page to:
- indicate related resources on
the web
- post reading assignments
- post homework
- post answers to questions asked
in tutorials, and exams.
Course
Contents
- Motivation
- A real world application of
functional programming - software prototyping.
- Why functional programming
matters?
- Guided
Tour of Haskell, illustrating the following concepts:
- Functions as first class
objects
- Referential Transparency
- Laziness
- Data types and pattern matching
- Types
- Classes and overloading
- IO and Monads
- Lambda
Calculus
- Syntax of Lambda terms
- Alpha, beta and delta
conversions
- Normal forms, applicative order
and normal order reductions
- Church-Rosser theorems
- Y combinator and recursion.
- Type
Inference
- Hindley-Milner type checking
algorithm and its extension to handle type classes.
- Implementation
of FP Languages
- Issues in implementation of FP
languages.
- The spineless-tagless G-Machine
- Selected
topics in Functional Programming
- Bird-Meertens Formalism
- Abstract Interpretation
- Functional Programming using
Monads.
Grading
- 50% for
end semester performance
- 15% for
mid semester performance
- 35% for
four programming assignments
Annotated
References
The first two
references are for motivation. The
first paper reports an experiment to evaluate different programming
languages for ease in prototyping. The paper discusses why Haskell
rated way above most other languages. The second
paper shows how the two distinctive features of functional programming
languages, namely higher order functions and lazy evaluation,
play
important roles as powerful combining aids or glues in the development
of software.
- Paul Hudak and Mark. P. Jones, Haskell vs. Ada
vs. C++ vs. Awk vs. ... An experiment in Software Prototyping
Productivity , Technical report, Department of Computer Science,
Yale University, New Haven, CT 06518.
- John
Hughes, Why
Functional Programming Matters?, Technical Memo of Institutionen
for
Datavetenskap, Chalmers Tekniska Hogskola, Goteborg, Sweden.
The next
paper is a guided tour of Haskell. But be warned that the material is
not as gentle as it sounds.
- Paul
Hudak, John Peterson and Joseph Fasel. A
Gentle Introduction to Haskell Version 98. [html][ps].
This is the
language manual, the final arbiter.
- S. Peyton
Jones and John Hughes (eds), Haskell 98: A
Non-strict Purely Functional Language [html]
[ps].
- And here
is the Haskell98 library. [html]
[ps]
The next reference is probably
the best introductory text on functional programming.
- R.Bird . Introduction to Functional Programming using
Haskell. Prentice Hall Europe, 1998.
Lambda
calculus plays important roles in Functional Programming. Apart from
serving as a model of computation it is also used as an intermediate
representation in the implementation of functional programming
languages. The text by
Barendregt is a comprehensive text on lambda calculus.
Haskell
is a type-rich language. The references on type
systems and type inferencing are:
- My
notes on types.
- My
notes on type classes.
- Cordellia
Hall, Kevin Hammond, Simon Peyton-Jones & Phil Wadler. Type
classes in Haskell This is an easy to read reference on type
classes and its implementation.
- Henk
Barendregt. Lambda
Calculus with Types, From Handbook of Logic in Computer Science,
Eds. S. Abramsky, D. Gabbay, T.S.L. Maibaum, Oxford University Press.
- Michael
I. Schwartzbach. Polymorphic
Type Inference, BRICS Lecture Series Technical Report, LS-95-3,
June 1995.
The next
few references are on implementation of functional programming
languages. As you will learn, because of the large semantic gap between
a language like Haskell and a real machine, the compilation process is
divided into two steps. In the first, the functional program is
translated into instructions of an abstract machine, which are then
either interpreted or translated into instructions of a real machine.
The first book uses G-machine as the abstract machine, the second paper
introduces the Three Instruction Machine (TIM), and the third paper,
the state-of-art Spineless Tagless G-Machine.
There
is a draft of a later book by Simon Peyton-Jones. You might want to use
it as a reference.
This is a
list of papers on assorted topics.
Philip
Wadler How
to declare an Imperative
Philip
Wadler, The
essence of functional programming.
Jeremy
Gibbons, Calculating
Functional Programs
Graham Hutton , A
Tutorial on the Universality and Expressivenes of fold
General
reading on Functional Programming
- Some people
have asked me why
the use of Functional Programming languages was not as widespread as it
should have been, if one were to believe in the motivational papers. Phil Wadler, in
this article, suggests possible reasons.