subroutine stack and C machine model

[Frank]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right. The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

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?

 

[Kenny McCormack]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right. The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

If you use the 's-word' in this newsgroup, you will be shunned.

Further, the hyper-literal minded, autistics/Asbergers patient types
here, don't do well with allegories. They are, as I'm sure Kiki will
tell you by and by, best avoided.

 

[Seebs]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

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.

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

-s

 

[Seebs]

Further, the hyper-literal minded, autistics/Asbergers patient types
here, don't do well with allegories.

I am assured by people who apparently give a flying **** that people
treating patients with autism prefer the phrase "people with autism" to
"autistics". The name of the syndrome, BTW, is "Asperger's".

However, it is not necessarily the case that people with various
autism-spectrum traits don't do well with allegories; if anything, many
of them do exceptionally well with allegories, because they are conscious
that the allegory is a tool for thinking about something, not the reality
of the thing described.

They are, as I'm sure Kiki will
tell you by and by, best avoided.

Doubtless. Certainly, if I were jealous of people who were much better
at something than I, it would make sense for me to tell other people to
avoid them.

-s

 

[Stephen Sprunk]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right. The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

It may help you to think of nested function calls in terms of an
abstract stack, and many/most implementations actually do use a stack
because that's a logical way to do things*. The Standard does not
require one to exist, though, and even if your implementation does have
one, you'd best not go looking for "the stack" or try to examine it
unless you want your code to be utterly non-portable.

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 have no idea what you mean by "execution register".

S

 

[jacob navia]

Frank a écrit :

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?
Yes

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right.

C assumes a stack, and if the machine has no
stack register it must be implemented in software.

The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

The standard doesn't say it explicitely but the structure of
the language assumes a stack.

If main alls initialize, and initialize calls malloc we have
a stack of

main
initialize
malloc

and when malloc finishes, the stack is popped and we are in
initialize. When initialize is finished we pop the stack
and we get into main again.

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?

It is unclear what you meanby "execution register".

 

[Nick Keighley]

I am assured by people who apparently give a flying **** that people
treating patients with autism prefer the phrase "people with autism" to
"autistics".  The name of the syndrome, BTW, is "Asperger's".

However, it is not necessarily the case that people with various
autism-spectrum traits don't do well with allegories; if anything, many
of them do exceptionally well with allegories, because they are conscious
that the allegory is a tool for thinking about something, not the reality
of the thing described.

interesting. I come across a lot of people that don't seem to get
allegories and metaphors. They confuse the metaphor with the thing.
What I call abstraction-blindness.

"you can think of electricity as a fluid..."
"is it a fluid?"
"well it can be a usful model, voltage is like..."
"but, is it *really" a fluid?"
"depends what you mean by \"is\""

Is there an an-autistic syndrome?

 

[Nick Keighley]

In
<8ab64971-735c-48af-8642-e79b03faa...@v15g2000prn.googlegroups.com>,

I don't think the C Standard either allows or prohibits any
allegories. It is strangely silent on the matter.

"O, there's nothing to be hoped for from her! she's as headstrong as
an allegory on the banks of the Nile"

 

[Keith Thompson]

Frank a écrit :

C assumes a stack, and if the machine has no
stack register it must be implemented in software.

[...]

To be clear, there must be some stack-like (last-in first-out)
data structure to implement the set of information necessary to keep
track of the currently active set of function calls. This stack can
be implemented in any of a number of ways. A contiguous hardware
stack with a dedicated register pointing to the top is the most
common implementation.

jacob, I presume that's what you meant. I'm not sure what you
mean by "stack register". Obviously there must be some mechanism
to keep track of the top of the stack, and a dedicated hardware
register is a common choice, but it's not required or implied that
it should be a register.

The problem, as we've discussed at great length many times, is that
the phrase "the stack" is often used to refer to a particular kind
of stack implementation, one that's very common but not universal.

It's interesting to note that the C Standard fully describes the
semantics of the language without using the word "stack".

The distinction between a contiguous hardware stack and an abstract
stack (i.e., anything that implements a last-in first-out data
structure) is critical here.

 

[Chris Dollin]

To be clear, there must be some stack-like (last-in first-out)
data structure to implement the set of information necessary to keep
track of the currently active set of function calls.

