(CS-329 and CS-389, Autumn 2003)
Time and place
- Lectures: Room S9 (top floor, CSE):
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: Wed
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
and ACM syllabi.
The Why of Y
by Richard Gabriel.
- Another treatise on recursion by Eli Barzilay.
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.
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:
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.
I hope this will help you while revising the material.
are shown in color.
Canceled classes are struck out.
- Prereq survey.
- von Neumann architecture, semantic gap from high-level
- 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.
- Applying a lambda function by substitution.
- 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,
- TRUE, FALSE, IF (see bool.scm).
- Church numerals, INC, ZERO?
- Redex, normal form, alpha, beta, eta conversions.
- Normal and applicative order.
- PAIR, LEFT, RIGHT (see
- More representation games: PLUS, TIMES, DEC.
- Using Church numerals to implement FACT
- 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).
- DEC using PAIR (see
- The FACT functional (see
- Hack: fact-church.
- Derivation of the normal order Y combinator.
- Scheme structures; building ASTs from concrete syntax
- Implementing a
name lookup environment
using lambda expressions.
- Static scoping through the environment data structure.
- The notion of a closure.
- 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 call-time
Env as a second param to Procs.
- Some details on how to desugar and eval FLK.
- Non-hierarchical namespaces via modules
(precursor of objects).
- Tail recursive form of factorial.
- Using lambda expressions to represent pending computation.
- Continuation: a loose definition.
- Continuation passing style (see
- FLCPS: A tail recursive variant of lambda grammar.
- Lectures canceled owing to ICML and KDD conference trips.
- 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
- From CPS conversion to writing standard semantics.
- New eval functions which use a continuation as an addition
- Implementation of label and goto.
- Proposed syntax for exception handling in FLK,
similar to Java.
- Java exceptions: see Ex1.java
and Ext2.java. Both return 3, invoking
the outer AEx handler.
- Quiz 1
- Standard semantics for callcc.
- Implementing iterative loops using callcc
- 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.
- Modeling mutable storage; non-determinism example.
- The operational view of store.
- Quiz 2
- Accessor functions for store: new, read
- Operational semantics: a state transition system.
- Standard denotation semantics to support mutable store.
- Modifications to the semantics domains
Proc, Cont, etc.
- Some basic evals for begin, call, etc.
- No class, midterm week
- No class, work visit
- Mutable store accessors: NEW_LOC, NEW_STORE, READ, WRITE.
- Standard semantics with mutable store.
- Why do Conts need another Store parameter?
- Call by value, deep and shallow copy.
into how Scheme does memory mgmt for parameter-passing.
- Translation from implicit (FLref) to explicit memory access.
- Call by reference and the aliasing problem.
- Direct standard semantics for implicit memory access
pass-by-reference language FLref.
- Array representation and parameter passing issues.
- 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.
- Mutable objects in FL: the FLOP language.
- A combination of desugaring and evaluation.
- Definitions of class, instance, member, method.
- Object as a function table in Scheme.
- Method as a symbol to be matched in function table.
- 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.
- How object references are cast to superclasses.
- Implementing virtual functions by adding a this
parameter to all method parameter lists.
- Declarative/logic programming paradigm.
- Rule base, rules, LHS, RHS, clauses, conjunction, disjunction.
- Variables, constants.
- Prolog examples.
- Prolog examples, continued.
- Inferencing with constant nullary functions.
- Quiz 3
- Final exam.
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
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
- 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,
'(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
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
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
- 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
- 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.
Implement a subset of FLOP (our toy object oriented language).
We will support these language constructs:
(method M (Ia*) Em) )
All methods are NON-virtual.
Methods can call each other in mutual recursion.
Implement FLOP (our toy object oriented language).
The language constructs look like this:
(class Cname [extends Base]
([virtual] method M (Ia*) Em) )
- 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.
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