CS 613: Design and Implementation
of Functional Programming Languages
: Amitabha Sanyal
me, in xfig
updated on: 21st July 2003.
The first assignment is
on the newsgroup iitb.courses.cs613
The second programming assignment
is here. Submission is during
the November 15-16 weekend.
in the course.
Welcome to the course on
Functional Programming Languages. I shall use this page to:
indicate related resources
on the web
post reading assignments
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
Data types and pattern
Classes and overloading
Side effect free IO
Syntax of Lambda terms
Alpha, beta and delta conversions
Normal forms, applicative
order and normal order reductions
Y combinator and recursion.
checking algorithm and its extension to handle type classes.
of FP Languages
Issues in implementation
of FP languages.
topics in Functional Programming
Functional Programming using
for end semester performance
for mid semester performance
for two programming assignments
for quizzes (maybe three of them)
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.
shall use the next paper for a guided tour of Haskell. But be warned that
the material is not as gentle as it sounds.
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 for
Datavetenskap, Chalmers Tekniska Hogskola, Goteborg, Sweden.
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 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.
Peyton Jones and John Hughes (eds),
Haskell 98: A Non-strict Purely Functional Language [html]
here is the Haskell98 library. [html]
I am trying to acquire copies
of a later edition which uses Haskell.
and P.Wadler. Introduction to Functional Programming,
Prentice Hall, New York, 1988.
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.
Introduction to Functional Programming using Haskell. Prentice Hall Europe,
the topic of type systems and type inferencing, you have the following
notes on types.
notes on type classes.
Hall, Kevin Hammond, Simon Peyton-Jones & Phil Wadler.
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, June
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.
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.
Tutorial on the Universality and Expressiveness 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.
this article, suggests possible reasons.