CMSC 22100/32100: Programming Languages

Course Description

Programming languages are the most fundamental tools involved in the creation of software. In a sense, they constitute the raw material out of which software is constructed. This is a foundational course exploring the principles and concepts underlying the design of programming languages. We follow a formal approach based on operational semantics to give clear and precise descriptions of language concepts, such as flow of control, data structures and types, modularity and abstraction. Our goal will be to start with the simplest core concepts and achieve a deep and thorough understanding as we explore additional features. This approach is in contrast to many conventional programming language courses and text books, which present a relatively superficial survey of the notable features of several "representative" languages (the botanical approach).

The major paradigms of functional, imperative, and object-oriented programming will be covered, starting with the functional paradigm because of its simplicity. Programming examples and exercises using Standard ML will help make the formal concepts more concrete.

Students should have experience programming in one or more programming languages, but exposure to a functional programming language like Scheme, ML, or Haskell will be particularly relevant. Familiarity with basic concepts of naive set theory and logic would be helpful. Inductive definitions and inductive proofs will play a central role.

The course is being taught as a combinded graduate/undergraduate course. There will be additional reading and assignments for the graduate students that extend the core material.

Course Text

The primary text for the course consists of the provided Lecture Notes. These notes will be revised and extended as the course proceeds.

Other references that are useful for background material or further study are:

• Practical Foundations for Programming Languages by Robert Harper.
• Transitions and Trees: An Introduction to Operational Semantics, by Hans Hüttel, Cambridge Univ. Press, 2010, ISBN 978-0-521-14709-5.
• Types and Programming Languages, by Benjamin Pierce, MIT Press, 2002, ISBN 0-262-16209-1. A thorough and readable reference emphasizing type systems.
• Discrete Structures, Logic, and Computability by James Hein. This text covers relevant topics in set theory, logic, and discrete math and has been used as a textbook in CMSC 15300, Foundations of Software.
• Naive Set Theory by Paul Halmos, Springer, 2001, ISBN 3540900926. A republished edition of a classic introductory text on basic set theory. Also available in a Kindle edition on Amazon.com, and as a PDF file from the University Library web site (via the Hathi Trust Digital Library — search in lens.lib.uchicago.edu).

Programming Exercises

This course is not centered on programming projects, but the operational semantics techniques used to formalize programming language concepts are easily translated to programs that implement the concepts. We will use the language Standard ML for such programming experiments. There are several good sources of documentation and tutorials for SML/NJ available online, and some of these are given in the course SML/NJ page.

Course Policies

• Grading will be based on the following:
• Homework exercises: 60%
• Midterm exam: 15%
• Final exam: 25%
• Assigments: Homework assignments will normally be given on Tuesdays and will be due at the beginning of the same day the following week, unless otherwise specified. The policy on late homework is that each student can have a one-time 24 hour extension of the due date, to be used at their discretion. Extensions for cause (illness, religious holiday, family emergency) will be granted on a case-by-case basis, in response to a request in advance of the due date.
• Late Homework Policy: The policy will be that each student can have a one-time 24 hour extension of the due date, to be used at their discression. Extensions for cause (illness, religious holiday, family emergency) will be granted on a case-by-case basis, in response to a request in advance of the due date.

  This supercedes the original stated policy that late homework can be handed in the class following the due date with a 30% penalty. But for the first assignment, you have a choice of following either policy.

• Collaboration: As in most courses, we encourage students to discuss course material among themselves. Discussions of assignment problems is also permitted to an extent, but submitted assignments should be your own work, and any collaborative inputs should be acknowledged.
• Final Examination: The final examination will be a two hour in-class exam given during Finals week.