Statement on Schildt submitted to wikipedia today

[spinoza1111]

In





Reference, please. I can find no such admission. The closest I found
was that he writes "clear, readable text", which is far from being
the same thing.

That's implicated by the phrase "clear and readable". You can't be
clear and readable if you are not true, and in math and programming
this means that uncharitable hermeneutics can "prove" you "false", but
IF you are clear and readable then you are true and they are wrong.

For example, in calculus, there's no such thing as "the smallest real
number > 0": but it is sometimes a useful fiction.

No, the error lies in *assuming* a stack-based implementation without
specifying that assumption. C does not require implementations to be
stack-based, and not all implementations are stack-based.



MrNilges, you really need to learn to read the material you're
discussing before you give opinions about it. Herbert Schildt claims
to teach ANSI C, and your saying "no" doesn't change the facts. It is
certainly true that he includes non-ANSI stuff, but he is obviously
aware of the distinguishing line, believes he knows where that line
is, and endeavours to teach it.

McGraw and he decided to use ANSI because of the confusion created by
the standards effort, an attempt to use public monies and the public
interest to protect corporate profits.

"However, the main emphasis [of this book] is on the ANSI C standard"

The main, not the only.

- Herbert Schildt.
"This book fully covers and emphasizes the ANSI C standard" - Herbert
Schildt.

And more.

"Non-ANSI functions will be marked to avoid any confusion" - Herbert
Schildt, in a clear indication of his recognition that the separation
of ANSI C routines from extensions is a significant one.

Seebach's basic dishonesty or fallacy is his claim or belief that the
Standard could make, in addition to positive claims, negative claims.
For example, to reason that BECAUSE the Standard does NOT mention
stacks, one may not talk about stacks lest one make a false claim, is
a reversion to a barbarous Scholasticism, the Scholasticism of the
"proof" that all books except the Bible (or Qu'ran) should be burned:
"if it is in the Bible (or Qu'ran), we should read it there: if it is
not in the Bible (or Qu'ran) it is the word not of G-d (or Al'lah) but
of Satan (or Shaitan), therefore it, and all *kafirs* who preach this
blasphemy, must be consigned to the flames".

Now, given your background, you may find this reasoning perfectly
acceptable. I do not. I would find it MORE acceptable in reasoning
about The Most High, but even on religious terms, is it not blasphemy
to treat the Standard as Holy Writ? And is it not just silly to treat
Schildt like Joan of Arc and burn him repeatedly as a witch, which is
what you're doing?

"ANSI" - Herbert Schildt; the word is peppered through my sample text
(which is not the Annotated ANSI C Standard, by the way, and the very
existence of his book by that name shows that he is trying to teach
ANSI C).

Hey, reading Rainbow, the mere occurence of a Noun is not a claim.

Because it contains little, if anything, of value to most C
programmers, but much that is only of interest to special interest
groups. For example, a whole bunch of complex arithmetic stuff has
been added - but that ship has sailed, as anyone who needs it has
either already written their own library or uses an implementation
extension.

Incompetent and semi-competent programmers and their managers have
been saying this in my experience since 1970. My manageress at
Motorola, a singularly unpleasant woman, told me in 1979 that all
possible compilers had been written. Of course, at that very instant,
a fat French immigrant in a Goombah shirt was cruisin' around Silicon
Valley, and writin' a Pascal Compiler.

In the old days, they told Tom Edison it couldn't be done. But even in
the 1970s they said instead, been done, son.

I say, let reinvention of the wheel thrive.

For those who are a little reluctant to believe your assertions, can
you please name some of these people and provide easily verifiable
independent reference sources that back up your claim?

Edward G. Nilges, author of Build Your Own .Net Language and Compiler,
Apress 2004: I defend reputations which is somewhat different

Jacob Navia (67800 Google Hits, many from .edu sites referencing his
compiler): I sense from his posting pattern and comments that he
prefers to code

Dan Appleman (prolific commentator and author primarily on Windows
programming who unlike me has a sweet temper and who unlike me has
been honored for his decent and eleemosynary nature)

Herb Schildt, author of Born to Code and many other well-received and
top-selling books on programming who has NEVER to my knowledge
bothered to wrestle with you swine since he gets dirty and you like it

 

[Phil Carmody]

The word "stack" has two relevant meanings.

One is a hardware stack, which advances in a particular direction
through contiguous memory. This is a common, but not universal,
method used in C implementations.

The other is a data structure with last-in first-out (LIFO) behavior.
This kind of stack can be implemented in a variety of ways: as a
contiguous array, as a linked list, or as organized flocks of carrier
pigeons.

The contiguous array and the linked list behave subtly differently.
A linked list implies nothing about the size of the data that its
stage in the LIFO is responsible for. In contrast, a contiguous
array's made of identically sized atoms. One has to code a linked
list within the array in order to emulate the linked list's flexibility.

I'm sure that Nick was using the term "logical stack" to refer to the
latter.

I'm not. That would rarely be the more likely of the two to be meant.

The problem is that people who, for example, talk about "passing
arguments on the stack", are generally referring to a contiguous
hardware stack and incorrectly assuming that it's universal in C
implementations.

Agreed.

Phil

 

[Nick Keighley]

There are also processors which have a dedicated hardware stack (which
is called a stack in the processor manual) on which the "standard" C
implementation deliberately avoids using the [stack] most of the time. The
simple reasons for this being that the stack is only 8 words deep and
there is no accessible stack pointer so *all* you can do is push values
on and pop values off (a call pushes the program counter and a return
pops it, in addition there are push and pop instructions, normally used
to pop return values off the stack before it overflows and push them
back again later). There is a convention of using AR7 as a software
stack pointer, and a convention on which direction it grows, but you
could equally well use any of the other indirect registers (you would
probably not use AR0 because it has other uses) and because of the way
the registers work you could have the stack grow either up or down with
no loss of performance.

I'm sure I've mentioned the processor I'm thinking of, the TMS320C25
(which is one of my favourite processors) in these discussions before,
but I could be wrong.

What I called a "logical stack" would be the ADT type of stack. As
Spinoza
comments this is accessible only at one end. So an ADT would go
something
like:-

ADT: Stack
CONSTRUCTOR () -- creates an empty stack
push (Item)
Item pop ()
Item top () -- returns top item
Truth empty? ()

I'm sure I've got a VDM definition of a stack somewhere...

This would actually be a PITA to implement C on top of as there is no
access to non-top items. So using Spinoza's definition (a stack is
something
that allows access at only one end) we'll reverse Jacob's question.

