CPS 206 Advanced Programming Fall, 1999

Text: Finkel: Advanced Programming Language Design

Sections to be covered are indicated below by a notation following the chapter title. Chapters with no such notation will not be discussed. The notation "#n" indicates that this chapter is the n-th to be discussed.:

Chapter 1 Programming Languages as Software Tools

(#1 2 lectures)

1. Evaluating Programming Languages

2. Background Material on Programming Languages

Variables, Data Types, Literals, and Expressions

Control Constructs

Procedures and Parameter Passing

Block Structure

Runtime Store Organization

3. Final Comments

EXERCISES

Chapter 2 CONTROL STRUCTURES

(#3 2 lectures, skip 4)

1. Exception Handling

2. Coroutines

Coroutines in Simula

Coroutines in CLU

Embedding CLU Iterators in C

Coroutines in Icon

3. Continuations: Io

4. Power Loops

5. Final Comments

EXERCISES

Chapter 3 TYPES

(#4 3 lectures, skip 5,8,9)

1. Dynamic-Typed Languages

2. Strong Typing

3. Type Equivalence

4. Dimensions

5. Abstract Data Types

6. Labels, Procedures, and Types as First-Class Values

7. ML (See also Ullman: Elements of ML Programming, Prentice Hall

0-13-184854-2 1994)

Expressions

Global Declarations

Local Declarations

Lists

Functions and Patterns

Polymorphic Types

Type Inference

Higher-Order Functions

ML Types

Constructed Types

8. Miranda

9. Russell

10. Dynamic Typing in Statically Typed Languages

11. Final Comments

EXERCISES

Chapter 4 FUNCTIONAL PROGRAMMING

(#5 3 lectures)

1. LISP

Function Syntax

Forms

Programmer-Defined Functions

Scope Rules

Programming

Closures and Deep Binding

Identifier Lookup

The Kernel of a LISP Interpreter

Run-time List Evaluation

Lazy Evaluation

Speculative Evaluation

Strengths and Weaknesses of LISP

2. FP

Definition of an FP Environment

Reduction Semantics

Persistence in Functional Languages

Limitations of Functional Languages

Lambda Calculus

EXERCISES

Chapter 5 OBJECT-ORIENTED PROGRAMMING

1. Definitions

2. A Short Example

3. Simula

4. Smalltalk

Assignment and Messages

Blocks

Classes and Methods

Superclasses and Subclasses

Implementation of Smalltalk

Subtle Features

5. C++

The Consequences of Static Binding

Sample Classes

6. Final Comments

EXERCISES

Chapter 6 DATAFLOW

1. Dataflow Computers

2. Val

3. Sisal

4. Post

Data Types

Programs

Synchrony Control

Guardians

Speculative Computation

5. Final Comments

EXERCISES

Chapter 7 CONCURRENT PROGRAMMING

(#2 3 lectures: Skip 3,4, Lynx, Linda, SR)

1. Starting Multiple Threads

2. Cooperation by Means of Shared Variables

Join

Semaphores

Mutexes

Conditional Critical Regions

Monitors

Crowd Monitors

Event Counts and Sequencers

Barriers

Performance Issues

3. Transactions: Argus

4. Cooperation by Procedure Call

Rendezvous

Remote Procedure Call (RPC)

Remote Evaluation (REV)

5. Cooperation by Messages

CSP

Lynx

Linda

SR

Object-Oriented Programming

Data-Parallel Programming

6. Final Comments

EXERCISES

Chapter 8 LOGIC PROGRAMMING

(#6 2 lectures -- 1.1 only)

1. Prolog

Terms, Predicates, and Queries

Separating Logic and Control

Axiomatic Data Types

List Processing

Difference Lists

Arithmetic

Termination Issues

Resolution Proof Techniques

Control Aspects

An Example of Control Programming

Negation

Other Evaluation Orders

Constraint-Logic Programming (CLP)

Metaprogramming

2. Godel

Program Structure

Types

Logic Programming

Conditionals

Control

3. Final Comments

EXERCISES

Chapter 9 AGGREGATES

(#8 3 lectures)

1. Strings

Literals and Simple Operations

Representation

Pattern Matching

Associative Arrays

Sub-strings as First-Class Values

SNOBOL

Icon

Homoiconic Use of Strings: Tcl

2. Arrays: APL

Operators and Meta-operators

An APL Evaluator

Incremental Evaluation

Database Languages

Data Types

Control Structures

Modifying Data

SQL

3. Symbolic Mathematics

4. Final Comments

EXERCISES

Chapter 10 FORMAL SYNTAX AND SEMANTICS

(#7 3 lectures, skipping parts of 3)

1. Syntax

2. Axiomatic Semantics

Axioms

A Simple Proof

Weakest Preconditions

3. Denotational Semantics

Domain Definitions

Product Domains

Disjoint-Union Domains

Function Domains

Domain Equations

Non-recursive Definitions

Recursive Definitions

Expressions

Identifiers

Environments

Variables

Conditional and Iterative Statements

Procedures

Functions

Recursive Routines

Modeling Memory and Files

Blocks and Scoping

Parameters

Continuations

Statement Continuations

Declaration Continuations

Procedures, Functions, and Parameters

Flow of Control

Summary of Syntactic and Semantic Domains and Semantic Functions

4. Final Comments

EXERCISES