Nitpick: only if there's some recursion. Otherwise each function can
have its own static area for storing locals & return addresses.

If there's no recursion and no function-pointer variables, the compiler
could "just" inline everything!

 

[BGB / cr88192]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

in an abstract sense, one may exist (defined in terms of the function
calling sequence).
but, it need not be a HW stack...

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right. The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

C doesn't prohibit a graph representation either, only that I don't know of
any real implementations that do it this way.

for example, if opposed to having a linear stack (FIFO WRT function calls),
one instead has a linked-list of "call frames", where calling each function
creates a new frame and begins execution within this frame, and upon
completion returns to the parent frame.

in this case, for simple code it just happens to resemble the good old
familiar stack model.


now, where this would start to show itself, would be if one were to add a
feature, lets call it "call/cc", which would capture an object known as a
'continuation' and allow an inner function to 'call' back into the original
frame which executed the call/cc, and maybe from there actually call back
into the frame which called outwards, ...

(I decided against providing an example of this...).

but, at this point, even the conceptual model of the stack could shatter,
and the standard need not actually prohibit this sort of implementation.

(I may note here that newer versions of the JVM are actually implementing
this feature, granted, Java is not C...).

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?

"execution register" is not a standard term, one is stepping on thin ice
here...


but, as others have noted, there is setjmp/longjmp, which allow non-local
control-flow transfers (in a form that some other languages would term "exit
only continuations").

then the big "can of worms" would be if longjmp were allowed to actually
jump back into a place it previously jumped out of.

 

[Lew Pitcher]

in an abstract sense, one may exist (defined in terms of the function
calling sequence).
but, it need not be a HW stack...



C doesn't prohibit a graph representation either, only that I don't know
of any real implementations that do it this way.

for example, if opposed to having a linear stack (FIFO WRT function
calls), one instead has a linked-list of "call frames", where calling each
function creates a new frame and begins execution within this frame, and
upon completion returns to the parent frame.

This is, in essence, how the CODE/370 C compilers (on IBM's MVS and Z-OS
mainframe operating systems) build their code.

in this case, for simple code it just happens to resemble the good old
familiar stack model.


now, where this would start to show itself, would be if one were to add a
feature, lets call it "call/cc", which would capture an object known as a
'continuation' and allow an inner function to 'call' back into the
original frame which executed the call/cc, and maybe from there actually
call back into the frame which called outwards, ...

I don't understand your idea here. Are you exploring the sort of thing a
co-routine might do, or are you exploring the sort of thing recursion might
do?

In the case of recursion, the CODE/370 (and followon) compiler(s) would
allocate a new "call frame", and link it back to the old one. The new "call
frame" would handle the current (recursed) function invocation's local
memory requirements until that function terminates, then would be unlinked
and discarded, with the previous "call frame" being returned to prominence.
You get the effects (and limitations) of a hardware stack without actually
having a CPU-enforced hardware stack.

I can't say /how/ co-routines would work. I don't know of any example that
shows the switching between two functions without a function call (and thus
an implicit allocation of a new "call frame").

(I decided against providing an example of this...).

but, at this point, even the conceptual model of the stack could shatter,
and the standard need not actually prohibit this sort of implementation.

(I may note here that newer versions of the JVM are actually implementing
this feature, granted, Java is not C...).

[snip]
--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

 

[Keith Thompson]

Nitpick: only if there's some recursion. Otherwise each function can
have its own static area for storing locals & return addresses.

If there's no recursion and no function-pointer variables, the compiler
could "just" inline everything!

Meta-nitpick: In the abstract machine, the set of currently active
function calls does behave in a last-in first-out manner, even if
the implementation pre-allocates activation records and/or doesn't
take any action to deallocate them when they're no longer active.

An implementation in which a non-recursive program has a statically
allocated activation record for each function is just another example
where a "stack" (in the abstract sense) is implemented by a method
other than a classic contiguous hardware stack.

 

[BGB / cr88192]

This is, in essence, how the CODE/370 C compilers (on IBM's MVS and Z-OS
mainframe operating systems) build their code.

ok.


I don't understand your idea here. Are you exploring the sort of thing a
co-routine might do, or are you exploring the sort of thing recursion
might
do?

In the case of recursion, the CODE/370 (and followon) compiler(s) would
allocate a new "call frame", and link it back to the old one. The new
"call
frame" would handle the current (recursed) function invocation's local
memory requirements until that function terminates, then would be unlinked
and discarded, with the previous "call frame" being returned to
prominence.
You get the effects (and limitations) of a hardware stack without actually
having a CPU-enforced hardware stack.

I can't say /how/ co-routines would work. I don't know of any example that
shows the switching between two functions without a function call (and
thus
an implicit allocation of a new "call frame").

I was talking about 'continuations'.

http://en.wikipedia.org/wiki/Continuation

these don't traditionally exist in C-family languages, but are common in
many functional languages, including, for example, Scheme, ...


the main difficulty with them is that it is difficult to add them without
introducing a lot of "issues" (such as needing to use a heap-like structure
for call frames, deal with the issue that call frames may continue to exist
after a given function returns, ...).

none the less, I was mostly pointing out that they "could" be added to C,
which would more or less break a stack-centric mindset of the call/return
process (essentially replacing it with a graph structure).


or such...

 

[Herbert Rosenau]

I'm looking and talking about a lot of C that is new to me this
weekend. Does the abstract machine that is described in the standard
have a subroutine stack?

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.

I've heard before that one can imagine things as a stack, and that
wouldn't be wrong, but then again it wouldn't be right. The comment
I'm looking for is not what the standard prohibits in terms of
allegories.

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.

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?

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.


--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

 

[Herbert Rosenau]

C assumes a stack, and if the machine has no
stack register it must be implemented in software.

Rubbish!

Once more that the Naiva proves that he knows nothing about C.

No wounder that nobody trusts his commercial comiler.

The standard doesn't say it explicitely but the structure of
the language assumes a stack.

If main alls initialize, and initialize calls malloc we have
a stack of

main
initialize
malloc

No, there is no stack recommended.

and when malloc finishes, the stack is popped and we are in
initialize. When initialize is finished we pop the stack
and we get into main again.

No, there is nothing popped! There are more architectures around than
I86 and other OSes than mickysoft windows and its assumes. GBut Naiva
is naive enough to think that nothing exept windows on I86 exists.

Sztop to blame yourself by posting in clc!

Stop spamkming for your properitayry commercial product!

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

 

[Seebs]

That said, I'm fishing for an execution model that uses the above
functions.

I think they've been used in at least some programs to try to implement
coroutines and the like.

-s

 

[Ben Pfaff]

That said, I'm fishing for an execution model that uses the above
functions. Don't worry, I don't know much about it. I have Plauger's _The
Standard C Library_ for reference.

Sometimes they're used for error handling, e.g. in libpng:

When libpng encounters an error, it expects to longjmp back to your
routine. Therefore, you will need to call setjmp and pass your
png_jmpbuf(png_ptr). If you read the file from different routines, you
will need to update the jmpbuf field every time you enter a new routine
that will call a png_*() function.

See your documentation of setjmp/longjmp for your compiler for more
information on setjmp/longjmp. See the discussion on libpng error han-
dling in the Customizing Libpng section below for more information on
the libpng error handling. If an error occurs, and libpng longjmp's
back to your setjmp, you will want to call png_destroy_read_struct() to
free any memory.

if (setjmp(png_jmpbuf(png_ptr)))
{
png_destroy_read_struct(&png_ptr, &info_ptr,
&end_info);
fclose(fp);
return (ERROR);
}

The page at http://www.freetype.org/david/reliable-c.html is a
"paper" that describes this kind of design technique.

 

[Frank]

In Dread Ink, the Grave Hand of Seebs Did Inscribe:

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

These were the functions I was thinking of. We all understand that the
Standard says things and doesn't say things, and that this is one that it
says nothing about. I hope there will be no objections to topicality.
....and now that Han is back, I'll be interested in his opinion and
disappointed to read him giving himself as Keith.

That said, I'm fishing for an execution model that uses the above
functions. Don't worry, I don't know much about it. I have Plauger's _The
Standard C Library_ for reference.

P.J. must have been Heathfield's typing instructor

 

[Frank]

In Dread Ink, the Grave Hand of Herbert Rosenau Did Inscribe:

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.

Vielen Dank, Herbert.

Wie sagt man 'stack' auf Deutsch?
--
Frank

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