Statement on Schildt submitted to wikipedia today

[Dik T. Winter]

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

You mistype "recursive" and "non-recursive". Being "re-entrant" has nothing
at all to do with a stack. A function is not "re-entrant" if it uses, for
example, a global variable, because two parallel invocations can give
different results from when the invocations are serial.

 

[Bart]

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


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.

Surely with virtual memory you can have a stack area that will detect
when it overflows and can grow automatically. You just have to the
keep the virtual stack address distant from the rest of the program.

What advantage do contiguous stack frames give you?  And what

Allocation speed, bearing in mind stack frames can be different sizes
and you don't want to waste time messing about with malloc and free.

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.

(One of my early language efforts actually had the statements stack
and unstack:

int a,b;
double x;

stack a,b;
unstack x; /* or unstack b,a */

which did exactly what you might expect. It was quite handy too,
although I've grown out of that now. So some of us were thinking
'stack')

 

[spinoza1111]

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

That point was well made by speakers at ASPLOS 1987 which was overrun
by RISC kiddies. Wirth was there and seemed to be depressed.

It is true that a single stack is a bottleneck, but this doesn't
disprove its centrality. You just need more stacks.

 

[spinoza1111]

 >spinoza1111wrote:

...
 > >                                                     Something that
 > > works like a stack is needed to evaluate expressions and to manage
 > > subroutine call and return.
...
 > 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.

That sounds broken. How did it handle a simple recursive factorial
program? I understand that it was impossible, for early Fortran
compilers, to execute recursive code. But this means that your
counterexample does not show what you intend it to show. Yup, gotta
have stacks.

 

[spinoza1111]

Richard Heathfield a écrit :








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.

With all due respect for you and your work, if you knew senior
Microsoft developers, you would discover that this is not the case. I
agree that there's a corporate drive at Microsoft to create ignorant
programmers, dependent on "rational" software development
environments, the seat cost being in the thousands of dollars: I
discovered in China that software development firms can't use Visual
Studio Enterprise because it's too expensive.

But this is not a Microsoft dynamic, Jacob. It is a capitalist
dynamic. Within the non-Microsoft world I discover the same
"capillary" (as in Foucault) implementation of social structures,
because outside of Microsoft there's the same rage to develop "tools"
that deskill others. Moreover, the politics appear the same, as in the
case of C standardization aimed at deskilling C programmers,
accompanied by campaigns of personality destruction.

I stopped programming in assembler in 1978 and returned to it only at
Princeton to modify old assembler programs. Now, this makes my "low
level code" skills rusty, but it's not ethical to deliberately use a
low level language to solve a real problem for real money.

In object-oriented languages like C Sharp and Visual Basic, if you
want to learn about basic low-level structures, the best way is to
develop visual software simulators for the low level stuff as I did
for my book.

 

[Nick Keighley]

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,

no it isn't. It's an abstract definition that does not rely on OO
features.
The C++ standard library implements it without using OO features (ie.
inheritance) it uses only C++'s generic feature (templates). It could
equally
be implemented in another language that had decent generic features
but
no OO (eg. original Ada). In a language like C generics could be
imitated
with fancy macro magic or code generate it. Really the only thing that
needs
to vary is the type of Item.

and it is useful. However, most real
implementations allow stack dumps,

the C++ standard library isn't real?

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.

hello?


<snip>

 

[Nick Keighley]

ie. not a stack in the sense of contiguous memory

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

