2.2 Tracing the Execution of a Recursive Definition

Most functional programming environments support traced execution of definitions. Next, we show the traced output of the Scheme version of sum.

> (trace sum)
#<unspecified>
> (sum 5)
"CALLED" sum 5
 "CALLED" sum 4
  "CALLED" sum 3
   "CALLED" sum 2
    "CALLED" sum 1
     "CALLED" sum 0
     "RETURNED" sum 0
    "RETURNED" sum 1
   "RETURNED" sum 3
  "RETURNED" sum 6
 "RETURNED" sum 10
"RETURNED" sum 15
15

If a programming environment does not support traced evaluation, it is straight forward to implement traced versions of recursive definitions. This is illustrated for the J version of sum.

traced_sum =: monad define script
entering y.
if. y. = 0
  do. leaving 0
  else. leaving y. + traced_sum y. - 1
end.
)

Program traced_sum (J Version)

The functions entering and leaving are defined as shown below.

entering =: 'Entering, input = '&trace
leaving =: 'Leaving, result = '&trace

trace =:  monad define script
display y.
:
display (format x.),format y.
y.
)

display =: 1 !: 2 & 2

Execution of traced_sum gives the following output.

   traced_sum 5
Entering, input = 5
Entering, input = 4
Entering, input = 3
Entering, input = 2
Entering, input = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Leaving, result = 3
Leaving, result = 6
Leaving, result = 10
Leaving, result = 15
15