subroutine stack and C machine model

"Frank" <> wrote in message
news:8ab64971-735c-48af-8642-...
> 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.

BGB / cr88192

On October 12, 2009 11:17, in comp.lang.c, BGB / cr88192
() wrote:

>
> "Frank" <> wrote in message
> news:8ab64971-735c-48af-8642-...
>> 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.

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

Lew Pitcher

Chris Dollin <> writes:
> Keith Thompson wrote:
>> 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!

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.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson

"Lew Pitcher" <> wrote in message
news:3fa4f$4ad34aac$cef8a40f$...
> On October 12, 2009 11:17, in comp.lang.c, BGB / cr88192
> () wrote:
>
>>
>> "Frank" <> wrote in message
>> news:8ab64971-735c-48af-8642-...
>>> 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.
>
> This is, in essence, how the CODE/370 C compilers (on IBM's MVS and Z-OS
> mainframe operating systems) build their code.
>

ok.

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

BGB / cr88192

On Mon, 12 Oct 2009 02:13:47 UTC, Frank <>
wrote:

> 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

On Mon, 12 Oct 2009 09:24:33 UTC, jacob navia <>
wrote:

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

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!

Herbert Rosenau

On 2009-10-13, Frank <> wrote:
> 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
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Seebs

Frank <> writes:
[setjmp, longjmp]
> 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.
--
"I don't have C&V for that handy, but I've got Dan Pop."
--E. Gibbons

Ben Pfaff

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

> On 2009-10-12, Frank <> wrote:

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

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

Whining is anger through a small opening.
~~ Al Franken

Frank

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

> On Mon, 12 Oct 2009 02:13:47 UTC, Frank <>
> wrote:
>
>> 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.

Vielen Dank, Herbert.

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

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

Frank