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.

• HW-1 and some solutions (NOTE: I have not double checked these for correctness)
• Review some class notes on managing store, cells, and mutation, courtesy Varun Kacholia. NOTE: There are some comments in these notes which need clarification; I will post some on the newsgroup.
• HW-2
• Review some class notes on array management, courtesy Rahul Balani.
• HW-3
• HW-4

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:
  1. Compile and run the following programs: swap.C and swap.f.
  2. Explain the results by making educated guesses about how the two languages handle pass-by-reference.
  3. 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. Extra classes 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.

2002-07-24

• 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.

2002-07-31

• 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.

2002-08-07

• 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

VLDB

2002-08-22

VLDB

2002-08-23

VLDB

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++.

2002-09-05

• 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.

2002-09-12

• 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

Midterm, also see Delete.cpp.

2002-09-23

• Midterm review.
• Implementing loops and coroutines using callcc.

2002-09-26

• Coroutines, continued.

2002-09-26

• Exceptions, throw and catch.

2002-09-27

PT field trip with Siva

2002-09-30

2002-10-03

Guest lecture by RKJ

2002-10-04

Guest lecture by RKJ

2002-10-07

Quiz

2002-10-10

Guest lecture by AS

2002-10-11

Guest lecture by AS

2002-10-14

Guest lecture by AS

2002-10-17

• 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.