subroutine stack and C machine model

[Moi]

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.

The "logical" stack is not the only way to guarantee LIFO behavior, IMHO.

Imagine a message passing architecture, where each function is actually a
node in a network. A function starts living once it has received its
parameters, does the computations, and it can stop to exist once it has
sent it's return value.

This is of course silly, and maybe difficult to implement (eg. nodes need
to "block" once the perform a call to an other node and need to be woken
up once the callee returns), but is certainly doable, and will behave
*as if* a stack were involved. A stack is not needed to impose LIFO-order.

(global and static variables and longjumps are left as an exercise for
the reader ;-)

HTH,
AvK

 

[Flash Gordon]

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.

One of the processors I used to program (the first I programmed in C, in
fact), had a hardware stack in a very pure form. A call pushed the
return address on to the stack and a return popped it off. The only
other instuctions that allowed you to access it were the push
instruction (pushing a value on) and pop instuction (popping it off).
You literally could *not* read any item on the stack except by popping
items until you reached the one you wanted. This is very different from
hardware stacks on other processors, and is of no use for a lot of the
implementation of "call frames", i.e. you could not use it for local
variables.

It also had a number of index registers any of which *could* be used to
increment a contiguous stack, and there was nothing in the processor
that made it prefer growing in any particular direction.

 

[Keith Thompson]

The "logical" stack is not the only way to guarantee LIFO behavior, IMHO.

Imagine a message passing architecture, where each function is actually a
node in a network. A function starts living once it has received its
parameters, does the computations, and it can stop to exist once it has
sent it's return value.

This is of course silly, and maybe difficult to implement (eg. nodes need
to "block" once the perform a call to an other node and need to be woken
up once the callee returns), but is certainly doable, and will behave
*as if* a stack were involved. A stack is not needed to impose LIFO-order.

I'd say that's still a logical stack. In fact, I'd say that a logical
stack is *by definition* something with LIFO semantics.

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

 

[Moi]

I'd say that's still a logical stack. In fact, I'd say that a logical
stack is *by definition* something with LIFO semantics.

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

Well, given the presumptions
1) a function can not execute before it has obtained its arguments
2) a function can not return a value to it's caller before it has
finished its computations.
3) a caller cannot continue ("is blocked") until the callee has returned
its value.

I can see no stack (abstract or concrete) in the above, only ordered
events.
As an execution model (for a single processor machine) it is still silly,
of course.

AvK

 

[Moi]

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

[I forgot something]

Well, for instance in the pseudo-program

***/

int fa(int a);
int fb(int a, int b); /* not shown, but recurses back to fa() or fb() */

int fa(int a)
{
int r;

r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;

return r;
}

**/

, the two function calls to fa() _could_ be executed in parallel (without
changing the semantics of "function call"), which would be hard
(impossible ?) using a "linear" stack. (they could finish in the wrong
order, leaving "holes" in the stack or fifo)

[ disclaimers about side-effects, etc ... ]

AvK

 

[Keith Thompson]

Well, given the presumptions
1) a function can not execute before it has obtained its arguments
2) a function can not return a value to it's caller before it has
finished its computations.
3) a caller cannot continue ("is blocked") until the callee has returned
its value.

I can see no stack (abstract or concrete) in the above, only ordered
events.

Really? Consider the set of currently active function calls. There
has to be some kind of activation record for each active call; if
there are two pending calls to foo(), there are two corresponding
activation records. Activation records enter and leave this set in a
strictly last-in first-out manner. (Whether they're actually
allocated as the enter the set an deactivated when they leave it is
another question; if an activation record isn't actually deallocated
when the function returns, it becomes garbage.) So how is that not a
stack?

 

[Keith Thompson]

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

[I forgot something]

Well, for instance in the pseudo-program

***/

int fa(int a);
int fb(int a, int b); /* not shown, but recurses back to fa() or fb() */

int fa(int a)
{
int r;

r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;

return r;
}

**/

, the two function calls to fa() _could_ be executed in parallel (without
changing the semantics of "function call"), which would be hard
(impossible ?) using a "linear" stack. (they could finish in the wrong
order, leaving "holes" in the stack or fifo)

