Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Courses ECS 140A, ECS 142

Grading: Letter; problem sets (10%), project (30%), midterm (20%), final (40%)

Catalog Description:
Advanced topics in programming languages, including formal syntax and semantics, the relation between formal semantics and verification, and an introduction to the lambda calculus. Additional topics will include language design principles, alternative programming language, in-depth semantic theory and models of language implementation.

Expanded Course Description:

Lectures provide an introduction to the theoretical side of the study of computer programming languages, including language definition methods and the lambda calculus. The usefulness of advanced language features in appropriate programming applications is also discussed, with examples. The project gives students an opportunity to experiment with defining and prototyping a programming language.

The lectures topics include the following, not necessarily listed in chronological order:

  1. Motivation for Formal Language Definition
    1. Standardization, program portability, program verification
    2. Rapid prototyping, language implementation
  2. Overview of Language Definition Methods
    1. Axiomatic, operational, algebraic, attribute-grammar, denotational
    2. Applicability, equivalence proofs
  3. Criteria for Language Definitions
    1. Consistency, completeness, non-circularity, exceptions
  4. Standard Concepts in programming Language Definition
    1. Abstract syntax, syntax-driven definition, referential transparency
    2. Semantic domains: State, environment, store, etc.
    3. Continuations
  5. Applications of Denotational Semantics
    1. Least fixed points, while loops, recursive programs
  6. The Lambda Calculus
    1. Lambda notation, alpha-beta-and eta-reduction, normal order reduction
    2. The Y fixed-point combinator
    3. Curry, Scott, and the semantics of the lambda calculus
    4. The Lambda calculus as the basis of the definition and implementation of functional languages
  7. Programming Languages and the Lambda Calculus
    1. Currying, functions as first class objects, lazy and eager evaluation
    2. LISP, Scheme, ML
  8. Applications of Advanced Language Features
    1. Data abstraction, polymorphism and type inference
    2. Currying, functions as first class objects, lazy and eager evaluation
  9. Optional Additional Topics: Language Design
    1. Language features and intended application
    2. Syntax
  10. Optional Additional Topics: Alternative Programming Styles
    1. Dataflow, logic, distributed, and/or concurrent languages, etc.
  11. Optional Additional Topics: Language Theory
    1. Reflection, strictness analysis, abstract interpretation
    2. Graph reduction, combinators
  12. Programming Language Implementation Models
    1. Implementation of imperative languages
    2. Implementation of functional languages (e.g. ML)
    3. Implementation of logic-based languages (e.g. Prolog)
    4. Special topics: heap allocation, garbage collection

B. Meyer, Introduction to the Theory of Programming Languages, Prentice Hall, 1991.
J. Ullman, Elements of ML Programming, Prentice Hall, 1994.

Programming Project:
The students will apply the concepts of the class to a real programming language, for which they will create the following: informal requirements, formal syntax, formal semantics, an interpreter, and a verification system for a subset of the language which will be used to verify a few sample programs. The students will demonstrate that this rigorous approach to language design and implementation produces a rugged and easily modifiable system, an important concept in making language design and implementation an engineering discipline.

Engineering Design Statement:
The project involves the design, implementation, and testing of a programming language. The facilities used for these programming projects resemble those that would be found in industry to the extent possible, given the academic constraints. The project assignment defines performance specifications and constraints, and outlines a general approach to the problem. However, design and implementation details are left to the students. Lectures discuss general concepts of programming languages and design choices available to programmers, in terms of algorithmic design, what language features can be employed to solve a particular problem, and what languages are most appropriate for particular application domains. Projects are graded based on the design and performance, including documentation. Examination questions are based on design methods discussed in lecture and from the project.

ABET Category Content:
Engineering Science: 2 units
Engineering Design: 1 unit

Instructor: K. Levitt, R. Pandey

Prepared by: K. Levitt (Feb. 1977)


Revised: 2/97