K
Keith Thompson
jacob navia said:
Examples have been presented of machines that are still in production
use. Please pay attention.
Would that it were so.
[...]
Examples have been presented of machines that are still in production
use. Please pay attention.
Would that it were so.
[...]
S
spinoza1111
Sorry for the misunderstanding, sir. My point was that there were
machines without hardware stacks, and that on these machines, stacks
had to be implemented in software to handle the runtime of languages
like C.
The IBM 1401 had no stack. To implement a specification language for a
data base I developed in 1973, where the user or a programmer would
enter selection logic in Reverse Polish notation, I implemented a
stack with a fixed bound, indexed by one of the 1401's hardware index
registers: the 1401's index registers were at fixed memory locations
between 87 and 95 if memory serves. Like many compilers of its day,
this imposed a constraint on the complexity of selection logic over
and above the length of the expression, whereas today, software stacks
can be "unlimited" linked lists extended as needed.
Stackless IBM machines like the 360 could run Algol and PL.I, where
both languages require a stack, by supporting some sort of stack in
their code.
The fact that stackless machines have disappeared outside of embedded
systems clearly makes your case. I was in no way attempting to
undermine it. Quite the opposite: as a mathematical realist (but not
as a Platonist) I have shown that the stack as a concept doesn't
disappear merely if we don't implement it as an unbounded array or
linked list. Even if we write a recursive descent compiler without
using an explicit stack, preferring to pass compiler state as a
parameter, we're using a stack, that of the runtime.
Some years prior to writing the 1401 code, I'd gotten into a debate in
my class on the philosophy of logic with students who believed that
Jan Lukasiewicz' Polish Logic (from which of course we get RPN) showed
that parentheses had no ontological status and needed no ontological
assay, as opposed to logical operators and variables. The teacher
pointed out that the function still was part of "the world" and
therefore had ontological significance.
Likewise for the stack. For a classic regex you need nothing like a
stack. For a language that is mostly or wholly context free but which
uses unbounded "parentheses" (or which expresses control flow in RPN)
you need a stack. Period.
S
spinoza1111
Oh, I see the problem. Jacob, I did not write that. I came up with
cases where stacks were missing and therefore had to be implemented.
Like Voltaire's (?) God, if the stack did not exist we'd have to
invent it...otherwise we'd be programming in regular expressions.
S
spinoza1111
It's not a war story. I got into data processing as an elaborate
(Vietnam era) draft dodging scheme (which seems to have gotten out of
hand) because I agreed with Jane Fonda et al. So, it's not a war
story. My point was that even long ago, when IBM gear didn't have
stacks and the 1620's subroutine call machine was messed up, if you
wanted to parse or run languages in the Algol family, you needed
simulated stacks (aka stacks). All you could do was compile Fortran
with just Go To and no subroutines and some sort of ugly hack for
parenthesised expressions.
Indeed, when I worked on early cellphone technology at Motorola, some
clown had implemented a compiler without stacks. Instead, it allocated
a fixed array of activation records for subroutine calls, and when
that array was full, it was like "that's all folks". Recursion?
Whuzzat? A Communist plot?
W
Walter Banks
jacob said:
How recent do you want? The eTPU released in the last few years is a stackless processor used in automotive and general aviation engine control and process control. It is a mid volume processor with about 100M currently out there.
Several RISC processors developed in the last decade do not have stacks. Xgate for example.
A Microchip PIC whose ISA (Harvard Architecture) released in the last year has a limited subroutine return stack and no data stacks.
A Freescale CISC processor 68RS08 (2006) does not have a stack.
w..
S
spinoza1111
You are grasping at straws here. If you can write an optimizing
compiler that detects code that doesn't need a stack, this doesn't
prove that C doesn't need a stack. And you haven't proved at all that
Schildt was not right in using the most vivid metaphor.
Surely you jest: are you drunk? To prove that you don't need a stack
to evaluate expressions, you have to require that all expressions must
be evaluated left to right (or right to left) without precedence, as
in APL Hell. It might be possible to "preprocess" an expression
mathematically to avoid using a run time stack, but this means you're
doing runtime work at compile time. Nothing wrong with that
(optimizers do it for constant expressions) but it's declaring
victory, not victory. It's a game of whack a mole. The stack keeps
"popping" up and you keeping "pushing" it down.
Even if you inline everything you still need a stack for expression
evaluation at run time.
Schildt was using a well-known and well-respected teaching device: to
explain the semantics of C using an idealized machine with a stack.
There is indeed no reason why I write
Pentam Iamb: I am who am,
S
spinoza1111
Don't patronize your betters.
Silence is death.
J
jacob navia
Walter Banks a écrit :
and general aviation engine control and process control. It is a mid
volume processor with about 100M currently
out there.
This is a slave processor for handling several input/output channels at
once. There is no standard C compiler for this thing, probably
because the lack of a stack register and many other limitations
intrinsic to a slave processor.
There is a limited C compiler that should
conform to a future standard of C for embedded processors.
As an example it lacks the essential point. A C Compiler that
supports a standard or even a great subset of the standard.
Again and again the same stuff. If it has a C compiler it has a stack...
It was difficult to find the instruction set for the Xgate but
eventually, I found one at
http://www.opencores.org/websvn,filedetails?repname=xgate&path=/xgate/trunk/doc/xgate_specs.pdf
What do we read at page 13?
Xgate Stack Pointer Register (XGISPHI)
Xgate Stack Pointer Register (XGISPLO)
Another hint is that in the documentation of freescale (the company that
makes this chip) it says:
<quote>
General Setup Guidelines (page 11)
Firstly, interrupts should be disabled: CLI (just to be sure), and the
initial stack pointer should be loaded. In most cases, on the S12X, a
value of $4000 (top of RAM+1) is adequate.
<end quote>
If that chip doesn't have a stack pointer I do not see how it could
be loaded at startup...
Does a C compiler run on that?
There are many processors out there but the discussion was about
C...
Sure, maybe that's why no C compiler for it exists?
There is almost no docs for that one. In the scale of unknown
and irrelevant chips that one should be in the first places.
By the way, where do you have that information?
Where can I verify that the chip has no stack???
Conclusion
There is no C implementation known without a hardware stack...
and general aviation engine control and process control. It is a mid
volume processor with about 100M currently
out there.
This is a slave processor for handling several input/output channels at
once. There is no standard C compiler for this thing, probably
because the lack of a stack register and many other limitations
intrinsic to a slave processor.
There is a limited C compiler that should
conform to a future standard of C for embedded processors.
As an example it lacks the essential point. A C Compiler that
supports a standard or even a great subset of the standard.
Again and again the same stuff. If it has a C compiler it has a stack...
It was difficult to find the instruction set for the Xgate but
eventually, I found one at
http://www.opencores.org/websvn,filedetails?repname=xgate&path=/xgate/trunk/doc/xgate_specs.pdf
What do we read at page 13?
Xgate Stack Pointer Register (XGISPHI)
Xgate Stack Pointer Register (XGISPLO)
Another hint is that in the documentation of freescale (the company that
makes this chip) it says:
<quote>
General Setup Guidelines (page 11)
Firstly, interrupts should be disabled: CLI (just to be sure), and the
initial stack pointer should be loaded. In most cases, on the S12X, a
value of $4000 (top of RAM+1) is adequate.
<end quote>
If that chip doesn't have a stack pointer I do not see how it could
be loaded at startup...
stack and no data stacks.
Does a C compiler run on that?
There are many processors out there but the discussion was about
C...
Sure, maybe that's why no C compiler for it exists?
There is almost no docs for that one. In the scale of unknown
and irrelevant chips that one should be in the first places.
By the way, where do you have that information?
Where can I verify that the chip has no stack???
Conclusion
There is no C implementation known without a hardware stack...
O
osmium
jacob navia said:
Jacob Navia also wrote, earlier:
How did 30 become 40? 2009-30 = 1979, this is the cutoff point YOU
provided. You can't unring a bell. The 1100 series was actively sold well
after 1979. You can find a paper describing the architecture in the
Proceedings of the ACM, unfortunately such papers are not free. You can
verify my assertion by reading that paper. The series did not disappear at
the beginning of the seventies.
O
osmium
spinoza1111 said:
Sorry for the misunderstanding, I thought you were an American. Anybody in
engineering or allied fields in that country knows what "war story" means.
O
osmium
osmium said:
It is the Communications of the ACM, or CACM, not proceedings. Damn.
K
Keith Thompson
jacob navia said:
Have you reached that conclusion on the basis of examining every
existing C implementation?
Consider the following hypothetical conforming C implementation.
Each function call creates an activation record containing space
for parameters, other local varables, and housekeeping information
(return address, etc). Every time a function call occurs at
run time, a new activation record is allocated via some mechanism
similar to malloc(). Successively allocated activation records are
not necessarily adjacent in memory, and do not necessarily occur
in any particular order in memory. (We'll assume for simplicitly
that the system has a single monolithic (virtual?) address space,
so the latter is meaningful.) On return from a function, its
activation record is deallocated by a mechanism similar to free(),
and the previous activation record (the one for the caller) becomes
the current one. Activation records are maintained in a linked
list to make this possible.
I assert that such an implementation is feasible, that it could
conform to the C standard, and that it does not use a "hardware
stack" in the sense that we've been using the term. Do you agree
so far? If not, why?
My understanding is that certain IBM mainframes, many of which
are currently in production use, use just such a mechanism.
This has been mentioned many times in threads here in which you
have participated.
How does this not falsify your claim that "There is no C
implementation known without a hardware stack"?
T
Tim Streater
Keith Thompson said:
Just to be clear about this, to me a "hardware stack" exists where a
machine has a register, probably called the SP in the manufacturer's
docs, where a procedure call (JSR, Jump To Subroutine, say) puts the
return address where the SP points, decrements the SP, and jumps off to
the procedure. The return from this is typically done with a RET
instruction that jumps to the address pointed at by the SP and then
increments the SP.
Arguments for the procedure will typically have been pushed on the stack
at some point (apologies if the above is a bit vague, it's 20 years
since I was looking at the PDP-11 or VAX instruction set).
Now, as I recall, the IBM 370 (and its follow up machines such as the
3090), don't have such a register, and their procedure call / return
cannot therefore use such a hardware stack. Yet I wrote lots of code in
C for IBM mainframes under VM/CMS, and I used - indeed *relied* on - the
ability of this code to be re-entrant.
Clearly Mr Navia is talking rubbish.
W
Walter Banks
jacob said:
The eTPU is a 24 bit processor with a complete instruction set.
We have a C compiler for the eTPU based on C99 and ISO/IEC 18037.
We run standard C test suites on this processor.
Wrong Xgate processor Google freescale xgate
There are at least three C compilers that support the xgate. xgate is used
both as a co-processor and in multiprocessor configurations with S12
and other parts
It does.
There are at least two C compilers for the RS08
I worked on the ISA for the RS08.
Now you have some examples.
My point is there are alternatives to stack based processors with C
compilers, some created recently spanning a range of processors and
applications. Each of these are mid to high volume embedded system
parts. Performance is the primary reason that these parts do not
have a stack. These parts especially the eTPU were designed for
compiler friendly machine generated code.
Most of the rest the stack less processors that I am aware of
are RISC ISA's.
Googling stackless processors gets about 16,000 hits many of
them on Stackless Python. There are some processor desciptions
and some stackless code implementation papers.
There are also many processors that have and effectively use
a stack. (Please don't take this comment out of context).
Regards,
Walter..
J
jacob navia
Tim Streater a écrit :
Clearly YOU do not know what you are talking about.
I rote in this group March 16th 2008, in a thread
called
BUNCH OF PEDANTS
----------------
The regulars go on denying that C uses a stack. They should
read this:
<begin quote>
Any function in C may be recursive
(without special declaration) and most possess several "automatic"
variables local to each invocation. These characteristics suggest
strongly that a stack must be used to store the automatic variables,
caller's return point, and saved registers local to each function;
in turn, the attractiveness of an implementation will depend heavily
on the ease with which a stack can be maintained.
<end quote>
This was written by an expert in C.
True, there is no mention of a stack in their bible
Fact is, there isn't any C implementations that don't use
a stack to store the automatic variables.
Up to now, this people are unable to put forward a single
example of an implementation that doesn't use a hardware
stack (maintained by a register in a contiguous memory
addressing space)
Their first "example" was ARM and some Risc processors.
I proved them wrong.
Then they started tripping with IBM mainframes. Nope, I showed
them the documentation of the IBM compilers for mainframes
where they describe the stack and its associated register (r13)
Then they started with the 8051. I showed them that that processor
has a stack (it has PUSH/POP instructions apparently) but it is
too small, so some compilers use an external stack.
Even if they have not a single example, they go on with bullshit of the
style "but an implementation *could* exist that... blah blah blah"
Facts are not important. The C standard does not mention a stack,
and that is it. It is possible then to throw at unaware people that
asks questions in this group sentences like
"C has no stack"
"There is no stack in C"
Since they have no arguments, they discuss with tricks like
1) After you have proved them yet another time wrong, they will
answer with the eternal sentence "The standard doesn't mention a
stack" and the discussion can start from the beginning
2) After you have proved that the machine XYZ DOES have a stack,
they say "But an implementation *could* exist" and the discussion
can start from the beginning.
I decided that it is a waste of time to discuss with them. They just
repeat their bullshit without caring about what you answer to them
Personally I will not answer any more to falcolner and co. "C has no
stack" for them? Let it be.
Clearly YOU do not know what you are talking about.
I rote in this group March 16th 2008, in a thread
called
BUNCH OF PEDANTS
----------------
The regulars go on denying that C uses a stack. They should
read this:
<begin quote>
Any function in C may be recursive
(without special declaration) and most possess several "automatic"
variables local to each invocation. These characteristics suggest
strongly that a stack must be used to store the automatic variables,
caller's return point, and saved registers local to each function;
in turn, the attractiveness of an implementation will depend heavily
on the ease with which a stack can be maintained.
<end quote>
This was written by an expert in C.
True, there is no mention of a stack in their bible
Fact is, there isn't any C implementations that don't use
a stack to store the automatic variables.
Up to now, this people are unable to put forward a single
example of an implementation that doesn't use a hardware
stack (maintained by a register in a contiguous memory
addressing space)
Their first "example" was ARM and some Risc processors.
I proved them wrong.
Then they started tripping with IBM mainframes. Nope, I showed
them the documentation of the IBM compilers for mainframes
where they describe the stack and its associated register (r13)
Then they started with the 8051. I showed them that that processor
has a stack (it has PUSH/POP instructions apparently) but it is
too small, so some compilers use an external stack.
Even if they have not a single example, they go on with bullshit of the
style "but an implementation *could* exist that... blah blah blah"
Facts are not important. The C standard does not mention a stack,
and that is it. It is possible then to throw at unaware people that
asks questions in this group sentences like
"C has no stack"
"There is no stack in C"
Since they have no arguments, they discuss with tricks like
1) After you have proved them yet another time wrong, they will
answer with the eternal sentence "The standard doesn't mention a
stack" and the discussion can start from the beginning
2) After you have proved that the machine XYZ DOES have a stack,
they say "But an implementation *could* exist" and the discussion
can start from the beginning.
I decided that it is a waste of time to discuss with them. They just
repeat their bullshit without caring about what you answer to them
Personally I will not answer any more to falcolner and co. "C has no
stack" for them? Let it be.
L
Lew Pitcher
On September 8, 2009 16:59, in comp.lang.c, jacob navia ([email protected])
wrote:
[snip]
Sorry, Jacob, but R13 is definitely *not* a hardware "stack pointer"
register.
The use of R13 in MVS (and it's follow-on operating systems) and VSE
(and /it's/ followns) is as a single pointer to a linked-list of
dynamically allocated memory blocks. There is no direct equivalent of a
PUSH or POP instruction that places data at a location pointed to by a
register /and/ increments (or decrements) the register atomically.
In fact, the use of R13 as a pointer to a save area (as this block is
called) is a /software convention/, and not dictated by hardware at all.
You can't say that R13 is a stack pointer in the hardware sense. The /best/
you can do is say that IBM mainframe pointers implement a fifo using a
linked-list of activation records, and the topmost activation record is
pointed to by R13 (and possibly other registers).
Additionally, since such an activation record could exceed 4K in size, R13
may not necessarily be used to access the contents of the record; other
registers may be used instead.
Finally, since R13 points to the /previous/ activation record, the currently
executing function will use a /different/ register to access it's own
dynamically-allocated storage.
[snip]
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------
wrote:
[snip]
Sorry, Jacob, but R13 is definitely *not* a hardware "stack pointer"
register.
The use of R13 in MVS (and it's follow-on operating systems) and VSE
(and /it's/ followns) is as a single pointer to a linked-list of
dynamically allocated memory blocks. There is no direct equivalent of a
PUSH or POP instruction that places data at a location pointed to by a
register /and/ increments (or decrements) the register atomically.
In fact, the use of R13 as a pointer to a save area (as this block is
called) is a /software convention/, and not dictated by hardware at all.
You can't say that R13 is a stack pointer in the hardware sense. The /best/
you can do is say that IBM mainframe pointers implement a fifo using a
linked-list of activation records, and the topmost activation record is
pointed to by R13 (and possibly other registers).
Additionally, since such an activation record could exceed 4K in size, R13
may not necessarily be used to access the contents of the record; other
registers may be used instead.
Finally, since R13 points to the /previous/ activation record, the currently
executing function will use a /different/ register to access it's own
dynamically-allocated storage.
[snip]
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------
K
Keith Thompson
jacob navia said:
Quite possibly. If you don't choose to identify who wrote the
quotation, we can't judge the writer's C expertise. I haven't been
able to find either your "BUNCH OF PEDANTS" article or the original
quotation in Google; I'd appreciation a more precise citation.
In any case, I agree with the quoted paragraph, assuming that by
"stack" the author meant some kind of LIFO data structure, not
necessarily a contiguous hardware stack.
Do you acknowledge that there is a difference between these two usages
of the word "stack"?
I've never programmed in C on an IBM mainframe. (I had some
peripheral exposure to them many years ago, but it didn't involve C.)
You claim that C implementations on IBM mainframes use a contiguous
hardware stack. People whose technical judgement I trust more than
I trust yours have said that they don't.
[...]
Facts are very important. It is a fact that such implementations
could exist.
It is a fact that the C standard does not mention a stack.
[...]
When did you decide that, and how does this discussion fit in with
that decision?
[...]
J
jacob navia
Lew Pitcher a écrit :
I said in this group in Sat, 15 Mar 2008 11:16:43 +0100
There is nothing more "big iron" that the IBM mainframes... at least
within my limited experience since I quit using that environment
in 1984.
The C compiler for the IBM mainframes is "C for VM/ESA", a C89
compiler.
We find in the users guide
http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/cbcvpg00/CCONTENTS
3.1.4.3 Accessing Automatic Memory
Use the EDCDSAD macro to access automatic memory. Automatic memory is
reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
The length of the allocated area is derived from the ulen and/or dlen
values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
reserves space for the *stack frame* needed for the C environment.
<end quote>
I repeat: "... the stack frame needed for the C environment".
The documentation goes on to specify that register 13 (R13) is used to
address this memory.
I said in this group in Sat, 15 Mar 2008 11:16:43 +0100
There is nothing more "big iron" that the IBM mainframes... at least
within my limited experience since I quit using that environment
in 1984.
The C compiler for the IBM mainframes is "C for VM/ESA", a C89
compiler.
We find in the users guide
http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/cbcvpg00/CCONTENTS
3.1.4.3 Accessing Automatic Memory
Use the EDCDSAD macro to access automatic memory. Automatic memory is
reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
The length of the allocated area is derived from the ulen and/or dlen
values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
reserves space for the *stack frame* needed for the C environment.
<end quote>
I repeat: "... the stack frame needed for the C environment".
The documentation goes on to specify that register 13 (R13) is used to
address this memory.
J
jacob navia
Keith Thompson a écrit :
"Portability of C Programs and the UNIX System"
S.C. Johnson and D.M. Ritchie
http://cm.bell-labs.com/cm/cs/who/dmr/portpap.html
OK?
Please Mr Thompson. Let's not start this all over again.
"Portability of C Programs and the UNIX System"
S.C. Johnson and D.M. Ritchie
http://cm.bell-labs.com/cm/cs/who/dmr/portpap.html
OK?
Please Mr Thompson. Let's not start this all over again.
L
Lew Pitcher
First off, let's take a look at the beginning of that section, shall we?
3.1.4 Using Standard Macros
To communicate properly, assembler routines must preserve the use of
certain registers and particular storage areas, in a fashion consistent
with code from the C compiler. C VM/ESA provides three macros for use
with assembler routines. These macros are in SCEEMAC MACLIB. The macros
are:
EDCPRLG
Generates the prolog for assembler code
EDCEPIL
Generates the epilog for assembler code
EDCDSAD
Accesses automatic memory
And we see that you aren't reading about how the C compiled code works, but
about how an Assembly language program must interface with a C program.
What you don't see in the description of the EDCDSAD macro is the magic
that the EDCPRLG macro performs to permit EDCPRLG to work.
Let's move on and follow some of the document that you quote, shall we?
Your quote indicates that the "automatic memory" thus accessed is reserved
either by the USRDSAL or DSALEN operands of the EDCPRLG macro. OK, so let's
look at section 3.1.4.1 Assembler Prolog, which discusses the EDCPRLG
macro. Here we find that...
USRDSAL=ulen
Is used only when automatic storage (in bytes) is needed. To address
this storage, see the EDCDSAD macro description. The ulen value is the
requested length of the user space in the Dynamic Storage Area (DSA).
Ohhhh.... looks like the USRDSAL that you refer to is a static-length block
of memory, allocated at function-entry time.
What about DSALEN, then?
DSALEN=dlen
Is the total requested length of the DSA. The default is 120. If fewer
than 120 bytes are requested, 120 bytes are allocated. If both dlen and
ulen are specified, then the greater of dlen or ulen+120 is allocated.
If DSALEN=NONE is specified, no code is generated for DSA storage
allocation, and R13 will still point to the caller's DSA. Therefore, you
should not use the EDCEPIL macro to terminate the assembler routine..
Instead, you have to restore the registers yourself from the current
DSA. To do this, you can use an assembler instruction such as
LM 14,12,12(13)
You should not use EDCDSAD to access automatic memory if you have
specified DSALEN=NONE, since DSECT is addressable using R13.
Hmmm... again, a fixed length block, this time not to exceed 120 bytes long.
Again, not a stack, but a fixed-length activation record.
Now, as for using R13, the documentation for EDCDSAD says
"The DSECT is addressable using Register 13, which is initialized by the
prolog code."
A DSECT is a description of a fixed-size, fixed-layout area of arbitrary
memory. Consider it the equivalent of a struct {}; as it simply names the
arrangement of data. Like a struct, a DSECT describes something of fixed
size and of fixed layout. It doesn't describe an array of things, but a
single collection of things.
The documentation says that R13 points to this DSECT. In C terms...
register struct EDCDSAD *R13;
No stack here. Simply a fixed layout activation record, pointed to by a
register pointer variable.
Now, as to IBM's reference to a "stack frame", I'm not going to try to
deduce why they phrased it that way. However, I can assure you that there
is *NO* machine stack. And certainly *NO* machine stack addressed by R13.
Indeed, R13 isn't really permitted to change (unlike a stack pointer), as
it *always* has to point at the beginning of the save-area.
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------