Programming Languages
(CS329 and CS389, Autumn 2002)
Staff
 Instructor: Soumen Chakrabarti
 TA's:
Surya Varma R (rsvarma @ cse.iitb.ac.in),
Apurva Rameshchandra
Jadhav (apurvaj @ cse.iitb.ac.in), and
A Ramasubramaniyan (sriram @ cse.iitb.ac.in).
Time and place
 Lectures: Room A2, Mon 11:30, Thu 10:30, Fri
11:30. In addition we may want one extra hour some weeks. I prefer
Thu 8:30. Ask your friendly CR about lastmoment rescheduling
and check my homepage about sudden travel plans.
 Lab (CS389): Slot L2, OSW Lab, Tue afternoon (but we wish to
make this flextime)
 Office hours: Fri afternoons. Any other meetings by prior
email appointment only.

Do not use my regular email for matter related to the course.
A new email cs329 @ cse.iitb.ac.in will
be set up for this purpose. There will also be a newsgroup
iitb.courses.cse329 which you should actively read.
Syllabus
The syllabus set by the department/institute should be
available here, but it is not always uptodate.
You might want to check out the
IEEE
and ACM syllabi.
Evaluation for CS329
 Tentative scores and grades
have been posted. A text version is
also available in case you cannot run Excel.
 A midterm exam, worth 20%.
 A quiz, worth 20% (probably flex time).
 A final exam, worth 40%.
 Homeworks, worth 20%.
 Check out last year's course page
for some idea of what's in store.
 Dishonesty will be taken very seriously. Since I don't have enough
time to deal with dishonesty, I will simply report it, which will be
worse because matters will thereafter go out of my hands.
Check out sample
honor codes elsewhere.
Homeworks (CS329)
You can do these in groups of 23 students. All students in a
group will submit ONE writeup and get the same credit. You are
strongly encouraged to check out the homeworks from previous
offerings.
Lab assignments (CS389)
You can do these in groups of 23 students. All students in a
group will submit ONE program and get the same credit. The TAs are
responsible for specifying precisely what is to be printed, and in
what format, because part of the evaluation on test cases will be done
by scripts. Students are responsible for adhering to these specs.
You are strongly encouraged to check out the homeworks from previous
offerings.
 Lab1
 Lab2:
 Compile and run the following programs:
swap.C and
swap.f.
 Explain the results by making educated guesses about how the
two languages handle passbyreference.
 Change the programs in any interesting ways you can think of
to find out more about the respective implementations of stores,
cells, and parameter passing.
 Lab3 (due 20020926):
Write in Scheme the solution to the loopbreak problem in
the midterm exam. Determine experimentally if the total memory
(stack and heap) occupied by the Scheme program grows without bound
as an unbounded number of iterations are executed. Report how you
made these measurements.
 Lab4 (due 20021005):
Using the coroutine technique presented in class, write in Scheme a
program with three different logical threads of control A, B, and C.
A is a producer of successive integers 0, 1, 2, etc. B and C share a
cell in the store. The cell s holds an integer, initially 0. Having
produced an integer, A alternately transfers control to B and C,
giving it the integer x just generated. If B gets control, it
increments the contents of s by 2*x and reverts control to A. If C
gets control, it increments the contents of s by 3*x and reverts
control to A. Insert suitable print statements to make sure your
program is working as intended.
 Lab5
 Lab6 (due 20021110): Inspect this C++ code for Prologlike inferencing with
only nullary relations (i.e., no variables and unification). Enhance
it with unification to handle relations.
Lecture calendar
I hope this will help you while revising the material.
are shown in color.
Canceled classes are struck out.
 20020722

 Intro to course and administrative details.
 Kernel and desugaring approach to language design.

 Lambda grammar.
 Parse trees and Stoy diagrams.
 Syntactic equivalence of expressions.
 20020725

 Free and bound variables.
 Rules of substitution [E2/I]E1.
 20020726

 Alpha, beta, eta transformation rules.
 Implementation of integers and INC.
 20020729

 Integers and INC, ZERO?, DEC, PLUS, MULT, etc.
 Booleans and AND, OR, NOT, IF etc.

 Normal form, normal and applicative order reductions.
 ChurchRosser theorems.
 20020801

 Recursion using pure lambda expressions.
 20020802

 Solving functional equations for fixpoints.
 The Ycombinator.
 20020805

 FLK/FL syntax.
 Data types: nonnegative integers, booleans.
 IF construct
 The rec construct to support recursion.

 Denotational semantics of FLK.
 The role of the environment.
 20020808

 Using the environment to implement static scoping.
 Uses of dynamic scoping.
 20020809

 Modified use of the environment to implement dynamic scoping.
 Stacklike usage of the dynamic environment.
 20020812

 Extending FLK to FLK! to model a Store.
 Intro to operational semantics.
 20020815

 Modeling Store accessors as sideeffectfree functions.
 Denotational semantics of FLK!.
 20020816

 Denotational semantics of FLK! (cont'd).
 Parameter passing: passbyvalue, passbyname, passbyreference.
 Syntactic translation from FLFL (pbref) to FLK!.
20020819
20020822
20020823
 20020826

 Passbyreference, the aliasing problem.
 Passbyvalueresult, passbyneed.
20020829
 20020830

 Handling arrays in FLK!.
 Denotational semantics for arrays.
 Passing arrays and array elements into Procs.
 20020902

 Intro to objectoriented programming:
encapsulation, inheritance.
 Inheritance examples in C++.

 Extending FLK/FLK! to FLOP: a toy OO language.
 Object, method, class, new
 20020905

 Supporting member variables via closures and Store.
 Letting methods call each other by providing this.
 Pointer casting, virtual methods, and inheritance.
 20020906

 Tail recursion.
 Rewriting some recursive routines in a tailrecursive form.
 Continuationpassing style of writing (recursive) programs.
 20020909

 FLTR: A tailrecursive variant of FLK.
 Syntactic translation from FL to FLTR.
 Intro to standard semantics.

 More CPS conversion examples.
 Standard semantics for FLK!.
 20020912

 Standard semantics for FLK!.
 Continuations as storetransformers.
 The exit, label
and goto constructs.
 20020913

 Standard semantics for label and goto.
 The callcc construct and its standard denotation.
 20020918
 20020923
 Midterm review.
 Implementing loops and coroutines using callcc.
 20020926
 Exceptions, throw and catch.
20020927
 20020930
 20021003
 20021004
 20021007
 20021010
 20021011
 20021014
 Quiz review.
 Logic programming.
 20021017
 Introduction to logic programming.
 Rulebase, rule, relation, clause, antecedent, consequent, goal.
 20021018
 Examples of the inference process:
quicksort, permutation.
 20021024
 Backtracking.
 Inferencing with nullary relations.
 20021025
 Unification, most general unifier.
 Resolution and inferencing.
 20021028
 Types, type safety.
 Type checking and inferencing overview.
 Adhoc and parametric polymorphism.
 Type constants, variables, compound and function types.
 20021031
 Adhoc polymorphism examples.
 Parametric polymorphism examples using C++ templates and Haskell.
 Type inferencing as equation solving.
 20021101
 Type equivalence, recursive types.
 Inference rules.
 A reconstruction procedure.
Copyright statement
The copyrights to documents and software referred to herein remain
with the respective copyright holders. The copyright to this specific
course organization, course handouts, and exams is owned by IIT
Bombay.