CS422 - Programming Language Design (Fall 2007)
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 language design paradigms will be investigated and rigorously defined, including: static versus dynamic binding, call-by-value, by reference, by name, and by need, type checking and type inference, objects and classes, concurrency. Since the definitional (or specification) 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: Tu/Th 3:30 - 4:45, 1302 Siebel Center
- Credit: 3 or 4 credits
- Professor: Grigore Rosu (Office: SC 2110)
- Office hours: 10:00 - 12:00 on Mondays (held by Grigore Rosu in SC 2110)
- Web site: http://fsl.cs.uiuc.edu/index.php/CS422_-_Programming_Language_Design_%28Fall_2007%29
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 (updated on August 23, 2007; complete) [L1]
- Operational Semantics (updated on September 6, 2007; complete) [L1,L2,L3,L4]. We covered:
- Small-step SOS
- Big-step SOS
- Modular SOS
- Reduction semantics with evaluation contexts
- Homework 1 (40 points), due Sept 11, midnight: the three HW exercises in the lecture notes on operational semantics above. First exercise is on pages 63-65 and is worth 20 points. Second exercise is on page 90 and is worth 10 points. Third exercise is on page 116 and is worth 10 points.
- Maude (updated on September 6, 2007; complete) [L5,L6]
- CHAM and K (updated on September 13, 2007; incomplete) [L7,L8]
- k2maude.zip - K definitions in Maude (updated on September 18, 2007; incomplete) [L8]
- Homework 2 (40 points), due Sept 25, midnight: the two HW exercises in the lecture notes on Maude above, plus defining increment and halt in CHAM and K. The first two exercises are worth 15 points each; the remaining two are worth 5 points each.
- K for the Maude User (updated on September 25, 2007; incomplete) [L10]
- Defining SILF: a Simple Imperative Language with Functions (updated on October 03, 2007; complete) [L9,L11,L12]. We defined:
- A concrete K semantics
- A dynamically checked type system
- A statically checked type system
- Homework 3 (40 points), due Thursday, October 11, midnight: There are three K definitions to complete, one for the untyped SILF (15 points), one for the dynamically typed SILF (15 points) and one for the statically typed SILF (10 points). See the README.txt file in the archive below:
- Elements of Functional Programming (updated on October 04, 2007; incomplete) [L13].
- Defining Untyped FUN: a Simple Untyped Functional Language (updated on October 16, 2007; complete) [L14,L15].
- Homework 4 (40 points), due Tuesday, October 23, midnight: Complete the K definition of FUN (30 points) and then add 4 more examples (10 points). You only need to modify the file xyz-semantics.maude in the archive below for the first part, and also file xyz-programs.maude for the second:
- Notes on Types (updated on October 16, 2007; VERY incomplete - but not needed for HW5) [L16].
- Defining Polymorphic FUN with Type Declarations (updated on November 6, 2007; complete) [L16,L17].
- Defining Polymorphic Type Inference (Milner's W procedure) (updated on November 3, 2007; complete) [L20,L21].
- Homework 5 (40 points), due Monday, November 12, midnight
- Elements of Object-Oriented Programming (updated on November 06, 2007; incomplete) [L22].
- Defining Untyped SKOOL: a Simple Untyped Object-Oriented Language (updated on November 12, 2007; complete) [L23].
- Denotational Semantics (updated on November 28, 2007; complete) [L24].
- Homework 6 (40 points), due Wednesday, December 5, midnight
- A Language Design Challenge: The UGLY Language (updated on November 27, 2007; incomplete) [L25].
- Sample Finals (from past iterations of CS422)
Information on the unit project will be available soon.