Programming Languages
(CS-329 and CS-389, Autumn 2000)

Staff

• Instructor: Soumen Chakrabarti
• TA's: Yusuf Batterywala, N. Mallikarjuna Rao, Nikhil

Time and place

• Lectures: 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 honor code should be in place informally.

Evaluation for CS-389

• 100% programming assignments and projects. Please check your scores and grades for possible clerical errors.
• A scatter plot of CS389 vs CS329 marks are available. Correlation is positive, thank goodness.

Hardware resources

• Prof. Sanyal's corresponding graduate 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.
• 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.
• Why functional programming matters by John Hughes. A classic paper from 1984.
• 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.
• A chapter from a delightful book, The 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: 1, 2.

Software resources

• The Scheme page at MIT.
• MIT Scheme has been downloaded for Linux 2.1 and glibc 2.0. Please do not download it individually.
• Scheme documentation at CSE server.

Lecture calendar

2000-07-24

• Introduction and administrative details
• Abstract models of computation and architectural realities
• Functional programming, the model and lambda calculus

2000-08-01

• Introduction to the lab skills required
• Lambda grammar, free and bound variables
• Outline of the first programming assignment

2000-08-02

• Kernel and desugaring approach to language design
• Core language: lambda calculus plus basic datatypes
• Representing integers, booleans, conditional, pairs, lists

2000-08-04

• Implementing DEC and recursion in lambda calculus
• Structured operational semantics
• Introduction to denotational semantics
• The role of the environment, store, continuations

2000-08-09

• Functionals and fixpoint functions; the rec construct
• FLK syntax and denotation

2000-08-11

• Illustration of FLK interpretation using the environment
• Introduction to FL (let and letrec) and desugaring FL into FLK

2000-08-16

• Modeling mutation and the store using FLK!
• Scoping

2000-08-18

• Using mutable cells to implement recursive naming
• Static and dynamic scoping

2000-08-30

• Parameter passing mechanisms: pass by value and pass by name

2000-09-05

• An experimental language with pass-by-denotation
• Motivation for non-hierarchical scoping

2000-09-06

• Array data type
• Pass by reference, value-result, need
• Return to non-hierarchical scoping using modules

2000-09-08

• Modules, objects, methods, constructors

2000-09-13

• Single and multiple inheritance

2000-09-15

• Last part of object-oriented language design using FL/FLK
• Review of some questions from the previous midterm
• Introduction to tail recursion

2000-09-20, 22

Midterm week, no classes

2000-09-27

• Midterm review
• Tail recursion and continuation-passing style (CPS)
• Stack behavior of CPS programs

2000-09-28

• Guest lecture by RKJ on object-oriented programming

2000-09-29

• Midterm review continued: swap.C, swap.f
• Algorithm for conversion to CPS

2000-10-04

CPS conversion example
• Introduction to standard semantics

2000-10-06

• Standard semantics with store and continuations
• Non-local control transfer
• Introduction to exception handling

2000-10-11

• The callcc construct and its meaning
• Translating callcc to CPS

2000-10-13

• Implementing coroutines using callcc

2000-10-18

• Declarative or logic programming paradigm
• Examples: list member, append, ancestor
• Reversability of input and output
• The Prolog execution model
• Problems with symmetry and cut

2000-10-20

• Substitutions, most general substitution
• The unification algorithm

2000-10-25

• 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

2000-10-27

Diwali, no class

2000-11-01

• Introduction to type reconstruction
• Inference rules for type reconstruction

2000-11-10

• Milner-style type reconstruction algorithms
• Course summary
• Summary of Scheme interpretation and compilation

2000-11-10

Final exam

Assignments to supplement lectures

• Homework 1
• Homework 2
• Homework 3
• Homework 4

Programming assignments

Please coordinate with your friendly CR and TAs to decide on a uniform submission format.

Assignment 1 (Due 2000-08-18)

1. 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 one-line answer.
2. Design the environment data structure with the accessor functions discussed in class for storing name-to-value bindings. Call the functions empty-env, extend-env, and lookup-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)

1. 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.
2. 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)

1. Use the lambda engine to run recursive factorial and list-length functions using various forms of the Y-combinator.
2. 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)

1. 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.
2. 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.
3. Implement FLOP (as in the midterm exam) using the FL/FLK interpreter code you have built so far. You need not implement the store.

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.