CS 613: Design and Implementation
of Functional Programming Languages
Instructor
: Amitabha Sanyal
That's
me, in xfig
Last
updated on: 21st July 2003.
Announcements
-
The first assignment is
on the newsgroup iitb.courses.cs613
-
The second programming assignment
is here. Submission is during
the November 15-16 weekend.
-
Your performance
in the course.
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
-
Side effect free IO
-
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
-
20%
for two programming assignments
-
15%
for quizzes (maybe three of them)
Annotated
References
The
first two references are for motivation. The first paper reports
an experiment to evaluate different programming languages for their ability
to aid writing a prototype for a significantly large software. Read for
yourself 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.
We
shall use the next paper for 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 a masterly
introduction to functional programming. However, there is a single copy
in the library, in which the examples are in Miranda instead of Haskell.
-
R.Bird
and P.Wadler. Introduction to Functional Programming,
Prentice Hall, New York, 1988.
I am trying to acquire copies
of a later edition which uses Haskell.
-
R.Bird
.
Introduction to Functional Programming using Haskell. Prentice Hall Europe,
1998.
Lambda
calculus plays important roles as a) a model of computation, and b) in
implementation of functional programming languages. A comprehensive treatment
of lambda calculus is available in the text by Barendregt.
On
the topic of type systems and type inferencing, you have the following
references:
-
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, in the second step, are converted into instructions
of the real machine. The first book is a classic reference. It uses G-machine
as the abstract machine. The second paper introduces the Three Instruction
Machine (TIM), and the third reference, a nearly 100 page paper, introduces
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 Expressiveness 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.