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

Administrivia

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.

Evaluation

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)
		   (cond
		     ((null? lst) 1)
		     ((= 0 (car lst)) (escape bailout 0))
		     (else (* (car lst) (list-prod-shortcut (cdr lst))))
		     );cond
		   );lambda
		 ))
		(list-prod-shortcut lst) );let
		);label
	);define
      

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 qsort1.pro and qsort2.pro 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 color2.pro and modify it to not print redundant permutations of a given coloring.

Solve any one of the following problems:

• Implement a desugaring of the following features of FLOP into FL!: classes with new, single inheritance and super, virtual and non-virtual methods, and implicit access to members (i.e., should not need to say this.var inside methods).
• Starting with the AST implementation in ast.scm and the unification program in prolog.scm, write in Scheme the first (monomorphic) version of the reconstruction algorithm R.

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

• 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.
• Lambda expressions and their use as an intermediate ("target") language.
• "Meaning" of lambda expressions.
• From lambda expressions to Stoy diagrams and abstract syntax trees.
• Free and bound variables.

2004-08-03 Tue

• Performing substitutions on ASTs with no bound variable names.
• Applying a lambda function by substitution.
• A recursive definion of substitution via string manipulation.
• Redex, normal form, alpha, beta, eta conversions.
• Self-replicating expression ( (\ x (x x)) (\ y (y y)) ).
• Normal and applicative order evaluation; see order1.scm and order2.scm.
• TRUE, FALSE, IF (see bool.scm).
• PAIR, LEFT, RIGHT (see pair.scm).
• Church numerals, INC, ZERO? (see number.scm).
• More representation games: PLUS, TIMES, DEC.

2004-08-06 Fri

• Environment as a mapping from identifiers (variable names) to values.
• An environment implementation using lambda expressions.
• Introduction to the Eval function and various semantics types: Value, Proc, etc.
• Using an environment to drive name lookups in Eval (instead of resorting to explicit beta-substitution.

2004-08-09 Mon

• Examples of static and dynamic scope; demo that Scheme follows static scope.
• The notion of a closure.
• Why dynamic name binding is also desirable.

2004-08-10 Tue

• 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).
• The FACT functional (see fact.scm).
• Using Church numerals to implement FACT (see fact.scm).
• Derivation of the normal order Y combinator.
• A complete guide to recursion and the Y-combinator.

2004-08-13 Fri

• Implementing dynamic scoping by passing a call-time Env as a second param to Procs.
• Scheme structures; building ASTs from concrete syntax (see ast.scm).
• Some details on how to desugar and eval FLK.

2004-08-16 Mon

• More plumbing for CS389
• Modules

2004-08-17 Tue

• Non-hierarchical namespaces via modules (precursor of objects).
• Mutable store and its primitive access functions new, read and write.

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

• Store, continued.
• FL!, an imperative dialect of FL/FLK and its interpretation using the primitive Store access functions.
• Store needs to be an extra arg to Proc.
• Store mutations, normal order evaluation, and non-determinism.

2004-08-31 Tue

• Scheme implements implicit allocation on let and implicitly performs two-level (Env, Store) dereferencing to support set!.
• swap in different languages.
• FLR, a pass-by-reference language with implicit dereferencing.
• Directly evaluating FLR.
• Desugaring FLR to FL!.
• Call by reference and the aliasing problem.

2004-09-03 Fri

• Passing aggregate parameters such as arrays into procedures.
• Probes to find out the effect of references on passing primitive params, object params, and arrays in Java.
• Eval for arrays, two versions.
• Call by value, deep and shallow copy of parameters.
• Probes into how Scheme does memory mgmt for parameter-passing.

2004-09-06 Mon

• Mutable objects with members and methods.
• A combination of desugaring and evaluation.
• Definitions of class, instance, member, method.
• Classes as objects with a new method.
• The FLOP language: FL + object-orientation.

2004-09-07 Tue