"does anyony know of a real world implementation of C that uses a
computer-science style stack to pass arguments?"

In thirty years of programming I have never come across one.

 

[Chris Dollin]

What I called a "logical stack" would be the ADT type of stack. As
Spinoza
comments this is accessible only at one end. So an ADT would go
something
like:-

ADT: Stack
CONSTRUCTOR () -- creates an empty stack
push (Item)
Item pop ()
Item top () -- returns top item
Truth empty? ()

I'm sure I've got a VDM definition of a stack somewhere...

This would actually be a PITA to implement C on top of as there is no
access to non-top items.

It matters not; just make the items unfixed-size arrays of bytes. The
"top item" is the current frame with all the stacked locals [if there
are none, as an obvious optimisation we can omit the frame ...]. A C
function can only see its own frame, not any non-top frame, so that's OK.

[It can /access/ elements in the non-top frame, using pointers,
but that's using a completely different mechanism.]

--
"Is there a reason this is written in iambic pentameter?" Marten,
/Questionable Content/

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

 

[Nick Keighley]

Perhaps it's Kant/Heisenberg kinda thing. Time is an attribute of
one's perception of the world; not an attribute of the world itself.

in that case who is going to win the 3:30 at Haydock?

 

[spinoza1111]

jacob navia wrote:
Keith Thompson a écrit :
The problem is that people who, for example, talk about "passing
arguments on the stack", are generally referring to a contiguous
hardware stack and incorrectly assuming that it's universal in C
implementations.

<snip>





There are also processors which have a dedicated hardware stack (which
is called a stack in the processor manual) on which the "standard" C
implementation deliberately avoids using the [stack] most of the time. The
simple reasons for this being that the stack is only 8 words deep and
there is no accessible stack pointer so *all* you can do is push values
on and pop values off (a call pushes the program counter and a return
pops it, in addition there are push and pop instructions, normally used
to pop return values off the stack before it overflows and push them
back again later). There is a convention of using AR7 as a software
stack pointer, and a convention on which direction it grows, but you
could equally well use any of the other indirect registers (you would
probably not use AR0 because it has other uses) and because of the way
the registers work you could have the stack grow either up or down with
no loss of performance.

I'm sure I've mentioned the processor I'm thinking of, the TMS320C25
(which is one of my favourite processors) in these discussions before,
but I could be wrong.

What I called a "logical stack" would be the ADT type of stack. As
Spinoza
comments this is accessible only at one end. So an ADT would go
something
like:-

ADT: Stack
    CONSTRUCTOR ()    -- creates an empty stack
    push (Item)
    Item pop ()
    Item top ()       -- returns top item
    Truth empty? ()

I'm sure I've got a VDM definition of a stack somewhere...

This would actually be a PITA to implement C on top of as there is no
access to non-top items. So using Spinoza's definition (a stack is
something
that allows access at only one end) we'll reverse Jacob's question.

