subroutine stack and C machine model

[spinoza1111]

Without necessarily taking sides in this debate, I'd
like to inject a note of sanity!  

The "call frames" (whatever they're called) of reentrant functions
in *any* programming language that supports such recursion will
*necessarily* form a stack.  That *stack* *might* be implemented
as a ring buffer or a list but it *will* be a stack conceptually;
and it may aid the student to understand this.

Sure, it's *possible* to impose some overly restrictive
hyper-technical definition of "stack", for no purpose except
to announce, pedantically, that the recursive call frame
... err ... stack(!) need not be a Stack(tm).  But noone's
interest is served by this, certainly not that of the student
looking for a *model* by which he can understand a programming
language.  (I had a useful model for learning C 30 years ago
and, whatever my detractors want to claim about my skill, it
*did* allow me to retire and raise my kids in a rose garden.
Had only The Standard(tm) been available to me for learning,
I would have stuck to other languages.)

Now, it probably *is* true, and this may be all the pedants
are trying to say, that the word "stack" is not defined
in The C Standard(tm).  Well, the word "bizarre" is probably
not defined there either, yet I need that word to describe
some of the pedantry seen in this ng.
(Present company excepted!)

Hope this helps.
James Dow Allen

Any one proof in mathematics is going to use a certain set of
techniques to the exclusion of others used in other possible proofs.
No real mathematician ever concludes that a student might understand a
proof but reason that this is the only way to prove the theorem. They
are as teachers instead delighted that the student "gets" it.

Whereas it's more characteristic of Fascists (yup, Fascists) to worry
about the teaching process to the extent of canceling classes (as in
arguments for California's Prop. 13 in 1976, which claimed that
California teachers were teaching Bad Things on the way to reducing
California's education system to what it is today: the worst in the
nation).

It's also characteristic of these Fascists (yup, Fascists) to sue
teachers as in the case of a Pace university class which sued its biz
skewl programming teacher for making them calculate Avogrado's number.
Homeys claimed that he was not teachin' them "practical business
programming" such as how to cover up referential loops in spreadsheets
when your boss is scamming derivatives on the side.

Mr. Allen, we're looking in my view at a generation of vipers here.
Our co-workers actually had to invent and to think on the job. Today,
these young whippersnappers might be called programmers, but in many
cases their jobs are so "rationalized" that they never actually code.
Instead, I'd guess that most of them sit around meetings trashing each
other and deciding how to ship the actual coding to Pondicherri or
Bangalore where people actually code, while making racist smart
remarks about Indians.

John Hennessy and his Risc kiddies dominated 1987 ACM ASPLOS. You
shuddha heard those boys on the stack: they hated the stack. Wirth was
there, and after Wirth made a brave defense of software stability and
safety as opposed to the Risc kiddies' childish obsession with
"speed" (itself a metaphor) I saw Wirth isolated and alone in the
middle of the hotel lobby.

RISC went on to lay an egg as we know. Not only did Intel continue to
dominate, RISC concepts as added to Pentiums merely made them more
CISC because (d'oh) RISC+CISC==CISC, not RISC. And oh yes, the
floating point bug happened, didn't it, although that is probably not
Hennessy's fault. It merely resulted from the insane stress on wrong
answers at a high but metaphorical speed.

The "stack" is not JUST a teaching tool. It also proves predictions
about what software will do, and this is something that Seebach et al.
seem loth to do.

 

[spinoza1111]

Of course.  I've made this point myself on numerous occasions.


The problem is that, although the word "stack" can be and commonly
is used to refer to any last-in first-out date structure, it's
also, in some contexts, used to refer specifically to a contiguous
hardware stack that grows in a specific direction in memory.
This is especially true when it's used in the phrase "*the* stack".

For example, I learned PDP-11 assembly language before I learned C.
That gave me a very specific idea of what "the stack" is.


Too many people assume that C requires the use of "the stack",
i.e., of a contiguous hardware stack managed via a dedicated CPU
register known as the "stack pointer".  And too many other people,
who should know better, seem to encourage this misconception.

No, the problem is that you believe that a "stack" is a "contiguous
region of storage, etc." It's not. It's just something accessed at one
end for reading and writing. If the runtime language is Chomsky type
2, it's a mathematical truth that a "stack" is needed to run your
code.

It would be great if you had a formal notation that replaced
visualization, because visualization implies that stack entries have
to have, over and above their last in first out access order, a
sequential geometry. But you do not use formal notation. Instead, you
say to teachers that they may not teach because their images may
confuse, like the worst type of Fascist (yes, Fascist) who is afraid
that teachers might give their students the wrong idea.

 

[spinoza1111]

What you say is totally correct.

The problem is that many people do not understand the word "stack" in
terms of an abstract data structure, but rather, as a fixed region of
memory in which all function arguments, call records, automatic variables,
and suchlike are stored with monotonically decreasing (or increasing)
addresses.

That, in fact, is the objection people have to Schildt's writing about
"the stack" -- that he specifically introduced a particular x86 memory
layout as "how C works", rather than introducing the abstract data
structure of a "stack".

The objection is not to the term itself, but to a particular interpretation
of it.  Basically, if someone refers to the call frames, etc., as "the
stack", the chances are about 9:1 that they think it's a single contiguous
region of memory with monotonically decreasing addresses, and this is not
a particularly good way to conceptualize it; it results in failures to
understand the much more complicated reality of call sequences and ABIs.

You have given no evidence for this inference. The fact is that
working people use mental models all the time without ever confusing
the properties of the model with the properties of reality.

The problem is that university education largely inculcates contempt
for actual work and workers.

There is no evidence in Schildt that he recommends using
incrementation to invalidly explore a stack, and there is evidence in
what you post that you are willing to recommend doing things like this
as when you recommended longjmp without mentioning that it is legacy.

Early programmers not only were able to factor out the accidents of a
data structure from its essence, they also created the modern "theory"
which was then expropriated by the professoriat and "Platonized". The
result? Computer science majors who can't program.

 

[Nick Keighley]

I'm not sure how an "abstract machine" can be said to have anything...
What colour is it?

Without necessarily taking sides in this debate, I'd
like to inject a note of sanity!  

doomed. doomed.

The "call frames" (whatever they're called) of reentrant functions
in *any* programming language that supports such recursion will
*necessarily* form a stack.  That *stack* *might* be implemented
as a ring buffer or a list but it *will* be a stack conceptually;
and it may aid the student to understand this.

"any programming language" has to exclude those that support
continuations and possibly co-routines. Event driven programs don't
look very stack-like either. Are occam or Ada programs entirely stack
based?

Now, it probably *is* true, and this may be all the pedants
are trying to say, that the word "stack" is not defined
in The C Standard(tm).  Well, the word "bizarre" is probably
not defined there either, yet I need that word to describe
some of the pedantry seen in this ng.
(Present company excepted!)

what they are trying to say is that needn't be a HARDWARE STACK in
contiguous memory with dedicated registers and instructions. When some
people say "the stack" this *is* what they mean. Read the rest of the
(sometimes bad-tempered) thread.

 

[Nick Keighley]

John Hennessy and his Risc kiddies dominated 1987 ACM ASPLOS. You
shuddha heard those boys on the stack: they hated the stack.

RISC machines don't have stacks? Is this the stack(1) "an abstract
data structure with LIFO semantics" or a stack(2) "a contiguous area
of memeory with a dedicated hardware register and dedicated
instructions"?

RISC went on to lay an egg as we know.

Your phone likely contains an ARM (Advanced Risc Machine) chip.

<snip>

I'd stick to the wooly subjects like marxist sociology if I were you.
You do so much better in them than subjects that require actually
knowing something about the subject you are discussing.

 

[spinoza1111]

RISC machines don't have stacks? Is this the stack(1) "an abstract
data structure with LIFO semantics" or a stack(2) "a contiguous area
of memeory with a dedicated hardware register and dedicated
instructions"?

They hated the stack, yet because of mathematical reality (the
connection between Chomsky Type 2 and the stack) they had to support
stacks.

Your phone likely contains an ARM (Advanced Risc Machine) chip.

<snip>

I'd stick to the wooly subjects like marxist sociology if I were you.
You do so much better in them than subjects that require actually
knowing something about the subject you are discussing.

Whatever. It sounds to me that your "knowledge" is corporate in
nature: an uncritical affirmation of technology that itself has to be
rejected to do technology. Part of it, for example, was the
"knowledge" of the 1960s: that "programming" was easy and was getting
easier.

 

[Dik T. Winter]

> The "call frames" (whatever they're called) of reentrant functions
> in *any* programming language that supports such recursion will
> *necessarily* form a stack.

Not necessarily if this means that the last called function is on top
of the stack while the last but one is just below that. You can keep
the last used frame of a function in some fixed memory and stack that
memory when the function is called again, so in a call sequence:
A(1) -> B(1) -> C -> B(2) -> D -> A(2)
the stack would contain on top A(1) and below that B(1) and nothing more.
A(1) is put on the stack when A(2) was called and B(1) when B(2) was
called.

 

[Dik T. Winter]

> The objection is not to the term itself, but to a particular interpretation
> of it. Basically, if someone refers to the call frames, etc., as "the
> stack", the chances are about 9:1 that they think it's a single contiguous
> region of memory with monotonically decreasing addresses, and this is not
> a particularly good way to conceptualize it;

Strange enough, the first machines I did program had a stack with *increasing*
addresses, it was ony when I encountered the PDP that I saw a machine where
it was commonly done differently.

 

[Dik T. Winter]

> RISC went on to lay an egg as we know. Not only did Intel continue to
> dominate, RISC concepts as added to Pentiums merely made them more
> CISC because (d'oh) RISC+CISC==CISC, not RISC. And oh yes, the
> floating point bug happened, didn't it, although that is probably not
> Hennessy's fault. It merely resulted from the insane stress on wrong
> answers at a high but metaphorical speed.

You have clearly no idea about the origin of the floating point bug.
(An error in two bits of the mask for the processor.)

 

[Dik T. Winter]

> There is no evidence in Schildt that he recommends using
> incrementation to invalidly explore a stack, and there is evidence in
> what you post that you are willing to recommend doing things like this
> as when you recommended longjmp without mentioning that it is legacy.

You are lying. Peter recommended *looking* at setjmp/longjmp as a routine
where the logical order of call unwinding was not performed (which he
understood was the original question).

 

[spinoza1111]

...
 > RISC went on to lay an egg as we know. Not only did Intel continue to
 > dominate, RISC concepts as added to Pentiums merely made them more
 > CISC because (d'oh) RISC+CISC==CISC, not RISC. And oh yes, the
 > floating point bug happened, didn't it, although that is probably not
 > Hennessy's fault. It merely resulted from the insane stress on wrong
 > answers at a high but metaphorical speed.

You have clearly no idea about the origin of the floating point bug.
(An error in two bits of the mask for the processor.)

No, I clearly fail to mistake the tree for the forest. Contempt for
correctness produced the floating point bug.

 

[spinoza1111]

...
 > There is no evidence in Schildt that he recommends using
 > incrementation to invalidly explore a stack, and there is evidence in
 > what you post that you are willing to recommend doing things like this
 > as when you recommended longjmp without mentioning that it is legacy..

You are lying.  Peter recommended *looking* at setjmp/longjmp as a routine
where the logical order of call unwinding was not performed (which he
understood was the original question).

Without mentioning its unsafety...its absurdity.

 

[Seebs]

You are lying.

Objection! Assumes facts not in evidence. An allegation of lying refers
to the writer's internal awareness.

We do not have evidence showing that spinoza1111 can comprehend simple
sentences reliably, therefore, it is not justified to accuse him of lying
when he reports things contrary to what other readers thought a sentence
meant.

Peter recommended *looking* at setjmp/longjmp as a routine
where the logical order of call unwinding was not performed (which he
understood was the original question).

Yes.

That said, I don't think the word "legacy" changes anything; I'm not aware
of any plans to discontinue those functions, and if you know what they are
for and how to use them, they may be reasonable choices. (It's worth noting
though that, in all the time I've been writing C, I don't think I've EVER
used them.)

-s

 

[Seebs]

In

Well, in the quote above Keith makes clear that he is describing a
misconception about what "the stack" is,

And it's been pointed out repeatedly that one of the reasons people complain
about Schildt's books is that he pushes that particular misconception...

-s

 

[Clot Hears]

Objection! Assumes facts not in evidence. An allegation of lying refers
to the writer's internal awareness.

We do not have evidence showing that spinoza1111 can comprehend simple
sentences reliably, therefore, it is not justified to accuse him of lying
when he reports things contrary to what other readers thought a sentence
meant.

He certainly can't produce them, that's for damn sure.

 

[Keith Thompson]

Blue, apparently.

<snip>

Blue. No, yell-- aaaaaauuuugggghhhhH!

 

[James Dow Allen]

The "call frames" (whatever they're called) of reentrant functions
in *any* programming language that supports such recursion will
*necessarily* form a stack.

Not necessarily ...
[snipped description of a *conceptual* stack
implemented in part with temporary caches].

Yes, I'd intended to cover such things when I wrote

That *stack* *might* be implemented
as a ring buffer or a list ...

(I should have added ", etc.")

But this is irrelevant to my main point, which is that
those learning C are looking for a useful *model*.

When John von Neumann defined 5 as (4 union {4}), he
didn't claim this was God's definition (or an ISO definition!);
it's just a useful *model* that allows insights or theorem
proofs. To claim that the "stack" model is unhelpful,
we'd have to believe that it would mislead the beginner
enough for him to write faulty programs. Would it?

Certainly there *are* programs which try to "know" about
C's stack. The infamous Internet fingerd-spoofer comes
to mind. But is it not farfetched to imagine a programmer
knowledgeable enough to write such a program without
realizing it is non-portable?

Any other examples of C programs (besides compilers and
debuggers) which try to "know" any details of "stack" layout?
I can think of one.

* * * * *

I shouldn't mention this, since it will be used against
my argument, but one that comes to mind is one of Bill Joy's
programs which, IIRC, actually had code something like
if (END < p || (int)p < 0)
; /* don't free autos and statics */
else
free(p); /* !!!!! */

Non-portable?
Don't waste time reciting the obvious.
Hideous code?
No doubt about it.
Horrible idea?
Absolutely.
Who would I hire to fix an imminent software disaster if the
choices were Bill Joy in his prime, or one of his detractors?
Bill Joy.

James Dow Allen

 

[spinoza1111]

And it's been pointed out repeatedly that one of the reasons people complain
about Schildt's books is that he pushes that particular misconception...

No, he does not. His use of the stack does not entail the stack having
any one particular layout.

 

[Keith Thompson]

Not necessarily if this means that the last called function is on top
of the stack while the last but one is just below that. You can keep
the last used frame of a function in some fixed memory and stack that
memory when the function is called again, so in a call sequence:
A(1) -> B(1) -> C -> B(2) -> D -> A(2)
the stack would contain on top A(1) and below that B(1) and nothing more.
A(1) is put on the stack when A(2) was called and B(1) when B(2) was
called.

I think you may be conflating the two different meanings of "stack".

Call frames for currently active functions do form a stack, in the
sense of last-in first-out data structure. Calling a function pushes
a new frame on the stack; returning from a function pops the top-most
frame. Even setjmp and longjmp maintain the stack discipline.

In the model you describe, this stack of call frames is not allocated
contiguously. It's still a logical stack. It's just not organized
as a contiguous hardware stack. You seem to have another stack-like
data structure that's something other than the call stack, but the
call stack is still there.

 

[spinoza1111]

Objection!  Assumes facts not in evidence.  An allegation of lying refers
to the writer's internal awareness.

We do not have evidence showing thatspinoza1111can comprehend simple
sentences reliably, therefore, it is not justified to accuse him of lying
when he reports things contrary to what other readers thought a sentence
meant.


Yes.

That said, I don't think the word "legacy" changes anything; I'm not aware
of any plans to discontinue those functions, and if you know what they are
for and how to use them, they may be reasonable choices.  (It's worth noting
though that, in all the time I've been writing C, I don't think I've EVER
used them.)

You would have been on Herb like a fly on shit had he so much as
mentioned these statements beyond merely mentioning their existence
for the same reason you deliberately and maliciously interpreted his
use of a concrete implementation of a stack as the belief that the
stack *must* have that layout. You consistently and wrongly assume
that people know computer science iff they use fashionable (non-
Microsoft) platforms and what this establishes is that you can't think
in difficult environments that don't pander to your prejudices.

Shibboleths replace listening. And when you are treated as you have
maligned Schildt you whine like a baby.

Navia was able to clarify the semantics in the best way to clarify
semantics, which is to present a concrete, mathematically
intuitionist, construction with clearly essential features (the LIFO
property) of a stack alongside accidents (its order and the
implementation of push and pop, which changes depending on the stack
layout).

You prefer to sound sage without informing or mentoring by saying what
is not the case, condemning your auditors to an ignorance which you
intend.

You need to remove your attack on Schildt and apologize to him.