The evaluation of an expression in Scheme always yields a value. Some
expressions, however, have side effects -- incidental events that
occur whenever the expression is evaluated, more or less independently of
the computation and return of the expression's value. For example, output
is a side effect: when a display expression is evaluated, it
returns some unspecified value (in Chez Scheme,
#<void>), but it also causes the argument to be written
out.
When you're developing or debugging a program, you'll occasionally find it useful to add expressions with side effects to the procedures you write, in order to trace the sequence of events during the evaluation of a call to a complicated procedure.
Consider, for instance, the following procedure to add 2 to each element in a list:
(define add2
(lambda (ls)
(if (null? ls)
'()
(cons (+ (car ls) 2) (add2 (cdr ls))))))
Check that this procedure works correctly, by running it with the command
(add2 '(2 6 -3 0 4.689))
The add2 procedure is recursive, and we might want to
view the parameter ls each time that add2
is called. This can be accomplished by inserting calls to the
display and newline procedures, as follows:
(define parameter-labelled-add2
(lambda (ls)
(display "ls: ") ; Print a label for LS.
(display ls) ; Print out the current value of LS.
(newline) ; Start a new output line.
(if (null? ls)
'()
(cons (+ (car ls) 2) (parameter-labelled-add2 (cdr ls))))))
Run this revised procedure with the same data you used previously, by typing
(parameter-labelled-add2 '(2 6 -3 0 4.689))
Study and account for the side effects of evaluating this expression.
How does the output from parameter-labelled-add2 change if a
second call to the newline procedure is added, immediately
after the first? Explain the format of the output.
What happens if the lines
(display "ls: ") (display ls) (newline)
are moved from immediately before the if expression to
immediately after it? Explain the format of the output.
What happens if the calls to display and newline
appear both before and after the if
expression?
The body of the parameter-labelled-add2 procedure consists of
four separate commands that are executed sequentially: Scheme guarantees
that the side effects of the display and newline
procedure will occur in the order in which those commands appear in the
procedure definition.
This need to execute several steps in sequence arises frequently in Scheme.
If the steps make up the body of a procedure, as in the preceding example,
or if they follow the test inside a cond-clause, it is
sufficient just to write the commands one after another; this construction
is sometimes referred to as an implicit begin. Scheme also
provides an explicit begin expression that groups a sequence
of commands into one large command and causes them to be executed as a
group, but in the specified order. Such an expression might be needed if
the sequence of commands forms the consequent or the alternative of an
if-expression:
(if (on-fire? 'house)
(begin
(go-outside)
(place-telephone-call 'fire-department))
(begin
(get 'potato-chips)
(turn-on 'tv)))
The syntax of an if=expression requires that the consequent be
a single expression, not a sequence of expressions, and that the
alternative, if present, also be a single expression. The
begin combines the sequence of commands into a single
expression, as required.
As a further example, consider the following modification of
add2.
(define exits-labelled-add2
(lambda (ls)
(display ls)
(if (null? ls)
(begin
(display " then clause")
(newline)
'())
(begin
(display " else clause")
(newline)
(cons (+ (car ls) 2) (exits-labelled-add2 (cdr ls)))))))
Run this revised procedure with the same data:
(exits-labelled-add2 '(2 6 -3 0 4.689))
Explain the format of the output.
Section 2.5 of the textbook describes how to use output side effects to
trace the execution of a procedure. By writing and invoking
special-purpose entering and leaving procedures
to print the output, one can keep track of the various recursive
invocations of the procedure, the successive values of its parameters,
and the values it returns. Here's how it would work for
add2:
(define entering
(lambda (procedure-name parameter)
(display "Entering procedure ")
(display procedure-name)
(display " with parameter ")
(display parameter)
(newline)))
(define leaving
(lambda (procedure-name result)
(display "Leaving procedure ")
(display procedure-name)
(display " with result ")
(display result)
(newline)
result))
(define fancy-add2
(lambda (ls)
(entering 'fancy-add2 ls)
(if (null? ls)
(leaving 'fancy-add2 '())
(leaving 'fancy-add2
(cons (+ (car ls) 2) (fancy-add2 (cdr ls)))))))
> (fancy-add2 '(2 6 -3 0 4.689))
Entering procedure fancy-add2 with parameter (2 6 -3 0 4.689)
Entering procedure fancy-add2 with parameter (6 -3 0 4.689)
Entering procedure fancy-add2 with parameter (-3 0 4.689)
Entering procedure fancy-add2 with parameter (0 4.689)
Entering procedure fancy-add2 with parameter (4.689)
Entering procedure fancy-add2 with parameter ()
Leaving procedure fancy-add2 with result ()
Leaving procedure fancy-add2 with result (6.689)
Leaving procedure fancy-add2 with result (2 6.689)
Leaving procedure fancy-add2 with result (-1 2 6.689)
Leaving procedure fancy-add2 with result (8 -1 2 6.689)
Leaving procedure fancy-add2 with result (4 8 -1 2 6.689)
(4 8 -1 2 6.689)
This works, but it's a nuisance to insert the calls to
entering and leaving. Chez Scheme provides a
built-in tracing facility that gives you the same information and is much
easier to use. Here's the idea: If you replace the keyword
define in a procedure definition with the keyword
trace-define, Chez Scheme will generate a line of output when
it enters or leaves the procedure:
(trace-define traced-add2
(lambda (ls)
(if (null? ls)
'()
(cons (+ (car ls) 2) (traced-add2 (cdr ls))))))
> (traced-add2 '(2 6 -3 0 4.689))
|(traced-add2 (2 6 -3 0 4.689))
| (traced-add2 (6 -3 0 4.689))
| |(traced-add2 (-3 0 4.689))
| | (traced-add2 (0 4.689))
| | |(traced-add2 (4.689))
| | | (traced-add2 ())
| | | ()
| | |(6.689)
| | (2 6.689)
| |(-1 2 6.689)
| (8 -1 2 6.689)
|(4 8 -1 2 6.689)
(4 8 -1 2 6.689)
Each ``entering'' line reproduces the procedure call, with the value of the parameter written out in the argument position. Each ``leaving'' line shows the value returned by the procedure call. The vertical bars at the left-hand side are designed to help you connect the ``entering'' line for a particular procedure call to the ``leaving'' line for the same call.
There's one exception to this pattern. It often happens that two successive ``leaving'' lines would necessarily be exactly alike, because the procedure being traced simply returns the result of a recursive call without performing any more computation on it. In this situation, Chez Scheme will print only one ``leaving'' line even when there are two or more matching ``entering'' lines.
For example, suppose you trace the textbook's procedure for recovering the last item from a non-empty list (Program 2.2, page 47):
(trace-define last-item
(lambda (ls)
(cond ((null? (cdr ls)) (car ls))
(else (last-item (cdr ls))))))
If ls has more than one element, its last item is same as the
last item of its cdr, so after the last item of the cdr has been recovered,
there's no more computation to do. Here's what a typical trace of this
procedure looks like:
> (last-item '(3 1 4 1 5 9 2 6 5)) |(last-item (3 1 4 1 5 9 2 6 5)) |(last-item (1 4 1 5 9 2 6 5)) |(last-item (4 1 5 9 2 6 5)) |(last-item (1 5 9 2 6 5)) |(last-item (5 9 2 6 5)) |(last-item (9 2 6 5)) |(last-item (2 6 5)) |(last-item (6 5)) |(last-item (5)) |5 5
There is only one ``leaving'' line for all nine ``entering'' lines, because the ``leaving'' lines would all necessarily show the same value.
Here is a definition of a procedure called iota that takes
any non-negative integer upper-bound as argument and returns a
list of the non-negative integers strictly less than
upper-bound, in ascending order:
(define iota
(lambda (upper-bound)
(iota-kernel 0 upper-bound)))
(define iota-kernel
(lambda (so-far upper-bound)
(if (= so-far upper-bound)
'()
(cons so-far (iota-kernel (+ so-far 1) upper-bound)))))
Use trace-define to turn on tracing for iota and
iota-kernel. Trace the call (iota 7).
The factorial of a given positive integer is the product of all
the positive integers less than or equal to it. For instance, the
factorial of 5 is 1 * 2 * 3 * 4 * 5, or 120. Write a Scheme procedure that
computes the factorial of a given positive integer. Trace the call
(factorial 12).
The binomial coefficient C(n, k) of a pair of
natural numbers n and k is equal to 0 if n <
k, and to 1 if k is 0 or if n = k; in any other
case,C(n, k) = C(n - 1, k - 1) +
C(n - 1, k). Write a Scheme procedure
binomial that computes the binomial coefficient of two given
natural numbers. Trace the call (binomial 5 2).
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/side-effects.html
created February 12, 1997
last revised June 21, 1998
Henry Walker (walker@math.grin.edu) and John David Stone (stone@math.grin.edu)