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).
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 a ≤ x ≤ b. We want to encapsulate the notion of an interval using a service manager,
with mutation functions Write a function 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 1ary lambda expression. A sample solution is as follows: ;;makerunningaverage: > (num > num) (define (makerunningaverage) (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 servicemanager paradigm for encapsulation, and adding a little more functionality. The functions we want to support are: Write a function, In lecture, we showed why we need new semantics to deal with mutation when we have selfreferential and coreferential 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. 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.
The following exercises ask you to write some destructive list processing functions. A useful technique in some of these may be to write the nondestructive 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). 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
(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, Question: What will the input lists look like after
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" Write a function, removeevens! , which consumes a list and
modifies that list to contain only the oddindexed 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)) (removeevens! lst) the value of
Write a function, Question: What restriction must we place on the input list to
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: Write a service managerbased implementation of a sorted list as
described above, with the four given operations. Your implementation should
use destructive list processing to avoid creating new 

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