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

From: Benjamin L. Russell (dekudekuplex at yahoo.com)
Date: Sat Apr 26 18:01:33 EDT 2008

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


Posted on the users mailing list.