subroutine stack and C machine model

[Frank]

In Dread Ink, the Grave Hand of Stefan Ram Did Inscribe:

The »Kellerspeicher« was invented and patented in 1957 by
the German Friedrich Ludwig Bauer. So this concept was
first named by a German word.

http://en.wikipedia.org/wiki/Stack_(data_structure)

The term »stack« (»Stapel«) was coined later, and Bauer was
reported to have said, that he actually prefered it to his
original term, IIRC.

One reference is

Sequential Formula Translation
K. Samelson and F. L. Bauer
Communications of the ACM
Volume 3, Issue 2 (February 1960)
Pages: 76 - 83
ISSN:0001-0782

Thanks Stefan, I read up on setjmp and longjmp last night and came pretty
close to not understanding anything. Plauger does state that the only way
to make it work from C is to use assembler, which I never really knew and
haven't touched for decades. Thus, much of the technical material for the
topical part of this thread is beyond OP's ability.

I don't think the word "stack" appears in K&R.
--
Frank

[Roger Ailes, Fox News Founder, Chairman and CEO, and former
Nixon-Reagan-Bush strategist, is] a cynical Republican ideologue with no
regard for fairness and balance.
~~ Al Franken,

 

[Frank]

In Dread Ink, the Grave Hand of Richard Heathfield Did Inscribe:

When was the last time he displayed even the slightest interest in C
programming? If ever? The group wastes a lot of its time being
distracted by irrelevant non-entities such as KM, AT, and RNSN. I
suggest that this time would be better spent discussing (or even
actually using!) the C language.

<snip>

At the risk of sounding ignorant, I don't know who K**, A**, or R** is.

Furthermore, I think that if you solve the problem of gas costing the US
govt $400 a gallon in Afghanistan, you eliminate these wretched, rapacious,
psychopathic corporations which plague what used to be democracy.

 

[Frank]

In Dread Ink, the Grave Hand of Phil Carmody Did Inscribe:

And if it's not intended to be female, it's a cradle reduplication,
and thus implicitly diminutive and thus disrespectful.

It's just another one of his inane ticks. That's what killfiles
were invented for.

Phil

You have extraordinary linguistic insights, Phil.

Certainly you wouldn't contend that a killfile contains Han when he's got
something to say.
--
Frank

And just like in 1984, where the enemy is switched from Eurasia to
Eastasia, Bush switched our enemy from al Qaeda to Iraq. Bush's War on
Terror is a war against whomever Bush wants to be at war with.
~~ Al Franken,

 

[Frank]

In Dread Ink, the Grave Hand of Keith Thompson Did Inscribe:

Drop the comma operator and you're probably right.

Let me seed srand with the above and see how things turn out.
--
Frank

