Lectures and Details

Overview

Language Design and Implementation (CS 4501-002, 18460) will acquaint you with the fundamental ideas surrounding the design and implementation of high-level programming languages. The course will stress underlying theoretical concepts as well as a significant, practical course project. At the same time, the course will focus on making this material accessible to students of varied backgrounds.

Students will gain experience with functional and object-oriented programming via the OCaml and Cool programming languages. In addition, students may optionally complete assignments using their choice of Python, Ruby, JavaScript, or Haskell. The Assignments and final project in this course lead to the construction of an interpreter for a subset of Java. This involves scanning, parsing, type-checking and interpreting code. You will master concepts such as context-free grammars, variable bindings, control flow, types, subtyping, and method invocation.

Compilers Practicum (CS 4501-005, TBA) will acquaint you with the fundamentals of compiler construction: you will produce a program that accepts as input source code in a high-level language and produces as output low-level assembly code representing an executable program. You will master fundamental concepts of dataflow analysis, optimization, code generation, calling conventions, as well as code generation for object-oriented programming.

Enrollment Restrictions

Because Language Design and the Compilers Practicum share a number of core concepts (e.g., intermediate representations, type checking, formal language semantics, etc.), to take the Compilers Practicum you must also take the Language Design course (or have taken CS 4610 in a previous semester). Thus, you have two options:

1. Take only Language Design and Implementation.
   • You may not receive credit for both Programming Languages (CS 4610) and also Language Design and Implementation.
2. Take both Language Design and Implementation and also Compilers Practicum.
   • You may not receive credit for both Compilers (CS 4620) and also Compilers Practicum.

All descriptions and assignments on this webpage refer to Language Design only unless otherwise noted. That is, any assignments related to the Compilers Practicum course will be cleared marked as such and are not required for students not taking the Compilers Practicum.

Project and Assignments

The Language Design course project consists of five Programming Assignments. Taken together, the assignments form a complete interpreter for Cool, the Classroom Object-Oriented Language. The project components are assigned in roughly increasing order of size and difficulty; proportionately more time is allotted for the later assignments. Later assignments will be weighted more heavily in the final grade.

The Compilers Practicum course project consists of five programming assignments (called "Compilers Assignments" for clarity). These assignments culminate in an optimizing compiler for Cool.

For both courses, programs will be evaluated for correctness, organization, and documentation.

Assignments may be done individually or in teams of two. The first Language Design assignment must be done individually, however. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.

Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each Assignment; each member receives the same grade for the assignment. If a partnership is not going well, the teaching assistants will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment without instructor permission.

Assignments are due at 11:50pm on the date in the course schedule. Assignments will be turned in electronically via a special submission server.

Course Programming Languages

Three programming languages are required as part of this course:

• Cool is an imperative, strongly-typed classroom object-oriented programming language. It can be viewed as a simplified version of Java. You will learn Cool as part of this course.
• OCaml is an efficient, functional, strongly-typed, object-oriented language with imperative support. You will learn OCaml as part of this course.
• Python is a structured, imperative programming language with a high emphasis on readability and support for object-oriented and functional programming. You are expected to know imperative and object-oriented prorgamming in Python before entering this course; you will learn functional programming in Python as part of this course.

In addition, three additional optional languages are available and you may use them to complete programming assignments.

• Haskell is an advanced, statically-typed, lazy, purely functional language.
• JavaScript is a dynamically-typed language with object-oriented, imperative and functional support; it is often used in web and asynchronous programming.
• Ruby is an imperative, dynamically typed, object-oriented language with functional support.

Review Sets

There are seven Review Sets provided for Language Design and Implementation. These Review Sets are not graded assignments, and are instead provided as a structured system for students to evaluate their mastery of the material and prepare for written examinations. The instructor and the teaching assistants will be happy to go over Review Set answers during office hours.

Examinations

Language Design will contain two midterm examinations and may contain a final examination. The midterms will be held in class.

The Compilers Practicum may contain a final examination, held concurrently with the Programming Languages final examination.

For both courses, the exams are open-note by default (one piece of paper, front and back, prepared by you). The exams are not open-book. No electronic devices are allowed. No cellphones, PDAs, palmtops, laptops, etc. No early, late or make-up exams will be given. Please plan accordingly.

Grading

It is impossible to pass the course without doing the programming assignments. For Language Design, the relative weight of the components of your grade will be approximately:

For the Compilers Practicum, the relative weight of the components of your grade will be approximately:

For both courses, the grades will follow a standard curve: once the final numerical grade has been computed according to the above formula, the average grade will be somewhere in the B+ range. Note that this is explicitly a very high curve. Doing significantly better than the average will yield an A. Doing significantly worse than the average will yield a B, C, D or F.

Students interested in an experience equivalent to the Programming Languages (CS 4610) elective of previous semesters should consider the optional Legacy Grading Contract.

We follow the Honor System. You should know that fairly sophisticated plagiarism detection software will be used on the Assignments; cheating on an assignment or exam will result in a score of 0 for it as well as a score of 0 for the entire course.

Regrade and Late Policy

An assignment turned in h hours late has its point value reduced by h%. Thus if you turn in a Assignment at 8am the next day (i.e., 8 hours late) your grade for that assignment will be multiplied by 0.92.

Regrades for exams, Assignments, or written assignments must be received within one week of you receiving your score. All regrade requests should be made to the TA. When we regrade an assignment we will look over it very carefully for correctness: it is possible that after a regrade you will end up with fewer points than before the regrade. Regrades should be treated with caution and used only when the graders have made a clear mistake evaluating your work.

All course materials submitted for a grade must be turned in by a date marked on the course syllabus (usually near 11:50pm on Tuesday, May 10th).

Research

Your class work might be used for research purposes. For example, we may use anonymized student assignments to design algorithms or build tools to help programmers. Any student who wishes to opt out can contact the instructor or TA to do so after final grades have been issued. This has no impact on your grade in any manner.

Students interested in considering undergraduate research should make an appointment to talk about it. I am happy to discuss independent study projects, SEAS STS senior theses, CLAS Distinguished Major theses, paid research work over the summer, research work for credit, and graduate school.

Additional References

You may find the following additional resources helpful:

• Hal Abelson, Jerry Sussman, and Julie Sussman's Structure and Interpretation of Computer Programs. The book's full text is available on-line and it is an excellent resource for functional programming and the lambda calculus.
• Aho, Sethi and Ullman's Compilers: Principles, Techniques, and Tools. Also known as the Dragon book, it covers basic compiler technology.
• Andrew Appel's Modern Compiler Implementation in Java.