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.
Course Description
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
Newsgroup
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]
- Introduction
- Maude
slides
[Lectures 3,4]
- Maude
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
- Informal description
PL-book-IMP.pdf
- Formal semantics (in all styles below, using Maude)
imp.zip
- Informal description
- 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
- Mathematical background on complete partial orders
- IMP++ language
- Informal description
PL-book-IMP++.pdf
- Informal description
- Conventional Executable Semantics
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. ![]() ![]() |
- MSOS
PL-book-msos.pdf
- Evaluation contexts
PL-book-rsec.pdf
- CHAM
PL-book-cham.pdf
- MSOS
- K Framework
slides (PDF)
slides (PPTX)
- K tool - use the K virtual machine (KVM) if you don't want to install it.
- K Framework
- Defining SIMPLE: An Imperative Language
- Untyped SIMPLE
- Typed SIMPLE
- Staticaly typed SIMPLE
- Dynamically typed SIMPLE
- Defining KOOL: An Object-Oriented Language
- Untyped KOOL
- ASCII K definition
-
Generated PDF poster
(incomplete)
- Typed KOOL
- Statically typed KOOL
- ASCII K Definition
-
Generated PDF poster
(incomplete)
- Dynamically typed KOOL
- ASCII K Definition
-
Generated PDF poster
(incomplete)
- Defining FUN: A Functional Language
-
- ASCII K definition
-
Generated PDF poster
(incomplete)
HW7 ![]() |
---|
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. |