CS 456: Programming Languages

Meeting Time

Tuesday, Thursday, 12:1:15
CS G066

Instructor

Suresh Jagannathan
Room 216, Computer Science
Ph: x4-0971
email: suresh@cs.purdue.edu
Office Hours: Tuesday, Thursday: 3-4pm

Course Overview

In the relatively short history of computing, there have been hundreds of programming languages invented, and undoubtedly hundreds more will appear during our lifetime. How do we judge the quality, novelty, and expressive power of these myriad languages? What are the criteria that dictate when a new language design or feature is warranted? How do we relate different languages and their features to one another? How do we distinguish between language features that are really different, from those that only appear to be?

These are some of the questions that we will explore in this class. Among the many questions we will not answer are those dealing with programming techniques or methodology, or software engineering. This course will not teach you how to be a better programmer; it does aim however to teach you to be a better programming language designer.   By exposing you to insights and formalisms on language design, you will be able to better rationalize and objectively analyze language features and paradigms.

Some of the topics we will cover include:

  1. The essence of modularity and abstraction, and how languages have attempted to support them.
  2. The significance of naming.
  3. Unifying notions of control and their implementation. Recursive programming techniques.
  4. Semantic formalisms for describing languages.
  5. The role of types. Polymorphism and object-oriented programming. Type inference.
  6. Domain-specific languages. Macros.
  7. Program correctness and safety.
  8. Computational reflection and aspect-oriented programming.

To help us in our investigation, we will will strive to identify foundational components of a language and use these components to build toolkits that will allow us to express new, more complex, language features. Our components will be drawn from a simple core language called the lambda-calculus, and our toolkits will be defined as extensions of the calculus.

By the end of the class, students should be comfortable with objectively assessing and comparing superficially disparate language features, understanding how these features impact implementations, and be able to distinguish concepts that truly are foundational from those that just appear to be. Most importantly, the overarching goal of this course is to equip students to ask better questions about language design, even if the answers themselves are not readily apparent.

Prerequistes

It is assumed that students taking this class would have had exposure to an undergraduate software engineering and/or compilers class, and be comfortable with basic mathematical concepts, and software implementation techniques. Although students need not be fluent in Scheme (the language in which programming assignments are to be completed), they should be confident in their ability to grasp its key features, and gain fluency quickly by self-study.

Academic Honesty

Students are encouraged to work together to clarify issues presented in class. Small programming assignments will be given during the course.  Students are free to work together on these assignments.

Grading

Grading for the class is as follows:


          Scribe      20% 
Project 30%
Midterm 1 25%
Midterm 2 25%

A scribe will be appointed for every topic, which may span two to three classes. The role of the scribe is to summarize and clarify the lectures, and transcribe this summary into a form suitable for posting on the course web-site.   Students will work in small teams on a semester-long programming project.  An oral presentation of the project will be given during the last week of class.

Text

The main text for this class will be Programming Languages: Application and Interpretation by Shriram Krishnamurthi. The .pdf for the text is available here.
 

In addition, students might find the following texts also useful:

Resources

The Scheme programming language is the language in which programming examples in the text are written, and the language used for programmming assignments. Dr. Scheme is an integrated development environment and implementation for Scheme. Students with access to a desktop or laptop machine should download a copy. Dr. Scheme will also be available on the department machines. There are links to many resources from the Dr. Scheme website that you can use to learn more about Scheme.   You may also find the online version of the text How to Design Programs useful; it provides hints on how to use Dr. Scheme. In addition, the Scheme report gives a precise description of the language. An accessible tutorial on Scheme can be found here.
 

Lectures

Lecture 1:   Introduction and overview.
Link to course Twiki lecture notes.

Project

The semester-long project is based last year's ICFP programming contest. Your task is to design a language to program ants, define a specification that describes the language, and implement both a simulator (i.e., interpreter) and a "compiler" for the language. We will hold a competition at the end of the semester that pits different teams together.

Some code samples that illustrate how to use Dr. Scheme's pattern-matching and structure macros, in addition to providing examples on higher-order programming, can be found here.

Project Deadlines

September 27, 2005: finish implementation of the simulator
October 6, 2005: language design (informal)
October 27, 2005: language design (formal specification)
November 17, 2005: implementation