The machine stack and the C language

S

Serve Lau

Tomás Ó hÉilidhe said:
I never write recursive functions unless I really really really really
have to. In 95% of cases, you can just use a loop.

tail recursion can always be rewritten to a loop
 
S

Serve Lau

It would be interesting tha they AT LAST point out the implementations
of C where there is "NO STACK"... Obviously implementations crippled
beyond recgnition that do not implement recursion do NOT count.

I dont think this has been answered yet. I would love to know about a
"stackless" implementation that does support recursion.
 
C

Chris Hills

CBFalconer said:
There is only one C - that described in the ISO C standard, or its
antecedants. Once the language is extended, it is no longer
portable C.

The fact it is not portable is not relevant.

You can write perfectly conforming C that is not portable.
 
J

James Kuyper

Chris said:
The fact it is not portable is not relevant.

You can write perfectly conforming C that is not portable.

True, but should such code be on-topic here? The US declaration of
independence is conforming C code, because a conforming implementation
of C can, as an extension, accept it after issuing at least one
diagnostic message. I believe that a conforming implementation of C
which accepts all code which has no #error directives that survive
conditional compilation, always producing at least one diagnostic
message, has in fact been created. Should that fact be used as an excuse
for discussing the US revolutionary war in this newsgroup? Where do you
draw the line?
 
J

jacob navia

James said:
True, but should such code be on-topic here? The US declaration of
independence is conforming C code, because a conforming implementation
of C can, as an extension, accept it after issuing at least one
diagnostic message. I believe that a conforming implementation of C
which accepts all code which has no #error directives that survive
conditional compilation, always producing at least one diagnostic
message, has in fact been created. Should that fact be used as an excuse
for discussing the US revolutionary war in this newsgroup? Where do you
draw the line?

Why do we have to draw lines?

The same people that want strictly on topic messages discuss
British poetry for a week, or the wiring standards
for electrical circuits for a week.

We could discuss extensions to C, POSIX and other things that
concern C directly. comp.std.c is for discussing the standard
language.
 
J

James Kuyper

Serve said:
I dont think this has been answered yet. I would love to know about a
"stackless" implementation that does support recursion.

I believe it has been. The people who are saying that a stack is not
required are not using the word "stack" in the abstract sense of a
generic LIFO allocation mechanism. They are using it in the more
common, more concrete sense of the word, to refer specifically to
implementation of LIFO semantics by use of a single large block of
memory which grows and shrinks only at one end.

Real implementations have been described in this thread that don't
possess such a stack, using activation records which are allocated and
deallocated from locations in memory that are not in any particular
order. I don't see any reason why such an implementation should have any
trouble supporting recursion.
 
J

jacob navia

James said:
I believe it has been. The people who are saying that a stack is not
required are not using the word "stack" in the abstract sense of a
generic LIFO allocation mechanism. They are using it in the more
common, more concrete sense of the word, to refer specifically to
implementation of LIFO semantics by use of a single large block of
memory which grows and shrinks only at one end.
In the starting message of this post I cited Mr Lew Pitcher
that started all this:

Repeat after me: "There is no stack in the definition of the C
Language"

Just that. No qualifiers, no "There is a stack that can be
implemented without a machine stack". JUST THAT.

Besides this is nonsense because even if you have a linear
stack it is based on memory pages this days, that are not
contiguous at all and scattered all around in real memory.

That is why I specified: <<The sentence "there is no stack"
is wrong>>

Real implementations have been described in this thread that don't
possess such a stack, using activation records which are allocated and
deallocated from locations in memory that are not in any particular
order. I don't see any reason why such an implementation should have any
trouble supporting recursion.

Because they have a stack OBVIOUSLY!

If there is no hardware stack, the implementation does it with a
software stack BECAUSE C NEEDS A STACK.

I think we agree here with the basics. Lets agree then that the
sentence

"There is no stack in C"

is completely wrong.

The sentence:

C needs a stack and if there is no hardware stack it can
be implemented by other means.

is right.

OK?
 
J

James Kuyper

jacob said:
James Kuyper wrote: ....

Why do we have to draw lines?

The same people that want strictly on topic messages discuss
British poetry for a week, or the wiring standards
for electrical circuits for a week.

Wiring standards were originally brought into the discussion simply to
make an on-topic point about standards in general. After that, the
sub-thread drifted. Could you please identify any specific message on
that sub-thread after it drifted, posted by anyone who favors strict
topicality, which didn't include a statement that this was an
inappropriate place for such a discussion?
We could discuss extensions to C, POSIX and other things that
concern C directly. comp.std.c is for discussing the standard
language.

No, comp.std.c is for discussing the language standard - what it means,
whether particular code strictly conforms with the standard, whether a
particular implementation technique is conforming, how it should be
changed, etc.. Discussions of how use the language defined by that
standard are off-topic on comp.std.c. People who want to discuss the
usage of standard C without raising any issues about the standard itself
are routinely re-directed to comp.lang.c.
 
B