but only to the CAE. The CAE in turn has a way of finding the previous
CAE
like a pointer (or something fancier in the case of languages that
don't have
C's simple LIFO usage pattern).

It makes it harder, Reading Rainbow.

You use the term a lot. If you want me to understand how I've been
insulted
you'll have to explain this (Americanism?).

So why'd you mention threading then? It adds nothing to your sentence,
apart from bulk. Maybe that was the intent.

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

putting it in a register makes it a global. C has quite a few globals
like
stdin. Most programs, even good ones, have a few globals.

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.

quite

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.

no, don't give them incorrect mental models.

It's just bad practise to index past one variable in an activation
record and expect to see the "next" parameter.

trust me, clc does get questions like that

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,
ok

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.

I was told it was a stack of plates with spring under it so the stack
rose slightly (popped up) as the top plate was removed. Such things
do
exist in some cafeteria. Probably banned now 'cos the bottom plate
only
gets washed once a year.

But it was realized soon enough that
implementing a stack as a contiguous vector was not necessary.



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

the technology then goes into todays fly-by-wire civilian aircraft.

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

the VAX went on chip long ago. I've got orders of magnitude more
memory in my phone that the original VAX had.

<snip>

 

[Nick Keighley]

P.S.

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

I thought you were telling him his chip was in the future.
I thought you were complementing him on the chip's design!

 

[Dik T. Winter]

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

The T90 falls in the catagory "or similar".

 

[Dik T. Winter]

>
> That sounds broken. How did it handle a simple recursive factorial
> program? I understand that it was impossible, for early Fortran
> compilers, to execute recursive code.

It was not so much impossible as well as disallowed according to the Fortran
standard upto at least Fortran 77. And indeed, on that system recursion was
impossible, it catered only for standard conforming programs.

> Yup, gotta
> have stacks.

Not for expressions (as you asserted), but only for recursion.

 

[Lew Pitcher]

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.

But, that screws up R13, which /always/ must point at the start of the
SAVEAREA (i.e. the "stack frame").

[snip]

Perhaps IBM weren't capable of doing anything simple.

No. IBM had to fit the requirements of the C language into an
already-established operational environment, on a CPU architecture
that /did not/ include a dedicated stack-pointer register. So, they chose
to expand the already-existing linked-list of SAVEAREAs to include a
scratchpad area for automatic variables.

Recursion is handled by chaining saveareas together, with each instance
having it's own savearea. The total size of a single instance's automatic
variable allocation is known (excluding VLAs, which can be handled
differently) at compile-time, and thus the size of each scratchpad area
within the chained SAVEAREAs is known.

The CPU /does not/ have a dedicated stack pointer.

The OS environment /already/ requires R13 to point at the equivalent of an
activation record.

It takes little effort on the part of the language implementors to expand
that activation record to include the "automatic" variables allocated to
one instance of the function, and to use the existing mechanism of linking
and unlinking these activation records to facilitate recursion.

FWIW, the first 72 octets (18 "fullwords") of the SAVEAREA are reserved for
storage of general registers and other linkage information.
SAVEAREA+4 holds the previous contents of of the previous caller's R13
SAVEAREA+12 holds the previous contents of R14
SAVEAREA+16 holds the previous contents of R15
SAVEAREA+20 holds the previous contents of R0, etc
It is the responsibility of the called function to save the caller's
registers and state, and then point R13 to the empty savearea that any
called functions will save the current function's state in. Thus, you see
at the beginning of an Assembly program
STM 14,12,12(13) SAVE CALLERS REGISTERS IN HIS SAVEAREA
ST 13,MYSAVEAREA+4 SAVE CALLERS SAVEAREA POINTER IN MY SAVEAREA
LA 13,MYSAVEAREA SET MY SAVEAREA POINTER TO POINT TO MY SAVEAREA

and at the end

L 13,MYSAVEAREA+4 RESTORE CALLERS SAVEAREA POINTER
LM 14,12,12(13) RESTORE CALLERS OTHER REGISTERS
BR 14 RETURN TO CALLER

I was employed to write programs in IBM Assembler for about 30 years. This
comes naturally to me. As does refuting Jacob's dilettante assertions about
IBM's operating environment.

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

 

[Nick Keighley]

As near as I can make out, it's a USA TV series designed to encourage
young children to read. Perhaps the closest equivalent current during
your own childhood would be "Peter and Jane" (a series of about three
dozen books, published from 1964 onwards, so obviously it depends on
how old you are). Perhaps "Janet and John" may be more familiar to
you (used in the UK in the 1950s and 1960s);

I'm a Janet and John person.

"look Janet there is the ball"

it appeared to be designed to actively discourage children from
reading.

it is referenced in "Yes
Minister" (or possibly "Yes Prime Minister") to describe a report's
one-paragraph executive summary for Cabinet ministers - "the Janet
and John bit".

What it has to do with C, however, is beyond me.

presumably he thinks that if I can't understand what he meant
then I have a reading problem.

 

[Kenny McCormack]

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

Feel free to stop any time. You continue making claims with which I
disagree, in the face of evidence that you're wrong. Don't expect me
to ignore that.[/QUOTE]

Truer words were never spoken...

(Because, you see, I have no life outside of this newsgroup)

 

[Willem]

Richard Heathfield wrote:
) Nick Keighley wrote:
)> presumably he thinks that if I can't understand what he meant
)> then I have a reading problem.
)
) Whereas, if /he/ can't understand what /you/ meant, clearly you have a
) writing problem.

