Study Guide for Test on SICP Sections 2.2.2-3 and 2.4-2.5
	       (See also the Little Schemer, Chapter 5)

This study guide contains two parts. The first is the actual
directions from the test.  These will appear on the first page.  The
second is a list of topics.


DIRECTIONS FROM THE FIRST PAGE OF THE TEST

For this test, you can use one (1) page (8.5 by 11 inches, one (1)
side, no less than 9pt font) of notes.  Don't use anything with
printing on the other side. No photo-reduction is permitted.  You may
not share your notes with anyone else during the test.  These
notes are to be handed in at the end of the test, so please have your
name in the upper right hand corner of your notes.  Use of other notes
or failure to follow these instructions will be considered cheating.

WARNING: you won't have time to learn the material on during the test.
Just write down what would be too tedious to remember otherwise.

If you need more space, use the back of a page.  Note when you do that
on the front.

This test is timed.  We will not grade your test if you try to take
more than the time allowed.  Therefore, before you begin, please take
a moment to look over the entire test so that you can budget your
time.

For programs, indentation is important to us for ``clarity'' points;
if your code is sloppy or hard to read, you will lose points.  Correct
syntax also matters.  Check your code over for syntax errors.  You
will lose points if your code has syntax errors.

Of course, you may write helping procedures or methods whenever you
wish.  It may be helpful to give a comment that describes what they
do, if it's not completely clear from the name.

You may assume that all Java code is in the unnamed package on this test,
unless the problem states otherwise.

You may use any of the built-in procedures in Scheme.


TOPICS FOR THE TEST

The problems on this test will be mostly similar to homework 7,
although there may be one or two that are related to discussions we
had in class, which we did not have time to put on the homework.
Study Hint: probably the most helpful thing you can do is to create
your own test, take it on paper, and then type and debug your
programs on-line.

This test will involve writing both Scheme and Java programs.
There may a few problems in which we ask you to write in Scheme
something that was written in Java on homework 7, or vice versa.

Topics and skills that are more important are indicated by a +,
those are less important by a -.

1. Hierarchical Structures (SICP 2.2.2, Little Schemer ch. 5)
   and the visitor pattern.

+ Write recursions in Java over trees and
  atomic-expressions using the visitor pattern.  We would
  provide you with the library package lib.atomic_expression as in the
  homework.  (Homework problems included ScaleAtomicExpression,
  MapAtomicExpression.)
+ Write instances of the visitor pattern that abstract recursion
  patterns over atomic expressions (as in the MapAtomicExpression
  homework problem).
+ Apply the visitor pattern in Java to other datatypes that have
  mutually recursive structure.  (Homework: the BinaryMobile problem.)
- Explain why we do not need to use the visitor pattern in Scheme.

2. Sequences as Conventional Interfaces (SICP 2.2.3)
   also known as Pipe and Filter Architectures 

- Use map, filter, accumulate, and so on to write Java (or Scheme) programs
  by filling in the missing parts of Java (or Scheme) programs.
+ Implement new versions of such higher-order procedures in Java
  (like FoldLeft in the homework).
- Explain the shift from list-based architecture to iteration-based
  architecture that was used when we changed to Java.

3. Multiple Representations for Abstract Data (SICP 2.4),
   and Systems with Generic Operations (SICP 2.5.1-2).

+ Explain and use the concept of additivity.
+ Explain the problems involved in dealing multiple representations of
  data in a single program.  What features of Java help with this?
+ Be able to explain the relative advantages and disadvantages of
  explicit dispatch, data-directed dispatch, and message passing.
+ Be able to compare and contrast the support provided by Scheme and Java
  for dealing with (a) multiple representations of data,
  (b) data-directed programming, (c) message passing, and
  (d) systems with generic operations in general.
+ Be able to use these ideas in making and justifying choices for the
  design of systems. (As in the homework problem where you designed a
  system for Insatiable Enterprises Inc.)
+ Write Scheme (or Java) programs that use the operation-type table.
  (As in the homework problem for doing symbolic derivatives with
  data-directed dispatch.)
+ Write Scheme (or Java) programs that use the technique of
  data-directive dispatch and the operation-type table.
  (As in the homework problem where you designed a system for
  Insatiable Enterprises Inc.)
- Write Java code to implement a version of the operation-type table.
+ Write Scheme programs that use the technique of
  message passing, built around a dispatch procedure.
  (As in the homework problem where you wrote make-from-mag-ang.)
- Describe the alternatives for handling cross-type operations.
- Explain how coercions can be used to implement cross-type
  operations, and to inherit operations.  Explain how coercions work
  in Java between subtypes and their supertypes.