Ben Bacarisse

Tim Smith said:
You could easily design a runtime that doesn't need a stack. The
function call system would work as follows:

1. When a function is called, it is passed a pointer to a block of
memory. This block of memory contains the return address for the call,
and the arguments to the function, and space for the return value. I'll
call this the argument block.

2. The first thing the function does is allocate a block of memory.
This block of memory is large enough to hold all the local variables of
the function, plus enough extra space to hold the largest argument block
the function needs for any calls it makes. I'll call this the
function's local block.

3. When a function returns, it frees its local block.

4. When a function needs to call another function, it fills in the
argument block as needed for the function it wants to call, and calls it.

5. A specific register is assigned for use in passing the pointer to the
argument block to the called function. The machine's equivalent of goto
is used to actually transfer control to the other function. Similarly,
goto is used to return.

You omitted (or glossed over) the fact the these blocks of memory must
be chained together. There are lots of slightly different ways to
this but they all result in a linked list of what are often called
"activation records". To many people, this can be called a stack,
even though the activation records are not contiguous in memory.

One poster said that they can't see how to implement recursion without
a stack, and you may have shown them something that they did not know
(that the activation records can be a non-contiguous linked list) but
whether or not this is a stack is to do with definitions. If everyone
who has posted had appended their definition of a stack, then I don't
think there would have been much of a thread -- except, perhaps, to
argue explicitly about the definitions. I don't think there is any
disagreement about the facts.

Obviously your definition of a call stack is that it must be
contiguous in memory when seen from the program's side of the VM
architecture, but the other point of view is also perfectly
reasonable. Of course, if you feel strongly about the *definition*
and want to have a debate about then, OK, but c.l.c is probably
not the best place. I don't feel strongly enough about the definition
to disagree with you (except to point out the missed chaining in your
otherwise very clear explanation) but I would not object to the other
definition (that there is always a call stack of some sort) either!
 
J

James Kuyper

Chris said:
Yes... Now you want Pure ISO C that is completely portable?

No, I want this group to concentrate on questions about portable aspects
of the C language, leaving the non-portable aspects to be discussed by
other groups which are more competent to discuss them. This group has
way too many messages to be easily reviewed. If we could somehow
magically remove the off-topic messages, the complaints about the
off-topic messages, and the complaints about the complaints about
off-topic messages, it would be a much easier group to monitor. If I
want to learn about, for example, Microsoft-specific issues in C
programming, I'll look for a microsoft-specific newsgroup, I don't want
to see it here.
 
S

Serve Lau

Keith Thompson said:
Should comp.unix.programmer be eliminated and merged into comp.lang.*,
since all Unix programming is done in some language?

C is defined by the C standard. That's why it's called the C
standard.

I always go to alt.bible.bashing when I have questions about bash
 
C

CBFalconer

Chris said:
The fact it is not portable is not relevant. You can write
perfectly conforming C that is not portable.

In some newsgroups, yes. However, this is c.l.c, and the subject
is the portable standardized C language. I believe you have been
so advised before. Note that you don't receive such topicality
corrections in c.a.e.
 
M

Malcolm McLean

jacob navia said:
Why do we have to draw lines?

The same people that want strictly on topic messages discuss
British poetry for a week, or the wiring standards
for electrical circuits for a week.

We could discuss extensions to C, POSIX and other things that
concern C directly. comp.std.c is for discussing the standard
language.
There is a difference between topic drift and a post that starts off-topic.
For instance a biographical thread about Ada Lovelace would clearly be
off-topic here, but maybe OK on comp.programming.
However discussion about who was first to deprecate gotos, which is topical,
could easily lead to a discussion about Ada Lovelace, which would be
acceptable though not topical, becasue the discussion has naturally led to
that point.
 
K

Keith Thompson

jacob navia said:
If there is no hardware stack, the implementation does it with a
software stack BECAUSE C NEEDS A STACK.

I agree, with two minor qualifications.

1. A compiler might generate code for a particular program without
using a stack if it can prove that the particular program doesn't need
recursion. A function for which there is never more than one active
call can have its activation record allocated statically. On most
systems, this is not a particularly useful optimization, but it might
be on some. So a compiler must be able to support a stack (a LIFO
data structure), but it needn't necessarily always use it.

2. There's no need to shout. The conventional way to denote emphasis
is to surround the emphasized text with *asterisks*. Too much
all-caps text makes my eyes bleed.
I think we agree here with the basics. Lets agree then that the
sentence

"There is no stack in C"

is completely wrong.

No, it is not completely wrong, it is merely unclear, especially if
you refuse to understand the writer's intent. The word "stack" is
commonly used to refer to a contiguous hardware stack of the kind that
we've discussed to death in this thread. It is perfectly true that
the word "stack" does not appear in the C standard, and that a C
implementation does not need to use a hardware stack.

