Programming language design and analysis

Fall semester 2011/2012. Old course page
Instructor: Marius Minea
marius@cs.upt.ro

Course information

Lectures: Thu 18-20h, A 204
Lab: Tue 8-10h, B528
Office hours: on request

Evaluation:
Homeworks / lab / projects: 50%.
Exam: 50%
Grades

Lecture notes

1. Introduction. Functional Programming
2. Lambda Calculus
   Readings: Principles of Programming Languages, Uday Reddy, U. Birmingham
   Lambda Calculus. Introduction (L. Allison) (up to excl. Circular Programs)
   Lambda calculus (course notes, Jeff Foster)
3. Typed lambda calculus and type inference. lecture slides by Jeff Foster, U. of Maryland (slides 1-17, 37-48, 58-63)
4. Type systems. slides.
   Readings: Luca Cardelli: Type Systems (p.1-7)
   L. Cardelli, P. Wegner. On Understanding Types, Data Abstraction, and Polymorphism (sec. 1-1.5, 2.1-2.2)
   Eager and lazy evaluation. Streams as delayed lists (from Abelson and Sussman)
5. Continuations. slides, TU Darmstadt
6. Garbage collection. slides by Vladimir Shmatikov, U. Texas, Ina Schaefer, U. Kaiserslautern
7. Constraint Logic Programming. slides by Thom Frühwirth (see comparison between search/solving in LP and CLP)
   slides on ECLiPSE (H. Simonis) -- Ch. 4 and 5
8. The Java virtual machine slides from Aarhus University
9. Dynamic compilation slides by Michael Hind (IBM) (w/o details for sec. 3 and 4)
10. Language support for concurrency. More details: Ted Leung's A Survey of Concurrent Constructs
    See also a discussion of persistent data structures

Homeworks

1. Homework 1. Functional program interpreter. Due Oct. 18, 2011
2. Homework 2. Lambda calculus interpreter. Due Nov. 1, 2011
3. Homework 3. Type inference. Due Nov. 15, 2011
4. Homework 4. Prolog interpreter. Due Nov. 29, 2011
5. Homework 5. Bytecode checker. Due Dec. 22, 2011

Resources

Books

• Abelson and Sussman, Structure and Interpretation of Computer Programs. The classic MIT introductory programming course at MIT, now online.
  You should be able to use it as reference for the notions in the first three chapters
• Friedmann, Wand and Haynes, Essentials of Programming Languages.
  Perhaps more heavily interpreter-oriented, but also very well explained. Available in the free ebook library
• van Roy and Haridi, Concepts, Techniques and Models of Computer Programming.
  Well structured and very readable. An essentially complete draft is available.
• S. Krishnamurthi, Programming Languages: Application and Interpretation. Made available for free by the author.
  Also very well structured and readable, with a few special topics (see e.g. continuations for web programming)

Software

• the OCaml implementation and documentation
• the OCaIDE development environment (Eclipse plugin)
• a short introductio to OCaml (Scott Smith, Johns Hopkins U.)

Supplementary reading

• E. Meijer, P. Drayton. Static Typing Where Possible, Dynamic Typing When Needed

Project topics

Program analysis tools and infrastructures

• CIL, a program analysis and transformation infrastructure for C programs, written in ML. Easy to use (see example analyses provided), and you can do a lot with a few lines of ML code.
• LLVM. A compiler infrastructure for C/C++ written in C++. Mature, with lots of analysis modules, allows you to define your own compilation/analysis pass. Check out the list of LLVM projects and open projects.
• Soot, a Java optimization framework with several levels of representations for analyzing and transforming Java bytecode
• WALA, a library for analyzing Java programs developed at IBM.
• Other Java bytecode libraries: ASM, BCEL, Javassist
• Phoenix, a Microsoft compiler and analysis framework for .NET

Sample project ideas

• Analyze a program to derive and visualize useful information (call graph, use-def information, etc.)
• Instrument a program for use in testing/debugging. For example, determine dataflow coverage; the actual object type/method called in virtual method calls (also usable as a coverage measure); log the interactions between objects/components. Analyze/interpret/visualize the results
• Implement a (dynamic) memory leak detector for Java or evaluate and compare existing ones.
• Implement a dataflow analysis to verify a desired property of your program
• Implement and automate a refactoring
• Benchmark/compare/evaluate a set of bug detection/program verification tools of your choice