CS 136 Tutorials - Spring 2007

Tutorials »

Tutorial 2: Service Managers and Destructive Methods (May 11)

This tutorial first briefly covers the use of service managers to achieve encapsulation. Then we delve more deeply into destructive functions, especially destructive list processing. These concepts are introduced in Lecture Module 2 (see Handouts).

  1. Service Managers
  2. New semantics for mutation
  3. In lecture, we showed why we need new semantics to deal with mutation when we have self-referential and co-referential data structures. Using these new semantics, work through the evaluation of the following code snippets. You should also be able to show the effects of the examples using box and pointer diagrams. These will likely be useful to you to help visualize what is happening, but remember they are not a replacement for the strict semantics.

  4. Destructive List Processing
  5. When we speak of "destructive list processing", what we usually mean is that the original list or lists passed in to the function as arguments may be changed (or "destroyed"). A natural question is why we would ever want to do this. The reason is that we make use of list mutation (i.e. set-first! and set-rest!) to avoid creating new cons cells in our function execution, thus making the program more memory-efficient.

    The following exercises ask you to write some destructive list processing functions. A useful technique in some of these may be to write the non-destructive version of the function first, and then try to modify this solution to use mutation and avoid creating new cons cells (this is done for you in the first example).

  6. All-encompassing example

Last modified on Wednesday, 09 January 2019, at 14:31 hours.