Programming language design and analysis

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

Lectures: Wed 18-20h, A 110
Monday lectures at 16h, 8 nov. and 15 nov.
Lab/Project: Mon 18-20h, B528
Office hours: on request

Evaluation:
Homeworks / lab / projects: 50%.
Exam: 50%
Exam (+makeup) grades
Overall grades

Introduction. Functional Programming
Functional Programming. Lambda Calculus
Readings: Lambda Calculus. Introduction (L. Allison) (up to excl. Circular Programs)
Lambda calculus (course notes, Jeff Foster)
Lambda calculus (course notes, Susan Older)
Types
Jeff Foster: Type Systems (lecture slides, 1-17, 37-48, 58-63)
Eager and lazy evaluation. Lazy streams.
Readings: Streams as delayed lists (from Abelson and Sussman)
Continuations and exceptions. Slides part 1 and part 2 (Mark Hills, UIUC).
Continuations: Ch. 16.1-2, 19.1-3 from the PLAI book.
Garbage collection. slides by Vladimir Shmatikov, U. Texas, Ina Schaefer, U. Kaiserslautern
The Java virtual machine slides from Aarhus University
Dynamic compilation slides by Michael Hind (IBM) (w/o details for sec. 3 and 4)
Language support for concurrency. More details: Ted Leung's A Survey of Concurrent Constructs
See also Clojure on agents, data structures and refs; and basic notions of Erlang (with sample code)
Domain-specific languages. See also Martin Fowler's book (archived draft)
Case studies: Advances in Programming Languages, University of Edinburgh (lect. 9-11, selections)
Python slides by Mihai Oaida
Monads: handling side effects in functional programming. slides (Edinburgh course)
See also: Understanding monads, Haskell monads and I/O (sec. 1-4)

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)

Choose a project, individually or in pairs, on a topic of your interest related to programming languages. Suggestions below:

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

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

Last modified: Fri Oct 29 11:55:00 EEST 2010