198:314 Principles of Programing Languages
Spring 2001
LECTURE TOPICS with references to the textbook.
The lectures, projects and assignments provide the exact material you are responsible for. the precise

Introduction

Introduction to course, programming paradigms: functional, logic, imperative, object oriented; history of programming languages. Language design issues: orthogonality, abstraction; syntax, semantics, tokens, grammars, compilation, execution model, interpreters. (Sethi Ch. 1, ASU Ch.1). (When possible, we will post lecture notes. Use ghostview to magnify and read them. )

Syntax of Programming Languages ( lecture notes)

Context free grammars, derivation, parse tree, ambiguity, statement grammars;

Expression grammars, operator precedence and associativity, abstract syntax, concrete syntax. BNF, EBNF. (Sethi Ch. 2; ASU Ch 2.2).

Regular expressions and their language; finite (deterministic and non-deterministic) automata; the relationship of the two. (ASU Chs 3.3-3.4).

Functional Programming/Scheme

Purely functional programming, function definition and application, referential transparency, intro to Scheme, S-expressions. Lists, their construction (cons/car/cdr), equality. Function definitions and read-eval-print loop. Quoting.

Recursive functions, functions as first-class citizens (lambda, apply, map). Currying; fancier reductions (reduce and fold).

Let, Let*, environments, closures.

(Sethi Ch.10).

Data types: their use and implementation.

Types, their utility, type checking and safety. Simple/primitive datatypes. Compound datatypes:
arrays (layout, (runtime?) bounds);
record structures (layout, strange C syntax);
pointers (l-value vs. r-value; pointers in C: pointer arithmetic, space allocation; comparison with "references" (in languages like Scheme, Java); pointers to functions.
strings: arrays and pointers (in C)
variants and union types, and how they lead to type unsafety.

Type declaration and equivalence, casting, coersion, overloading, subtypes (widening & narrowing).(Sethi Ch 4 except 4.6).

Abstract data types: packages in Ada and classes in C++ (specification vs. implementation, parametric polymorphism, friend classes); (Sethi Ch.6)

Object Oriented Languages and Programming (C++)

Class hierarchies; implementation and interface inheritance (base/derived class; abstract class; over-riding).

Dynamic dispatch at run-time.
(Sethi Ch.7.1-7.6)

Control structures

Branching, loops; structured programming, structured loop exits in C: break, continue; Boehm-Jacopini theorem, label-valued variables. (Sethi Ch.3.1-3.4, 3.7)

Logic Programming/Prolog

Database of facts; queries with variables; backtracking; rules; recursion. Logic Programming (assertions) vs. Prolog (+control). Tracing control. Lists and list manipulation in Prolog. General data structures. Cut and its uses. Arithmetic in Prolog. Parsing in Prolog. "Generate and Test" programming.

(Sethi Ch.11.1-11.3, only guess-an-verify in 11.4, 11.5)

Procedures: parameters, scopes, implementation

Parameter passing: by value, by name, by reference, by value-result; lazy vs. eager; aliasing. (Sethi Ch 5.1-5.2).

Scope: free/global vs. bound/local variables; procedure activation tree and scope; static vs. dynamic scope. Run-time stack implementation, procedure nesting depth, activation records, displays, central reference table. (Sethi Ch 5.3-5.5, 15.1 - or any other language allowing nested procedure definitions.).

Concurrency

Parallelism and concurrency; architecture models, fairness, liveness, safety; Concurrency as interleaving: sharing data safely, mutual exclusion, semaphores, produce-consumer example solved in a variety of ways using Ada's rendezvous mechanism.
(Sethi Ch.12, but OMIT explanation of figure 12.9, monitors)