CS 136 Tutorials - Spring 2007

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
    • Closed line interval
    • A closed interval on the real number line between numbers a and b is usually denoted by [a,b], and this represents all numbers x such that axb.

      We want to encapsulate the notion of an interval using a service manager, with mutation functions set-a and set-b for the endpoints, and a single predicate function contains? which consumes a number and returns true iff that number is in the interval.

      Write a function make-interval which consumes two initial endpoints a and b and produces a service manager which can handle the three messages given above.

    • Keeping a running average (Part II)
    • In last week's lab, we saw an example where we want to add test scores into some type of structure, and to be told the running average of all scores entered so far at each step. This was implemented as a single function which returned a 1-ary lambda expression. A sample solution is as follows:

      ;;make-running-average: -> (num -> num)
      (define (make-running-average)
        (local ((define sum 0)
                (define n 0))
          (lambda (new)
            (begin (set! sum (+ sum new))
                   (set! n (+ n 1))
                   (/ sum n)))))

      Now we want to extend this solution by using the service-manager paradigm for encapsulation, and adding a little more functionality. The functions we want to support are:

      • add-score: num →

        Adds in the given score and updates internal variables accordingly

      • get-avg: → num

        Returns the average of all scores entered so far.

      • get-max: → num

        Returns the highest score entered so far.

      • get-min: → num

        Returns the lowest score entered so far.

      • get-num-scores: → num

        Returns the number of scores entered so far

      Write a function, make-score-averager, which takes no arguments and returns a service manager supporting the above functionality.

  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.

    • (define-struct node (ssn name left right))
      (define node1 (make-node 5 'Tingting false false))
      (define node2 (make-node 1 'James false node1))
      (set-node-ssn! node1 6)
    • (define lst-1 (cons 'b (cons 'c empty)))
      (define lst-2 (cons 'a (rest lst-1)))
      (set-rest! (rest lst-2) (cons 'd empty))
      (set! lst-1 (cons 'a (cons 'd empty)))
      (set-rest! lst-2 (rest (rest lst-2)))
      (set-rest! lst-1 empty)

  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).

    • Merging two sorted lists
    • Given two lists of numbers in ascending order, it is a relatively common operation to merge those two lists, resulting in one list of numbers in ascending order. The following is a simple implementation of merge that does not use mutation:

      (define (merge alon1 alon2)
        (cond [(empty? alon1) alon2]
              [(empty? alon2) alon1]
              [(< (first alon2) (first alon1))
               (cons (first alon2) (merge alon1 (rest alon2)))]
              [else
               (cons (first alon1) (merge (rest alon1) alon2))]))

      Create a new function, merge!, which behaves similarly to merge, but uses mutation to avoid creating any new cons cells - that is, using destructive list processing.

      Question: What will the input lists look like after merge! finishes execution? Should we even care?

    • Flattening a list of lists
    • To "flatten" a list of lists is to create a single list which contains each element in each list of the list of lists, in order. So, for instance, "flattening" '((1 2) () (3) (4 5 6)) would produce '(1 2 3 4 5 6).

      Write a function, flatten!, which consumes a list of lists, and flattens to create a single list, using mutation to avoid creating new cons cells.

    • Removing even-indexed elements
    • Write a function, remove-evens!, which consumes a list and modifies that list to contain only the odd-indexed elements. Note that sometimes with destructive list processing, we do not care what happens to the original input lists, but here the whole point is that the original list should be mutated in a specific way. So, for example, after executing the following two lines of code:

      (define lst '(a b c d e f g))
      (remove-evens! lst)

      the value of lst should be '(a c e g).

    • Removing odd-indexed elements
    • Write a function, remove-odds!, which consumes a list and modifies that list to contain only the even-indexed elements. This is of course quite similar to the previous exercise, and in fact you are encouraged to call remove-evens! as a helper function. But there is a rather significant complication.

      Question: What restriction must we place on the input list to remove-odds!? Why?

  6. All-encompassing example
    • Sorted List
    • We want to encapsulate a list of numbers sorted in ascending order, and a few operations on that list. The underlying representation could be a binary tree, but we will just use normal Scheme lists for simplicity. We want to implement the following operations on sorted lists:

      • insert: num →

        Inserts the given number into the list in the correct position

      • remove: num → true/false

        Removes the first occurance of the given number from the list, returning false if and only if the number was not found in the list.

      • contains: num → true/false

        Checks if the given number is in the list, and returns false if and only if it is not.

      • size: → num

        Returns the number of elements in the list.

      Write a service manager-based implementation of a sorted list as described above, with the four given operations. Your implementation should use destructive list processing to avoid creating new cons cells whenever possible (it is not always avoidable).

 

Last modified on Friday, 19 August 2011, at 18:05 hours.