[taos-glug] Re: stack frames

One problem w/ SICP is that it makes more assumptions about the reader
than it should.

That said, there is a pretty easy way to know if something is truly
recursive or not.

The reason you need to build up stack frames is NOT to call a function,
but to come back and finish a function.  For example, if I have a program:

sub foo()
{
int a, b

a = 3
b = 2

return multiply(a, b);
}

When I call multiply I do not need the stack frame.  Why?  A and B have
already been sent via the function call, and the result of the function
call needs no further processing, so it can be sent directly to the
function that called foo.  Let's look at the stack when we are running
foo:

calling function's return addy
foo's formal parameters (none in this case)
foo's locals - A and B

When we call multiply, since we don't need any of foo's locals or formal
parameters, we can DELETE it's stack frame and REPLACE it with multiply's
stack frame:

calling function's return addy
multiply's formal parameters (A and B)
multiply's locals - unknown

We didn't even have to include foo's return address because we're
returning the result directly to the calling function.

So, basically, if you call a function as the LAST part of a function, it
replaces the current stack frame.  If you do ANYTHING AT ALL with the
return value (add 1, multiply, ANYTHING), you have to keep your current
stack frame.  So if our function was

sub foo()
{
int a, b

a = 3
b = 2

return multiply(a, b) + 1;
}

It would not be able to replace the current stack frame, because we still
have to add 1 to the result of the multiply function before returning to
the calling function.  In this case our stack frame would look like:

calling function's return addy
foo's formal parameters (none in this case)
foo's locals - A and B
foo's return address
multiply's formal parameters (A and B)
multiply's locals - unknown

Let me know if that helps.

Jon

> You're right.  I'm frustrated.
>
> I don't know how to "prove" an answer to Ex. 1.9 one way or another.   That's
> what I meant by "cheating" with the "begin" and "display" statements.
>
> Lacking any insight about how to demonstrate a result by a convincing
> argument, I had hoped to be able to show something with brute force diagnostic
> printout.
>
> That didn't really work either.   I included my code and results below,
> but it probably isn't worth your while to look a them.   They don't really
> show anything:  the only real difference is that the calls are interleaved in
> the second one and not in the first.   I don't see how that that proves
> anything.
>
> I guess, in a practical situation, if I dumbly wrote unnecessarily recursive
> code, I'd eventually know something was wrong because the program would
> run out of memory or it would run very slowly.   Then, still lacking
> theoretical insight, I'd experiment with different methods until I got
> something that seemed to work.   It's a low-IQ approach, I'll admit, but it
> might be effective.
>
> The bottom line is that I don't want to get bogged down in SICP as I did
> last year. So I'm going to put this question aside for now.   Maybe
> later in the book, there will be an opportunity to revisit it with better
> insight.
>
> I'm thinking that, if SICP truly is a classic, then we need to give it the
> same full-bore reading effort that we would give to a literary or 
> philosophical
> classic.  It would be silly to give up on Hamlet after one try.   It might
> be that the first reading just makes you aware of what is being talked
> about.   Then it takes subsequent passes to understand it.
>
> On the other hand, I'm more willing to trust that Hamlet is a classic than
> SICP.
>
> Philip
>
> ===================================================================
>
> Here are my programs and results, but they're probably not interesting--or
> even intelligible--to anybody but me.   And they don't prove anything anyway.
>
> (define (inc c)
>   (begin
>     (display "returning from inc ")
>     (display (+ c 1))
>     (newline)
>     (+ c 1)))
>
> (define (dec c)
>   (begin
>     (display "returning fron dec ")
>     (display (- c 1))
>     (newline)
>     (- c 1)))
>
> (define (plus_1 a b)
>   (if (= a 0)
>     (begin
>       (display "returning from plus_1")(newline)
>       b)
>     (inc (plus_1 (dec a) b))))
>
> (display "(plus_1 4 5) = ") (display (plus_1 4 5)) (newline)
>
> (define (plus_2 a b)
>   (if (= a 0)
>       (begin
>       (display "returning from plus_2")
>       (newline)
>       b)
>       (plus_2 (dec a) (inc b))))
>
>
> (display "(plus_2 4 5) = ") (display (plus_2 4 5)) (newline)
>
>
> Results
> --------
>
> (plus_1 4 5) =
> returning fron dec 3
> returning fron dec 2
> returning fron dec 1
> returning fron dec 0
> returning from plus_1
> returning from inc 6
> returning from inc 7
> returning from inc 8
> returning from inc 9
> 9
> (plus_2 4 5) =
> returning fron dec 3
> returning from inc 6
> returning fron dec 2
> returning from inc 7
> returning fron dec 1
> returning from inc 8
> returning fron dec 0
> returning from inc 9
> returning from plus_2
> 9
>
>

Other related posts: