No machine stack and C

[jacob navia]

I thought that an implementation of C without a machine
stack was impossible.

Mr Banks corrected me since he says his implementation of C
includes recursion and simulates the stack in software.

That will be horribly slow, but proves that many things
you consider impossible can be done

I stand corrected then

jacob

 

[Walter Banks]

I thought that an implementation of C without a machine
stack was impossible.

Mr Banks corrected me since he says his implementation of C
includes recursion and simulates the stack in software.

That will be horribly slow, but proves that many things
you consider impossible can be done

I stand corrected then

jacob

Thanks..

It actually is quite fast. Consider the following
implementation choices.

1) Run time function frames only need to be allocated for
the functions that are recursive either directly or long path

2) Tail end recursion and other optimizations eliminate most of
the recursive functions.

3) Non recursive functions can use the full instruction set for
data access and manipulations which improves the
performance enough to justify using similar techniques on
processors with a full data stack.

4) Stack or heap data allocation require runtime stack
management for recursive functions. Minimizing the
number of recursive functions through compiler optimizations
significantly improves performance.

We have metrics that show that in real life embedded system
applications using these processors fewer that 1% of the
applications need recursive support (6 in 2000 applications
in our sample)

Regards,


Walter..

 

[Keith Thompson]

I thought that an implementation of C without a machine
stack was impossible.

Mr Banks corrected me since he says his implementation of C
includes recursion and simulates the stack in software.

That will be horribly slow, but proves that many things
you consider impossible can be done

I stand corrected then

Excellent!

Will you reconsider the insults you've directed at the people who have
been trying to tell you this all along?

 

[Moi]

Excellent!

Will you reconsider the insults you've directed at the people who have
been trying to tell you this all along?

GROUP HUG! GROUP HUG!

AvK

 

[Kenny McCormack]

Excellent!

Will you reconsider the insults you've directed at the people who have
been trying to tell you this all along?

You're not getting it.

I know what Jacob is really saying, and I can tell you, you won't like it.

 

[spinoza1111]

Excellent!

Will you reconsider the insults you've directed at the people who have
been trying to tell you this all along?

Please don't, Jacob. Just because the stack is simulated doesn't mean
it doesn't exist, and it does NOT imply that Schildt was wrong.

 

[spinoza1111]

You're not getting it.

I know what Jacob is really saying, and I can tell you, you won't like it..- Hide quoted text -

- Show quoted text -

Jacob, I misspoke when I implied that there was a connection between
C's being mostly Chomsky type 2 and the runtime stack. Likewise you
had a Homeric nod when you implied that a MACHINE stack was necessary.
It is not, but the fact that a SOFTWARE stack was necessary confirms
that a runtime STACK is a sine qua non.

Which in turn means that Schildt was correct as any compsci prof in a
good university talking about stacks in a beginner class. The fact
that C allows the programmer to declare register variables, and that
optimizers use registers, does not in any way imply that it's possible
to get by without a stack.

Which in turn means that Seebach and Feather were engaged in what you
French guys call a canard, a Dreyfusard.

That's their game: while making trivial and nontrivial errors
themselves, they use errors fungibly, making your dignified and manly
admission of a misstep into an auto da fe, expecting you to recant
before their Holy Inquisition, and acknowledge their "expertise".

I am moved by your intelligence and your command of written English,
and your accomplishments. Please remain here!

Illegitimi non carborundum, Monsieur!

 

[Phil Carmody]

In <[email protected]>,
spinoza1111 wrote:



Curiously enough, in one place Schildt actually gets it *right*. In
C:TCR2, on p719, he writes: "Like most C compilers, Microsoft C
passes arguments to functions on the stack."

In other words, it appears that even Schildt agrees that C does not
need a stack for passing arguments. (If he did not, why say "most"
rather than "all"?)

If he did not, why did he mention it at all?

Phil

 

[Richard Tobin]

Curiously enough, in one place Schildt actually gets it *right*. In
C:TCR2, on p719, he writes: "Like most C compilers, Microsoft C
passes arguments to functions on the stack."

In other words, it appears that even Schildt agrees that C does not
need a stack for passing arguments. (If he did not, why say "most"
rather than "all"?)

Needing a stack to pass arguments and needing a stack are rather
different. Every C implementation I've heard of that uses registers
to pass arguments saves registers on the stack. So even if you say
they don't use a stack to pass arguments, passing arguments results in
them using a stack.

-- Richard

 

[user923005]

Needing a stack to pass arguments and needing a stack are rather
different.  Every C implementation I've heard of that uses registers
to pass arguments saves registers on the stack.  So even if you say
they don't use a stack to pass arguments, passing arguments results in
them using a stack.

They could certainly be stored in a hash table.
A stack is definitely optional.
Now, they do have to be saved somewhere.
That's a horse of a different color.

 

[spinoza1111]

They could certainly be stored in a hash table.
A stack is definitely optional.
Now, they do have to be saved somewhere.
That's a horse of a different color.- Hide quoted text -

- Show quoted text -

If arguments are saved on a table of hash
Your code is guaranteed to go smash
Unless you have some way of finding them...it's called a key
And, oh dear me,
Where shall we put the hash table key?
Hey, I have thought of something brilliant!
Let's put them on a stack!
Isn't that magnificent!

 

[user923005]

On Sep 11, 1:26 pm, (e-mail address removed) (Richard Tobin) wrote:

If arguments are saved on a table of hash
Your code is guaranteed to go smash
Unless you have some way of finding them...it's called a key
And, oh dear me,
Where shall we put the hash table key?
Hey, I have thought of something brilliant!
Let's put them on a stack!
Isn't that magnificent!

The solution to this problem is so obvious it does not need mention.
The key is part of the hash table entry. It comes from the free
store.
We can store anything we need as part of the key, including (for
instance) the current instruction pointer.

A stack is a handy data structure to store information and since we
only push and pop in function calls, it seems a natural fit.
But a hash table using dynamic allocation would easily work also.
That a stack is unnecessary is transparently obvious in that many
other data structures can accomplish the same thing.

It's astonishing that anything as obvious and simple as this should
need any sort of explanation.

 

[spinoza1111]

On Sep 11, 1:26 pm, (e-mail address removed) (Richard Tobin) wrote:



The solution to this problem is so obvious it does not need mention.
The key is part of the hash table entry.  It comes from the free
store.
We can store anything we need as part of the key, including (for
instance) the current instruction pointer.

A stack is a handy data structure to store information and since we
only push and pop in function calls, it seems a natural fit.
But a hash table using dynamic allocation would easily work also.
That a stack is unnecessary is transparently obvious in that many
other data structures can accomplish the same thing.

It's astonishing that anything as obvious and simple as this should
need any sort of explanation.- Hide quoted text -

It's more astonishing that your explanation is so poor, and that it so
confuses pointer direction. If your "hash table" contains "the current
instruction pointer", by which you may or may not mean "the return
address from the current function", you have no way (or have explained
no way) of how the executing code gets to the proper location in your
hash table.

In older machines, "the proper location in your hash table" would have
been a single-valued scalar in a register, but it was found that this
value needed to be "saved" when a called subroutine called another at
a second level. In fact, Dijkstra pointed this out wrt the IBM 1620:
even the notion of a subroutine calling another subroutine was
considered rich and strange in American circles circa 1960, in a
climate where some programmers prided themselves on not using
subroutines, but coding like Men, "branching back" and "coming from"
like Men.

Since the scalar-register was considered a "save" area, the need to
"save the save area" was immediately recognized as problematic by
sensitive computing souls...whence the stack, which is what your model
needs to function. You can get by, if functions never call themselves
directly or indirectly, without a stack although you pay a heavy
price. You CANNOT get by if functions call themselves recursively.

 

[user923005]

On Sep 11, 1:26 pm, (e-mail address removed) (Richard Tobin) wrote:





It's more astonishing that your explanation is so poor, and that it so
confuses pointer direction. If your "hash table" contains "the current
instruction pointer", by which you may or may not mean "the return
address from the current function", you have no way (or have explained
no way) of how the executing code gets to the proper location in your
hash table.

In older machines, "the proper location in your hash table" would have
been a single-valued scalar in a register, but it was found that this
value needed to be "saved" when a called subroutine called another at
a second level. In fact, Dijkstra pointed this out wrt the IBM 1620:
even the notion of a subroutine calling another subroutine was
considered rich and strange in American circles circa 1960, in a
climate where some programmers prided themselves on not using
subroutines, but coding like Men, "branching back" and "coming from"
like Men.

Since the scalar-register was considered a "save" area, the need to
"save the save area" was immediately recognized as problematic by
sensitive computing souls...whence the stack, which is what your model
needs to function. You can get by, if functions never call themselves
directly or indirectly, without a stack although you pay a heavy
price. You CANNOT get by if functions call themselves recursively.

Every time a function gets called, an instance counter for the
function is incremented.
If the instance counter is part of the key, we can unambiguously find
the values stored for a given function invocation.

 

[spinoza1111]

On Sep 11, 1:26 pm, (e-mail address removed) (Richard Tobin) wrote:





Every time a function gets called, an instance counter for the
function is incremented.
If the instance counter is part of the key, we can unambiguously find
the values stored for a given function invocation.

Very clever, but no cigar. The instance counter and the entries
accessed using it form a stack: so we're back to where we started!

Furthermore, you have more than one function in the normal case,
therefore you have a set (array?) of instance counters growing in an
unbounded fashion each time a new function is called. I'd guess this
array is another one of your famous hash tables, indexed by function
name.

Each function has a LIFO stack of activation records in the heap.

Very cleverly, you've killed the single Stack only to have it re-
emerge, a Hydra-headed monster indeed!

- Hide quoted text -

 

