CS 331, Programming Languages
Autumn, 2008 - 2009
Purandar Bhaduri, ext: 2360, email: pbhaduri.
SHOBHIT AGARWAL (email: shobhit)
KAPIL KUMAR CHITTORA (email: k.chittora)
C. SURENDRANATH CHOWDARY (email: c.chowdary)
PRAVEEN MOPARTHY (email: p.moparthy)
Useful additional material
1. Semantics of Programming Languages. Lecture Notes by Nick Benton.
2. Formal Semantics of Programming Languages, Lecture Slides by Zhendong Su.
3. Programming in Standard ML, online book by Robert Harper.
4. On understanding types, data abstraction, and polymorphism, Luca Cardelli and Peter Wegner, Computing Surveys, Vol. 17, No. 4, December 1985.
1. Glynn Winskel, The Formal Semantics of Programming Languages: An Introduction, MIT Pres, 1993.
1. Week of 25 August 2008:
a. Download and install ESC/Java as an Eclipse plugin from http://jmleclipse.projects.cis.ksu.edu/docs/esc-java.shtml. Alternatively, if you face problems with the site, try the instructions at http://www.cs.virginia.edu/cs201j/plugin/ .
b. Alternatively, you may download other versions of the tool. See details at http://kind.ucd.ie/products/opensource/ESCJava2/.
c. Go through the documentation and run ESC/Java on small examples.
2. Lab Exercise 1: Due 10 October, Friday
Write simple Java programs for the following examples presented in the class and use ESC/Java to analyse the partial correctness of your programs. Submit your work and give a demo to the TA assigned to you.
a. The greatest common divisor of two positive integers.
b. The quotient and remainder of two positive integers.
3. Lab Exercise 2: Due 24 October, Friday
Download and install SML/NJ. You will have to implement a data type in ML for representing arbitrary trees, where a node can have an arbitrary number of children and an integer valued field. Then implement the following algorithms in ML. The output should print out the values of the nodes in the traversal. Submit source code and sample runs to the appropriate TA.
a. Algorithms for depth-first and breadth-first traversal of an input tree.
b. An algorithm for preorder traversal of an input tree.
4. Lab Exercise 3: Due 14 November, Friday
Download and install SWI-Prolog if it is not already there on your machine. You will have to implement the Floyd-Warshall algorithm for the all pairs shortest path problem (see Section 25.2 on pages 629 onwards in Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein). Assume that the input graph is represented using the predicate edge(X,Y,N), meaning there is an edge from node X to node Y whose cost is N. Submit source code and sample runs to the appropriate TA.