0368.1105 Extended Introduction to Computer Science

Dr. Yishai Feldman (yishai@math.tau.ac.il)
Sunday 16-18, Thursday 15-17, Schreiber 12
Office hour: Monday 17-18

Textbook

Harold Abelson and Gerald Jay Sussman, with Julie Sussman: Structure and Interpretation of Computer Programs, MIT Press, 2nd ed., 1996, 1st ed., 1985. (SICP)

Scheme interpreter

  1. The recommended Scheme interpreter: PC Scheme/Geneva - a public domain interpreter. Get the files from a local copy.
  2. Other Implementations: A repository that contains a lot of scheme implementations.
  3. Scheme home page.
  4. Newsgroup: comp.lang.scheme.

Software

The following files are suitable for running on PC Scheme/Geneva. In all the interpreters, the functions eval and apply have been renamed, and the new primitive function (exit) can be used to exit the interpreter.
  1. The meta-circular evaluator: run-mce.scm.
  2. The analyzing evaluator: run-anlz.scm, uses the file analyze.scm.
  3. The type-checking evaluator (not in the book): run-type.scm, uses the file typechk.scm.

Course outline

This list will be updated as the course progresses.
Section numbers mentioned are from SICP, and when included without comment they were covered in full, except for exercises. Section numbers prefixed by "I" are from the 1st edition, "II" marks the 2nd edition, and unmarked numbers are the same in both. Material not covered in the book is marked with a "*".
  1. Sun Oct 13:
    Introduction to the course and its requirements. Philosophy of the new course. Expressions (1.1.1). Naming and environment (1.1.2). Evaluating combinations (1.1.3).
  2. Thu Oct 17:
    Compound procedures (1.1.4). Constructing procedures using lambda (without let) (1.3.2). Substitution model for procedure evaluation (1.1.5). Conditional expressions and predicates (1.1.6).
  3. Sun Oct 20:
    Example: Square roots by Newton's method (1.1.7). Procedures as black-box abstractions (1.1.8). Linear recursion and iteration (1.2.1). Tree recursion (1.2.2). Orders of growth (1.2.3).
  4. Thu Oct 24:
    Orders of growth (1.2.3) - cont. Exponentiation (1.2.4). Greatest Common Divisors (1.2.5). Let (1.3.2).
  5. Sun Oct 27:
    Procedures as parameters (1.3.1). Procedures as general methods (1.3.3) - only half-interval method. Procedures as returned values (I1.3.4).
  6. Thu Oct 31:
    Introduction to data abstraction (2.1). Example: Aritmetic operators for rational numbers (2.1.1). Abstraction barriers (2.1.2). What is meant by data? (2.1.3). Hierarchical data (2.2).
  7. Thu Nov 7:
    Representing sequences (2.2.1), including Ex. 2.20 (mapcar). Printing lists (*). Representing trees (2.2.2). Symbols and quote (I2.2.3, II2.3.1).
  8. Sun Nov 10:
    Data representations in the read-eval-print loop (*). Symbolic Differentiation (I2.2.4, II2.3.2).
  9. Thu Nov 14:
    Sets (I2.2.5, II2.3.3). Multiple representations of abstract data (I2.3, II2.4). Representations for complex numbers (I2.3.1, II2.4.1). Manifest types (I2.3.2, II2.4.2).
  10. Sun Nov 17:
    Data-directed programming (I2.3.3). Systems with generic operations (I2.4). Generic arithmetic operators (I2.4.1).
  11. Thu Nov 21:
    Example: Symbolic algebra (I2.4.3, II2.5.3) - without rational functions. Assignment and local state (3.1). Local state variables (3.1.1). The costs of introducing assignment (I3.1.2, II3.1.3).
  12. Sun Nov 24:
    The benefits of introducing assignemnt (I3.1.3, II3.1.2). The environment model of evaluation (3.2). The rules for evaluation (3.2.1). Applying simple procedures (3.2.2). Frames as the repository of local state (3.2.3).
  13. Thu Nov 28 (AY):
    Internal definitions (3.2.4). Mutable list structure (3.3.1). Representing queues (3.3.2).
  14. Thu Dec 5 (AY):
    Representing tables (3.3.3) - one dimensional tables. Vectors (*). Binary search (*). Sorting: bubble sort, quicksort (*).
  15. Thu Dec 12:
    Representing tables (3.3.3) - two dimensional and local tables. Mergesort (*). Streams as standard interfaces (I3.4.1, II2.2.3) - started.
  16. Sun Dec 15:
    Streams as standard interfaces (I3.4.1, II2.2.3) - cont. Higher-order procedures for streams (I3.4.2, II2.2.3) - without nested mappings.
  17. Thu Dec 19:
    Implementing streams (I3.4.3, II3.5.1) - memoization. Infinitey long streams (I3.4.4, II3.5.2) - without "Streams as signals".
  18. Sun Dec 22:
    Using streams to model local state (I3.4.6, II3.5.5). Exploiting the stream paradigm (II3.5.3) - only "Formulating iterations as stream processes".
  19. Thu Dec 26:
    The metacircular evaluator (4.1). The core of the evaluator (4.1.1). Representing expressions (4.1.2).
  20. Sun Dec 29:
    Evaluator data structures (4.1.3). Running the evaluator as a program. (4.1.4).
  21. Thu Jan 2:
    Variations on a Scheme (I4.2). Alternative binding disciplines (I4.2.2). Separating syntactic analysis from execution (II4.1.7). Example (*).
  22. Sun Jan 5:
    Example - continued (*). Strong typing (*).
  23. Thu Jan 9:
    Type-checking interpreter (*) - started.
  24. Sun Jan 12:
    Type-checking interpreter (*) - continued. Extensions: user-defined types, type constructors, polymorphic types, union types (*).