CS252r:   History of Programming Languages
1 When and Where
2 What
3 How
4 Topics
5 Other topics

CS252r: History of Programming Languages

Christos Dimoulas

1 When and Where

We meet every Monday and Wednesday (except university holidays) from 11:30 to 13:00 at Maxwell-Dworkin 323. Topics provides more details for each meeting.

2 What

This course is definetely not about this. This seminar is about ideas that occupied for some time the minds of programming languages researchers and morphed into mature and recognizable research trends within the field.

Previous incarnations of CS252r were taught by Steve Chong: Fall 2015, Fall 2014, Fall 2013, Spring 2012, Spring 2011, Fall 2009.

Some ideas proved so successful that we forgot their origins and nowadays, they seem as obvious as if they were engraved in our brains with a beam from an alien mothership at the beginning of time. Did, for instance, the connection between the λ-calculus and formal programming language semantics emerge out of nothing? Or did type soundness always mean progress and preservation?

Some other ideas had their moments under the spotlight and then seemingly vanished. Years later, other ideas appear that look completely new but at closer inspection carry traits of these forgotten ideas. Some times the connection is tight enough that it seems as if an old idea reincarnated into a new one, even under the same name. Are, for example, the refinement types of today’s Haskell unrelated to the refinement types of ML from the 90s?

Of course, many ideas do vanish for good (or better they haven’t resurfaced yet). But even the “failed” ideas teach us at least how to prune the research space and how to avoid repeating the mistakes of the past. And who knows, looking at failed ideas may reveal an “old” solution applies a “new” problem. Who could have guessed that delimited continuations would find an application in the architecture of web browsers?

Independently of their fate, the ideas we will look into during our meetings demonstrate how programmers tried to organize their thoughts into programs, what linguistic means they created to streamline this process and what techniques they came up with to reason about programs.

3 How

During each meeting, we will look into one mature topic in programming languages research. Mature topics describe a completed route from precise research questions to an answer rather than still active and evolving research efforts.

For half of the meetings, I have selected and will present topics that cover the history and development of a few important questions in programming languages research. Topics shows the dates, titles and other details of these meetings.

For the rest of the meetings, each participant will pick 3 to 5 papers that form the spine of a mature topic and give a white-board presentation of these papers. Depending on the number of participants in the course, each participant will present once or twice during the semester. Other topics includes a list of possible topics that participants could pick.

Outside the presentations, participants will compile an annotated bibliography for the papers they selected for their topics. The bibliography should consist of a bibtex style entry together with an alternative title, a short summary and, an evaluation/significance paragraph for each paper.

Finally, the participants that do not present in a given meeting are not expected to have read the presented papers in advance. They are expected, though, to fill this anynymous evaluation form and turn it in by the next meeting. The form will provide presentation feedback to each meeting’s presenter.

I will be available to help participants select topics and relevant papers, structure their presentations and, prepare the annotated bibliography. I will also read through the evaluation forms, discuss them and provide additional feedback. In particular, presenters are expected to arrange at least three meetings with me per presentation: one at least two weeks before the presentation to select topic and papers, one at least one week before the presentation to discuss the structure of the presentation and, one at most one week after the presentation to evaluate the presentation and the annotated bibliography. Please, communicate with me via email to arrange the meetings.

The structure of the seminar aims to:

Formally, the last four points together with discussion participation during the meentings are the indices that will determine the grade of the students that register for the course. In reality, though, this is a seminar course and you get out of it what you invest in it.

4 Topics





From LISP and ALGOL 60 to interpreters and abstract machines



From interpreters and abstact machines to the λ insight



The λ insight formally and the science of syntax



Putting syntax to work, for real



From mathematical functions to programs

Guest lecture: Dan Huang


From mathematical functions to syntax

Guest lecture: Dan Huang


The power of syntax: type soundness



From monads to programming with monads



Representation independence



The birth of Prolog



Typeful programming



History of actors

Guest lecture: Tony Garnok-Jones


The chemical abstract machines (CHAM): Solutions to model concurrency



Early web scripting



Barendregt’s cube and programming with dependent types



Origins of garbage collection



A history of Haskell

Guest lecture: Pablo Buiras


Parametricity and relational reasoning



Recursion, state and relational reasoning



Applicative bisimulations and the λ-calculus



Applicative bisimulations for higher-order state



Equivalence in calculi for concurrency





5 Other topics

The following is a list of topics that participants in the seminar can choose to present. Of course, this is not an exclusive list. Participants can propose other topics too as long as a proposed topic covers a cohesive theme of mature ideas in programming languages research.