CS422 - Programming Language Design (Fall 2010)

From FSL
Jump to: navigation, search

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 - 1: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)


Web Interface to CS422

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 25px-Pdf_icon.png slides Info_circle.png [Lecture 1]
HW1 (due Tuesday, September 14) Downarrow.png
The following four exercises from the Maude slides: (1) Ex 4, pg 25; (2) Ex 6, pg 38; (3) Ex 7, pg 39; (4) Ex 8, pg 40.
HW2 (due Wednesday, October 6) Downarrow.png
The following ten exercises from the book, all done by modifying the Maude definitions of IMP in the archive imp-original.zip above: (1) Ex 32, pg 77 (bigstep); (2) Ex 33, pg 80 (bigstep); (3) Ex 37, pg 96 (small-step); (4) Ex 38, pg 98 (small-step); (5) Ex 50, pg 116 (msos); (6) Ex 51, pg 116 (msos); (7) Ex 77, pg 152 (rsec - do only the third approach, i.e., ignore those in Fig 3.39); (8) Ex 78, pg 152 (rsec - do only the third approach, i.e., ignore those in Fig 3.39); (9) Ex 85, pg 166 (cham); (10) Ex 86, pg 166 (cham). Since the lecture notes on denotational semantics are not ready, we will include the similar two exercises for it in HW3.
HW3 (due Tuesday, October 19) Downarrow.png
Define the IMP++ language in each of the semantic styles using Maude. Complete the corresponding imp++ subdirectory in the imp.zip archive above. The imp.zip archive already contains the definitions of each of IMP++'s features in isolation, that is, the solutions of the Exercises 89, 90, 91, 92, ..., 117 in the lecture notes on IMP++ above. Feel free to use those however you wish. In class, we also discussed adding blocks with local variable declarations to IMP++; ignore those for now, we will rediscuss them later. Also, the denotational semantics will be covered in the next homework; you have enough already in HW3.
HW4 (due Tuesday, November 2) Downarrow.png
Same as HW3, but for denotational semantics and K. Add them in the corresponding imp++ subdirectory in the imp.zip archive above. Note that the archive changed from HW3, so make sure you are not reusing the old one. This time, you are not given the definitions of IMP++'s features in isolation. All you are given is the definition of IMP using denotational semantics and K, in the directory 0-imp-original. Feel free to skip the definition of spawn in denotational semantics. If you want to use the K-Maude tool below for the K part feel free to do it. However, it suffices to just extend the provided Maude definition.
  • Download the K tool from HERE (get the source, through SVN, instead of the ZIP)
  • SIMPLE: An Imperative Programming Language (see the K tool directory, under examples/simple) [Lectures 17, 18]
  • Untyped
  • Dynamically typed
  • Statically typed
HW5 (due Wednesday, November 17) Downarrow.png
Add multidimensional arrays, threads with synchronization, and exceptions to SIMPLE. Do it by modifying the existing definition of SIMPLE that comes with the K tool above (in examples, under simple). For multidimensional arrays, you have to support arrays of arrays, e.g., a[4][5][6], etc. For threads, you should be able to basically cut-and-paste their definition from the CHALLENGE language (thanks to K's modularity). For exceptions, you should support the syntax "try Stmt1 catch(X) Stmt2" and "throw Exp;" with the usual semantics: Stmt1 is evaluated; if it terminates normaly, then discard the try...catch; if Stmt1 throws Exp then evaluate Exp to some value V, bind X to V, then evaluate Stmt2; once the try...catch is executed, continue the execution normally. To define exceptions, you may want to add a new stack cell (i.e., a list), say xstack. For each of the features, devise two or three examples proving that your semantics works.
  • SKOOL: An Object-Oriented Programming Language (see the K tool directory, under examples/skool) [Lectures 19, 20, 21]
  • Untyped
  • Dynamically typed
  • Statically typed
HW6 (due before the final) Downarrow.png

Our current SKOOL language (download its definition from the K-Maude tool svn above) has only public class members (fields and methods). This is not very nice for an OO language. We want to allow programmers to say explicitly which members are public. Therefore, you are suppossed to make all members private by default and allow a special member modifier, say "public", which makes the corresponding field or method public. For example, "public var x:c;" or "public method m() { };". Only modify the skool/typed subdirectory (that is, do not worry about the untyped version of SKOOL but do worry about the typed SKOOL, both dynamic and static). Also, add 2-3 interesting programs to skool-styped-programs.k that work with your definitions. It is in your interest to include tricky ones, because they will be used to test all HWs. There are some options regarding how pivate/public members work. To avoid any misunderstandings, we stick to how they work in Java.

  • FUN: A Functional Programming Language (see the K tool directory, under examples/fun) [Lectures 22, ...]
HW7 (due before the final) Downarrow.png

As discussed in class, this HW asks you to define the type inferencer of FUN from scratch. You can use as example the one for EXP that we discussed in class (see examples/exp in the svn archive). Feel free to dissallow polymorphic reference types. Those are tricky.

  • Sample Finals (from past iterations of CS422)
Personal tools