CS 613: Design and
Implementation of Functional Programming Languages
: Amitabha Sanyal
me, in xfig
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.
first assignment. Announcement on
22nd January 28th January .
on 5th February 11th
- Quiz 1 on 15th February.
- Midsemester on 25th February. The question paper and its solution.
- The second assignment.
February 4th March.
Submission on 12th March
- The third assignment.
Announcement on 12th March
Submission on 26th March
- The fourth
Announcement on 26th March.
Submission on 9th April.
- Quiz 2 on 12th April.
Welcome to the course on
Functional Programming Languages. I shall use this page to:
- indicate related resources on
- post reading assignments
- post homework
- post answers to questions asked
in tutorials, and exams.
- A real world application of
functional programming - software prototyping.
- Why functional programming
Tour of Haskell, illustrating the following concepts:
- Functions as first class
- Referential Transparency
- Data types and pattern matching
- Classes and overloading
- IO and Monads
- Syntax of Lambda terms
- Alpha, beta and delta
- Normal forms, applicative order
and normal order reductions
- Church-Rosser theorems
- Y combinator and recursion.
- Hindley-Milner type checking
algorithm and its extension to handle type classes.
of FP Languages
- Issues in implementation of FP
- The spineless-tagless G-Machine
topics in Functional Programming
- Bird-Meertens Formalism
- Abstract Interpretation
- Functional Programming using
- 50% for
end semester performance
- 15% for
mid semester performance
- 35% for
four programming assignments
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,
important roles as powerful combining aids or glues in the development
paper is a guided tour of Haskell. But be warned that the material is
not as gentle as it sounds.
- 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.
Functional Programming Matters?, Technical Memo of Institutionen
Datavetenskap, Chalmers Tekniska Hogskola, Goteborg, Sweden.
This is the
language manual, the final arbiter.
Hudak, John Peterson and Joseph Fasel. A
Gentle Introduction to Haskell Version 98. [html][ps].
The next reference is probably
the best introductory text on functional programming.
- S. Peyton
Jones and John Hughes (eds), Haskell 98: A
Non-strict Purely Functional Language [html]
- And here
is the Haskell98 library. [html]
- R.Bird . Introduction to Functional Programming using
Haskell. Prentice Hall Europe, 1998.
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.
is a type-rich language. The references on type
systems and type inferencing are:
notes on types.
notes on type classes.
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.
Calculus with Types, From Handbook of Logic in Computer Science,
Eds. S. Abramsky, D. Gabbay, T.S.L. Maibaum, Oxford University Press.
I. Schwartzbach. Polymorphic
Type Inference, BRICS Lecture Series Technical Report, LS-95-3,
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.
This is a
list of papers on assorted topics.
is a draft of a later book by Simon Peyton-Jones. You might want to use
it as a reference.
to declare an Imperative
essence of functional programming.
Graham Hutton , A
Tutorial on the Universality and Expressivenes of fold
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.