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

Staff

• Instructor: Soumen Chakrabarti
• TA's: Gulavani Bhargav Subhas (), Deepa Paranjpe ().

Time and place

• Lectures: Room S9 (top floor, CSE): M11:30, W11:30Th8:30, F11:30). Ask your friendly CR about last-moment rescheduling and check my homepage about my travel plans.
• Lab (CS-389): Slot L2, OSW Lab, Tue afternoon (but we wish to make this flex-time)
• Office hours: WedFri afternoons. Any other meetings by prior email appointment only.
• Try not to use my regular email for matter related to the course. A new email will be set up for this purpose. There will also be a newsgroup iitb.courses.cse329 which you should actively read.

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.

• NEW! The Why of Y by Richard Gabriel.
• Another treatise on recursion by Eli Barzilay.
• Prof. Sanyal's corresponding graduate course home page.
• Essentials of Programming Languages by Daniel Friedman, Mitchell Wand, and Chris Haynes. Prentice Hall, ISBN 81-203-1355-0. Much of the course will refer to this book.
• A paper on CPS.
• Structure and Interpretation of Computer Programs by Harold Abelson, Gerald Jay Sussman and Julie Sussman.
• The MIT Scheme home page.
• A Scheme tutorial and user manual.
• The Haskell home page.
• Denotational Semantics: The Scott-Strachey Approach to Programming Languages by Joseph Stoy. MIT Press, Cambridge, MA, 1985.
• Some URLs on type reconstruction/inferencing: 1, 2.

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.

• A final exam, originally graded out of 35 marks, will be rescaled to 45% of the course total.
• A midterm exam, originally graded out of 15 marks, will be rescaled to 20% of the course total.
• Quiz 1, originally worth 20 marks, will be scaled to 12% of the course total. This was a pre-announced quiz.
• Quiz 2, originally worth 6 marks, will be scaled to 8 marks. Quiz 3 will remain at 8 marks. The maximum of Quiz 2 and Quiz 3 will contribute 8% to the course total.
• Homeworks, worth 15%.
• Extra credit for voluntary projects etc.

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-24

• Prereq survey.
• von Neumann architecture, semantic gap from high-level languages.
• Interpretation and compilation.
• What to study in a programming language: naming, storage, parameter-passing, control, type system.

2003-07-25

• Lambda expressions and their use as an intermediate ("target") language.
• "Meaning" of lambda expressions.
• Applying a lambda function by substitution.

2003-07-28

• From lambda expressions to Stoy diagrams and abstract syntax trees.
• Performing substitutions on ASTs with no bound variable names.
• Free and bound variables.

2003-07-29 (2 hours)

• A recursive definion of substitution via string manipulation.
• Normal and applicative order evaluation (to be completed, also see order1.scm, order2.scm).
• TRUE, FALSE, IF (see bool.scm).
• Church numerals, INC, ZERO? (see number.scm).

2003-07-30

• Redex, normal form, alpha, beta, eta conversions.
• Normal and applicative order.
• PAIR, LEFT, RIGHT (see pair.scm).

2003-08-01

• More representation games: PLUS, TIMES, DEC.
• Using Church numerals to implement FACT (see fact.scm).

2003-08-04

• Self-replicating expression ( (\ x (x x)) (\ y (y y)) ).
• Using the self-replicating expression to implement recursion using pure lambda expressions.
• The (rec I E) construct to express recursive functions (this is desugared into a pure lambda expression).

2003-08-05 (2 hours)

• DEC using PAIR (see number.scm).
• The FACT functional (see fact.scm).
• Hack: fact-church.
• Derivation of the normal order Y combinator.
• Scheme structures; building ASTs from concrete syntax (see ast.scm).
• Implementing a name lookup environment using lambda expressions.

2003-08-06

• A complete guide to recursion and the Y-combinator.

2003-08-08

• Static scoping through the environment data structure.
• The notion of a closure.

2003-08-11

• Summary of desugaring and eval from FLK to Scheme.
• Environment, closure, and static scoping revisited.
• Intro to dynamic scoping, why sometimes desirable.

2003-08-12 (2 hours)

• Implementing dynamic scoping by passing a call-time Env as a second param to Procs.
• Some details on how to desugar and eval FLK.

2003-08-13

• Non-hierarchical namespaces via modules (precursor of objects).

2003-08-18

• Tail recursive form of factorial.
• Using lambda expressions to represent pending computation.
• Continuation: a loose definition.
• Continuation passing style (see cps.scm).
• FLCPS: A tail recursive variant of lambda grammar.

2003-08-20

2003-08-22

2003-08-25

2003-08-27

2003-08-29

Lectures canceled owing to ICML and KDD conference trips.

2003-09-01

• Atomic and complex expressions, FLCPS grammar.
• Continuation as an extra parameter to functions.
• CPS conversion from core FLK to FLCPS.

2003-09-02 (1 hour)

• CPS conversion, continued.
• An example of CPS conversion.
• Bailing out of error conditions by junking the current continuation.

2003-09-03

• From CPS conversion to writing standard semantics.
• New eval functions which use a continuation as an addition parameter.
• Implementation of label and goto.
• Proposed syntax for exception handling in FLK, similar to Java.

