[lambdaheads]Missive

[Programming][Languages]

Prior courses may have taught you how to program. This course, in contrast, teaches you how to analyze programming languages. What are the questions one asks when confronting a new language? What intellectual tools do we have for comprehending and analyzing a language? When and how should we design new languages? And how can we go about implementing them?

There are two important reasons to study this material no matter where your interests lie. First, we seem to best learn design by studying design. Programming languages represent some of the most carefully designed artifacts in computer science (much more than most programs, certainly). By learning about and recreating their designs, you should grow as a designer. Secondly, computer science is essentially an economic discipline. Studying languages underscores this by presenting many fundamental trade-offs. As students of languages, we can study not only the trade-offs, but also the decisions past designers made and the effects that their choices had.

The topics in this course will be taken from:

  • Dynamic Semantics:
    • simple call-by-value language
    • closures
    • lexical binding
    • recursion
    • data constructors
    • mutation
    • advanced control
  • Types and Safety: all the above topics in the context of
    • typing judgements
    • safety
    • type soundness
    • explicit and implicit polymorphism
  • Program Organization: either classes and objects or modules
  • Compilation:
    • tail recursion
    • CPS
    • representation independence
    • register machines
    • allocation versus mutation
    • optimizers: adequacy and observational equivalence
  • Run-Time Systems
  • Theoretical Topics (if time permits):
    • operational semantics
    • lambda calculi
    • strong normalization
    • adequacy
This list will become more specific as we progress through the semester.

Coda: This field of study is one of the most venerable in all computer science; indeed, numerous early pioneers worked partially or exclusively in it, including several Turing Award winners: Alan Perlis (1966), John McCarthy (1971), Edsger Dijkstra (1972), Dana Scott (1976), John Backus (1977), Robert Floyd (1978), Ken Iverson (1979), Tony Hoare (1980), Niklaus Wirth (1984), Robin Milner (1991), Butler Lampson (1992), and others. We will touch on some of the contributions of these luminaries in this course.