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

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sat Apr 26 18:49:32 EDT 2008

Amen!

On Apr 26, 2008, at 4:22 PM, Benjamin L. Russell wrote:

>
>
> --- 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



Posted on the users mailing list.