[plt-scheme] running an MzScheme debugger in Emacs?
Just for reference, I forgot to mention the recursive procedure that generated a linear recursive process for factorial in my previous post on this thread. It was as follows:
--
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
--
This generated the following linear recursive process (already described):
--
(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
--
Also, I left out accumulators in the following portion:
> Suddenly, the real relation between linear iterative
> processes, tail recursion, continuations, tail calls, and
> control flow made sense!
It should have read as follows:
--
Suddenly, the real relation between linear iterative processes, tail recursion, accumulators, continuations, tail calls, and control flow made sense!
--
Control flow is the common thread linking all these together, yet mention of it is somehow left out in 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) of SICP. The resultant "playful programming" then becomes programming-without-really-understanding-what-you-are-doing, or the sorcerer's apprentice's magic going amok.
Benjamin L. Russell
--- On Sun, 4/27/08, Benjamin L. Russell <dekudekuplex at yahoo.com> wrote:
> From: Benjamin L. Russell <dekudekuplex at yahoo.com>
> Subject: Re: [plt-scheme] running an MzScheme debugger in Emacs?
> To: "Prabhakar Ragde" <plragde at uwaterloo.ca>, "Matthias Felleisen" <matthias at ccs.neu.edu>
> Cc: "PLT Scheme List" <plt-scheme at list.cs.brown.edu>
> Date: Sunday, April 27, 2008, 5:22 AM
> --- 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
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme