CS422 - Programming Language Design (Fall 2006)

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 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_2006%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.

  • 1 HW1 exercise (see page 47), due Thursday, Sept 14
  • 25px-Pdf_icon.png SOS rules for halt Info_circle.png (updated on September 27, 2006; may be useful for HW2)
  • 2 HW1 exercises (see pages 24 and 55), due Thursday, Sept 14
  • 25px-Zip_icon.png Maude modules Info_circle.png mentioned in the lecture notes
  • 1 HW2 exercise (see last page), due Thursday, Sept 28, midnight (email); this HW has only one exercise, but there are 8 subproblems to implement
  • 25px-Zip_icon.png Maude modules Info_circle.png mentioned in the lecture notes
  • 25px-Pdf_icon.png HW 4 Info_circle.png (posted on November 2, 2006; due November 16)
  • 25px-Pdf_icon.png HW 5 Info_circle.png (posted on November 30, 2006; due December 8)

Unit Project

The unit project for this semester (unless you have chosen a project independently and had it approved) will be to define a significant subset of the Scheme programming language. More details will appear here shortly. You will need to define Scheme in K, with a translation of this definition into Maude so that it can be executed. A parser will be provided for the latter portion, so you will not need to worry about syntax issues.

The best way to get started is to (re)familiarize yourself with Scheme. If you do not have it installed anywhere, you should download it. If you do not have a machine where you can do this installation, let me know -- it does not appear to be installed on the CSIL or EWS machines. Good versions of Scheme are available at:

You can also look at several good books online, including:

I would especially recommend the first, since it is focused just on learning the language, but the second has a number of good examples. If you have Essentials of Programming Languages (used in CS421 last Spring), that has a number of good examples too.

Again, the scope of the project is being finalized, but assume you will need to implement basic functionality (assignment, function declaration/function calls, support for numbers and strings, etc) as well as more involved features of the language, such as call/cc.

UPDATE 11/27/2006: The scope of the project definition is available in this 25px-Pdf_icon.png PDF Info_circle.png file. This contains information on the parts of Scheme that you are expected to implement. There may be additional clarifications; please watch the newsgroup and this page. Contact Grigore Rosu and/or Mark Hills with any questions.

UPDATE 12/1/2006: Here is a parser for the subset of Scheme we are using. You will need OCaml to build and run the parser. Please let me know if for some reason you do not have access to this. Once you have installed and built the parser, if you run the scheme command you will get a top-level environment where, when you enter in Scheme expressions, Maude-formatted terms will be returned. These terms can be pasted in to Maude or other files. I'm working on making this easier to use, but this should get you going for now. Also included is a Maude file with the syntax of Scheme that you can use to start building the semantics. Please let me (Mark Hills) know if you find any problems with this. 25px-Zip_icon.png Scheme Parser Info_circle.png

Personal tools