[plt-scheme] running an MzScheme debugger in Emacs?

--- On Sun, 4/27/08, Matthias Felleisen <matthias at ccs.neu.edu> wrote:

> [snip]
> 
> Why does SICP suggest the use of debuggers early on?
> Because SICP  
> does NOT pay attention to the systematic construction of
> programs but  
> uses 'playful programming' to explore computational
> ideas (a new  
> epistemology).

Yes, "playful programming" is a good way to put it.  Another way to describe it (at least at some points in doing some of the exercises) is "programming-without-really-understanding-what-you-are-doing" (this may be what the sorcerer's apprentice on the cover is really doing in casting the lambda spell).

While the Foreword and Preface to the First Edition of SICP provide excellent motivational material (especially the reference to programming as a "procedural epistemology" in the latter), and the book can be very fascinating, there are at least some parts of some of the exercises that leave something to be explained.

For example, Section 1.2.1:  Linear Recursion and Iteration (see http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1) describes a linear iterative process for computing factorial, and provides a Scheme procedure for computing this process.  This linear iterative process employs tail recursion.  However, it is not described anywhere in this section that the real reason that the following recursive procedure:

--
(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
--

generates a linear iterative process that looks like the following (when given an argument of 6):

--
(factorial 6)

(fact-iter 1 1 6)

(fact-iter 1 2 6)

(fact-iter 2 3 6)

(fact-iter 6 4 6)

(fact-iter 24 5 6)

(fact-iter 120 6 6)

(fact-iter 720 7 6)

720
--

while the following also recursive procedure generates a linear recursive process that looks like the following (again, when given an argument of 6):

--
(factorial 6)

(*6 (factorial 5))

(*6 (*5 (factorial 4)))

(*6 (*5 (*4 (factorial 3))))

(*6 (*5 (*4 (*3 (factorial 2)))))

(*6 (*5 (*4 (*3 (*2 (factorial 1))))))

(*6 (*5 (*4 (*3 (*2 1)))))

(*6 (*5 (*4 (*3 2))))

(*6 (*5 (*4 6)))

(*6 (*5 24))

(*6 120)

720
--

is that fact-iter calls itself last in the control flow.  Control flow is left unexplained.

This caused great difficulty when taking the following recursive procedure to generate a linear recursive process to count change (see Section 1.2.2:  Tree Recursion (see http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2)):

--
(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))
--

and then writing a recursive procedure to generate a linear iterative process to count change.

Much later, while doing preparatory research on continuations for Continuation Fest 2008 (see http://logic.cs.tsukuba.ac.jp/~kam/Continuation2008/), I chanced upon the following code for computing factorial:

--
(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (if (< n 0)
      (display "Wrong argument!")
      (fac-times n 1)))
--

in the entry for "Tail recursion" at Wikipedia (see http://en.wikipedia.org/wiki/Tail_recursion).  The following sentence was pivotal:

--
As you can see, the inner procedure fac-times calls itself last in the control flow.
--

The explanation continued:

--
This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:

  call factorial (3)
   call fac-times (3 1)
    call fac-times (2 3)
     call fac-times (1 6)
      call fac-times (0 6)
      return 6
     return 6
    return 6
   return 6
  return 6

into the more space- (and time-) efficient variant:

  call factorial (3)
  replace arguments with (3 1), jump to "fac-times"
  replace arguments with (2 3), jump to "fac-times"
  replace arguments with (1 6), jump to "fac-times"
  replace arguments with (0 6), jump to "fac-times"
  return 6
--

I stared at the code for a few moments, and wondered why fac-times called itself last, and why it used an accumulator.

Suddenly, it dawned upon me that the real reason that fac-times used less stack space than the following code:

--
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
--

was the very fact that fac-times called itself last in the control flow!  This allowed the compiler or interpreter to optimize the computation into a tail recursive process.  Suddenly, the real relation between linear iterative processes, tail recursion, continuations, tail calls, and control flow made sense!

Had SICP stated the relation between tail recursion and control flow when first introducing the concept of a linear iterative process, I would probably have had a much easier time in writing a procedure to generate a linear iterative process for counting change.

Benjamin L. Russell