Principles of
Programming Languages
(CS329 and CS389, Autumn 2003)
Staff
Time and place
 Lectures: Room S9 (top floor, CSE):
M11:30, W11:30
Th8:30, F11:30).
Ask your friendly CR about lastmoment rescheduling
and check my homepage about my travel plans.
 Lab (CS389): Slot L2, OSW Lab, Tue afternoon (but we wish to
make this flextime)
 Office hours: Wed
Fri 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 uptodate.
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 8120313550.
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 ScottStrachey Approach to Programming
Languages by Joseph Stoy. MIT Press, Cambridge, MA, 1985.

Some URLs on type reconstruction/inferencing:
1, 2.
Evaluation for CS329 (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 preannounced 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.
are shown in color.
Canceled classes are struck out.
 20030724
 Prereq survey.
 von Neumann architecture, semantic gap from highlevel
languages.
 Interpretation and compilation.
 What to study in a programming language: naming, storage,
parameterpassing, control, type system.
 20030725
 Lambda expressions and their use as an intermediate
("target") language.
 "Meaning" of lambda expressions.
 Applying a lambda function by substitution.
 20030728
 From lambda expressions to Stoy diagrams and abstract syntax trees.
 Performing substitutions on ASTs with no bound variable names.
 Free and bound variables.
 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).
 20030730
 Redex, normal form, alpha, beta, eta conversions.
 Normal and applicative order.
 PAIR, LEFT, RIGHT (see
pair.scm).
 20030801
 More representation games: PLUS, TIMES, DEC.
 Using Church numerals to implement FACT
(see fact.scm).
 20030804
 Selfreplicating expression ( (\ x (x x)) (\ y (y y)) ).
 Using the selfreplicating 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).
 DEC using PAIR (see
number.scm).
 The FACT functional (see
fact.scm).
 Hack: factchurch.
 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.
 20030806
 20030808
 Static scoping through the environment data structure.
 The notion of a closure.
 20030811
 Summary of desugaring and eval from FLK to Scheme.
 Environment, closure, and static scoping revisited.
 Intro to dynamic scoping, why sometimes desirable.
 Implementing dynamic scoping by passing a calltime
Env as a second param to Procs.
 Some details on how to desugar and eval FLK.
 20030813
 Nonhierarchical namespaces via modules
(precursor of objects).
 20030818
 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.
20030820
20030822
20030825
20030827
20030829
 Lectures canceled owing to ICML and KDD conference trips.
 20030901
 Atomic and complex expressions, FLCPS grammar.
 Continuation as an extra parameter to functions.
 CPS conversion from core FLK to FLCPS.
 CPS conversion, continued.
 An example of CPS conversion.
 Bailing out of error conditions by junking the current
continuation.
 20030903
 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.
 20030905
 Java exceptions: see Ex1.java
and Ext2.java. Both return 3, invoking
the outer AEx handler.
 20030906
 Quiz 1
 20030908
 20030910
 20030915
 Standard semantics for callcc.
 Implementing iterative loops using callcc
(see loop.scm).
 20030917
 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.
 20030919
 Modeling mutable storage; nondeterminism example.
 The operational view of store.
 20030922
 Quiz 2
 20030924
 Accessor functions for store: new, read
and write.
 Operational semantics: a state transition system.
 20030926
 Standard denotation semantics to support mutable store.
 Modifications to the semantics domains
Proc, Cont, etc.
 Some basic evals for begin, call, etc.
 20030929
 Midterm
20031001
20031003
 No class, midterm week
20031006
20031008
 No class, work visit
 20031010
 Mutable store accessors: NEW_LOC, NEW_STORE, READ, WRITE.
 Standard semantics with mutable store.
 Why do Conts need another Store parameter?
 20031013
 Call by value, deep and shallow copy.
 Probes
into how Scheme does memory mgmt for parameterpassing.
 Translation from implicit (FLref) to explicit memory access.
 Call by reference and the aliasing problem.
 20031015
 Direct standard semantics for implicit memory access
passbyreference language FLref.
 Array representation and parameter passing issues.
 20031017
 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.
 20031020
 Mutable objects in FL: the FLOP language.
 A combination of desugaring and evaluation.
 Definitions of class, instance, member, method.
 20031022
 Object as a function table in Scheme.
 Method as a symbol to be matched in function table.
 20031027
 The virtues of virtual functions.
 Members are accessed by lexical namespace (nonvirtual).
 Java has compulsory virtual functions.
 C++ and C# give you a choice.
 20031029
 How object references are cast to superclasses.
 Implementing virtual functions by adding a this
parameter to all method parameter lists.
 20031031
 Declarative/logic programming paradigm.
 Rule base, rules, LHS, RHS, clauses, conjunction, disjunction.
 Variables, constants.
 Prolog examples.
 20031103
 Prolog examples, continued.
 Inferencing with constant nullary functions.
 20031114
 Quiz 3
 20031125
 Final exam.
Homeworks (CS329)
You can do these in groups of 23 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 23 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 20030818
 We have already seen how to
build an AST from an input
FLK expression.
 Write Scheme functions freevar, boundvar,
and subst which use AST arguments.
 Extend parse to turn a string of decimal or binary digits
into a church numeral.
 Lab2 due 20030820
 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 20030823
 FLK has normal order evaluation,
but Scheme has applicative order evaluation. Write
a Scheme function flktoscheme 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
(flktoscheme
(parse
'(call (proc x 5) (/ 3 0)) )))
userinitialenvironment)
should print 5 and not throw an arithmetic exception.
Verify that unlike in Scheme,
we no longer need the reverseetareduction
in rec.scm
to make the Ycombinator work.
 Lab4 due 20030905
 We can predefine an FLK expression for the Ycombinator
(makerecursive). 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 20030911
 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 20030916
 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 (flktoscheme),
(*) 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 20030925
 Modify the eval function to implement dynamic scoping.
 Lab8 due 20031015
 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 20031030
 Lab10 due 20031202
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 NONvirtual.
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 20031203
 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.