Principles of Programming Languages
(CS329 and CS389, Autumn 2004)

The idea is, you memorize these things, then write them down in little exam books, then forget them. If you fail to forget them, you become a professor and have to stay in college for the rest of your life. ---Dave Barry


Lectures at S9 M11:30, Tu3:00, F11:30. The Tuesday class will be 1h or 2h depending on whether we are using an extra slot. No routine CS389 meetings. TAs: A. C. Rajeev, ; Gautham Anil, ; Vijay Krishnan, . Note: You need Javascript to view this page properly.


For CS329, there will be a midterm, a final, and a few quizzes. Any lecture hour is fair game for a quiz. Quizzes outside pre-scheduled lecture hours will be announced separately in advance.

CS389 grades will be determined entirely by performance in lab. assignments.

For any team submission, the whole team gets a single score.

Here is a spreadsheet that summarizes the current state of our evaluation process. While we will make every effort to ensure correctness and fairness, you are also responsible for monitoring this spreadsheet from time to time and reporting any problems you find with your marks.

Lab. assignments

Deadlines and tentative maximum credit are shown alongside. For late submissions your maximum credit will be a fraction of the full credit; 1 week late: 60%, more than 1 week late: 10%, after endsem starts: 0%. NOTE: The deadlines are final henceforth. Relative marks across assignments may vary a bit.

Add support for primitive functions to FLK
Add support for the rec construct using the make-recursive routine provided.
Add support for multi-binding let construct.
Desugar a looping construct similar to Scheme into Scheme without do, using callcc. The looping construct is (do Ebody while Econd). You need to support nested loops, and also the constructs (break Eout) and continue.
Desugar the (label I E) and (return Er) constructs to Scheme using callcc. (The choice of the word return was unfortunate; it wrongly hints at the return construct in Java/C++/C. Specifically, in the standard sense of return, you cannot return out of an arbitrary nesting of recursive calls all at once. Let us change the name return to escape.) You should be able to write code like this and achieve the desired short-cut if lst has a zero in the middle, as shown in class.
      (define (list-prod lst)
        (label bailout
	  (let ((list-prod-shortcut
	         (lambda (lst)
		     ((null? lst) 1)
		     ((= 0 (car lst)) (escape bailout 0))
		     (else (* (car lst) (list-prod-shortcut (cdr lst))))
		(list-prod-shortcut lst) );let
Add support for multi-binding letrec construct.
Write a different version of eval that uses dynamic scope.
Implement a thin wrapper around Scheme's set!-based store to give you the Store we used in class, together with the primitive accessors. Make sure they are reasonably efficient, e.g. don't walk down a linear list for each update.
Implement FLR on top of FLK and your Store implementation (i.e., FL!). Implement swap and show that it is working.
Inspect the two Prolog rulebases and and answer these questions (email to the TAs and get an ack within deadline):
  1. Why does qsort1 NOT permute when input and output are reversed?
  2. Why does qsort2 NOT sort properly when input and output are provided as intended?
  3. Write qsort3, a Prolog rulebase that does reversible quicksorting and permutation.
Also inspect and modify it to not print redundant permutations of a given coloring.
Solve any one of the following problems:

The total marks thus far out of which CS389 will be evaluated is .

Lecture calendar

Here is the tentative timeline of the course. I hope this will help you plan your semester and revise the material. Extra lectures, or 1h lectures that were drawn out to 2h, are shown in color. Canceled classes are struck out.

2004-07-27 Tue
2004-07-29 Thu
2004-07-30 Fri
Classes cancelled owing to field visit.
2004-08-02 Mon
2004-08-03 Tue
2004-08-06 Fri
2004-08-09 Mon
2004-08-10 Tue
2004-08-13 Fri
2004-08-16 Mon
2004-08-17 Tue
2004-08-20 Fri
2004-08-23 Mon
Lectures canceled owing to KDD conference trip.
2004-08-25 Wed
Quiz-1, 8 marks. Did you run out of time?
2004-08-26 Thu
2004-08-27 Fri
Lectures canceled owing to KDD conference trip.
2004-08-30 Mon
2004-08-31 Tue
2004-09-03 Fri
2004-09-06 Mon
2004-09-07 Tue
2004-09-10 Fri
2004-09-13 Mon
2004-09-14 Tue
Midterm week.
2004-09-15 Wed
Midterm exam (afternoon), 20 marks. Some of the answers reminded me of Calvin.
2004-09-17 Fri
Midterm week.
2004-09-20 Mon
2004-09-23 Thu
2004-09-24 Fri
2004-09-24 Fri, continued
2004-09-27 Mon
2004-09-28 Tue
2004-09-28 Tue
2004-10-01 Fri
2004-10-04 Mon
2004-10-05 Tue
2004-10-08 Fri
2004-10-11 Mon
2004-10-12 Tue
2004-10-15 Fri
2004-10-18 Mon
2004-10-19 Tue
2004-10-26 Tue
Quiz-2, originally 20 marks, but will be graded out of 16. Q1b will go down from 6 to 5 marks and Q1c (originally worth 3 marks) will not be graded (or only as extra credit) because the solution has unexpected dangerous bends for an in-class exam.
2004-10-29 Fri
2004-11-01 Mon
2004-11-02 Tue
2004-11-05 Fri
Quiz-3, 10 marks. Solutions: 1, 2.
2004-11-08 Mon
2004-11-09 Tue
2004-11-25 Thu
Final exam (now with some solutions and solution hints): 46 marks.

Copyright statement

Copyright to documents and software referred to herein remain with the respective copyright holders. Copyright to this specific course organization, course handouts, and exams is owned by IIT Bombay.