CS 136 Tutorials - Spring 2007

Tutorials »

Tutorial 1: Review (May 4)

This tutorial covers the basic the three basic tools in Scheme that we will be using in this course: Functions as values, Local expressions, and Elementary mutation. These concepts were introduced in Lecture Module 1 (see Handouts).

Local expressions

Polynomial simplification

Suppose we want a function to compute the value of the polynomial

f(x) = x⁴ + 8x³ + 25x² + 36x + 20

at a given point x. We could simplify this computation by noting that f(x) factors to

f(x) = (x+2)² * ((x+2)² + 1)

Using this simplification, and using a local expression to store an intermediate value, write a function f which consumes a number x and produces the value f(x).

Elementary mutation

Keeping a running total

Say we have a global variable sum, which is defined initially to be zero, with

(define sum 0)

Write a function, add-to-sum, which consumes a number and updates the value of sum to be the previous value of sum plus the given number. The function should produce the new value of sum.

Functions as values

apply-double

Write a function which consumes a 2-ary function (that is, a function which takes two arguments), and a single value, and produces the result of applying that function to the given argument repeated twice. So, for example, the line (apply-double + 4) should produce the result of (+ 4 4), which is of course 8.

make-add-surname

One way to write a name is as a list of two strings, for example ("Christopher" "Columbus"). We want a function that consumes a given (i.e. first) name as a string, and produces a list of that given name and some surname. Write a function which consumes a surname (string) and produces a function as described above, to add given names to that surname.

So, for example, if we have:

(define add-bush (make-add-surname "Bush"))
(add-bush "George")
(add-bush "Laura")

then the result would be:

(list "George" "Bush")
(list "Laura" "Bush")

Combining these ideas

The following exercises will require you to combine the three tools described above to write some more complex functions.

Next integer

We want a function which takes no arguments and produces, on consecutive calls, the next integer in increasing order. Your task is to write a function, make-next-integer, which consumes one integer (the starting point), and produces such a function.

So, for instance, if we execute the following code:

(define next-from-5 (make-next-integer 5))
(next-from-5)
(next-from-5)
(next-from-5)

then the following numbers should be produced:

5
6
7

Keeping a running average

Professors, TAs, tutors, and the like often need to enter a list of marks and then find the average. We want a function that consumes one score and produces the average of all scores entered so far. We may want to do this many times, so using a global variable is undesirable. Rather, write a function, make-running-average, which takes no arguments and produces a new function as described above, initialized with no scores.

Recall the formula for computing the average of n scores s₁, s₂,...,s_n:

average = (s₁ + s₂ + ... + s_n)/n

So if we have the following code:

(define avg (make-running-average))
(avg 70)
(avg 80)
(avg 90)

then the following will be produced:

70
75
80

Hint: the most elegant solution actually stores two local variables.

Iterating through a list

We want a function that takes no arguments and returns each element of some list in order, in successive calls. When there are no more elements in the list, the function should just return empty. Such a function is called an iterator for the given list. Write a function called make-iterator which consumes a list and produces a function which is an iterator for that list.

So the following code:

(define iterator (make-iterator (list 'a 'b)))
(iterator)
(iterator)
(iterator)

would produce the following:

'a
'b
empty