(CS-329 and CS-389, Autumn 2000)
Time and place
Slot 6 (Room A2, Mon 11:30, Thu 8:30, Fri 11:30)
Wed 10:30--12, Fri 10:30--12, room F-11.
Ask your friendly CR about last-moment rescheduling and check my homepage
about sudden travel plans.
- Lab (CS-389): Slot L2, OSW Lab, Tue afternoon (but we wish to
make this flex-time)
- Office hours: Fri afternoons. Any other meetings by prior
email appointment only.
Evaluation for CS-329
- Tentative total marks out of 100 percent
and grades are out. Please let us know if
there is any clerical error.
Some corrections are already in.
- Final exam marks are out as well.
This counts for 50 percent. You can have a look at your graded finals
strictly during Monday 27th and Tuesday 28th afternoons.
- Homework marks have been collected
together. Homeworks count for 20 percent.
Check that your roll number matches your login name.
- Midterm scores have been collected
too. Midterm counts for 30 percent.
- Although IITB does not implement it, an
code should be in place informally.
Evaluation for CS-389
- 100% programming assignments and projects.
Please check your scores
for possible clerical errors.
A scatter plot
of CS389 vs CS329 marks are available. Correlation is
positive, thank goodness.
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.
Can programming be liberated from the von Neumann style?...
Turing Award Lecture by John Backus.
Communications of the ACM, 21(8) Aug. 1978, page 613.
functional programming matters by John Hughes. A classic paper
Denotational Semantics: The Scott-Strachey Approach to Programming
Languages by Joseph Stoy. MIT Press, Cambridge, MA, 1985.
Combinatorial Logic by Curry and Feys, volume 1 chapter 4.
North Holland Publishing Co., 1974.
chapter from a delightful book,
Little Schemer, explaining recursion using lambda expressions.
Exercises are also available.
An axiomatic basis for computer programming,
by C. A. R. Hoare,
in CACM 12(10) October 1969.
Guarded commands, nondeterminacy and formal derivation of programs,
by Edsger W. Dijkstra,
in CACM 18(8) August 1975.
- Haskell Homepage.
Some URLs on type reconstruction/inferencing:
- Introduction and administrative details
- Abstract models of computation and architectural realities
- Functional programming, the model and lambda calculus
- Introduction to the lab skills required
- Lambda grammar, free and bound variables
- Outline of the first programming assignment
- Kernel and desugaring approach to language design
- Core language: lambda calculus plus basic datatypes
- Representing integers, booleans, conditional, pairs, lists
- Implementing DEC and recursion in lambda calculus
- Structured operational semantics
- Introduction to denotational semantics
- The role of the environment, store, continuations
- Functionals and fixpoint functions; the rec construct
- FLK syntax and denotation
- Illustration of FLK interpretation using the environment
- Introduction to FL (let and letrec) and desugaring FL
- Modeling mutation and the store using FLK!
- Using mutable cells to implement recursive naming
- Static and dynamic scoping
- Parameter passing mechanisms: pass by value
and pass by name
- An experimental language with pass-by-denotation
- Motivation for non-hierarchical scoping
- Array data type
- Pass by reference, value-result, need
- Return to non-hierarchical scoping using modules
- Modules, objects, methods, constructors
- Single and multiple inheritance
- Last part of object-oriented language design using FL/FLK
- Review of some questions from the
- Introduction to tail recursion
- 2000-09-20, 22
- Midterm review
- Tail recursion and continuation-passing style (CPS)
- Stack behavior of CPS programs
- Guest lecture by RKJ on object-oriented programming
- Midterm review continued:
- Algorithm for conversion to CPS
CPS conversion example
- Introduction to standard semantics
- Standard semantics with store and continuations
- Non-local control transfer
- Introduction to exception handling
- The callcc construct and its meaning
- Translating callcc to CPS
- Implementing coroutines using callcc
- Declarative or logic programming paradigm
- Examples: list member, append, ancestor
- Reversability of input and output
- The Prolog execution model
- Problems with symmetry and cut
- Substitutions, most general substitution
- The unification algorithm
- Types: static, dynamic, simple, monomorphic, polymorphic
- Type-checking, type reconstruction/inferencing, type safety
- Type equivalence, recursive types, subtypes, types as a partial order
- Ad-hoc and parametric polymorphism, templates
- Haskell syntax for types and interfaces
- Introduction to type reconstruction
- Inference rules for type reconstruction
- Milner-style type reconstruction algorithms
- Course summary
- Summary of Scheme interpretation and compilation
Assignments to supplement lectures
You can form groups and turn in only one writeup per group.
All group members will get the same score in a homework.
Please coordinate with your friendly CR and TAs to decide on a
uniform submission format.
- Assignment 1 (Due 2000-08-18)
- Find out if Scheme follows applicative order or normal order by
writing a suitable simple program using the infinite expression shown
in class. Make available to the TAs a short Scheme program and a
- Design the environment data structure with the
accessor functions discussed in class for storing name-to-value
bindings. Call the functions empty-env,
Make the Scheme code available to the TAs.
- Assignment 2 (Due 2000-08-25)
Write a program in Scheme that will read a file with a lambda
expression in free format and turn it into an abstract syntax tree
(AST). To avoid confusion with the scheme lambda
keyword, we will use Lambda. The AST should have
nodes called ID, ABS and
APP. Having constructed the AST, number the nodes in
left-to-right depth-first order. Having done that, for each node,
print out if it is a free variable. If it is a bound variable, print
the node number of the binding ABS.
- Assignment 3 (Due 2000-10-01)
Implement a substitution routine called ast-subst
which will accept an AST for E1 and E2 and output a
AST corresponding to [E2/I]E1, with variables renamed as necessary.
Implement a normal order and an applicative order lambda execution
engine. Write code to print steps of evaluation in a readable manner.
- Assignment 4 (Due 2000-10-08)
Use the lambda engine to run recursive factorial and list-length
functions using various forms of the Y-combinator.
Modify your interpreter to use an environment rather than
ast-subst. Is this easier or harder to code than
using substitution? Is it more or less efficient at runtime?
- Assignment 5 (Due 2000-10-31)
Try running the expressions involving callcc given as
examples in class using Scheme. Some syntax such as new and
write will need to be changed to run as Scheme code.
Write a FLK to FLCPS translator using the codebase you already have.
You can choose the simpler subset of FLK as in class.
Consider the following code:
(+ 1 (label EXIT (+ 2 (* 3 (/ 4 (goto EXIT 5))))))
Hand-translate this to use FLK and callcc.
Translate in turn to FLCPS using your program and execute the FLCPS
using the lambda engine you have implemented.
Implement FLOP (as in the midterm exam) using the FL/FLK interpreter
code you have built so far. You need not implement the store.
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