Programming Languages Spring 2000

Programming Languages
Spring 2000

Staff and timings

Instructor: Soumen Chakrabarti
Teaching assistants: Prajakta Ganu and Anand Mitra
Hours: ~~M11:30~~ Th8:30,11:30 and F11:30 (but keep watching this space)

Assessment

Final 50%
Midterm 20%
Homeworks and programming assignments 30%

Homeworks and programming assignments can be done in groups of two. Everyone in a group will get the same score in a particular homework or assignment.

Grades are out!

Scribed class notes

Class notes will be posted alongside the schedule below as they become available.

06/01	Introductory lecture, no notes
07/01	Sunil Pandey
10/01	Gaurav Bhalotia
13/01	Narendra Singh Rana

Course contents

Here are tentative plans on expanding on the prescribed outline.

Week	Topic	Handouts
3/1-7/1	Introduction and administrative details Abstract models of computation and architectural realities Functional programming, the model and lambda calculus Renaming, variable capture, substitution	7/1
10/1-14/1	Alpha, beta and eta transformations Representation games: boolean, pair, Church numerals Normal order and applicative order reductions Church-Rosser property Implementing recursion with lambda	10/1, 13/1
17/1-21/1	Recursion and the Y-combinator Getting familiar with Scheme and FL/FLK syntax Structured operational semantics Introduction to denotational semantics	14/1 Hw1
31/1-4/2	Denotational semantics for FLK and FL Modeling the environment Mutation and modeling the store	3/2
7/2-11/2	Closures and static scope Dynamic scope Parameter passing
14/2-18/2	Pass by reference Modules for non-hierarchical scoping Midterm review	Review
25/2	Midterm	Solutions
28/2-3/3 (RKJ)	Object oriented programming Classes, methods, public, private, protected Subclasses and inheritance Polymorphism and overloading?
9/3-10/3	Implementing OO languages using functional paradigm Tail recursion Control flow Continuation passing style	Hw2+Lab
16/3-24/3	Continuation-passing interpreters Standard semantics Non-local control transfer Exception handling	Hw3+Lab
28/3-31/3	Axiomatic semantics Reasoning about imperative programs Pre-and-post semantics Weakest precondition
6/4-7/4	Complete axiomatic semantics for while-loops Types, primitive types, records, arrays, unions Type algebra, type checking and inferencing
13/4-14/4	Logic programming Unification and resolution Applications to type inferencing and axiomatic semantics
13/4-14/4	Final	Solutions

Reading material

Denotational Semantics: The Scott-Strachey Approach to Programming Languages by Joseph Stoy. MIT Press, Cambridge, MA, 1985.
The Lambda Calculus: Its Syntax and Semantics by H. P. Barendregt. North Holland Publishing Co., 1984.
Combinatorial Logic by Curry and Feys, volume 1 chapter 4. North Holland Publishing Co., 1974.
Can programming be liberated from the von Neumann style?... Turing Award Lecture by John Backus. Communications of the ACM, 21(8) Aug. 1978, page 613.
Why functional programming matters by John Hughes. A classic paper from 1984.
A chapter from a delightful book, The Little Schemer, explaining recursion using lambda expressions. Exercises are also available.
Essentials of Programming Languages by Daniel Friedman, Mitchell Wand, and Chris Haynes. Prentice Hall, ISBN 81-203-1355-0.
An axiomatic basis for computer programming, by C. A. R. Hoare, in CACM 12(10) October 1969.
Guarded commands, nondeterminacy and formal derivation of programs, by Edsger W. Dijkstra, in CACM 18(8) August 1975.
Haskell Homepage.

Software resources

The Scheme page at MIT.
MIT Scheme has been downloaded for Linux 2.1 and glibc 2.0. Please do not download it individually.
Scheme documentation at CSE server.

Copyright statement

The copyrights to documents and software referred to herein remain with the respective copyright holders.

Programming LanguagesSpring 2000