C311 -- Programming Languages -- Spring 1995

Instructor: Christopher Haynes
Associate Instructor: Vikram Subramaniam
Prerequisites: C335, C343 (may be concurrent), and Scheme programming experience
Credit hours: 4
Lecture: Section 2000, MWF 9:05-9:55, in BH142
Discussion: Section 2001, T 2:30-3:20, in BH011; Section 2002, R 1:25-2:15, in BU429
Local newsgroup: ac.c.311

Overview

This course provides an introduction to the foundations of programming languages, allowing a thorough understanding of programming language semantics and critical implementation characteristics. This provides the basis for the best choice and use of existing languages, as well as language design. Interpreters and other language-processing programs are used throughout to present the essential elements of programming languages in a precise, analytic, manner. These programs will be written in Scheme++, an extension of the Scheme programming languages that supports the object-oriented programming in a style similar to C++, but more dynamic. This provides hands-on experience with the elements of programming language semantics. The extensive use of interpreters in this course also develops skill in meta-linguistic abstraction -- a powerful programming paradigm.

Topics include

Induction, Recursion, and Scope
Object-oriented programming
Direct semantics interpreters
Object-oriented semantics
Continuation-passing style
Continuation-semantics interpreter
Imperative form and stack architecture

Text

Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes, Essentials of Programming Languages, MIT Press and McGraw Hill, 1992. This text is frequently referred to as EOPL.

Syllabus

Chapters 1 through 4 of EOPL introduce preliminary programming language concepts and the basic elements of Scheme. They will be covered quickly. The material on Scheme should be reviewed as necessary. Most of the material in chapters 5 through 10 will be covered in detail. Time permitting, type systems will also be covered using a chapter in preparation for a second edition of the text, which will be made available at a copy center.

Communication

The course newsgroup, ac.c.311, will be used to post announcements, such as assignments, exams, and any exceptions to my usual office hours. You are also encouraged to use it to post questions related to the course or share information with the class. Make a habit of looking for new notes every day or two.

Undergraduates are also expected to read the newsgroup cs.students at least every week or so. It contains departmental announcements that may be important to you.

This course description is accessible as an HTML file on the World Wide Web with the URL http://www.cs.indiana.edu/classes/c311/home.html. It will be updated with additional information as the course progresses. To view a resource given its URL, use the Mosaic program on a networked PC, Mac, or Sun. Mosaic underlines HTML hypertext links. To follow a link, click on it. For example, you can access the newsgroup ac.c.311 by clicking on its underlined reference. Serial-line access to the Web is also possible, using the unix command lynx. The IU Computer Science Department's home page is a good place to start browsing for more information on the department, IU, the Web, or the World!

Interpreters

The core of this course is a large number of interpreterss for mini-languages expressing a variety of programming language semantics. The EOPL text presents these interpreters in Scheme, using a record-based abstract syntax. This class uses a series of object-oriented interpreters, written in Scheme++. These interpreters follow the EOPL interpreters closely in their functionality, but with formal support for expressing how they are interrelated.

The code for these interpreters will appear below as the course progresses. The first file includes the environments ADT, which is described in the Introduction to Scheme++ for C311. All files can be found in copper:/u/c311/ss/.

Laboratory Assignments

Links to assignments and solutions will appear below as they are posted. Most weeks an assignment will be posted by noon on Monday and due by 9 AM the following Monday. Solutions to assignments will posted by noon on the day they are due. Thus late assignments will not be accepted!

All assignments require the use of Chez Scheme. It is strongly suggested that you use the emacs editor, for which help is available. Use of the emacs customization file iuscheme.el is recommended. On copper this may be arranged by copying ~c311/emacs/.emacs to your home directory, or adding the contents of this file to your existing .emacs file.

We use a few extensions of standard Scheme that are not described in EOPL. To have these extensions automatically provided when you run scheme on copper, add ~c311/bin/ to the beginning of your shell load path. To accomplish this, add

 
    set path=(/u/c311/bin $path)

to your .login file, or

    PATH=/u/c311/bin:$PATH

to your .profile file.

Points will be deducted on the homework, quiz, and exams if the cardinal rules of indentation are violated, so make it a habit to follow them whenever you write Scheme code. This will also aid all of your Scheme programming. It is also strongly suggested that you write solutions to all exercises by hand and check them carefully for correctness before approaching a computer.

Assignments are submitted by emailing them to c311@copper, with a subject of the form handin N, where N is the number of the assignment. Thus for the first assignment the message must be exactly the characters "handin 1" (even the space before the number is significant!). Assuming the file hw1.ss containes your solution to the first assignment, it is suggested you submit it using the unix command

Mail -s "handin 1" c311@copper <hw1.ss

(note the capital M in Mail). Shortly after mailing the handin message you should receive a reply from the handin program. The reply may indicate some errors in your program, but is not guaranteed to report all errors.

Although assignments account for only about 15% of the total course grade, they are essential in order to master the material (assignment grades and exam grades have been highly correlated). Assignment grading will be done by the course associate instructor. The most important grading criteria is correctness, but efficiency and style may also be considered. Do not be concerned with minor efficiency matters, but credit may be lost if for example you use an exponential algorithm when there is a linear-time algorithm.

Policies

Evaluation

Quiz: 10%, in class, Monday, January 23rd, solutions.
Exam 1: 20%, in class, date to be announced
Exam 2: 20%, in class, date to be announced
Final Exam: 35%, in BH142, 10:15-12:15, Wednesday, May 3rd
Assignments: 15%, the lowest assignment grade will be dropped

Percentages are approximate.

Attendance and Academic Integrity

Class attendance will not be monitored, but regular attendance is strongly recommended. Attendance at examinations is compulsory; make-up examinations will not be given. See the Computer Science Department statement on academic integrity.

Withdrawal and Incomplete Grades

Withdrawal after 4 PM on Wednesday, March 8th, requires the dean's approval.

An incomplete (I) final grade will be given only by prior arrangement in exceptional circumstances conforming to departmental policy in which the bulk of course work has been completed in passing fashion.

chaynes@indiana.edu