Programming Languages
(CS-329 and CS-389, 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 last-moment rescheduling
and check my homepage about sudden travel plans.
- Lab (CS-389): Slot L2, OSW Lab, Tue afternoon (but we wish to
make this flex-time)
- 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 up-to-date.
You might want to check out the
IEEE
and ACM syllabi.
Evaluation for CS-329
- 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 2--3 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 2--3 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.
- Lab-1
- Lab-2:
- Compile and run the following programs:
swap.C and
swap.f.
- Explain the results by making educated guesses about how the
two languages handle pass-by-reference.
- 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.
- Lab-3 (due 2002-09-26):
Write in Scheme the solution to the loop-break 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.
- Lab-4 (due 2002-10-05):
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.
- Lab-5
- Lab-6 (due 2002-11-10): Inspect this C++ code for Prolog-like 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.
- 2002-07-22
-
- Intro to course and administrative details.
- Kernel and desugaring approach to language design.
-
- Lambda grammar.
- Parse trees and Stoy diagrams.
- Syntactic equivalence of expressions.
- 2002-07-25
-
- Free and bound variables.
- Rules of substitution [E2/I]E1.
- 2002-07-26
-
- Alpha, beta, eta transformation rules.
- Implementation of integers and INC.
- 2002-07-29
-
- Integers and INC, ZERO?, DEC, PLUS, MULT, etc.
- Booleans and AND, OR, NOT, IF etc.
-
- Normal form, normal and applicative order reductions.
- Church-Rosser theorems.
- 2002-08-01
-
- Recursion using pure lambda expressions.
- 2002-08-02
-
- Solving functional equations for fixpoints.
- The Y-combinator.
- 2002-08-05
-
- FLK/FL syntax.
- Data types: non-negative integers, booleans.
- IF construct
- The rec construct to support recursion.
-
- Denotational semantics of FLK.
- The role of the environment.
- 2002-08-08
-
- Using the environment to implement static scoping.
- Uses of dynamic scoping.
- 2002-08-09
-
- Modified use of the environment to implement dynamic scoping.
- Stack-like usage of the dynamic environment.
- 2002-08-12
-
- Extending FLK to FLK! to model a Store.
- Intro to operational semantics.
- 2002-08-15
-
- Modeling Store accessors as side-effect-free functions.
- Denotational semantics of FLK!.
- 2002-08-16
-
- Denotational semantics of FLK! (cont'd).
- Parameter passing: pass-by-value, pass-by-name, pass-by-reference.
- Syntactic translation from FLFL (p-b-ref) to FLK!.
2002-08-19
2002-08-22
2002-08-23
- 2002-08-26
-
- Pass-by-reference, the aliasing problem.
- Pass-by-value-result, pass-by-need.
2002-08-29
- 2002-08-30
-
- Handling arrays in FLK!.
- Denotational semantics for arrays.
- Passing arrays and array elements into Procs.
- 2002-09-02
-
- Intro to object-oriented programming:
encapsulation, inheritance.
- Inheritance examples in C++.
-
- Extending FLK/FLK! to FLOP: a toy OO language.
- Object, method, class, new
- 2002-09-05
-
- Supporting member variables via closures and Store.
- Letting methods call each other by providing this.
- Pointer casting, virtual methods, and inheritance.
- 2002-09-06
-
- Tail recursion.
- Rewriting some recursive routines in a tail-recursive form.
- Continuation-passing style of writing (recursive) programs.
- 2002-09-09
-
- FLTR: A tail-recursive variant of FLK.
- Syntactic translation from FL to FLTR.
- Intro to standard semantics.
-
- More CPS conversion examples.
- Standard semantics for FLK!.
- 2002-09-12
-
- Standard semantics for FLK!.
- Continuations as store-transformers.
- The exit, label
and goto constructs.
- 2002-09-13
-
- Standard semantics for label and goto.
- The callcc construct and its standard denotation.
- 2002-09-18
- 2002-09-23
- Midterm review.
- Implementing loops and coroutines using callcc.
- 2002-09-26
- Exceptions, throw and catch.
2002-09-27
- 2002-09-30
- 2002-10-03
- 2002-10-04
- 2002-10-07
- 2002-10-10
- 2002-10-11
- 2002-10-14
- Quiz review.
- Logic programming.
- 2002-10-17
- Introduction to logic programming.
- Rulebase, rule, relation, clause, antecedent, consequent, goal.
- 2002-10-18
- Examples of the inference process:
quicksort, permutation.
- 2002-10-24
- Backtracking.
- Inferencing with nullary relations.
- 2002-10-25
- Unification, most general unifier.
- Resolution and inferencing.
- 2002-10-28
- Types, type safety.
- Type checking and inferencing overview.
- Ad-hoc and parametric polymorphism.
- Type constants, variables, compound and function types.
- 2002-10-31
- Ad-hoc polymorphism examples.
- Parametric polymorphism examples using C++ templates and Haskell.
- Type inferencing as equation solving.
- 2002-11-01
- 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.