...................... o _______________ _,
` Good Morning! , /\_ _| | .-'_|
`................, _\__`[_______________| _| (_|
] [ \, ][ ][ (_|

 

[Frank]

In Dread Ink, the Grave Hand of James Dow Allen Did Inscribe:

It can also be used as a carefree man's backtracker as at
   http://james.fabpedigree.com/rrome.htm
where the calls occur from the following macros:

#define EITHER        if (S[1] = S[0], ! setjmp((S++)->jb)) {
#define OR            } else EITHER
#define REJECT        longjmp((--S)->jb, 1)
#define END_EITHER } else REJECT;

Just a word of warning: the behaviour of the above is undefined due to
the severe limits placed on the way setjmp can be called.

Thanks for this, Ben! Although the code *does*
seem to work on at least a few different platforms,
I've wondered whether this might just be a lucky
happenstance due in part to the fact that the
function is otherwise rather tame.

Basically you can have nothing more complex than !setjmp(...) or
setjmp [relational or equality op] [integer constant expression] as
the controlling expression of an if/switch/while/for/do.

One simple change I could make would be to
move the comma operator to inside the setjmp
argument, i.e. replace
if (S[1] = S[0], ! setjmp((S++)->jb)) {
with
if (! setjmp((S[1] = S[0], (S++)->jb))) {

Would this solve the problem?

The comma operator isn't just a fetish here,
but seemed essential to the "smoothness" of
these macros in the presence of "else".
If we insist, for some reason, on not using
the comma operator *at all*, a workaround may
be harder, assuming we reject an approach like:
/* which END_EITHER to use depends on number of OR's */
#define END_E1 } else REJECT; }
#define END_E2 } else REJECT; }}
#define END_E3 } else REJECT; }}}
#define END_E4 } else REJECT; }}}}
#define END_E5 } else REJECT; }}}}}
#define END_E6 } else REJECT; }}}}}}
Perhaps there's a clever solution based on some
" do { ... break ...} while()" construct, but I'll
leave that as an exercise.

Another interesting puzzle -- solution for which
would be embarrassing for me, but perhaps not overly
surprising -- is to redesign the macros to avoid
setjmp/longjmp altogether. (I would not consider a
solution "valid" in this sense if its overall
complexity increases, or if threads or fork()s
are substituted for the setjmp()s.)

Feel free to deprecate my code! Much of my C coding
is for my own amusement; code I've delivered to
paying customers has never been this bizarre.

Ben.

James Dow Allen

My understanding is that if it looks like C, then setjmp and longjmp are
useless.

 

[Ben Bacarisse]

In Dread Ink, the Grave Hand of James Dow Allen Did Inscribe:

It can also be used as a carefree man's backtracker as at
   http://james.fabpedigree.com/rrome.htm
where the calls occur from the following macros:

#define EITHER        if (S[1] = S[0], ! setjmp((S++)->jb)) {
#define OR            } else EITHER
#define REJECT        longjmp((--S)->jb, 1)
#define END_EITHER } else REJECT;

Just a word of warning: the behaviour of the above is undefined due to
the severe limits placed on the way setjmp can be called.

One simple change I could make would be to
move the comma operator to inside the setjmp
argument, i.e. replace
if (S[1] = S[0], ! setjmp((S++)->jb)) {
with
if (! setjmp((S[1] = S[0], (S++)->jb))) {

My understanding is that if it looks like C, then setjmp and longjmp are
useless.

What is the code that James posted a link to if not a use of setjmp
and longjmp? In my view, it is not only use of them, but an
interesting one.

 

[Phil Carmody]

In Dread Ink, the Grave Hand of Phil Carmody Did Inscribe:

You have extraordinary linguistic insights, Phil.

Not compared with many of the linguists that I hang around with.
And they're not real insights if they came from a book, which most of
them did.

Certainly you wouldn't contend that a killfile contains Han when he's got
something to say.

In order to contend something about a killfile, I'd need to know
something about that killfile. As you've not specified which killfile
you're talking about, nothing more can be said. I know my killfile
contains Han; I don't remember seeing anything that enriched my usenet
experience from him before I killfiled him, the probability that I
have missed anything interesting since is minimal.

Phil

 

[spinoza1111]

I'm not quite sure, but I think the answer is no.  Unless I don't
understand what you mean by a subroutine stack, in which case the
answer is probably no.

The word "stack" does not appear in the standard because whenever
American computer scientists get together they bitch and moan about
stacks, because they didn't invent the concept. As a result, the
standard fails to describe the semantics of C except in a weird
negative way, and this was by design: the intent of the standard was
profit preservation on behalf of vendors who'd laid off compiler
developers and had no intent to rehire them.

I don't think I understand.  If you're wondering about breaking the
calling sequence, consider setjmp()/longjmp().

Seebach, I suggest you take a longjmp. Using these legacy features is
far worse than anything your target Schildt ever suggested, and it is
deeply dishonest of you to recommend their use to a newbie while
condemning Schildt (and making a vulgar joke out of his family name)
for far less serious errors.

The "execution register" does not "amount to a stack". As in the case
of the standard, you are UNABLE to explain something so simple as a
stack to a newbie who needs this information. Because of this
deficiency, you attacked Schildt in a jealous and destructive rage.

 

[spinoza1111]

As the standard says nothing about stack you casn savely assume that
there is not known by C what a stack is, how it is used (when there is
one). The same is for heap.


You can savely assume that the abstract mashine uses something that
makes recursive calls possible but it lefts it open to the
implementation how that will go on.


The abstract mashine knows nothing about registers, stack(s), heap(s).
So it is left to the implkementation to use registers, stack(s),
heap(s) in a manner the real environment the implementation runs under
does (not) implement them.

For portability you can savely assume that the implementation your
program runs under knows how to send arguments to functions it has to
call in a manner as if there were something you would call a stack
(even it is not such thing as a stack available), in a hosted
environment there will be something that works like a heap regardless
of there is something that is a heap or not and that the
implementation knows how to handle general purpose or special
registers if the implementation knows of such things.

Again: the abstract mashine knows nothing about register(s), stack(s),
heap(s) - it is on the implementation to use them if they exists.

Doesn't your abstract mashine have spellcheck, mein Herr?

Undt grammar?

Seriously, if you want to be taken seriously...

I don't think you know what an abstract "mashine" is, mein Gnadige
Herr. I think like a lot of software managers, you think it's
something that knows nothing, is nothing, and cannot be spoken of,
because in MBA skewl you learned that "abstract" means "not important,
academic, don't worry about it".

Like most MBA types you think you can speak of it abstractly because
it is abstract, and you deny people who know more than you the right
to speak with your insulting and Fascistic attacks.

Any "abstract" machine in computer science has in fact a precise
description, often more precise than actual machines which may suffer
from hardware defects and timing failures. And all modern abstract
machines feature a stack or are powerful enough to simulate a stack
(all stack automata can be simulated by Turing machines: this was
proven in 1970).

 

[Clot Hears]

The word "stack" does not appear in the standard because whenever
American computer scientists get together they bitch and moan about
stacks, because they didn't invent the concept. As a result, the
standard fails to describe the semantics of C except in a weird
negative way, and this was by design: the intent of the standard was
profit preservation on behalf of vendors who'd laid off compiler
developers and had no intent to rehire them.

Seebach, I suggest you take a longjmp. Using these legacy features is
far worse than anything your target Schildt ever suggested, and it is
deeply dishonest of you to recommend their use to a newbie while
condemning Schildt (and making a vulgar joke out of his family name)
for far less serious errors.

The "execution register" does not "amount to a stack". As in the case
of the standard, you are UNABLE to explain something so simple as a
stack to a newbie who needs this information. Because of this
deficiency, you attacked Schildt in a jealous and destructive rage.

Another content-free post from Spinny. Syntactically correct for the
most part but with the usual zero semantics.

 

[Dik T. Winter]

>
> Seebach, I suggest you take a longjmp. Using these legacy features is
> far worse than anything your target Schildt ever suggested, and it is
> deeply dishonest of you to recommend their use to a newbie while
> condemning Schildt (and making a vulgar joke out of his family name)
> for far less serious errors.

Where did Seebach *recommend* the use of setjmp()/longjmp()? Do you have
a better place to look for something "that changes what happens in the
execution register"?

And, I would not call Frank a newby...

 

[Nick Keighley]

 spinoza1111 <[email protected]> wrote:

Another content-free post from Spinny. Syntactically correct for the
most part but with the usual zero semantics.

So why respond?

 

[spinoza1111]

Another content-free post from Spinny. Syntactically correct for the
most part but with the usual zero semantics.

What does that mean?

See the little phrases go
Watch their funny antics
The men who make them wiggle so
Are the teachers of semantics.

[Space Child's Mother Goose 1948]

I think you mean that you have a Master's degree...

"I have a Master's degree! In science!" - Ask Mister Science, Duck's
Breath Mystery Theater

....and can't understand the text in the class.

 

[spinoza1111]

...
 > > > Instead I'm trying to think of what might be useful, given that there
 > > > is an execution register, and that it amounts to a stack.  Does C have
 > > > a function that changes what happens in the execution register?
 > >
 > > I don't think I understand.  If you're wondering about breaking the
 > > calling sequence, consider setjmp()/longjmp().
 >
 > Seebach, I suggest you take a longjmp. Using these legacy features is
 > far worse than anything your target Schildt ever suggested, and it is
 > deeply dishonest of you to recommend their use to a newbie while
 > condemning Schildt (and making a vulgar joke out of his family name)
 > for far less serious errors.

Where did Seebach *recommend* the use of setjmp()/longjmp()?  Do you have
a better place to look for something "that changes what happens in the
execution register"?

Using the rule Seebach used on Schildt, I correctly, I think, construe
him as recommending a very bad and legacy practice without warning the
OP of its dangers, or of the fact that nearly all of these legacy
features, if considered for use, mean that the overall approach has
been sodomitical.

Seebach "jumped" Schildt for saying innocuous things by putting the
worst possible "construction" on them (selecting the worst possible
interpretation). So it's sauce for the gander to "jump" Seebach for
giving irresponsible and bug-creating advice here.

Nobody knew what the OP meant by the "execution register", least of
all the OP, since today, training in a real, solid assembly language
(whether for a real computer or a paper machine) is replaced by C
which can do assembly type tasks but only as an infantile disorder.

The OP needed in fact an accurate chalk-talk on the stack, and Navia
gave it to him despite being bullied by Rosenau, he of the fractured
English, a fractured English that results I think from contempt for
people and language. This is because not a "man" of you knows how to
explain runtime semantics without using a stack.

 

[James Dow Allen]

The word "stack" does not appear in the standard because...

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

 

[Keith Thompson]

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.

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

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.)

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.

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!)

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.

Knowing that call frames, or activation records, or whatever you
want to call them are managed in a LIFO manner is very useful in
understanding how C works. Assuming that call frames are allocated
contiguously in memory is not, but a lot of people seem to assume
that that's the only possible mechanism.

And those of us who point out that other mechanisms are (a)
possible, and (b) actually used in the real world are wrongly
accused of being excessively pedantic. (Certainly I'm pedantic;
I deny that I'm excessively so, at least in this case.)

 

[robertwessel2]

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.

No one objects to that. The C implementation is clearly obligated to
maintain the appearance of LIFO handling of automatic variables and
function calls. And with recursive calls of some types (specifically
those where you cannot eliminate the recursion in some fashion), a
LIFO structure of some sort seems inescapable for the implementation.

The problem is that almost always when someone asks about this, they
want to know how all this relates to the *hardware* stack (in fact the
title of this thread is "subroutine stack and C machine model"), and
they invariably mean stack in the hardware sense of a contiguous range
of memory pointed to by a register. The problem is that none of that,
or even most detail of whatever LIFO-like structure that may be
implemented for some compiled programs, is in any way meaningful from
the perspective of how C is defined. Not only is it irrelevant, it's
actually *wrong* in many cases. Consider the following code:

long fact(int f)
{
if (f==1)
return 1;

return f*fact(f-1);
}

What if the compiler is smart enough to do tail recursion
elimination? What is there to say about the "stack" in this case?
Logically, there are still function calls and local variables that
exist in a LIFO manner, but the reality would have *neither* of those.

Likewise, let's say someone claimed that evaluating: "i=j+1" involved
moving values into registers, adding, storing the results, etc. That
this happens on most machines in undeniable, but it's wrong to expect
it to always happen. The expression may be optimized away, you may be
running on a machine with a rich set of storage-to-storage
instructions, etc. But to give a newbie an expectation that there are
things called "registers" involved in this process, implying that it's
always true, may lead them to make incorrect assumptions about what is
going on.

If people who responded to "how does C work the stack?" answered in a
more conditional manner ("the C compiler maintains the appearance of a
LIFO for function calls and automatic variables, and this is commonly
implemented with [a hardware stack], but there is nothing in
particular required of that, and many things may be optimized
away...") there wouldn't be much of an objection. And exactly what do
you think a newbie is going to do with an understanding of how C's
stack works most of the time on x86?

 

[Seebs]

The word "stack" does not appear in the standard because whenever
American computer scientists get together they bitch and moan about
stacks, because they didn't invent the concept.

Your surrealism continues to amaze.

As a result, the
standard fails to describe the semantics of C except in a weird
negative way, and this was by design: the intent of the standard was
profit preservation on behalf of vendors who'd laid off compiler
developers and had no intent to rehire them.

You've said this before, but you've never provided even a tiny shred
of evidence -- even though I gave you multiple concrete counterexamples
to the claim.

Seebach, I suggest you take a longjmp. Using these legacy features is
far worse than anything your target Schildt ever suggested, and it is
deeply dishonest of you to recommend their use to a newbie while
condemning Schildt (and making a vulgar joke out of his family name)
for far less serious errors.

I'm not even sure I'm one of the people who uses the term in question,
but I really don't see what makes you care about it. Unless his whole family
writes C books, it seems a non-issue.

The "execution register" does not "amount to a stack". As in the case
of the standard, you are UNABLE to explain something so simple as a
stack to a newbie who needs this information. Because of this
deficiency, you attacked Schildt in a jealous and destructive rage.

Again, we can't help you fight your demons. See a therapist.

-s

 

[Seebs]

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.

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.

-s

 

[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.

No one objects to that.  The C implementation is clearly obligated to
maintain the appearance of LIFO handling of automatic variables and
function calls.  And with recursive calls of some types (specifically
those where you cannot eliminate the recursion in some fashion), a
LIFO structure of some sort seems inescapable for the implementation.

The problem is that almost always when someone asks about this, they
want to know how all this relates to the *hardware* stack (in fact the
title of this thread is "subroutine stack and C machine model"), and
they invariably mean stack in the hardware sense of a contiguous range
of memory pointed to by a register.  The problem is that none of that,
or even most detail of whatever LIFO-like structure that may be
implemented for some compiled programs, is in any way meaningful from
the perspective of how C is defined.  Not only is it irrelevant, it's
actually *wrong* in many cases.  Consider the following code:

long fact(int f)
{
   if (f==1)
       return 1;

   return f*fact(f-1);

}

What if the compiler is smart enough to do tail recursion
elimination?  What is there to say about the "stack" in this case?
Logically, there are still function calls and local variables that
exist in a LIFO manner, but the reality would have *neither* of those.

Likewise, let's say someone claimed that evaluating:  "i=j+1" involved
moving values into registers, adding, storing the results, etc.  That
this happens on most machines in undeniable, but it's wrong to expect
it to always happen.  The expression may be optimized away, you may be
running on a machine with a rich set of storage-to-storage
instructions, etc.  But to give a newbie an expectation that there are
things called "registers" involved in this process, implying that it's
always true, may lead them to make incorrect assumptions about what is
going on.

If people who responded to "how does C work the stack?" answered in a
more conditional manner ("the C compiler maintains the appearance of a
LIFO for function calls and automatic variables, and this is commonly
implemented with [a hardware stack], but there is nothing in
particular required of that, and many things may be optimized
away...") there wouldn't be much of an objection.  And exactly what do
you think a newbie is going to do with an understanding of how C's
stack works most of the time on x86?- Hide quoted text -

- Show quoted text -

The word "newbie" is a childish and demeaning term that contains
within its use the assumption that technical knowledge equals
maturity, when the reverse is true if technical knowledge
overspecializes and moronizes in the context of the corporation.

You're assuming that people cannot reason using models such as the
(old) practice in introductory computer science of presenting a
simplified paper machine without meaning to imply that real machines
are like paper machines in all respects.

The problem is that your teaching becomes a sort of Zen in which you
produce more negative than positive statements and this creates
mystification and confusion.

The students will develop mental models anyway since no matter what
Plato said, people cannot imagine the pure idea...not even in business
skewl, in which a bold attempt is made to purvey pure, unadulterated,
reine, zuivere bullshit.

They want to see it in terms of an actual instantiation because
Aristotle was right and Plato was wrong.

Why not show a canonical and non-optimized implementation of factorial
and talk about tail recursion and what compiler optimizers do at a
later time?