Section 2.5 of the textbook describes how to use output side effects to trace the execution of a procedure. For example, here's a procedure that takes a list of numbers and returns a list of their square roots:

(define sqrt-along-list
  (lambda (ls)
    (if (null? ls)
        '()
        (cons (sqrt (car ls)) (sqrt-along-list (cdr ls))))))

By writing and invoking special-purpose entering and leaving procedures to print the output, one can keep track of the various recursive invocations of this procedure, the successive values of the parameter ls, and the values it returns:

(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 sqrt-along-list
  (lambda (ls)
    (entering "sqrt-along-list" ls)
    (if (null? ls)
        (leaving "sqrt-along-list" '())
        (leaving "sqrt-along-list"
                 (cons (sqrt (car ls)) (sqrt-along-list (cdr ls)))))))

> (sqrt-along-list '(1 4 9 16 25 36))
Entering procedure sqrt-along-list with parameter (1 4 9 16 25 36)
Entering procedure sqrt-along-list with parameter (4 9 16 25 36)
Entering procedure sqrt-along-list with parameter (9 16 25 36)
Entering procedure sqrt-along-list with parameter (16 25 36)
Entering procedure sqrt-along-list with parameter (25 36)
Entering procedure sqrt-along-list with parameter (36)
Entering procedure sqrt-along-list with parameter ()
Leaving procedure sqrt-along-list with result ()
Leaving procedure sqrt-along-list with result (6)
Leaving procedure sqrt-along-list with result (5 6)
Leaving procedure sqrt-along-list with result (4 5 6)
Leaving procedure sqrt-along-list with result (3 4 5 6)
Leaving procedure sqrt-along-list with result (2 3 4 5 6)
Leaving procedure sqrt-along-list with result (1 2 3 4 5 6)
(1 2 3 4 5 6)

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 every time it enters the procedure and every time it leaves:

(trace-define sqrt-along-list
  (lambda (ls)
    (if (null? ls)
        '()
        (cons (sqrt (car ls)) (sqrt-along-list (cdr ls))))))

> (sqrt-along-list '(1 4 9 16 25 36))
|(sqrt-along-list (1 4 9 16 25 36))
| (sqrt-along-list (4 9 16 25 36))
| |(sqrt-along-list (9 16 25 36))
| | (sqrt-along-list (16 25 36))
| | |(sqrt-along-list (25 36))
| | | (sqrt-along-list (36))
| | | |(sqrt-along-list ())
| | | |()
| | | (6)
| | |(5 6)
| | (4 5 6)
| |(3 4 5 6)
| (2 3 4 5 6)
|(1 2 3 4 5 6)
(1 2 3 4 5 6)

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.

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

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

3. 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-1997/tracing.html