CS422 - Programming Language Design (Fall 2011)
Students enrolled in this class are expected to check this web page regularly. Complete lecture notes will be posted here.
CS422 is an advanced course on principles of programming language design. Major semantic approaches to programming languages will be discussed, such as structural operational semantics (various kinds), denotational semantics, and rewriting logic semantics. Programming language paradigms will be investigated and rigorously defined, including: imperative, functional, object-oriented, and logic programming languages; parameter binding and evaluation strategies; type checking and type inference; concurrency. Since the definitional framework used in this class will be executable, interpreters for the designed languages will be obtained for free. Software analysis tools reasoning about programs in these languages will also arise naturally. Major theoretical models will be discussed.
- Meetings: W/F 12:30 - 13:45, 1131 Siebel Center
- Credit: 3 or 4 credits
- Professor: Grigore Rosu (Office: SC 2110)
- Office hours: 10:00 - 12:00 on Tuesdays (held by Grigore Rosu in SC 2110); also by appointment any other time
More info on newgroups at UIUC: https://news.cs.illinois.edu/
Lecture Notes, Useful Material
The links below provide you with useful material for this class, including complete lecture notes. These materials will be added by need.
- Introduction slides [Lecture 1]
- Maude slides [Lectures 3,4]
|HW1 (due Wednesday, September 14)|
|The following three exercises from the Maude slides: (1) Ex 4, pg 25; (2) Ex 7, pg 39; (3) Ex 8, pg 40.|
- Conventional Executable Semantics All slides
- References cited in the book sections below PL-book-references.pdf
- IMP language
- Big-step structural operational semantics PL-book-bigstep.pdf
- Small-step structural operational semantics PL-book-smallstep.pdf
- Denotational semantics PL-book-denotational.pdf
- Mathematical background on complete partial orders PL-book-CPO.pdf
- IMP++ language
- Informal description PL-book-IMP++.pdf
|HW2 (due Friday, September 30 - ask for a weekend extension if you really need it)|
|Give formal semanitcs to IMP++ in all styles above. Each individual feature has already been added in the provided imp.zip archive above. Your job is to combine all of these features together into one language. HW2.zip shows the expected format of your HW2. It also includes a series of IMP++ programs that you may use to test your semantics. Everything you do should go under 6-imp++. You should first complete the imp++-syntax.maude file and make sure you can parse all the programs in imp++-programs.maude. Then add directories for each of the semantics. I created the one for small-step SOS for you and also added a file containing my Maude output when I execute all the provided programs.|
- K tool - use the K virtual machine (KVM) if you don't want to install it.
- Defining SIMPLE: An Imperative Language
- Defining KOOL: An Object-Oriented Language
- Defining FUN: A Functional Language
|Define a type inferencer for FUN. Start with the one discussed in class for EXP (found HERE) and keep adding features of FUN to it. As discussed in class, this is an open-ended problem, because you can always make your type inferencer better. Do not atempt to do better than we did in EXP. Do not get stuck with syntax: feel free to change the syntax of FUN to make it more easily parsable, but put a comments in your code explaining what you've done and why. Handle also 5 FUN programs showing that your type inferencer works. Note: some bugs were fixed in the K tool, so you may want to update your KVM.|