Advanced Compilers

The ideal programming language would provide the syntactic conveniences and support the programming paradigms that are most useful for any particular application. It would be equally useful for five-line and five-million-line programs. On the other hand, it would have a clear and simple semantics and lack any unnecessary or redundant features.

Clearly, these goals are at odds---or are they? Most general-purpose languages are constructed in two layers: a core language that provides a fixed set of syntactic forms and operators and an extended language that provides an additional set of library functions and the means to extend this set. This helps, but the programmer is still stuck with a predefined set of syntactic forms and no way to extend this set. What is needed is an analogous factoring of the language into a core language with a few simple syntactic forms and an extended language that provides an additional set of library syntactic forms and the means to extend this set. Of the major languages in use today, only the Lisp family of languages are designed in this manner, which makes them the only candidates for ideality.

In this course, we will study the origins of syntactic abstraction, from primitive macro assemblers to early Lisp macros. We will study how Lisp macro systems have evolved and investigate the current state-of-the-art as it is reflected in Scheme's syntax-rules and syntax-case macro systems. We will discuss how a good syntactic abstraction mechanism can help simplify a language and make its semantics more accessible, and we will discuss the role of syntactic abstraction in making a language more suitable for domain-specific programming. We will learn how macro systems are implemented and the role they play in the compiler---as well as the crucial role the compiler plays in syntactic abstraction.

The prerequisite for this course is a course in compilers, such as p423 or p523, or permission of the instructor. Familiarity with Scheme, while not essential, is useful, and students not already familiar with Scheme might want to learn a bit of Scheme on their own (e.g., from the first few chapters of The Scheme Programming Language) before the semester starts. Some projects may require work in pairs or larger groups. Individuals enrolled in the graduate version of the course may be asked to implement additional or more complex versions of certain assignments.