[plt-scheme] running an MzScheme debugger in Emacs?
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