Statement on Schildt submitted to wikipedia today

[Mark L Pappin]

Walter Banks a écrit :

Does a C compiler run on that?

Not on it, but targetting it - several. I used to work on one of
them, but didn't push it here. (Hi again, DanH!)

See http://tiny.cc/mchipc

(redirects to
http://www.microchip.com/stellent/i...deId=1406&dDocName=en534868&page=wwwCompilers
for your convenience)

Walter's company does C compilers for PIC too, in case you hadn't
noticed. Of course, Walter doesn't push his compiler here either.

There are many processors out there but the discussion was about
C...


Sure, maybe that's why no C compiler for it exists?

http://bytecraft.com/It_s_here

Oh look - a counter example.

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?

http://freescale.com
seems to have bucketloads, including a 132-page Technical Data Sheet
for the first (group of) RS08 chip(s) I found drilling down through
their parametric search. Granted, it took me as much as 5 minutes to
get there, this being my first time looking at their web site and all,
but your "almost no docs" seems at odds with what looks like to me
"enough docs to write software and build hardware".

Where can I verify that the chip has no stack???

Jack Ganssle's article
http://embedded.com/columns/breakpoint/215801305
(referenced from Walter's blog) says

The RS08 has [...] an accumulator, PC, a shadow PC, and a two bit
condition code register. That's it.

Want a call stack? Well, you could implement one in software, much
as we did in the old 1802 days, but the RS08 is designed for
simple applications that don't do much calling.

However, my PDF viewer found 3 occurrences of the word "stack" in that
132-page TDS above, which suggests to me that there is in fact a
stack, somewhere - perhaps Walter can elaborate.

mlp

 

[Lew Pitcher]

Keith Thompson a écrit :

You missed the statement immediately before the statements you quoted:
"On the PDP-11/70 the calling sequence is relatively efficient (it costs
about 20 microseconds to call and return from a function) so it is clear
that a less efficient calling sequence will be quite expensive."

It appears that DMR was discussing a specific implementation on a machine
that provides a stack. He doesn't seem to be generalizing about /all/
implementations, or the language in general.

"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?

Oh, you mean

Portability of C Programs and the UNIX System*
* Originally published in The Bell System Technical Journal, Vol. 57, No.
6, Part 2, July-August 1978, pp 2021-2048. Copyright © 1978 American
Telephone and Telegraph Company.

Hmmmmm..... 1978? So, we're not talking ANSI/ISO C here, we're talking K&R C
on a DEC PDP 11/70.


--
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. ------

 

[Keith Thompson]

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.

You're assuming that the guide's use of the phrase "stack frame"
implies that it's allocated from a contiguous hardware stack.

The wording you quoted is consistent with the "stack frame" being
allocated by something similar to malloc(), so that successively
allocated stack frames are not necessarily contiguous or even in
any consistent order in memory. The stack frames are managed in a
last-in first-out manner (thus "stack"), but are not allocated from
a contiguous hardware stack. Which is how more than one person
here with direct experience on these systems has said it works.

And the real point here is (or should be) that *it doesn't matter*.
The assumption that C uses a hardware stack, aside from not being
universally true, is not particularly helpful in understanding the
language. I could write code for use on an IBM system without knowing
or caring how stack frames are allocated. All I need to know is that
a stack frame is allocated when a function is called and deallocated
when the function returns.

The C standard manages to define the entire language without using the
word "stack". The word doesn't appear in the index of either K&R2 or
H&S5; I don't know whether it's used anywhere in the text.

The C language does not depend, or even imply, on the existence of a
hardware stack.

 

[jacob navia]

Walter Banks a écrit :

A Freescale CISC processor 68RS08 (2006) does not have a stack.
Sure, maybe that's why no C compiler for it exists?

http://bytecraft.com/It_s_here

Oh look - a counter example.

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?

http://freescale.com
seems to have bucketloads, including a 132-page Technical Data Sheet
for the first (group of) RS08 chip(s) I found drilling down through
their parametric search. Granted, it took me as much as 5 minutes to
get there, this being my first time looking at their web site and all,
but your "almost no docs" seems at odds with what looks like to me
"enough docs to write software and build hardware".

Where can I verify that the chip has no stack???

Jack Ganssle's article
http://embedded.com/columns/breakpoint/215801305
(referenced from Walter's blog) says

The RS08 has [...] an accumulator, PC, a shadow PC, and a two bit
condition code register. That's it.

However, my PDF viewer found 3 occurrences of the word "stack" in that
132-page TDS above, which suggests to me that there is in fact a
stack, somewhere - perhaps Walter can elaborate

Mark,

The RS08 does not have any hardware supported subroutine or data
stacks.

Subroutine return addresses are stored in two register pair called the
shadow PC. For functions that have leaf functions the shadow PC
can be saved and restored. (keep the context guys there are no
hardware stacks)

It is used in a lot of small embedded applications. Like many small
embedded applications it was designed to do event driven processing.
Event implemented functions typically run to completion providing
an execution structure that is flat, memory efficient and cycle efficient.
The later allows the clock speed to be reduced in many applications
reducing power and emi.

Event functions are C functions dispatched with a small os..

The processor is small, very small and surprisingly efficient when
used with a good compiler. Typically within a few percent of code
size and execution speed of code running on the S08 processors
which have more complex instruction sets and stack frames
where needed.

Compilers accomplish the code efficiency on the RS08 through
application level optimization. Like most good embedded system
compilers recursion is aggressively handled in the data and control
flow analysis which essentially eliminates recursive functions. The
RS08 does not have interrupts but does have the ability to run in
multiprocessor environments and applications.


Regards,


Walter..
--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com
(e-mail address removed)

Mr Banks.

Dennis Ritchie said about the portability of C:
<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>

I do not want in any way to denigrate your work, or to say that your
compiler is not very good for that processor. But full C support
means that you should handle recursive functions.


You say:

> Like most good embedded system
> compilers recursion is aggressively handled in the data and control
> flow analysis which essentially eliminates recursive functions.

I agree that it is a good solution for machines that do not have a
stack. It is probably an EXCELLENT compiler.

But it is not the standard language.

Recursion is a fundamental characteristic of that language. You have
done probably a very good job implementing a subset of C but you
can't do what the hardware doesn't do.

That is all I wanted to say.

Yours sincerely

jacob

 

[jacob navia]

Keith Thompson a écrit :

You're assuming that the guide's use of the phrase "stack frame"
implies that it's allocated from a contiguous hardware stack.

The wording you quoted is consistent with the "stack frame" being
allocated by something similar to malloc(), so that successively
allocated stack frames are not necessarily contiguous or even in
any consistent order in memory. The stack frames are managed in a
last-in first-out manner (thus "stack"), but are not allocated from
a contiguous hardware stack. Which is how more than one person
here with direct experience on these systems has said it works.

And the real point here is (or should be) that *it doesn't matter*.
The assumption that C uses a hardware stack, aside from not being
universally true, is not particularly helpful in understanding the
language. I could write code for use on an IBM system without knowing
or caring how stack frames are allocated. All I need to know is that
a stack frame is allocated when a function is called and deallocated
when the function returns.

The C standard manages to define the entire language without using the
word "stack". The word doesn't appear in the index of either K&R2 or
H&S5; I don't know whether it's used anywhere in the text.

The C language does not depend, or even imply, on the existence of a
hardware stack.

There is a fundamental difference of attitude here.

You stay at concepts without any connection to how they are IMPLEMENTED.

To the contrary, for me IMPLEMENTATION allows me to better understand
and use a concept.

I think both viewpoints are valid, but there is no way that you can
abstract from what Dennis Ritchie said about the language: it needs
a hardware stack and if there isn't the implementation is quite
difficult. It could be that stack frames aren't contiguos as in
most processors, but within a stack frame you have the automatic storage
of course in a contiuguos chunk of memory.

Those frames are organized in a stack-like manner. That would (by the
way) explain why C came relatively late to those machines: the
difficulty of having to keep track of a software stack is large.

It would be surprising that programs do not allocate a big chunk of
memory at the start, then use it as a stack with just R13 pointing to it.

True, those chunks *could* be scattered all around, but in practice I
would very much doubt that that is the case.

 

[Dik T. Winter]

> Keith Thompson a écrit : ....
>
> I would like that you provide an example. I strongly believe that
> you have none, or some dead system decades ago.

The first one I did encounter was on an Alliant (yes, dead some time ago),
because of parallelism, that is, two routines could be active at the same
time, which means that the standard usage of a stack is not possible. They
called it a "cactus stack". When I implemented a threads library on a
Sun SPARC, I did approximately the same.

>
> I can say that in 30 years programming in C I never saw a machine
> without a hardware stack or a dedicated register for that purpose.

The CDC Cyber did not have a hardware stack, and also not a dedicated
register. Different programming languages that needed something
stacklike for that purpose used different registers to maintain a stack,
which made it difficult to link Algol 68 and Pascal routines.

The PC/RT did not use the stack either for the purpose of parameter
passing and whatever. The NS32K had a stack, but of only limited usage.

And if I remember well, the IBM S/360 and later did not have a proper
stack either (but that one I have barely programmed at such a low level).

And, all those machines I have used during the last 30 years.

 

[jacob navia]

Lew Pitcher a écrit :

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.

Of course. As ALL stack frames.

When a function prologue is entered in a function lcc-win generates

sub $128,%rsp

allocating space for the stack frame.

You say that there is a malloc procedure being called at each
procedure entry? With a corresponding free at the end?

Well, that is exacly how the stack frames are allocated, freed in
ANY processor. The only thing you insist is that those stack
frames could be non-contiguous.

It would be surprising though, that those inefficiencies would be
in a production C compiler from IBM... I mean what can be easier
than allocating a chunk of memory at program start and have a register
point to it?

I.e. a stack pointer,

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.

And why is not a stack? Because it is freed in a LIFO manner as all
stacks should be!!

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.

A collection of local variables of course!

That is what stack frames *ARE*

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.

Yes, it corresponds to the RBP register in the x86 architecture, that
is never permitted to change since it points to the base of the stack
frame (or "save area" as you call it)

Let's agree that those machines *could* have non-contiguous stack
frames. It would be highly surprising if the C implementation
didn't setup a memory area pointed by a single register that allows
to have contiguos memory stack instead of calling "malloc" at
each function entry and "free" at each function epilogue...

 

[jacob navia]

Lew Pitcher a écrit :

Oh, you mean

Portability of C Programs and the UNIX System*
* Originally published in The Bell System Technical Journal, Vol. 57, No.
6, Part 2, July-August 1978, pp 2021-2048. Copyright © 1978 American
Telephone and Telegraph Company.

Hmmmmm..... 1978? So, we're not talking ANSI/ISO C here, we're talking K&R C
on a DEC PDP 11/70.

He was speaking about the language he designed. Context is the
portability of the C language (as the basis of UNIX portability).

Yes, when Dennis Ritchie says something that regulars do not want to
hear then he is speaking in 1978 about the old PDP11.

Yeah, sure.

As if C99 would have said that recursion is obsolete...

 

[Dik T. Winter]

> It was plain to my by 1975 that programming without stacks was evil.

It was clear to me much later that programming parallel processes with only
a single stack is extremely difficult.

 

[jacob navia]

Richard Heathfield a écrit :

I have programmed in C on several IBM mainframes. And the most
important thing about all the mainframe implementations I used is
this: they were conforming C implementations, and therefore I didn't
(and don't) give two hoots whether they had a stack or not. One
simply does not need to know, when writing portable C. I suppose I
could have written code that made assumptions about the stack (e.g.
the initialisation foolishness one hopes only to see in FAQs), but I
didn't. Had I been foolish enough to have done so, I might have
discovered that one or more of those implementations did, or did not,
use a stack.

One of the many little beauties of C is that you can explain how it
works in purely abstract terms - you don't need to assume a stack.

Yes, the more abstract the better. The less we speak about reality and
the more about abstract and confusing concepts without any concrete
examples the better.

In principle, both viewpoints are valid. In practice, C is very much
related to the machine and I find this tendence to ignore the basics
of how a mahine actually WORKS a plague of today's programmers.

They know C# and maybe they have a dim idea of how it works,
but below the abstract machine Microsoft gives them they have
no clue.

A pity.

 

[Dik T. Winter]

>
> Nor have I, but my experience is not universal. Well, actually I
> probably have seen such machines, but I've never interacted with them
> closely enough for the issue to come up.

If I remember right, you have had access to a Cray-1 or similar. That was
a machine that did not have a hardware stack, nor a dedicated register for
that purpose. And, yes, C was implemented on it.

 

[jacob navia]

P.S.

Mr Banks, the clock of your machine is in the future by about 20-30
minutes.

 

[Keith Thompson]

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?

Ok. That was written in 1978, and the passage you quoted referred
specifically to implementing C *on the PDP-11/70*. It does not
support your claims.

The PDP-11/70 has a hardware stack. It would have been foolish to
implement C on that system without using it.

Please Mr Thompson. Let's not start this all over again.

Feel free to stop any time. You continue making false claims in the
face of evidence that you're wrong. Don't expect me to ignore that.

 

[Bart]

Those frames are organized in a stack-like manner. That would (by the
way) explain why C came relatively late to those machines: the
difficulty of having to keep track of a software stack is large.

Not large. Instead of Push R0 you'd have to do Add R13,4: Mov [R13],R0
or some such thing, maybe even a single instruction, assuming a linear
upwardly growing stack.

For Call you'd need to first push the label address following the next
Call/Jump unstruction.

The stack frame: well you don't even need to use the return address
stack. But if you did, again just a few simple instructions: designate
a frame pointer, push it, copy stack pointer into the frame pointer,
step the stack pointer by the amount of local data.

It really doesn't sound a big deal to me, to implement a stack-based
language on a machine without hardware stack instructions. Unless
there're some pecularities of IBM architecture that would make this
difficult. A small processor of course may just not have the
resources.

It would be surprising that programs do not allocate a big chunk of
memory at the start, then use it as a stack with just R13 pointing to it.

Perhaps IBM weren't capable of doing anything simple.

 

[Dik T. Winter]

> You are wrong for the same reason IBM messed up the 1620 in Dijkstra's
> paper at http://www.cs.utexas.edu/~EWD/transcriptions/EWD00xx/EWD37.html.
> Subroutine call and return CANNOT be implemented without a stack where
> a stack is a set (bounded or not, hopefully the latter) because
> subroutine call and return IS a lifo process all the way down to the
> bare metal.

You are wrong or deliberately lying. Dijkstra does not advocate the stack
there (although he knew about it because some of the early machines at the
MC did have a stack). What he writes there is that the error is that
somewhere data is written which can not be retrieved without a special
instruction (i.e. the return address without the instruction to jump back).
I know of quite a few computers that did write the return address in code
memory before starting a routine, like the CDC Cyber that on a RJ (Return
Jump, i.e. call routine) wrote an unconditional jump back at the first
address of the routine called and entered the routine on the next address.
This worked very well (and would have had the approval of Dijkstra). And
indeed it worked without failure for Fortran programs. Where is the stack
in that case? And indeed it would work with all languages without recursion.
But languages of Algol pedigree required recursion, so a software stack had
to be implemented.

 

[Dik T. Winter]

> 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.

Given the state of Fortran at that time, you needed only one word per
subroutine to maintain everything you need every allowed depth of
subroutines. How one word per subroutine allocated at the start of the
subroutine can be considered a stack escapes me.

On the other hand, doing a threads library in C/C++ with only a single stack
is impossible.

 

[Keith Thompson]

Lew Pitcher a écrit :

He was speaking about the language he designed. Context is the
portability of the C language (as the basis of UNIX portability).

Yes, when Dennis Ritchie says something that regulars do not want to
hear then he is speaking in 1978 about the old PDP11.

Yeah, sure.

No, when he says he's speaking about the PDP-11/70, he's speaking
about the PDP-11/70. Read the entire paragraph, not just the snippet
you posted. (And the article was written by Johnson and Ritchie, not
just Ritchie).

As if C99 would have said that recursion is obsolete...

What?

 

[Keith Thompson]

If I remember right, you have had access to a Cray-1 or similar. That was
a machine that did not have a hardware stack, nor a dedicated register for
that purpose. And, yes, C was implemented on it.

No, I never had access to a Cray-1. I did use a Cray T90 for a while;
I never looked into how it implemented function calls.

 

[Keith Thompson]

Keith Thompson a écrit :

There is a fundamental difference of attitude here.

You stay at concepts without any connection to how they are IMPLEMENTED.

To the contrary, for me IMPLEMENTATION allows me to better understand
and use a concept.

Then you should pay attention to how the IMPLEMENTATION of C on IBM
mainframes actually works, as described by people who have actually
used it.

I think both viewpoints are valid, but there is no way that you can
abstract from what Dennis Ritchie said about the language: it needs
a hardware stack and if there isn't the implementation is quite
difficult. It could be that stack frames aren't contiguos as in
most processors, but within a stack frame you have the automatic storage
of course in a contiuguos chunk of memory.

Sure, I'd expect each stack frame to be contiguous, but the frame
itself is not stack-like; it's just a random-access chunk of memory.

Those frames are organized in a stack-like manner. That would (by the
way) explain why C came relatively late to those machines: the
difficulty of having to keep track of a software stack is large.

Why would it be paricularly difficult? The compiler generates
appropriate system calls to allocate and deallocate stack frames,
and each frame contains a pointer to its parent. It looks fairly
straightforward to me, only slightly more complex than a hardware
stack implementation. Even the compiler itself doesn't need to
know or care whether successive stack frames are contiguous.

Note that the generated code never needs to access any stack frame
other than the current one. So why does it matter how they're
allocated? (A hardware stack might be more efficient, but presumably
there are reasons why it's not practical on certain systems.)

It would be surprising that programs do not allocate a big chunk of
memory at the start, then use it as a stack with just R13 pointing to it.

I don't believe that's how it works, and frankly I can't think of any
good reason why it should be.

True, those chunks *could* be scattered all around, but in practice I
would very much doubt that that is the case.

If you allocate a large contiguous chunk of memory at program startup,
that means you have to know or estimate the program's stack size in
advance, with a very real risk of either running out or allocating too
much. If you allocate stack frames from the OS as they're needed,
each program uses only as much stack space as it actually needs, and
the system has better control over programs that use too much.

What advantage do contiguous stack frames give you? And what
conceptual advantage does the assumption of a contiguous stack really
give you in understanding C programming? I'm sure it matters a
great deal if you're implementing a compiler, but the vast majority
of us aren't doing that.

 

[Dik T. Winter]

> spinoza1111 wrote: .... ....
> 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/.

The compiler I have studied best in this regard was the Fortran compiler
for the CDC Cyber series. For all expressions in a particular subprogram
it counted the number of memory places needed to evaluate an expression
when the number of registers was insufficient. It reserved places for
this after the local variables (that followed the code of the subprogram)
and did use them just as temporary variables. I still fail to see how that
qualifies as a stack.