• Inheritance and virtual methods in FLOP.
• The virtues of virtual functions.
• Member and method access in different OO languages like Scheme and C++.
• Members are accessed by lexical namespace (non-virtual).
• Java has compulsory virtual functions.
• C++ and C# give you a choice.

2004-09-10 Fri

ADFOCS/ECML/PKDD trip.

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

ADFOCS/ECML/PKDD trip.

2004-09-23 Thu

• Some probes into inheritance policies of C++ and Java.
• How to represent objects in Scheme.
• Object as a function table in Scheme.
• Method as a symbol to be matched in function table.

2004-09-24 Fri

• How object references are cast to superclasses.
• Implementing virtual functions by adding a this parameter to all method parameter lists.
• Broad C++ tutorial, virtual methods.
• MSDN blog on virtual methods.
• How to write portable C++.

2004-09-24 Fri, continued

• Intro to control constructs: iteration without space blowup, while, for, break, continue, exit, return.
• Exception handling motivations.
• Tail recursive form of factorial: passing control info as params to functions.

2004-09-27 Mon

• Using lambda expressions to represent pending computation.
• Continuation: a loose definition.
• Continuation passing style (see cps.scm).
• Continuation as an extra parameter to functions.
• Atomic and complex expressions.

2004-09-28 Tue

• FLCPS: A tail recursive variant of lambda grammar.
• CPS conversion from core FLK to FLCPS.
• An example of CPS conversion.

2004-09-28 Tue

• From CPS conversion to writing standard semantics.
• New eval functions which use a continuation as an addition parameter.
• label and return.
• Bailing out of error conditions by junking the current continuation.

2004-10-01 Fri

• Intro to callcc.
• 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)))))
  	    

• Formal semantics 1, 2 of callcc with an example 1, 2, 3.

2004-10-04 Mon

• Some mind-bending callcc examples.
• Implementing iterative loops using callcc (see loop.scm).

2004-10-05 Tue

• Quick review of dynamic resolution of this in FLOP.
• 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.

2004-10-08 Fri

• Proposed syntax for exception handling in FLK, similar to Java.
• Implementing exceptions in FLAX (FLk And eXceptions).

2004-10-11 Mon

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

2004-10-12 Tue

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

2004-10-15 Fri

• Inference with nullary predicates: Infer.cpp.
• Unification written in Scheme: prolog.scm

2004-10-18 Mon

• Intro to types, basic concepts.
• Static and dynamic types.
• Implicit and explicit types.
• Ad-hoc and parametric polymorphism.

2004-10-19 Tue

• More Prolog examples.
• Negation and failure, unintuitive implications.
• Back to type analysis...
• Type variable, type expressions, type environment, type schema.
• Setting up type equations by walking an AST.

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

• Type reconstruction with homogeneous collections and no polymorphism: design of the R type inference algo: 1, 2, 3.
• An example of R at work.
• Shortcomings of a monomorphic framework.
• Pitfalls with cellof and subtyping.

2004-11-01 Mon

• Typing Y and letrec constructs.
• Parametric polymorphism (e.g. templates in C++).
• Inference rules with parameteric polymorphism.

2004-11-02 Tue

• Inference rules with parameteric polymorphism, continued.
• Reconstruction algorithm for parametric polymorphism: 1, 2, 3.
• Some worked-out examples of reconstruction.

2004-11-05 Fri

Quiz-3, 10 marks. Solutions: 1, 2.

2004-11-08 Mon

• Garbage collection and memory management, motivation.
• Reference counting and pitfalls.
• Tracing GCs, type-safe Store.
• Stop-and-copy GC.
• Semi-space GC, the asymptotic efficiency argument.
• Check out a whole site about GC and a great survey.

2004-11-09 Tue

• Course round-up: overall block diagram of an interpreter supporting objects, type analysis, exceptions, etc.
• Some worked-out problems.
• Brief overview of axiomatic semantics. Here are some links you are expected to be familiar with before the final exam.
  • A book chapter.
  • Some slides.
• Good luck with your finals! (Yes, we will have finals.)

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.