Michael Elhadad
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
Reference Material
SCM for PCs
The following file
contains a complete package to run scheme on a PC. It contains scm.exe,
slib, notes on the course, and a version of SCM with Windows programming
functions and many examples (1 Mb). (If you need, bring a diskette to copy
it directly.)
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
Harold Abelson and Gerald Jay Sussman, with Julie Sussman:
Structure and Interpretation of Computer Programs, MIT Press,
2nd ed., 1996. (SICP)
See also the
Home page of the book.
Last modified June 9th, 1997
Michael Elhadad