Someone who says "There is no stack in C" is *clearly* using the word
"stack" in the sense of a hardware stack, not in the sense of a
general LIFO data structure. Such a statement is "completely wrong"
only if you reject the idea that the word "stack" can possibly have
that meaning. And yet posters here very commonly use the unqualified
word "stack" with *exactly* that meaning, particularly when referring
to "*the* stack". I wish they wouldn't, but they do.

Since we're trying to be agreeable, can you agree with the above?
The sentence:

C needs a stack and if there is no hardware stack it can
be implemented by other means.

is right.
Agreed.

OK?

OK.
 
C

CBFalconer

Malcolm said:
.... snip ...

However discussion about who was first to deprecate gotos, which
is topical, could easily lead to a discussion about Ada Lovelace,
which would be acceptable though not topical, becasue the
discussion has naturally led to that point.

However the 'goto' subject is not topical, because gotos have never
been, and never will be, deprecated. :) (Speaking topically, of
course.)
 
K

Keith Thompson

jacob navia said:
comp.std.c is for discussing the standard language.

Please stop repeating this falsehood. comp.std.c is for discussing
the language standard.
 
M

Malcolm McLean

Keith Thompson said:
Someone who says "There is no stack in C" is *clearly* using the word
"stack" in the sense of a hardware stack, not in the sense of a
general LIFO data structure. Such a statement is "completely wrong"
only if you reject the idea that the word "stack" can possibly have
that meaning. And yet posters here very commonly use the unqualified
word "stack" with *exactly* that meaning, particularly when referring
to "*the* stack". I wish they wouldn't, but they do.
Let's say someone is a bit shaky on what static variables are.
A perfectly reasonable way of explaining it is to say that the automatic
variables are stored on the stack, and the stack pointer is reset when the s
function returns, but the static variables are not.
That's a concrete image a person can get into their head, and it is close
enough to the truth. It's not the full truth of course. The "stack" may or
may not have some sort of hardware support, it might even be optimised to
nothing except in the case of recursive functions.
Where you do need to be more specific is if something thinks it is important
whether the stack grows upwards or downwards in memory, or wants to know how
to avoid stack overflow.
 
C

Chris Hills

James Kuyper said:
No, I want this group to concentrate on questions about portable
aspects of the C language,

Well that is an even tighter and artificial restriction on this group
with is computer languages :- C not Standard C or god forbid only
portable standard C

That is up to you. I am sure people will discuss it with you. Others
have different interests in using C
leaving the non-portable aspects to be discussed by other groups which

Not a chance.
are more competent to discuss them. This group has way too many
messages to be easily reviewed. If we could somehow magically remove
the off-topic messages, the complaints about the off-topic messages,
and the complaints about the complaints about off-topic messages, it
would be a much easier group to monitor.

I agree... most of the messages are caused when people start shouting OT
stop the shouts of OT and

If I want to learn about, for example, Microsoft-specific issues in C
programming, I'll look for a microsoft-specific newsgroup, I don't want
to see it here.

So would I . I look on the most appropriate NG but when some one says
"how do I do ABC" it is very helpful to say whell ther eis no STD way
of doing it but the various methods are a , b, c, d and A&B are used
mainly in windows C on macs and D on linux... then the OP and we all
learn something usfull.

Then when the OP says I have a MAC/windows/Linux they can go to the
specific NG for more in depth discussions.

However we all need to know what is outside our own specific box. Not in
detail but we need an awareness.
 
J

James Kuyper

jacob said:
In the starting message of this post I cited Mr Lew Pitcher
that started all this:

Repeat after me: "There is no stack in the definition of the C
Language"

Just that. No qualifiers, no "There is a stack that can be
implemented without a machine stack". JUST THAT.

Besides this is nonsense because even if you have a linear
stack it is based on memory pages this days, that are not
contiguous at all and scattered all around in real memory.

That is why I specified: <<The sentence "there is no stack"
is wrong>>



Because they have a stack OBVIOUSLY!

If there is no hardware stack, the implementation does it with a
software stack BECAUSE C NEEDS A STACK.

I think we agree here with the basics. Lets agree then that the
sentence

"There is no stack in C"

is completely wrong.

The sentence:

C needs a stack and if there is no hardware stack it can
be implemented by other means.

is right.

OK?

No. It would be more accurate to say:

"The standard says nothing about stacks as such. What the standard says
about the lifetime of variables with automatic storage duration makes it
natural to implement them using the LIFO semantics of the stack that is
a commonplace feature of many computer architectures. However, the
standard does not mandate the use of such a stack; it doesn't even
mandate the LIFO semantics of an abstract stack, as the term is
understood in computer science."

Before you repeat that the claim, which has been frequently made in this
thread, that LIFO semantics are mandatory, please consider the following
implementation:

It allocates and deallocates space for activation records. It makes sure
that it always allocates a given record before the start of the lifetime
of the variables stored in that record, and it makes sure that it never
deallocates them until after the end of the lifetime of those
variables, but it does not always carry out the allocations and
deallocations in the same order as a LIFO mechanism would.

What requirement of the C standard would such an implementation violate?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top