[spinoza1111]

In <[email protected]>,

spinoza1111wrote:



Curiously enough, in one place Schildt actually gets it *right*. In
C:TCR2, on p719, he writes: "Like most C compilers, Microsoft C
passes arguments to functions on the stack."

In other words, it appears that even Schildt agrees that C does not
need a stack for passing arguments. (If he did not, why say "most"
rather than "all"?)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

Perhaps he was thinking of phony C compilers from fraudulent vendors.
Or, implementations of brain-damaged subsets of C for limited embedded
platforms where the user didn't need recursive procedures.

 

[Willem]

spinoza1111 wrote:
) Very clever, but no cigar. The instance counter and the entries
) accessed using it form a stack: so we're back to where we started!

Right.. "No True Scotsman".
You're getting predictable.


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

 

[spinoza1111]

spinoza1111wrote:

That statement doesn't make sense.

Translation: "I don't understand it".

A "register" is a scalar in the sense that it can contain only one
value at any time. It it is used to "save" a value in another
"register", and then needs to be saved, the value has to go somewhere
else.

The natural next step is to allocate a fixed array with a pointer to
the most recently used "register". Congratulations, you've just
triumphantly reinvented a great wheel: the stack.

Basically, the tendency in modern organizations, reinforced by modern
media (what was called "psychoanalysis in reverse" by the "Frankfurt
School" theorist Max Horkheimer) is to flatten, not only emotional
affect, but also cognition, since emotion and cognition are so
intimately linked. Subgoals are unmentionable, and the bourgeois
narrative of the 19th century (cf Zola or Dickens) of temporary
expedients on the way to ownership and mastery, is eradicated.

In its place is a universal Taylorism where even at the white collar
level, economic "rationality" insists that the propertyless employee
must, as a sort of Calvinistic punishment for his fallen state, work
on only one set of alienated goals with no memory.

This is not meant to be a detour and frolic, and it is not meant to
obfuscate, although it probably will be thought to do in present
company. But: the fact is that in early, industrial programming,
writing a subroutine without authorization was in some organizations a
termination offense. This is because the industrial "time and motion"
theories of Frederick Taylor had become widely taught in business
schools by the 1960s, despite the fact that Frederick Taylor was an
anti-German racist whose favorite wage-slave was "Schmitt" a
"Pennsylvania Dutchman", and despite the fact that his speed-ups
caused deaths, injuries and strikes.

Applied to programming, Taylorism created the infamous "lines of code
per hour" productivity metric and thousands of programmer deaths
through suicide and depression. Stacks and mere subroutines were
inimical to "Taylorists" because a tree structure of subroutines
CANNOT be meaningfully measured for time and motion studies which as
early as the 1950s were being applied to American white collar
employees. Therefore subroutines, and the only computing device
capable of handling subroutines, were under a cloud until the
invention of C...which was accepted in America because it was
inelegant and ugly enough to be thought virtuous by Calvinists.

 

[spinoza1111]

spinoza1111wrote:

I take it your experience with programing embedded systems is limited.

You take it right. "Experience" slaving away for unfeeling SOBs
doesn't produce wisdom, and atrophies intelligence.

 

[spinoza1111]

spinoza1111wrote:

) Very clever, but no cigar. The instance counter and the entries
) accessed using it form a stack: so we're back to where we started!

Right.. "No True Scotsman".
You're getting predictable.

We're not arguing about the essential nature of the Scotsman, nor of
the Dutchman for that matter: do you really want to get me started on
that subject Mijn Heer?

You are I believe accusing me of the logical fallacy of "definition
against disproof". Unfortunately for you, I have not wavered in my
definition of the stack as a set (not a contiguous vector) of elements
with an adjacency relationship implemented in an undefined but
reliable way (such as addition of one, or following a link), together
with the knowledge-of (not the index-of, nor the address-of) one
favored scalar member of the stack known as its top.

That is, a stack is (T, S, R) where T is the top and S is a set of
elements and R is the adjacency relationship. Only T is "public".

If you prefer C Sharp, with all private material starkly removed:

public class stack
{
public void push(object objValue) { ... }
public object pop() { ... }
}

This is of course weakly typed, but the latest release of C Sharp
gives us generic classes and types (which is light years beyond C):

public class stack<typType>
{
public void push(typType objValue) { ... }
public typType pop() { ... }
}

Please note that at this point, the stack could be implemented as
ANYTHING as long as push and pop fit the minimal expectation of a
stack.

Now, I realize that many programmers fall into what appears to be a
fallacy but related to my claim: the claim that (for example) C is
object oriented because they are "disciplined" (where the claim that
"I'm disciplined" is at odds, IMO, with the indisciplined personal
attacks right here).

Am I claiming in like manner that my "true Scotsman" above is always a
stack?

No, because semantically, there is no wiggle room. However I implement
the above it must behave LIFO, whereas almost any C crap can be called
"object oriented" by way of confusion of names with things.