"does anyony know of a real world implementation of C that uses a
 computer-science style stack to pass arguments?"

In thirty years of programming I have never come across one.

This is only the case if you overdefine a stack as being something
which can never be accessed at all except by push and pop of top
elements, and in real programming this is overly restrictive.
Therefore even in pure stack-oriented languages like Forth and
programmable calculator environments you could rotate the top, etc.
Even the above OO definition of a stack can be enriched with methods
to push, pop or even rotate multiple contiguous items in "frames".

 

[spinoza1111]

spinoza1111wrote:

You clearly didn't read what I posted. Check for starters how control
flow was done on the IBM 1620 you referenced earlier. As your
fundamental understanding of compilers advances, backed by
experience there will be the magical moment that there are actually
implementation choices for code generation.

This is an example of the type of post that should be eliminated,
since its topic sentence and its topic is I, and it is neither
compilers nor stacks, and it is Walter, wounded Walter, getting his
licks in by challenging my limitations...matters about which I am more
familiar with than Walter, wounded Walter, and which aren't germane.

Furthermore Walter, wounded Walter, runs out of steam after a good
beginning and (like many of the teachers of writing English prof
Stanley Fish indicts this week in his New York Times blog "Think
Again") Walter cannot finish a coherent sentence.

Control flow was actually "done" on the IBM 1620. Not all subroutines
need to be recursive, and many cases of recursion can be translated to
iteration.

However, to regard workarounds as advances, albeit common in
programming, is rebarbative, beard to beard, gnome to gnome. Sure,
there are plenty of programmers who regard themselves as smarter than
computer science professors because they did things on the IBM 1620
that it appears Dijkstra is saying couldn't be done.

But that isn't what Dijkstra is saying. He was saying, here and
elsewhere, that it's not "elegant" to push a pea up a mountain with
your nose: that mathematics is not a fairground attraction, and that
the measure of brilliance in programming or mathematics should not be
that of the circus or performing ape.

Dijkstra was of the same generation as Glenn Gould. Glenn Gould felt
that music should not be a fairground attraction in which a bunch of
wealthy bastards gleefully watches for the "genius" performer to make
an error, thereby confirming the bourgeoisie in their smug stupor of
self-satisfaction. Somewhat like Gould, Dijkstra refused to "perform"
by "hacking" solutions for IBM computers in order to satisfy an easily
awed audience, and like Glenn Gould, Dijkstra left the game.

Gould knew that there was something more to performing music than the
"culinary" appeal of pretty tunes measurable only by audience
satisfaction. Likewise, Dijkstra knew that data systems' worth is not
measured by "happy end users", a phrase of the nursery.

Having myself debugged a 1401 compiler and written, in the 1620's
sister machine, a data base that used Polish notation and stacks with
a small fixed upper bound, I agree with Dijkstra's theme, which is
that poor design out of the box isn't made any less poor by being
rescued by the hard work of anonymous grunts. Capitalist economics
assumes that most of us are idle fellows whose labour is worthless
unless we're making someone rich but I'd say that the design errors of
IBM hardware were objectively a way to cause reasonably intelligent
people to waste their time and fail to solve societal problems...which
have grown worse over time.

An expense of spirit in a waste of shame.

 

[spinoza1111]

In <[email protected]>,

spinoza1111wrote:


No, that's nonsense.


Course you can. "All dogs are cats." - clear, readable, and false.

I would stay out of this game if I were you. "All dogs are cats" is
neither clear nor readable because if it appeared in a work of
nonfiction it would be accounted a typo.

I'm always clear and readable.
Therefore, by your own argument,
everything I say is right and you are therefore wrong to disagree
with me, ever.

Petitio principii.

You claim I said "MrNilges", but I didn't. I said "Mr Nilges". Your
newsreader is eliding spaces again.

So? I have bigger fish to fry. Starting with you.

That's an assertion for which I can see no supporting evidence. I
won't say you're lying, but I can think it.

Stop thinking. It is obviously a strain for you.

"However, the main emphasis [of this book] is on the ANSI C
standard"

The main, not the only.

Sure. I didn't say he set out /only/ to teach ANSI C. Nevertheless, he
set out to teach ANSI C. And failed.

....and is laughing all the way to the bank.

Sure. I didn't say he set out /only/ to teach ANSI C. Nevertheless, he
set out to teach ANSI C. And failed.

....and is laughing all the way to the bank, since he fulfilled a need
and wrote a book you could not write.

Anyone may talk about anything they like, but that doesn't make them
right. If you want to rabbit on about stacks, fine, but if you give
the impression that they are *the* way in which C is implemented, you
betray your ignorance.

A number of posters have said that they have seen no other way. You
haven't shown us how to implement C without stacks. Something that
works like a stack is needed to evaluate expressions and to manage
subroutine call and return.

This happens to be a mathematical truth. A language with parentheses
(such as C, which uses literal parentheses in expressions, and which
uses the curly brace as a distinct form of balanced parenthesis to do
structured flow control) CANNOT be parsed by a finite state automaton
but NEED NOT be parsed by an automaton which has more than a read-
write tape and a stack.

This proves that to parse C you MUST USE a stack.

Now, I suppose that for perhaps 75% of all C programs, you could
discover that their usage of subroutine (function) calls is bounded or
nonexistent, and as such, could be determined at compile time. I
suppose that having made this determination you could make copies of
each function, suitably renamed. You could "preprocess"

void main()
{
a();
}

void a()
{
b();
}

void b()
{
printf("Hello world\n");
}

into

void main()
{
printf("Hello world\n");
}

Indeed, some optimizers go this far.

But you're bonehead if you believe that this is possible in general.
You're not a bonehead. Are you?

It isn't a matter of opinion that for the same reason you need a stack
in formal automata theory to PARSE C and C-like languages, you need a
stack to RUN their code. Therefore, you are libeling Schildt, since he
was well within known science when he used the stack to explain the
runtime.

Certainly true, but as usual you completely missed my point, which is
that the theme of ANSI conformance litters his books.

It's not his fault that C programs are in the main not conformant. It
was the fault of the C99 standards men, who failed to define C so as
to preserve the profits of vendors.

Incompetent and semi-competent programmers and their managers have
been saying this in my experience since 1970.

From what I have seen of your C knowledge, you are in no position to
judge competence.

My manageress at
Motorola, a singularly unpleasant woman, told me in 1979 that all
possible compilers had been written.

I don't see how this relates to my answer to your question. You asked
why C99 had been unsuccessful. I told you the basic reason - that it
fails to meet any significant need. Your reply appears to be a
complete non sequitur.

<snip>

Edward G. Nilges, author of Build Your Own .Net Language and
Compiler, Apress 2004: I defend reputations which is somewhat
different

So by "some" you mean "you". Let me insert that back into the
original: "The reason [that C99 failed], according to Edward G Nilges
(a deconstructionist teacher currently working in Hong Kong), is that
it was less concerned with the needs of working programmers, and more
concerned with spending public monies".

If one is some, then more than one is presumably many, so we can add
"many people think he's talking tosh, but then he always does."

Jacob Navia (67800 Google Hits, many from .edu sites referencing his
compiler): I sense from his posting pattern and comments that he
prefers to code

I have seen no evidence that Jacob Navia believes C99 failed *at all*,
let alone that it failed for the reason you claim.

Dan Appleman (prolific commentator and author primarily on Windows
programming who unlike me has a sweet temper and who unlike me has
been honored for his decent and eleemosynary nature)

I have seen no evidence that Dan Appleman believes C99 failed *at
all*, let alone that it failed for the reason you claim.

Herb Schildt, author of Born to Code and many other well-received
and top-selling books on programming who has NEVER to my knowledge
bothered to wrestle with you swine since he gets dirty and you like
it

I have seen no evidence that Herbert Schildt believes C99 failed *at
all*, let alone that it failed for the reason you claim.

<snip>

--
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- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -

 

[spinoza1111]

In

spinoza1111wrote:



No need. You *can*, but there's no "must" about it. The functionality
we're after is that of placing a bunch of parameters in a place where
the called function can find them, and providing the called function
with the necessary knowledge. This can easily be done using
practically any kind of searchable data structure - BSTs, B+-trees,
hash tables... There is no need whatsoever for it to be a stack, or

BSTs accessed as a stack.

B+-trees accessed as a stack.

Hash tables accessed as a stack.

OK, suppose when a function is called in Your Stupid Runtime (YSR) it
hashes its name to a global table to find its activation record.
Beauty eh?

Well, no. It may be calling itself recursively, directly or
indirectly.

OK, the caller will pass the callee an index to a table.

Oops. Where does the callee get the index? To fall into the language
of the typical incompetent programmer, "duh the caller will put it in
a buffer".

OK, how does the callee know where to look?

In a non-threaded environment, it is undecidable (a Halting Problem)
how many activation records will need to exist at any one time for any
given function. These activation records need to be accessible,
therefore many years ago wise men said that there shall be such an
area, and it need be accessible only at the top and lifo.

Behold, the Stack was created
It was much hated
By those who wanted the people to in darkness walk.

Any given procedure on entry has to find its activation record. At a
minimum it needs to know where to branch back on exit. Even if we do
something really, really stupid, and allocate a separate area for each
function, that function has no way of knowing which of n>0 activation
records it needs in the course of execution: it has no "key", since
the "key" would be part of the activation record itself.

It cannot "search" these, its "list" of activation records, therefore
it has to agree to take the activation record from one place, which
happens to be the most recently assigned place.

Now, my dear boy, this could be physically ANYWHERE in the list of
activation records. It could be at the end. It could be at the middle.
Or, it could be on the Planet Gazumbo. But no matter where it is, it
is the most recently USED place and it is accessed (drum roll) LIFO.
Therefore, even if we had a separate list of activation records for
each function they would each be a stack.

Oops.

Seebach was forbidding Schildt to speak clearly like so many cheap
thugs. He's asking Schildt's students not to even speculate about
runtime and so is a throwback to IBM programming of the 1960s, where
programmers sat miserably in cubicles speculating about what happens
when code runs.

to work like a stack. That just happens to be a common way to do it
because it's simple and quick.

To the programmer without science,
Shit happens.
To the uneducated without self-reliance,
Shit happens.

 

[Nick Keighley]

NickKeighleywrote:

What I called a "logical stack" would be the ADT type of stack. As
Spinoza
comments this is accessible only at one end. So an ADT would go
something
like:-

ADT: Stack
    CONSTRUCTOR ()    -- creates an empty stack
    push (Item)
    Item pop ()
    Item top ()       -- returns top item
    Truth empty? ()

I'm sure I've got a VDM definition of a stack somewhere...

This would actually be a PITA to implement C on top of as there is no
access to non-top items.

It matters not; just make the items unfixed-size arrays of bytes. The
"top item" is the current frame with all the stacked locals [if there
are none, as an obvious optimisation we can omit the frame ...]. A C
function can only see its own frame, not any non-top frame, so that's OK.

[It can /access/ elements in the non-top frame, using pointers,
 but that's using a completely different mechanism.]

cool! you're stacking frames or environments.

 

[Nick Keighley]

This is only the case if you overdefine a stack as being something
which can never be accessed at all except by push and pop of top
elements,

that's what a stack *is*. Read any basic computer science text
or data structures book. For instance from the documentation for C++'s
std::stack

"A stack is an adaptor that provides a restricted subset of Container
functionality: it provides insertion, removal, and inspection of the
element at the top of the stack. Stack is a "last in first
out" (LIFO)
data structure: the element at the top of a stack is the one that was
most recently added. [] Stack does not allow iteration through
its elements."

So somebody thinks that might be useful.

and in real programming this is overly restrictive.

not always. Parsers, simple calculators, infix to RPN,
maybe undo in editors etc.

Therefore even in pure stack-oriented languages like Forth and
programmable calculator environments you could rotate the top, etc.
Even the above OO definition of a stack can be enriched with methods
to push, pop or even rotate multiple contiguous items in "frames".

yes but they aren't *real* stacks. You make it much harder to
prove things by extending these basic CS primitives arbitarily.

 

[Chris Dollin]

spinoza1111 wrote:

I would stay out of this game if I were you. "All dogs are cats" is
neither clear nor readable because if it appeared in a work of
nonfiction it would be accounted a typo.

This is a work of nonfiction. Do you account it a typo?

--
"There are not enough adjectives in the English Faye,
language to describe how wrong you are." /Questionable Content/

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

 

[Nick Keighley]

BSTs accessed as a stack.

B+-trees accessed as a stack.

Hash tables accessed as a stack.

these are what I call "logical stacks"

OK, suppose when a function is called in Your Stupid Runtime (YSR) it
hashes its name to a global table to find its activation record.
Beauty eh?

Well, no. It may be calling itself recursively, directly or
indirectly.

OK, the caller will pass the callee an index to a table.

Oops. Where does the callee get the index? To fall into the language
of the typical incompetent programmer, "duh the caller will put it in
a buffer".

OK, how does the callee know where to look?

it's a global. You could call it _current_activation_environment
or something. Or you could keep it in a register. R7 is a common
choice.

In a non-threaded environment, it is undecidable (a Halting Problem)
how many activation records will need to exist at any one time for any
given function.

why does threading make this problem any easier?

These activation records need to be accessible,
therefore many years ago wise men said that there shall be such an
area, and it need be accessible only at the top and lifo.

Behold, the Stack was created

Any given procedure on entry has to find its activation record. At a
minimum it needs to know where to branch back on exit. Even if we do
something really, really stupid, and allocate a separate area for each
function, that function has no way of knowing which of n>0 activation
records it needs in the course of execution: it has no "key", since
the "key" would be part of the activation record itself.

it's a global at a fixed location.

It cannot "search" these, its "list" of activation records, therefore
it has to agree to take the activation record from one place, which
happens to be the most recently assigned place.

Now, my dear boy, this could be physically ANYWHERE in the list of
activation records. It could be at the end. It could be at the middle.
Or, it could be on the Planet Gazumbo. But no matter where it is, it
is the most recently USED place and it is accessed (drum roll) LIFO.
Therefore, even if we had a separate list of activation records for
each function they would each be a stack.

Oops.

C can do this but languages (eg. Scheme) that have things called
"continuations" (an abilty to resume at a previously saved location
and environment) cannot. Even C has messy things like longjmp and
signal.

Seebach was forbidding Schildt to speak clearly <elide nonsense>.

On the contrary he was trying to get him to speak clearly. It's
important
people don't walk away thinking recursion won't work ("but you've
already
used the memory for the parameters once!") but also important they
don't
get the mindset that causes them to ask

int a [2];
int j;

/* it's ok to access j like this isn't it?
beecause it's next to a on the stack */

a[2] = 99;


or a fascination with whether the stack "goes up or goes down".

An interest in implementaion is good (I like to know how things
work) but can become unhealthy.

My first reaction on reading the Ada spec. was "that's never going to
work". Because I couldn't see how exceptions (they were called
exceptions?)
could be coded in Z80 assembler. Cheaply.

But perhaps my scepticism was warrented. "Ada is fine on VAX 11/780;
we just can't get a Vax in the cockpit of a fighter aircraft".
"Ada's rendevous mechanism is fine; if you don't want real time
performance". "Compiler generators come in four sizes; small, medium,
large- and Ada". But Moore's Law fixed all that.

 

[Chris Dollin]

A number of posters have said that they have seen no other way. You
haven't shown us how to implement C without stacks. Something that
works like a stack is needed to evaluate expressions and to manage
subroutine call and return.

"Something that works like a stack", perhaps. For some value of "works
like". That "something" need not be the same as the thing the machine
manipulates that's called "a stack". There are at least two concepts
of "stack" knocking around, and it's at least confusing and more likely
wrong to confuse them.

For example ... subroutine call and return can be managed with
back-linked relocatable heap blocks. [I'm not claiming this is an
/efficient/ implementation.] While this is "stack-like", I don't
believe it's what many people mean when they talk about "the
stack". (And, "the" stack? A multi-threaded program -- and some
non-Standard-C programs are multi-threaded -- have multiple stack-
like things.) And as you have alluded to [later, snipped], a C
program without recursion need not use a stack /at all/.

As for expression evaluation: no, that doesn't need a run-time
stack (unless it calls functions that might recurse through this
one). Such a stack may be /convenient/, but it's not /necessary/.

This happens to be a mathematical truth. A language with parentheses
(such as C, which uses literal parentheses in expressions, and which
uses the curly brace as a distinct form of balanced parenthesis to do
structured flow control) CANNOT be parsed by a finite state automaton
but NEED NOT be parsed by an automaton which has more than a read-
write tape and a stack.

This proves that to parse C you MUST USE a stack.

That's compile-time work. I don't think parties on either side of
the discussion were talking about compile-time. Certainly when
they say that automatic variables are allocated on the stack,
or that arguments are passed on the stack, it's not the /compilers/
stack they're talking about. As far as I can tell.

--
"Is there a reason this is written in iambic pentameter?" Marten,
/Questionable Content/

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

 

[spinoza1111]

In

spinoza1111wrote:


No, as a BST.


No, as a B+-tree.


No, as a hash table.


No. Daft idea.


Wrong. You devote a register to the purpose.

"Devote"...hmm...

Precision of language (which includes a precise understanding of its
fuzziness) is here replaced by a stern Calvinist devotion which hopes,
barbarously, for reward: for "devoting registers" means they must be
saved...in save areas that insofar as they bloody well work,
constitute a stack.

From the register.

If the index points to a "work area" (where the demotic programmer
usage is formed and deformed by a confusion of virtue with precision:
programmers actually reason that if they give an area a grim enough
term it will serve its purpose), this "work area" must be "saved" (or
washed in the blood of the Lamb)...in a stack.

It looks in the register.

Schildt has written the runtime of a programming language. Navia has
written the runtime of a programming language. Hell, I have written
the runtime of a programming language. You have not. Instead, you've
just triumphantly, in your "register", reinvented a broken wheel:
essentially you've invented a stackless and dickless wonder: the IBM
OS/360 calling convention. This failed to work, creating a bogus
distinction between "re-entrant" and "non-re-entrant" code, as if the
latter could be a useful artifact over time.

 

[Walter Banks]

Rant snipped

Missed the point, again...

 

[spinoza1111]

these are what I call "logical stacks"
OK.





it's a global. You could call it _current_activation_environment
or something. Or you could keep it in a register. R7 is a common
choice.

If its a "scalar" global then there must be a "vector" somewhere else,
and this "vector" is a...stack.

why does threading make this problem any easier?

It makes it harder, Reading Rainbow.

<snip nonsense>

You have no ear for poetry, son.

it's a global at a fixed location.

It is a mark of incompetence to speak of globals at fixed locations.
It's Cobol psychology.

It cannot "search" these, its "list" of activation records, therefore
it has to agree to take the activation record from one place, which
happens to be the most recently assigned place.

Now, my dear boy, this could be physically ANYWHERE in the list of
activation records. It could be at the end. It could be at the middle.
Or, it could be on the Planet Gazumbo. But no matter where it is, it
is the most recently USED place and it is accessed (drum roll) LIFO.
Therefore, even if we had a separate list of activation records for
each function they would each be a stack.

Oops.

C can do this but languages (eg. Scheme) that have things called
"continuations" (an abilty to resume at a previously saved location
and environment) cannot. Even C has messy things like longjmp and
signal.
Exceptions.

Seebach was forbidding Schildt to speak clearly <elide nonsense>.

On the contrary he was trying to get him to speak clearly. It's
important
people don't walk away thinking recursion won't work ("but you've
already
used the memory for the parameters once!") but also important they
don't
get the mindset that causes them to ask

   int a [2];
   int j;

   /* it's ok to access j like this isn't it?
      beecause it's next to a on the stack */

   a[2] = 99;

or a fascination with whether the stack "goes up or goes down".

This is nuts. You're afraid the students will create mental models and
metaphorical maps, so you don't tell 'em jack.

It's just bad practise to index past one variable in an activation
record and expect to see the "next" parameter. You might in 99% of
cases, but it's still bad style, and it is no fault of the stack. It's
the fault of C.

I will concede that students can confuse accidental with necessary
elements when you create pictures in their minds, and the stack is a
vivid visual metaphor. It was probably invented by two geeks in the
company cafeteria, marveling at the fact that upper trays, the most
accessible, were also the warmest and wettest since the stack of trays
is accessed only at one end. But it was realized soon enough that
implementing a stack as a contiguous vector was not necessary.

Dijkstra in fact has an essay on finding a generalization of the
Pythagorean theorem for other than right triangles by dropping the
pictorial reasoning that accompanies its teaching in high or middle
school, and using symbolic reasoning instead.

But bitch-slapping Schildt for using the word without telling him how
to explain runtime operations, without having the skill or patience,
is a reversion to corporate programming of the Sixties where
programmers coded in ignorance.

An interest in implementaion is good (I like to know how things
work) but can become unhealthy.
True.

My first reaction on reading the Ada spec. was "that's never going to
work". Because I couldn't see how exceptions (they were called
exceptions?)
could be coded in Z80 assembler. Cheaply.

But perhaps my scepticism was warrented. "Ada is fine on VAX 11/780;
we just can't get a Vax in the cockpit of a fighter aircraft".

Good, because fighter aircraft are primarily used today to kill
civilians on the ground, especially by Israel.

"Ada's rendevous mechanism is fine; if you don't want real time
performance". "Compiler generators come in four sizes; small, medium,
large- and Ada". But Moore's Law fixed all that.

Indeed it did, except perhaps in the murderer's "cockpit".

 

[spinoza1111]

<snip>

This is only the case if you overdefine a stack as being something
which can never be accessed at all except by push and pop of top
elements,

that's what a stack *is*. Read any basic computer science text
or data structures book. For instance from the documentation for C++'s
std::stack

"A stack is an adaptor that provides a restricted subset of Container
functionality: it provides insertion, removal, and inspection of the
element at the top of the stack. Stack is a "last in first
out" (LIFO)
data structure: the element at the top of a stack is the one that was
most recently added. [] Stack does not allow iteration through
its elements."

So somebody thinks that might be useful.

That's the OO definition, and it is useful. However, most real
implementations allow stack dumps, and to do them you need to access
all members. This can be done by staying inside the restrictive
definition (popping elements to an array or linked list, and then
pushing them back) or the stack can allow it as a special favor. It's
still a "stack" in ordinary computing parlance.

not always. Parsers, simple calculators, infix to RPN,
maybe undo in editors etc.


yes but they aren't *real* stacks. You make it much harder to
prove things by extending these basic CS primitives arbitarily.- Hide quoted text -

This is another type of arrogance. Precisely as Euclidean geometry
emerged in praxis only to be codified by Euclid, actual programming
praxis developed the stack, and then became "computer science" lest
the working class be credited with creativity: Hegel's Slave must
never be acknowledged by the Master, yet the Master creates nothing
(cf the chapter on Lordship and Bondage in Hegel's Phenomenology of
Mind).

No, the reason why you *must* use a stack to parse and run C isn't
because there's a Platonic idea of a Stack up in the sky which may not
be "violated" by rotating its two top entries, it's because C is
Chomsky 2 for the most part (but not exactly, since C is praxis as
well as theory).

Most programmers and many computer scientists have an unexamined
Platonist philosophy of mathematics. I don't. Mine is more
intuitionist and marxist.

 

[osmium]

My recursive descent parser for subsetted quick basic in "Build Your
Own .Net Language and Compiler" passed the parser's state as
parameters, and did not have a stack for them. But the stack still
existed: I was in effect using the runtime stack of Visual Basic .Net.

Given the state of the art 30 years ago and the fact that Univac more
or less collapsed along with the "Seven Dwarfs" of the computer
industry in 1971, it is possible that the runtime of the compiler
allocated a large fixed array...but then treated this as a stack. It
may have limited the allowed depth of subroutine calls. But as such it
screwed up, rather than proving that you don't need a stack to do C,
or that Herb was wrong.

Why did you post this as though it responded to my post in some
way/shape/form? Jacob Navia said the regulars never came up with an example
of a stackless machine. I provided a concrete, provable example. I am not
sure I qualify as a regular", but other than that, I see no possible
rebuttal. Instead, you launch into a war story about your recursive descent
parser and the fate of the mainframe industry.

 

[jacob navia]

osmium a écrit :

spinoza1111 wrote:

Why did you post this as though it responded to my post in some
way/shape/form? Jacob Navia said the regulars never came up with an example
of a stackless machine. I provided a concrete, provable example.

Wait, a computer from the sixties????

How the hell do you expect that I verify your assertion in
2009??

Excuse me but if all the examples the regulars can bring is a machine
that existed around 40 YEARS ago, and disappeared at the beginning
of the seventies... well

no comment...