2003-09-05

• Java exceptions: see Ex1.java and Ext2.java. Both return 3, invoking the outer AEx handler.

2003-09-06

Quiz 1

2003-09-08

• Implementing exceptions in FLAX (FLk And eXceptions).
• Intro to callcc.

2003-09-10

• Informal semantics of callcc through Scheme examples. If your Scheme interpreter wants you to type call-with-current-continuation instead, you can ease typing by defining the following syntax first.

  (define-syntax flk-callcc (syntax-rules ()
      ((flk-callcc k Eb) (call-with-current-continuation (lambda (k) Eb)))))
  (define-syntax callcc (syntax-rules ()
      ((callcc Ep) (call-with-current-continuation Ep)))))
  

• Some mind-bending callcc examples.

2003-09-15

• Standard semantics for callcc.
• Implementing iterative loops using callcc (see loop.scm).

2003-09-17

• Implementing coroutines using callcc (see cor.scm).
• Summary: callcc is the most general form of control representation to expose to the programmer. It can be used to implement total and partial bailouts, label/goto, exceptions, loops, and coroutines.

2003-09-19

• Modeling mutable storage; non-determinism example.
• The operational view of store.

2003-09-22

Quiz 2

2003-09-24

• Accessor functions for store: new, read and write.
• Operational semantics: a state transition system.

2003-09-26

• Standard denotation semantics to support mutable store.
• Modifications to the semantics domains Proc, Cont, etc.
• Some basic evals for begin, call, etc.

2003-09-29

Midterm

2003-10-01

2003-10-03

No class, midterm week

2003-10-06

2003-10-08

No class, work visit

2003-10-10

• Mutable store accessors: NEW_LOC, NEW_STORE, READ, WRITE.
• Standard semantics with mutable store.
• Why do Conts need another Store parameter?

2003-10-13

2003-10-14

• Call by value, deep and shallow copy.
• Probes into how Scheme does memory mgmt for parameter-passing.
• Translation from implicit (FLref) to explicit memory access.
• Call by reference and the aliasing problem.

2003-10-15

• Direct standard semantics for implicit memory access pass-by-reference language FLref.
• Array representation and parameter passing issues.

2003-10-17

• Probes to find out the effect of references on passing primitive params, object params, and arrays in Java.
• Adding similar array support to FLref, using eval to evaluate down to calls to NEW_LOC, NEW_STORE, READ, WRITE.

2003-10-20

• Mutable objects in FL: the FLOP language.
• A combination of desugaring and evaluation.
• Definitions of class, instance, member, method.

2003-10-21

• Inheritance.
• Some probes into inheritance policies of C++ and Java.
• How to represent objects in Scheme.

2003-10-22

• Object as a function table in Scheme.
• Method as a symbol to be matched in function table.

2003-10-27

• The virtues of virtual functions.
• Members are accessed by lexical namespace (non-virtual).
• Java has compulsory virtual functions.
• C++ and C# give you a choice.

2003-10-29

• How object references are cast to superclasses.
• Implementing virtual functions by adding a this parameter to all method parameter lists.

2003-10-31

• Declarative/logic programming paradigm.
• Rule base, rules, LHS, RHS, clauses, conjunction, disjunction.
• Variables, constants.
• Prolog examples.

2003-11-03

• Prolog examples, continued.
• Inferencing with constant nullary functions.

2003-11-14

Quiz 3

2003-11-25

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.

• Is exception-handling in FLAX (see below) the same as in Java? Submit sample codes for Java and FLAX to demonstrate your answer. Deadline: 2003-09-21.
• Based on our eval for callcc, write a CPS conversion for the callcc construct. Deadline: 2003-09-30.
• In cor.scm, if we make the producer quit after 10 loop iterations, why does the consumer also quit soon thereafter, instead of continuing to increment counter by itself? NEW: Do you see the same effect if the consumer quits but the producer does not? If not, explain why not. Deadline: 2003-10-12.
• Follow the steps that eval takes on this code, showing clearly the different incarnations of Store that are passed around.

  (let ((aloc (new 1)))
    (read aloc))
  

  Deadline: 2003-10-20.

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.

• Write Scheme functions free-var, bound-var, and subst which use AST arguments.
• Extend parse to turn a string of decimal or binary digits into a church numeral.

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
         (flk-to-scheme
           (parse
             '(call (proc x 5) (/ 3 0))  )))
       user-initial-environment)

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

• Using hand-translation to Scheme, create an object fact-instance with a method run which calls itself. No explicit recursion should be visible and no Y-combinator can be used. Exploit this.
• Consider the following mutually recursive functions which work for positive inputs:

  (define (odd? num)
    (cond
     ((= 0 num) #f)
     ((= 1 num) #t)
     (else (even? (- num 1)))) )
  (define (even? num)
    (cond
     ((= 0 num) #t)
     ((= 1 num) #f)
     (else (odd?  (- num 1)))) )
  

  Using hand-translation to Scheme, create an object odd-even-instance with methods odd? and even? which call each other. Again, no explicit mutual recursion should be visible and no Y-combinator can be used. Exploit this.

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.