Formal Systems Laboratory

CS422 - Programming Language Design (Fall 2025)

Students enrolled in this class are expected to check this web page regularly. Complete lecture notes will be posted here, following the same model as in CS422 in Fall 2024.

We may sometimes meet online on zoom, eg when traveling to professional events: https://illinois.zoom.us/j/2172447431?pwd=dEtxWmdJR0FYOElUa1ZLL2RJRzdZUT09

Lecture Recordings

When we meet online, we will record the lectures and post the links here:

[Aug 28]

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-based 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.

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.

HW1 (due date: Thursday, Sept 11th, AoE)

Exercise 1 (10 points): Modify IMP (its Big-Step and its Small-Step SOS) to halt when a division-by-zero takes place, returning a configuration holding the state in which the division by zero took place.

Exercise 2 (10 points): Add a variable increment construct, ++x (increment x and return the incremented value), to IMP: first add it to the formal BNF syntax, then to the Big-Step SOS, then to the type-system, and then to the Small-Step SOS.

Exercise 3 (10 points): Add I/O constructs, read() and print(AExp) to IMP: first add these to the formal BNF syntax (read() is an AExp construct and print(AExp) is a Stmt construct), then to the Big-Step SOS, then to the type-system, and then to the Small-Step SOS.

Exercise 4 (10 points): Combine the three above: add division-by-zero halting, an increment construct, and the two I/O constructs to IMP. Feel free to comment on what’s going on, particularly on how inconvenient it is to do certain things in SOS (one of the points of this HW is to understand the limitations of SOS, so you will appreciate K).

HW2 (due date: Thursday, Oct 2nd, AoE)

Pick and do one exercise in each K Tutorial Lesson that we covered in class. Create a github repo, possibly as a clone of the K tutorial, and add the exercises there in the appropriate folders using any naming convention you prefer. When done, give me access to view your repo and send me an email to confirm that I have access. My github ID is grosu.

HW3 (due date: Tuesday, October 14, AoE)

Exercise 1 (10 points): The current K LAMBDA semantics of mu (in Lesson 8) is based on substitution, and then letrec is defined as a derived operation using mu. Give mu a different semantics, as a derived construct by translation into other LAMBDA constructs, like we defined letrec in Lesson 7. To test it, use the same definition of letrec in terms of mu (from Lesson 8) and write 3 recursive programs, like the provided factorial-letrec.lambda.

Note: See the mu-derived exercise in the nightly built for details and test programs.

Exercise 2 (10 points): Modify the K definition of IMP to not automatically initialize variables to 0. Instead, declared variables should stay uninitialized until assigned a value, and the execution should get stuck when an uninitialized variable is looked up.

Note: See the uninitialized-variables exercise in the nightly built for details and test programs.

Exercise 3 (10 points): Mofify IMP so that the K “followed by” arrow, ~>, does not explicitly occur in the definition (it currently occurs in the semantics of sequential composition). Hint: make sequential composition strict(1) or seqstrict, and have statements reduce to {} instead of ., … and don’t forget to make {} a KResult (you may need a new syntactic category for that, which only includes {} and is included in KResult).

Note: See the purely-syntactic exercise in the nightly built for details and test programs.

Exercise 4 (10 points): Define a variant of callcc, say callCC, which never returns to the current continuation unless a value is specifically passed to that continuation. Can you define them in terms of each other? Pick one of the substitution versus the environment-based definitions (get extra-credit if you do both).

Note: See the callCC (substitution), from-call-CC-to-callcc (substitution), from-callcc-to-call-CC(substitution), callCC (environment), from-call-CC-to-callcc (environment), and from-callcc-to-call-CC (environment) exercises in the nightly built for details and test programs.

Exercise 5 (10 points): The current halt; statement of IMP++ only halts the current thread. Define an abort; statement which halts the entire program.