Programming language design and analysis

Fall semester 2012/2013. previous: Fall 2011
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: Lambda calculus (course notes, Jeff Foster)
   Principles of Programming Languages, Uday Reddy, U. Birmingham (handouts 1-4)
3. Type systems.
   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)
4. Typed lambda calculus and type inference. lecture slides by Jeff Foster, U. of Maryland (slides 1-17, 37-48, 58-63)
5. Eager and lazy evaluation. sieve of Eratosthenes. See also streams as delayed lists (from Abelson and Sussman)
   Continuations. slides, TU Darmstadt (w/o simulation of web programs, implementation of continuations) ML example for factorial
6. Garbage collection. slides by Vladimir Shmatikov, U. Texas, Ina Schaefer, U. Kaiserslautern
7. The Java virtual machine slides from Aarhus University
8. Dynamic compilation slides by Michael Hind (IBM) (w/o details for sec. 3 and 4)
9. Constraint logic programming. introduction, relation with logic (R. Voicu); or
   slides by Thom Frühwirth (see comparison between search/solving in LP and CLP, p. 107-123, 129-135)
   short survey (Gavanelli & Rossi, sec. 1-2.1)
10. Language support for concurrency. More details: Ted Leung's A Survey of Concurrent Constructs
    See also: Concurrency in other languages (D. Aspinall, Edinburgh) and concept of persistent data structures in Clojure (J. Hickey)
    optional reading on STM
11. Java Concurrency. v. J. Manson, W. Pugh, S. Adve, The Java Memory Model (sec. 1-4)
12. Domain-specific languages. See also Martin Fowler's book (archived draft) (patterns for building internal DSLs)
13. The Design of Scala. overview, tutorial (classes, traits, type system)
    optional reading: a presentation comparing with Java design patterns

Homeworks

1. Homework 1. Functional program interpreter. Due Oct. 15, 2012. Extension: implement recursive functions (Oct. 22, 2012)
2. Homework 2. Lambda calculus interpreter. Due Nov 6, 2012
3. Homework 3. Type inference. Due Nov 27, 2012
4. Homework 4. Prolog interpreter. Due Dec 11, 2012

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)

Online Courses

Software

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