Principles of Programming Languages

Compiled by Matthias Felleisen

Short Description: Comp 1358 is an introduction to the principles of programming languages. It introduces students to the art of specifying programming languages with interpreters and to the analysis of basic language properties.
Course Material:
  • General Information
  • Syllabus
  • Readings
  • Assignments
  • The Newsgroup --- Read on a daily basis!
  • DrScheme, MzScheme, and documentation
    • Long Description: Comp 1358 consists of three parts:
  • The first part introduces means for discussing the syntax and the semantics of programming languages. The former is introduced via simplistic parsing (translations) of phrases into abstract syntax. Topics like lexical analysis and advanced parsing methods are left to the compiler course . The semantics of a number of traditional and not-so-traditional programming language constructs is specified via interpreters and reduction systems. The constructs include arithmetical and conditional expressions, blocks, lexically-scoped first-class functions, compound data, and control constructs (loop exits, first-class continuations, simple threads).

  • The second part illustrates how interpreters can be used to understand what kind of services a programming language offers. Two examples are covered: type safety and memory safety. Type safety guarantees that programs respect syntactically defined type abstraction boundaries and never raise certain classes of error signals. Memory safety guarantees that programs never accidentally access certain parts of memory and that they release memory if it is provably useless for the rest of the evaluation.

  • The third part shows how interpreters can systematically be transformed so that they use fewer and fewer language facilties. The key transformations are transformation of closures into records and the continuation-passing (and/or A-normal form) transformation. Using these transformations, a recursive interpreter can quickly be be re-written in a low-level language like C/C++. The transformation not only applies to interpreters but to all recursive programs. Implementing the transformations yields a compiler, but again, this topic is also left to the compiler course.
    • The course enables students to ask relevant technical questions about the semantics and pragmatics of the old and new programming languages that they are likely to encounter in the workplace (e.g., C++, Java, XML). They will also be able to build simple interpreters for new languages or embeed little "special-purpose" languages into languages with decent macro tools.

    The description is based on a semester-long course. The quarter-version will cover less. Cuts to be determined based on student experience and interest.