[ disclaimers about side-effects, etc ... ]

Ah, but in the C abstract machine they *can't* be executed in parallel
(though a C implementation can do so if and only if it doesn't affect
the visible behavior).

 

[Moi]

Moi <[email protected]> writes: [...]

Well, given the presumptions
1) a function can not execute before it has obtained its arguments 2) a
function can not return a value to it's caller before it has finished
its computations.
3) a caller cannot continue ("is blocked") until the callee has

Oops, I should have said: "... until *all* the callees have"

Really? Consider the set of currently active function calls. There has
to be some kind of activation record for each active call; if there are
two pending calls to foo(), there are two corresponding activation
records. Activation records enter and leave this set in a strictly
last-in first-out manner. (Whether they're actually allocated as the

In the "networked" model, there is no additional ordering needed; only
the partial ordening I sketched. The semantics stay the same, given no
side-effects, etc.

AvK

 

[Moi]

Ah, but in the C abstract machine they *can't* be executed in parallel
(though a C implementation can do so if and only if it doesn't affect
the visible behavior).

Yes I know. I only needed the parallelism to illustrate my point.
If only one (sub)function-call is pending, a linear stack (or some other
LIFO behavior) is adequate. In the abstract sense, only partial
("causal") ordering is needed.

On a really networked model (each node having it's own addres space)
, the "activation records" and "return values" are only messages floating
around, with no particular address or ordering thereof.

HTH,
AvK

 

[Dik T. Winter]

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

But there is something more: the call frame for a function can move from
one place to another (from the static section to the hardware stack).

 

[Phil Carmody]

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

I consider ARM to be at least as CISC as any processor out there.
They've got the RISC decoding (which might be considered the single
most important aspect), but everything else smacks of C not R.

Phil

 

[Phil Carmody]

Moi <[email protected]> writes: [...]

behave *as if* a stack were involved. A stack is not needed to impose
LIFO-order.

I'd say that's still a logical stack. In fact, I'd say that a logical
stack is *by definition* something with LIFO semantics.

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

(global and static variables and longjumps are left as an exercise for
the reader ;-)

Well, given the presumptions
1) a function can not execute before it has obtained its arguments
2) a function can not return a value to it's caller before it has
finished its computations.
3) a caller cannot continue ("is blocked") until the callee has returned
its value.

I can see no stack (abstract or concrete) in the above, only ordered
events.

Really? Consider the set of currently active function calls. There
has to be some kind of activation record for each active call; if
there are two pending calls to foo(), there are two corresponding
activation records. Activation records enter and leave this set in a
strictly last-in first-out manner. (Whether they're actually
allocated as the enter the set an deactivated when they leave it is
another question; if an activation record isn't actually deallocated
when the function returns, it becomes garbage.) So how is that not a
stack?

int outer() { return inner1()+inner2(); }

There's nothing to stop all three functions from being active
simultaniously. There's no order between inner1 and inner2, there's
no last in to be first out.

I've designed and programmed dataflow languages for which this makes
perfect sense to simplify the design, even if everything did become
serial in the end. (And the intention was sometimes to hive off
subtasks to DSPs and accelerators, and the abstractness of the original
design kept such options trivial to enable or disable.

Phil

 

[spinoza1111]

int outer() { return inner1()+inner2(); }

There's nothing to stop all three functions from being active
simultaniously. There's no order between inner1 and inner2, there's
no last in to be first out.

Change the plus sign to minus or divide.

 

[Ben Bacarisse]

Change the plus sign to minus or divide.

That makes no difference to the point being made.

<snip>

 

[Phil Carmody]

That makes no difference to the point being made.

Yeah. What's he on? He should either increase or decrease
his dosage.

I would rather everyone killfiled spinoza, rather than wasting
their time responding to him. I certainly don't feel that my
posts need defending from his nonsensical bilge.

Doffing hat nonetheless,
Phil

 

[spinoza1111]

Yeah. What's he on? He should either increase or decrease
his dosage.

So it's news to you that a+b==b+a but not if the plus sign is changed
to minus? So it's news to you than even commutative operations should
not be flipped especially in floating point environments?

I really wonder (especially in light of Nash) about people who still
think its cute to say things like the above.

I would rather everyone killfiled spinoza, rather than wasting
their time responding to him. I certainly don't feel that my
posts need defending from his nonsensical bilge.

I think they do, since I think you don't know what you're talking
about if you can argue from the commutavity of addition to no need for
the stack. You look the fool, who learned some fashionable things at
university but no foundations, which show that certain operations
don't need a stack but don't generalize to "no need for a stack".

I very much would appreciate me if ignorant people without reading or
writing ability killfiled me, as it would save me a lot of valuable
time in replying to fools.

 

[spinoza1111]

That makes no difference to the point being made.

Actually it does. In mathematical "intuitionism" (look it up, please),
mathematical truth has to be constructed, not assumed, nor argued by
using proof by contradiction. The instinctive Platonism of many
programmers led them into trouble because they used proof by
contradiction only to find that their software was buggy because it
hadn't been coded "intuitionistically" using the Bohm-Jacopini
primitives.

In "intuitionism" you haven't proved that the above code gives a
sensible result until you can present a model which constructs the
answer. The basic model is the stack.

It is true that "optimizing compilers" can reorder operands. It is
true that parallelism can further shuffle operands and do two
calculations simultaneously. But these code transformations have to be
intuitionistically justified.

Therefore, Schildt was correct in speaking of the stack, and you, Ben
Bacarisse, don't know your trade.

 

[spinoza1111]

I consider ARM to be at least as CISC as any processor out there.
They've got the RISC decoding (which might be considered the single
most important aspect), but everything else smacks of C not R.

Thank you: so RISC laid an egg.

 

[spinoza1111]

Moi <[email protected]> writes: [...]

You don't need to agree with my definition, but if you don't, how does
the system you describe not qualify as a "stack"?

[I forgot something]

Well, for instance in the pseudo-program

***/

int fa(int a);
int fb(int a, int b); /* not shown, but recurses back to fa() or fb() */

int fa(int a)
{
int r;

r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;

return r;

}

**/

, the two function calls to fa() _could_ be executed in parallel (without
changing the semantics of "function call"), which would be hard
(impossible ?) using a "linear" stack. (they could finish in the wrong
order, leaving "holes" in the stack or fifo)

How is it possible that the "two function calls" "could" be executed
in parallel? C99 standard 6.5.17: "The left operand of a comma
operator is evaluated as a void expression: there is a sequence point
after its evaluation. THEN [emphasis mine] the right operand is
evaluated...".

Yes, the expression "fa(a+1), fa(a-1)" could be evaluated in a non-
stack environment. There are probably ** very few ** code snippets
that could not be compiled to a machine with fixed registers. I say
this because the only time I needed to simulate a stack on the IBM
1401, a machine with three "index" registers, was in developing a
Polish notation based language for job specification, and because the
Fortran compiler I debugged on the 1401 had no stacks (and no
recursive subroutine calls).

But nobody, in all probability, has learnt to code C by reading a
standards manual, esp. not the C99 manual since its purpose was to
protect vendors. The stack by construction can provide the time and
space execution semantics of all possible C programs, and to attack
Schildt for using it was just stupid when stacks are pretty basic to
Comp Sci 101 even at the uni level.

Sounds to me that you guys AP'd out of CS 101 and went on to
overspecialize and never learned the basics of your trade. Passing an
AP exam is not the same thing as learning: its more monkey and
typewriter and swotting material that's soon forgot.

[ disclaimers about side-effects, etc ... ]

AvK

 

[Willem]

spinoza1111 wrote:
<snip>
)> ...
)> r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;
)> ...
<snip>
) How is it possible that the "two function calls" "could" be executed
) in parallel? C99 standard 6.5.17: "The left operand of a comma
) operator is evaluated as a void expression: there is a sequence point
) after its evaluation. THEN [emphasis mine] the right operand is
) evaluated...".

That's not a comma operator, so your whole post is moot.

HTH


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT