Principles of Programming Languages (201-1289101)

SOLUTION TO MOED ALEPH

UPDATE ON ENVIRONMENTS

Course Outline

• Class 1: Defining a Computer Language; Primitives, Composition, Abstraction; Evaluation Rules; Substitution model for compound procedure; Evaluation strategy, applicative order, normal order. (Mira Balaban's notes).
• Class 2: Special forms, conditional expressions; Functions as abstractions, local names, binding, renaming; Block structure, lexical scoping. (Mira's notes)
• Class 3: Procedures vs. processes; properties of processes: time and space complexity; linear recursive, iterative, tree recursive processes; examples: factorial, fibonacci, power, gcd. (Mira's notes)
• Class 4: Procedures as general methods; higher-order functions, procedures as parameters; lambda; let and local variables; examples: sum, integral, roots of equation, fixed point of function. (Mira's notes)
• Class 5: Procedures that return procedures; compose; repeated; general transformation methods: derive, average-damp; more general methods: newton's method, fixed-point-of-transform.
• Class 6: Introduction to data abstraction; Example: rational numbers package; Abstraction barriers. (Mira's notes)
• Class 7: Data definition: ADT + constraints; Hierarchical data: lists, trees; map; map-tree; streams.
• Class 8: Using sequences as conventional interfaces; filter, accumulate and map; graphic language 1: painters and combinations.
• Class 9: Graphic language 2: abstraction over painters; implementation of painters; supporting ADTs: vectors, segments, frames; implementation of painter combinations: beside, flip. Code for running the graphic language.
• Class 10: Symbols; equality; type predicates; run-time type information; Representing sets (1/2). (Mira's notes include symbolic derivation and Huffman coding examples).
• Class 11: Representing sets (2/2); Dealing with multiple representations; complex number example; generic functions (1/2); more on run-time type information.
• Class 12: Generic functions (2/2); Data-directed programming; Message passing. (Mira's notes)
• Class 13: Systems with Generic operations -- Arithmetic system. (Mira's notes include polynomial arithmetic examples).
• Class 14: Coercion. (Notes)
• Class 15: Cubes -- Mutation 1. (Mira's Notes)
• Class 16: Mutation 2 -- Environment model -- Message passing. (Mira's Notes and the account example)
• Class 17: Mutable structures -- Queues. ( Mira's Notes and Queue example, Table example)
  Additional notes on object-oriented programming.
• Class 18: Digital circuit simulator 1. (Notes)
• Class 19: Simulator 2.
• Class 20: Propagation of constraints. (Notes)
• Class 21: Concurrency 1.
• Class 22: Java basics 1 + Concurrency 2 (Threads). (Notes)
• Class 23: Java basics 2 + Delayed and infinite Streams. (Java, Friedman's Introductory slides on Streams in Scheme (infinite lists))

Assignments

• Assignment 1 - due Mon 17 Mar 1997.
  Solution to Assignment 1
• Assignment 2 - due Wed 02 Apr 1997.
  Solution to Assignment 2
• Assignment 3 - due Tue 15 Apr 1997.
• Assignment 4 - due Wed 4 June 1997. Use the constraint propagation code.
• Assignment 5 - due Sun 22 June 1997.
  (Now complete - finish it).

Reference Material

SCM for PCs

The following file contains a version of scm with turtle graphics compatible with the one installed on the Unix machines. It can be used for assignment 3.

Textbook

• SCM Scheme Implementation
• SLIB Portable Scheme Library
• Scheme Algorithmic Language (Standard Definition) (Postscript format)
• A WEB-Workshop on Scheme (by John David Stone).
• Introductory slides on Scheme (by Daniel P. Friedman, CS Dept. Indiana University).
• Introductory slides on Streams in Scheme (infinite lists) (by Daniel P. Friedman, CS Dept. Indiana University).
• JACAL Symbolic Math System written in Scheme
• Scheme home page.
• Other Implementations of Scheme: A repository that contains a lot of scheme implementations.