COM 1358: Analysis of Programming Languages
Spring 2000

Administrivia

Instructor: William D Clinger
Home page: http://www.ccs.neu.edu/course/com1358/index.html
Directory: /course/com1358

Prerequisite:  COM 1340 (or COM 1102, which is no longer offered).
This prerequisite was added when the course requirements for the
BS in computer science were revised for the class of 2004 and beyond.
(Students who intend to graduate under the old BS curriculum but have
not yet taken COM 1102 must substitute for it by taking COM 1340 and
an additional COM elective.)

Required Textbook:  Friedman, Wand, and Haynes.  Essentials of
Programming Languages (draft of 2nd edition, Spring 2000).
Chapters 1-3 and 6-8 of this draft are available at Gnomon Copy
as COM 1358 packet #1.

Recommended Document:  Kelsey, Clinger, and Rees [editors].  The
Revised^5 Report on the Algorithmic Language Scheme.  This document
is online and is also available at Gnomon Copy as COM 1358 packet #2.

COM 1358 introduces the concepts and techniques of a systematic
approach to understanding the semantics of mainstream programming
languages.  This approach regards a programming language as an
immutable abstract data type.  Most operations of this ADT are
essentially syntactic and very simple:  They construct an abstract
syntax tree, select a component of an abstract syntax tree, or
analyze an abstract syntax tree by cases.  There are also two
complex operations:  The scan&parse operation converts a textual
representation of a program into its abstract syntax tree, and
the evaluation operation computes the result of a program.

Scanning and parsing are covered in COM 1350 and COM 1355.  The
evaluation operation is the focus of COM 1358.

We will study the semantics of programming languages by writing
and analyzing formal specifications of the evaluation operations
for several different kinds of programming languages.  These formal
specifications are executable, so they can be used as interpreters,
but efficiency is not our primary goal.  In constructing our
interpreters, we will favor simplicity and theoretical clarity over
efficiency.  (Techniques for more efficient evaluation are covered
in COM 1355.)

Students will write, modify, and experiment with several different
interpreters.  These programming assignments will account for about
half of the final grade.  A midterm and final exam will account for
the other half.

Honesty is an important characteristic of computer scientists, and
security is an important aspect of software development.  In this
course, students are expected to protect their code from plagiarists
and thieves. The quality of this protection will be graded.


Outline

   * Recursive specifications
        o Inductive definitions
        o Context-free grammars
        o Scope of variables
   * Data abstraction
        o Abstract data types
        o Environments
        o Abstract syntax trees
   * Environment-passing interpreters
        o Local variables
        o Procedures
        o Recursion
        o Assignment
        o Parameter passing
   * Objects
        o Classes
        o Inheritance
        o Dynamic polymorphism
   * Types
        o Type safety
        o Static type checking