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, .
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.
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)
((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
- 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
qsort2.pro and answer
these questions (email to the TAs and get an ack within deadline):
Also inspect color2.pro
and modify it to not print redundant permutations of a given
- Why does qsort1 NOT permute when input and
output are reversed?
- Why does qsort2 NOT sort properly when input and
output are provided as intended?
- Write qsort3, a Prolog rulebase that does reversible
quicksorting and permutation.
- 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 .
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,
Canceled classes are
- Classes cancelled owing to field visit.
- 2004-08-02 Mon
- von Neumann architecture, semantic gap from
- 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
- "Meaning" of lambda expressions.
- From lambda expressions to Stoy diagrams and abstract
- Free and bound variables.
- Performing substitutions on ASTs with no bound
- 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
- TRUE, FALSE, IF (see
- PAIR, LEFT, RIGHT
- Church numerals, INC, ZERO?
- More representation games: PLUS, TIMES, DEC.
- 2004-08-06 Fri
- Environment as a mapping from identifiers (variable names)
- An environment
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.
- 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
- Derivation of the normal order Y combinator.
- A complete guide to
- 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
- Some details on how to desugar and eval FLK.
- 2004-08-16 Mon
- More plumbing for CS389
- Non-hierarchical namespaces via modules
(precursor of objects).
- Mutable store and its primitive access functions
new, read and write.
- Lectures canceled owing to KDD conference trip.
- 2004-08-25 Wed
- Quiz-1, 8 marks. Did you
run out of time?
- 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,
- 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
- 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.
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.
- ADFOCS/ECML/PKDD trip.
- Midterm week.
- 2004-09-15 Wed
- Midterm exam (afternoon),
20 marks. Some of the answers reminded me of
- Midterm week.
- ADFOCS/ECML/PKDD trip.
- 2004-09-23 Thu
- Some probes into inheritance policies of
- How to represent objects
- Object as a function table in Scheme.
- Method as a symbol to be matched in function table.
- 2004-09-24 Fri
- 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
- 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.
- From CPS conversion to writing standard semantics.
- New eval functions which use a continuation as an addition
- label and return.
- Bailing out of error conditions by junking the current
- 2004-10-01 Fri
- 2004-10-04 Mon
- Some mind-bending callcc
- Implementing iterative loops using callcc
- Quick review of dynamic resolution of this
- Implementing coroutines using callcc
- 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
Both return 3, invoking the outer AEx
- Declarative/logic programming paradigm.
For this segment, download
- Rule base, rules, LHS, RHS, clauses,
- Variables, constants.
- Prolog examples.
- 2004-10-15 Fri
- 2004-10-18 Mon
- Intro to types, basic concepts.
- Static and dynamic types.
- Implicit and explicit types.
- Ad-hoc and parametric polymorphism.
- More Prolog examples.
- Negation and failure,
- Back to type analysis...
- Type variable, type expressions, type environment, type schema.
- Setting up type equations by walking an AST.
- 2004-10-26 Tue
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
- Type reconstruction with homogeneous collections and no
polymorphism: design of the R type inference algo:
- 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.
- Inference rules with parameteric polymorphism, continued.
- Reconstruction algorithm for parametric polymorphism:
- Some worked-out examples of reconstruction.
- 2004-11-05 Fri
- Quiz-3, 10 marks.
- 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
site about GC and a
- 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.
- Good luck with your finals!
- 2004-11-25 Thu
- Final exam (now with some
solutions and solution hints): 46 marks.
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