Principles of Programming Languages
(CS-329 and CS-389, Autumn 2003)


Time and place

Syllabus and resource links

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)

Check out last year's course page for some idea of what's in store.

NOTE: A homework or lab. submission which is late by up to 48 hours will be graded out of 80% of the original points, one which is between 48 and 96 hours late will be graded out of 40% of the original points, and submissions later than 96 hours will get zero points.

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.

Keep watching this spreadsheet until the grades are finalized.

Lecture calendar

I hope this will help you while revising the material. Extra classes are shown in color. Canceled classes are struck out.

2003-07-29 (2 hours)
2003-08-05 (2 hours)
2003-08-12 (2 hours)
Lectures canceled owing to ICML and KDD conference trips.
2003-09-02 (1 hour)
Quiz 1
Quiz 2
No class, midterm week
No class, work visit
Quiz 3
Final exam.

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. Note: Please keep checking these specs as they may be mildly altered from time to time.

Lab1 due 2003-08-18
We have already seen how to build an AST from an input FLK expression.
Lab2 due 2003-08-20
Add native boolean and integer support from Scheme. I.e., translate FLK code which includes boolean and integer literals and primitive operators (like and, not, +, *) into Scheme without trying to translate them into pure lambda calculus. Do likewise for lists and strings.
Lab3 due 2003-08-23
FLK has normal order evaluation, but Scheme has applicative order evaluation. Write a Scheme function flk-to-scheme which will take as input a FLK AST, and turn it into code which will run on Scheme, to give the FLK programmer the impression that FLK is being evaluated in normal order. For example,
 (eval (unparse
             '(call (proc x 5) (/ 3 0))  )))
should print 5 and not throw an arithmetic exception. Verify that unlike in Scheme, we no longer need the reverse-eta-reduction in rec.scm to make the Y-combinator work.
Lab4 due 2003-09-05
We can pre-define an FLK expression for the Y-combinator (make-recursive). Using this FLK expression, write a Scheme function which will take an AST which may possibly use the rec construct, and convert it for execution into applicative order Scheme, giving the illusion of a normal order FLK interpreter with recursion.
Lab5 due 2003-09-11
Write a recursive Java program to find the product of a list of numbers, equivalent to the listprod function in cps.scm. If you invoke listprod on a list with a zero in the middle, you see that time is wasted in unrolling the recursion back to the beginning of the list, cascading multiply with zeroes:
  ]=> (listprod '(2 8 9 0 3 7 ))
  9 mul 0
  8 mul 0
  2 mul 0
  ;Value: 0
Using Java exceptions, modify your Java program so that this unwinding is not required. Your Java class name should be ListMult and its main static method should be do(...), which takes a Vector of Integers as input and outputs an Integer. Static method main should return the product of all numbers given on the command line.
Lab6 due 2003-09-16
Thus far, we have accomplished the following stages: Extended FLK expression to extended FLK AST (parse), extended FLK AST to core FLK AST with rec (desugar), removing rec (more desugar), from normal to applicative order (flk-to-scheme), (*) unparse, and eval using Scheme. Next, implement an eval function for FLK, written in Scheme, which inputs a core FLK AST without rec, and uses an environment to implement static scoping (i.e., the eval is inserted at the "*" above). Execute the code on Scheme. Instrument the code so that each extension of the environment prints a message showing the new binding.
Lab7 due 2003-09-25
Modify the eval function to implement dynamic scoping.
Lab8 due 2003-10-15
In the Scheme expression (set! Eloc Enval), we start with store s0, evaluate Eloc which produces store s1, then evaluate Enval which produces store s2, and then do the writing in s2 to produce s3. Scheme also returns the old value in the cell corresponding to location Eloc, but is this value w.r.t. store s0, s1, s2, or s3? Write probe expression/s to find out.
Lab9 due 2003-10-30
Lab10 due 2003-12-02

Implement a subset of FLOP (our toy object oriented language). We will support these language constructs:

  (class Cname
    (member x)
    (method M (Ia*) Em) )
All methods are NON-virtual. Methods can call each other in mutual recursion.

Old specs: Implement FLOP (our toy object oriented language). The language constructs look like this:

  (class Cname [extends Base]
    (member x)
    ([virtual] method M (Ia*) Em) )
The this argument is defined implicitly, but can be used explicitly as well, just like in Java. Methods can call each other freely. Methods can freely access members in Cname as well as Base. If Cname is extended from Base, a method toBase is automatically implemented by the system. The class itself is an object with a single new method as discussed.

Lab11 due 2003-12-03
Extend prolog.scm to implement basic logic programming without cuts. I.e., take the primitive prover we wrote in C++ and turn it into Scheme while adding the unification code we wrote in class.

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.