Of course not. Anything anybody does that he even slightly disagrees
with is intentional, malicious, and destructive behaviour.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Phil Carmody]

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.


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.

Clamping this on tangentially rather than directly in response to
your post, but something just struck me:

What about C interpreters. They are as much C as compilers. Do they
bother to create a linear stack upon which to put variables etc. ?
To be honest, if I were to implement a C interpreter, I'd not waste
time with a stack, I'd just use something more like activation
records?

Phil

 

[Keith Thompson]

Clamping this on tangentially rather than directly in response to
your post, but something just struck me:

What about C interpreters. They are as much C as compilers. Do they
bother to create a linear stack upon which to put variables etc. ?
To be honest, if I were to implement a C interpreter, I'd not waste
time with a stack, I'd just use something more like activation
records?

First, what exactly do you mean by "C interpreters"? It would be
possible, I suppose, to interpret C source code directly, but it's
more likely that C would be translated (compiled?) to some
intermediate form that would then be interpreted.

And what exactly do you mean by "activation records"? Presumably an
activation record contains all the information associated with a given
function call (parameters, local variables, return address, etc.), but
that doesn't answer the question of how they're allocated.

For an interpreter, I suppose managing activation records via
something like malloc/free would make more sense than it would for a
compiler; malloc and free impose more overhead than tweaking the stack
pointer, but the overhead is less significant in an interpreter.

But fundamentally, I can't think of any reason why an interpreter
should necessarily use a different mechanism than a compiler for the
same target -- unless the interpreted code runs on some particular
virtual machine that provides some convenient mechanism.

It's up to the implementer of the interpreter, just as it's up to the
implementer of a compiler. Any method that meets the requirements of
the language should be acceptable.

 

[Richard Tobin]

To be honest, if I were to implement a C interpreter, I'd not waste
time with a stack, I'd just use something more like activation
records?

I think "activation records" as normally used is not contrasted with a
stack (or stack frames). Stack frames are a kind of activation record.
A typical C implementation pushes an activation record onto the stack
when it calls a procedure, and pops it off when it returns.

-- Richard

 

[Phil Carmody]

First, what exactly do you mean by "C interpreters"? It would be
possible, I suppose, to interpret C source code directly, but it's
more likely that C would be translated (compiled?) to some
intermediate form that would then be interpreted.

Erm, something like 'tcc'? The computer that had it on blew up a
few months ago, and I've not resuscitated it yet. I would also
presume it does some translation into intermediate form.

And what exactly do you mean by "activation records"? Presumably an
activation record contains all the information associated with a given
function call (parameters, local variables, return address, etc.), but
that doesn't answer the question of how they're allocated.

I meant just the local variables. I don't see any reason to even keep
a return address in the same region as local variables, they are
unrelated to each other. (Which is why several of the architectures
mentioned do that in hardware.)

For an interpreter, I suppose managing activation records via
something like malloc/free would make more sense than it would for a
compiler; malloc and free impose more overhead than tweaking the stack
pointer, but the overhead is less significant in an interpreter.

But fundamentally, I can't think of any reason why an interpreter
should necessarily use a different mechanism than a compiler for the
same target -- unless the interpreted code runs on some particular
virtual machine that provides some convenient mechanism.

It doesn't _necessarily_ do anything a particular way. However,
there's no need for it to map its behaviour onto the underlying
instruction set, which is what C compilers have been focussed on.

It's up to the implementer of the interpreter, just as it's up to the
implementer of a compiler. Any method that meets the requirements of
the language should be acceptable.

Yeah, which was why I was asking for input from people who had
insight into the implementation of interpreters.

Phil

 

[Nick Keighley]

What about C interpreters. They are as much C as compilers. Do they
bother to create a linear stack upon which to put variables etc. ?
To be honest, if I were to implement a C interpreter, I'd not waste
time with a stack, I'd just use something more like activation
records?

but your "allocation records" need to allocated and freed in a LIFO
manner so a contiguous stack is a pretty compelling data structure.
On the other hand if you make everything heap based (malloc/free)
then you only have to deal with one "memory arena".

 

[Dik T. Winter]

> but your "allocation records" need to allocated and freed in a LIFO
> manner so a contiguous stack is a pretty compelling data structure.
> On the other hand if you make everything heap based (malloc/free)
> then you only have to deal with one "memory arena".

The CDC Algol 68 compiler did put every local variable on the heap.
The stack was only used for return addresses of functions and to
reserve space for expression evaluation.