COM 1358 Analysis of Programming Languages

Course Format
Course Coordinator
Textbooks and References

Prerequisites by Topic
Major Topics Covered in Course
Laboratory Projects

Course Description

Covers run-time behavior of programming languages; interpreters; static and dynamic scoping; parameter-passing mechanisms; implementation of functions and recursion; and features of current languages and their implementation.

4 QH credit
Prerequisite: COM 1350, COM 1340.

Course Information

Course is offered only during the Spring quarter. CS majors are guaranteed a place in class.
 

Spring 2001 (one section)

Course Format

BSCS03 Language track
BSCS04 Language core
BACS required core
BSIS general elective

This is a Language track course for BS CS majors graduating in the year 2003 and before, is a second four credit Language core course for BS CS majors graduating in the year 2004 and beyond and a required course for BA CS majors.

Course Coordinators

Professor William Clinger
will@ccs.neu.edu

Textbooks and References

Spring 2000

• Friedman, Wand, Haynes.  Essentials of Programming Languages (2nd edition), in draft form.

Course Goals

• Gain experience and comfort with formal and recursive specifications.
• Realize that programming languages have both syntax and semantics, and that both can be specified formally.
• Realize that a program is basically a tree-like data structure.
• Understand the semantics of two-step naming in mainstream programming languages (environments and stores, declarations and assignments, denoted and expressed values).
• Understand the semantics of procedures, parameter transmission, and dynamic method dispatch, and have some idea of how the semantics of these things can vary in different languages.
• Understand the notion of type safety and the semantics of simple types, and gain some appreciation for universally quantified types.
• Understand why the halting problem is undecidable.
• Know that all general purpose programming languages are Turing-complete, but that there are other measures of relative expressibility (Bohm-Jacopini and Patterson-Hewitt theorems). [This might not be a goal of the course for most instructors, but it is a goal of mine as I teach the course this quarter.]

Prerequisites by Topic

COM1350 Formal Languages and Automata

COM1340 Recursive Thinking

Major Topics Covered in the Course

Recursive specifications

• Inductive definitions
• Context-free grammars
• Scope of variables

Data abstraction
 

• Abstract data types
• Environments
• Abstract syntax trees

Environment-passing interpreters
 
• Local variables
• Procedures
• Recursion
• Assignment
• Parameter passing

Objects
 
• Classes
• Inheritance
• Dynamic polymorphism

Types
 
• Type safety
• Static type checking

Laboratory projects

The first assignment is basically a review of induction and recursion, and consists of many small exercises. Some of these exercises involve inductive definitions and/or proofs and/or syntactic derivations.  Others are to write small Scheme procedures, such as a procedure that computes the free variables of a term in the lambda calculus.

Write five small Scheme procedures that use higher-order procedures or other programming techniques that will be used throughout the course but that the students haven't yet gotten down.

Five exercises that require the student to answer questions about and/or modify a small interpreter for a language with local declarations but no procedures.

Five exercises related to computability. Two show that procedure-passing can be used to implement recursion even without recursive declarations. The other three have to do with self-reproducing programs.

Exercises that require the student to answer questions about and/or modify a small interpreter for a language with procedures, recursive declarations, and assignments.

Exercises that require the student to answer questions about and/or modify a small interpreter for a language with classes, inheritance, and dynamic ad hoc polymorphism.

Exercises that require the student to answer questions about and/or modify a static type checker.

Write a Java application that writes its own source code to System.out. Prove some of the easier lemmas that the instructor assumed in lectures concerning decidability/undecidability/expressibility.