[taos-glug] stack frames, and my answer to Exercise 1.9

It's obvious that it's going to take me a while to digest the
recent exchange between Jonathan and John on stack frames.

I've made some progress, though.  Hence this LONG message.

If you want to see my answer to Exercise 1.9, and the other online source
that I used to arrive at that answer, then skip to the end.

If you want to read my commentary, proceed.

==============================================================

The question in Exercise 1.9 is about "processes" as opposed to "procedures."

It still seems to me one needs to know more about the Scheme iterpreter than
we've been told so far in the book.   I don't see how you can tell, at the
level of Scheme source code, what's happening behind the scenes.

So, I think Exercise 1.9 is unanswerable IF you are just working through
SICP on your own.

However, if you bring in other information, such as what Jonathan and John
have provided, it puts the question in another context.

I don't claim to understand all of this stuff.   However,
I've seen what I think are related discussions elsewhere:  in another
book called "The Little Schemer" and in an email exchange I had a while
back with a guy at www.synthcode.com.   So we're into topics that a lot
of people think are important.

But I think our study group's problem is to come to terms with the book we
have, not to search all over the Internet for clues.

So, here's my somewhat simplistic and pragmatic take on what is being said
in SICP up to Exercise 1.9:

-  It is good to write recursive _procedures_ in Scheme.   That is to say,
   it is good to write _syntactically_ recursive procedures.

-  It is bad for non-Scheme languages to have iterative constructs, because
   they are unneeded "syntactic sugar."   (For example, a "for" loop in C
   is considered a "defect.")

-  It is good if a _process_ is iterative.

-  It is bad if a _process_ is recursive.

-  A syntactically recursive _procedure_ can correspond to an iterative
   _process_ IF the interpreter or compiler is a good one--that is to say,
   if it is tail-recursive.

Following are what I think are the two key paragraphs.   I think they need very
careful reading.   I'm not going to attempt a full exegesis, but I
do want to point out a couple of things.

(Just as an aside, it seems to me that in the relatively dry, academic
writing of these paragraphs, there are dramatic things being said.   I mean,
for heaven's sake, they tell C programmers that "for" loops are defects.   And
the term "syntatic sugar" seems to me to be loaded with disdain.   Are these
authors begging for a fight?  Are they insulting other academics?  Is it
a put-down to competing intellectuals like Bell Labs' Kernighan and
Ritchie?)

First, the key terms "process" and "procedure" LOOK quite similar.   I had to
discipline myself to distinguish them.

And I noted that there is a lack of parallelism in the authors' writing about
them.   In these paragraphs, the authors introduce the distinction by mentioning
process first and procedure second.   But the follow-up discussion reverses
that order.

In my opinion, we readers have to be very alert and attentive with these
authors.  I'm beginning to get accustomed to their way of writing, but
I still keep getting tripped up.

Second, there are some complications in their use of the terms "describe"
and "generate".   At first they talk about how "we describe" procedures
and processes, the "we" referring to themselves, I suppose.

Then they talk about writing a procedure that _generates_
an iterative process.   Later they talk about writing a procedure
that _describes_ an iterative process.

So they're using "describe" in two different ways.   Furthermore, right
in the middle of things, they change perspective between "generate" and
"describe" (that is, describe in its second sense).

Check me on this:

    In contrasting iteration and recursion, we must be careful not to
    confuse the notion of a recursive process with the notion of a
    recursive procedure.  When we describe a procedure as recursive, we
    are referring to the syntactic fact that the procedure definition
    refers (either directly or indirectly) to the procedure itself. But
    when we describe a process as following a pattern that is, say,
    linearly recursive, we are speaking about how the process evolves, not
    about the syntax of how a procedure is written. It may seem disturbing
    that we refer to a recursive procedure such as fact-iter as generating
    an iterative process. However, the process really is iterative: Its
    state is captured completely by its three state variables, and an
    interpreter need keep track of only three variables in order to
    execute the process.

    One reason that the distinction between process and procedure may be
    confusing is that most implementations of common languages (including
    Ada, Pascal, and C) are designed in such a way that the interpretation
    of any recursive procedure consumes an amount of memory that grows
    with the number of procedure calls, even when the process described
    is, in principle, iterative. As a consequence, these languages can
    describe iterative processes only by resorting to special-purpose
    ``looping constructs'' such as do, repeat, until, for, and while. The
    implementation of Scheme we shall consider in chapter 5 does not share
    this defect. It will execute an iterative process in constant space,
    even if the iterative process is described by a recursive
    procedure. An implementation with this property is called
    tail-recursive. With a tail-recursive implementation, iteration can be
    expressed using the ordinary procedure call mechanism, so that special
    iteration constructs are useful only as syntactic sugar.

Bottom line.  You've got to read very carefully.  I think I mostly understand
what these authors are saying here, but I don't know if it's entirely true, nor
whether I agree with it.

Off the top of my head, I would not say that it is obviously 
a "defect" to have different constructs to describe different processes (as
in C).   The alternative in Scheme is that one construct used in different
ways to describe different processes.   Which approach is better?  We'll see.

======================================================================
My answer to Exercise 1.9.

The first _procedure_ does NOT clearly _describe_ an iterative _process_.

The second _procedure_ DOES describe an iterative _process_.

What actually happens when the process executes is, in my opinion, an
open question.

However, because of what I've read elsewhere, I believe the second
procedure is written is such a way that a proper Scheme implementation
will turn it into an iterative process.   This is because the
"+" function is the very last thing in the procedure.

Besides what Jonathan and John wrote, I found clues to this answer in
"Teach Yourself Scheme in Fixnum Days."
http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-8.html#node_idx_308

So far, I've found that tutorial, "Teach Yourself Scheme in Fixnum
Days," to be helpful.

The SICP authors are very smart.   None of what I've written would be
accepted by them as a valid criticism of their book.   Looking back,
I see that they've been distinguishing between procedure and process all
along.   My mind just didn't register the difference properly.

Furthermore, they've got a disclaimer in the Preface to the first edition:
"We never formally teach the language, because we don't have to.   We just use
it, and the students pick it up in a few days."

Okay, so this means we have to pretend to be enthusiastic and brilliant
MIT freshmen in order to read this book.

Are we up to it?

Other related posts: