Looking for free memory pool software

[SM Ryan]

# Keith Thompson wrote:
#
# > [...]
# >> Languages like C actually use two virtual stacks, a protocol
# >> stack and an operand stack, but the language semantics are such
# >> to allow the stacks to be interleaved onto one physical stack.
# > [...]
# >
# > What is an "operand stack"?
#
# As I understand the post, SM Ryan used the terms 'protocol stack'
# and 'operand stack' in this way:
#
# Protocol stack: data structure with stack semantics that contains the
# return addresses for the currently active functions.

Also called the return stack. It contains the call/return linkages.

# Operand stack: data structure with stack semantics that contains the
# arguments and return values of the currently active functions.

Also called the value or parameter stack. Contains operator parameters
and return values.

# This distinction between two stacks can be useful if a system only has
# hardware support for, for example, a stack of return addresses.

It's useful for understanding language semantics. The reason structs
could not originally be function returns and why arrays still cannot
is because the function return is sandwiched between the operand stack
frames of the caller and callee. The compiler needs some way to slide
the function result through the return linkage. That was easy when
the function result could be entirely included in the registers.

Forth and Postscript maintain separate stacks. Ada implementations
often use two stacks as well to avoid copying function returns.

 

[Keith Thompson]

An automatic variable becomes accessible when the flow
of execution enters its block, and ceases to be accessible
when the flow leaves the block. It's not possible to say
exactly when they are "allocated" or "deallocated." Indeed,
some automatic variables may never be allocated at all:

[snip]

Good point. I should have referred to the lifetime of objects rather
than to allocation and deallocation.

It was the lifetime question I was trying to get at and Eric Sosman
put it much more clearly than my question. However, I am still puzzled
by your claim that there is a "strict last-in first-out (i.e.,
stack-like)" order to the lifetimes of objects with automatic storage.
Here is a simple example that I hope illustrates my question.

void foo(void) {
int i = 42;
float f = i;

...
}

I have no problem with the "last-in" bit since the declaration of f
can use the fact that i has already been initialized to 42. However,
when the closing brace that ends the function is reached, as far as I
can tell, there is nothing in the standard that requires the lifetime
of f to end before the lifetime of i. That is the strict "first-out"
bit that I cannot find. I recognise that it really doesn't matter
since (as far as I can see) there is no way to tell which of i and f
disappears first, but if that is so then surely the standard is not
requiring a "strict last-in first-out" order, but only a strict
"lifetime begins after declaration and ends sometime before the end of
function is reached" order?

I was considering groups of objects declared together in a given
block, not individual objects. (I neglected the fact that each
object's lifetime begins at its declaration, not at the beginning of
the block in which it's declared.)

But this is a whole lot of verbiage (much of it mine) in support of a
very minor point. The semantics of function calls and the lifetimes
of objects with automatic storage duration does imply that there must
be first-in/first-out (i.e., stack-like) stuff going on. But the
standard doesn't use the word "stack", it doesn't matter a whole lot
whether we use the word or not -- except that there isn't necessarily
a "hardware stack", which is a much more specific concept.

 

[Eric Sosman]

[...] The semantics of function calls and the lifetimes
of objects with automatic storage duration does imply that there must
be first-in/first-out (i.e., stack-like) stuff going on. [...]

That's (at least) the second post to this thread describing
a "stack" as following a FIFO discipline. Is there something
in the water?

 

[Keith Thompson]

Also called the return stack. It contains the call/return linkages.


Also called the value or parameter stack. Contains operator parameters
and return values.

Ok. Since the word "operand" is used by the standard to refer to
operands of operators, not function arguments, I assumed you were
talking about expression evaluation.

[...]

 

[Keith Thompson]

[snips]

Would you argue that a contiguous array implementation and a linked
list implementation are both "stacks", but a database implementation
is not?

Quite possibly. What this has to do with "the C main stack" isn't clear,
and this is the thing Malcolm was going on about. There is no such
thing.

Yes there is.

Would you also contend that there are "no such things" as global
variables in C?

It depends on what you mean by "global variables". Tell us exactly
what you mean by the phrase, and we can tell you whether C supports
them.

You can be as clever as you like but everyone KNOWS what is meant be the
C Stack. Whether conceptual or physical. It is there in one form or
another.

What "everyone KNOWS" is that there's a hardware stack, indexed by a
stack pointer (probably a CPU register), that grows contiguously
through memory. The problem is that it's not universally true.

 

[Keith Thompson]

I was considering groups of objects declared together in a given
block, not individual objects. (I neglected the fact that each
object's lifetime begins at its declaration, not at the beginning of
the block in which it's declared.)

Sorry, my mistake. The lifetime of an automatic object begins on
entry to the block containing its declaration, not at the point of the
declaration itself. (Scope is another matter; I've read the relevant
section of the standard, but it seems unclear on whether an automatic
object's scope begins at the beginning of the block or at the point of
declaration.)

But this is a whole lot of verbiage (much of it mine) in support of a
very minor point. The semantics of function calls and the lifetimes
of objects with automatic storage duration does imply that there must
be first-in/first-out (i.e., stack-like) stuff going on.

[...]

Whoops, I meant "last-in/first-out". Thanks to for pointing out the
error (this seems to be my day for them).

 

[Eric Sosman]

[...] The lifetime of an automatic object begins on
entry to the block containing its declaration, not at the point of the
declaration itself. (Scope is another matter; I've read the relevant
section of the standard, but it seems unclear on whether an automatic
object's scope begins at the beginning of the block or at the point of
declaration.)

For functions and variables the scope starts in the
declaration, just after the declarator and just before the
initializer (if there is one). Examples:

void func(void) {
int var = 42;
{
int *ptr = &var;
double var = *ptr;
}
}

In the inner block, ptr points at the int in the outer
block, not at the double in the inner block. The latter is
not in scope at the line where ptr is declared and initialized.

Second example:

struct node {
int isRoot;
int payload;
struct node *link;
} listHead = { 1, 0, &listHead };

(This might define the "handle" node of a circularly-linked
list, initialized to its "empty" condition.) The scope of
listHead begins right after its declarator, so it is in scope
and available for reference by the &listHead in the initializer.

Identifiers that are function arguments, struct/union/enum
tags, statement labels, macro names, and macro arguments have
different rules, in some cases quite different.

 

[Bart van Ingen Schenau]

# This distinction between two stacks can be useful if a system only
# has hardware support for, for example, a stack of return addresses.

It's useful for understanding language semantics. The reason structs
could not originally be function returns and why arrays still cannot
is because the function return is sandwiched between the operand stack
frames of the caller and callee. The compiler needs some way to slide
the function result through the return linkage. That was easy when
the function result could be entirely included in the registers.

Except that I have worked with C implementations that did not mix
parameter values and return addresses in a single stack.
One implementation in particular did not use any stack-like mechanism
for storing parameter values at all, if the relevant functions were not
involved in a recursive call-chain.
For recursive functions, a separate stack of parameter values was
maintained. For non-recursive functions, the parameters (and local
variables) would be stored at a fixed location in the memory.

Forth and Postscript maintain separate stacks. Ada implementations
often use two stacks as well to avoid copying function returns.

There is nothing in the C standard that forbids an implementation to use
separate structures for return addresses and parameter values in C.

Bart v Ingen Schenau

 

[Keith Thompson]

[...] The lifetime of an automatic object begins on
entry to the block containing its declaration, not at the point of the
declaration itself. (Scope is another matter; I've read the relevant
section of the standard, but it seems unclear on whether an automatic
object's scope begins at the beginning of the block or at the point of
declaration.)

For functions and variables the scope starts in the
declaration, just after the declarator and just before the
initializer (if there is one).

[SNIP]

Yeah, that's what I thought, but I couldn't find that in the standard,
particularly C99 6.2.1, "Scopes of identifiers". Can you provide C&V?
(I'm probably missing something obvious; at least, I'm missing
something that *should* be obvious.)

And apparently two object whose scopes start at different points but
end at the same point have, by definition, the "same scope":

Two identifiers have the _same scope_ if and only if their scopes
terminate at the same point.

 

[Eric Sosman]

[...] The lifetime of an automatic object begins on
entry to the block containing its declaration, not at the point of the
declaration itself. (Scope is another matter; I've read the relevant
section of the standard, but it seems unclear on whether an automatic
object's scope begins at the beginning of the block or at the point of
declaration.)

For functions and variables the scope starts in the
declaration, just after the declarator and just before the
initializer (if there is one).

[SNIP]

Yeah, that's what I thought, but I couldn't find that in the standard,
particularly C99 6.2.1, "Scopes of identifiers". Can you provide C&V?
(I'm probably missing something obvious; at least, I'm missing
something that *should* be obvious.)

Paragraph 7 of that section:

"[...] Any other identifier [those we're talking about]
has scope that begins just after the completion of its
declarator."

And apparently two object whose scopes start at different points but
end at the same point have, by definition, the "same scope":

Two identifiers have the _same scope_ if and only if their scopes
terminate at the same point.

I've always found it perplexing that two scopes demonstrably
different in their extent (see my simple example up-thread) are
termed "the same." It is obviously some strange meaning of the
word "same" that I wasn't previously aware of. Is a puzzlement,
or equivalent to a puzzlement, which is to say: the same as --
no, wait, don't go there.

 

[Keith Thompson]

Keith Thompson wrote:
[...] The lifetime of an automatic object begins on
entry to the block containing its declaration, not at the point of the
declaration itself. (Scope is another matter; I've read the relevant
section of the standard, but it seems unclear on whether an automatic
object's scope begins at the beginning of the block or at the point of
declaration.)
For functions and variables the scope starts in the
declaration, just after the declarator and just before the
initializer (if there is one).

[SNIP]
Yeah, that's what I thought, but I couldn't find that in the
standard,
particularly C99 6.2.1, "Scopes of identifiers". Can you provide C&V?
(I'm probably missing something obvious; at least, I'm missing
something that *should* be obvious.)

Paragraph 7 of that section:

"[...] Any other identifier [those we're talking about]
has scope that begins just after the completion of its
declarator."

Yup, I was missing something obvous. *blush*

I've always found it perplexing that two scopes demonstrably
different in their extent (see my simple example up-thread) are
termed "the same." It is obviously some strange meaning of the
word "same" that I wasn't previously aware of. Is a puzzlement,
or equivalent to a puzzlement, which is to say: the same as --
no, wait, don't go there.

It's certainly useful to talk about objects having scopes that end at
the same point, but "same scope" was not a good phrase to describe
this.

 

[Chris Torek]

Keith Thompson wrote:
[the Standard says]

I've always found it perplexing that two scopes demonstrably
different in their extent (see my simple example up-thread) are
termed "the same." It is obviously some strange meaning of the
word "same" that I wasn't previously aware of.

Well, really, it is implementation-centric, and refers to the fact
that symbol names can be entered into a "symbol table" with a
"scope number" attached to them. Once thus entered, names are
looked up with a method like [%]:

/* find symbol at given scope # if it exists, or return NULL if not */
extern struct symbol find_sym(const char *name, int scope);

struct symbol *sym;
int i;

for (i = current_scope_number; i >= 0; i--) {
sym = find_sym(name, i);
if (sym != NULL)
break;
}
if (i < 0) {
error("undefined symbol %s", name);
return ERROR;
}
...

Moreover, when "exiting" the scope numbered n (normally due to a
"}"), we simply remove all the symbols whose number is n. (I
say "normally" because there is at least the case of prototype
scope, ended by a closing parenthesis. Also, "scope 1" tends
to be reserved for goto-labels, so that the close brace that
ends a function jumps from "scope 2" -- the function body -- to
"scope 0", the "global" [really, translation unit] scope.)

Since these symbols have the same "scope number", they have "the
same" scope, even though they do not even *exist* until they are
entered into the table -- which means that their starting points
differ, so that (as you note) their scopes are at least *slightly*
different.

It would be more accurate, but even more implementation-centric,
to say that the two identifiers have "the same scope number",
instead of "the same scope".

[% One might hope that the method is "like" this except far more
efficient. For instance, it would be no doubt better to look
up the name in a hash-table, and from that, find all occurrences
at all scopes, e.g., via a linked list.]