subroutine stack and C machine model

[spinoza1111]

In

spinoza1111wrote:



This is comp.lang.c, where the Standard (warts and all) is topical.


On the contrary, knowing it is essential if you're going to make
meaningful statements about it. The degree to which one's statements
about a subject can be taken seriously by experts in the field
depends greatly on the amount of knowledge one has about that
subject.


Well, "admit" is the wrong word, "failed" is questionable, and "it" is
ambiguous, but "you" seems unexceptionable enough.

Since I wasn't on the Committee that developed C99, it is hardly my
place to "admit" either its success or its failure. I can make claims
about it if I choose, but admission isn't my problem, one way or the
other.

The C90 Standard was a huge success. The C99 Standard, 10 years on,
has yet to be widely implemented. Because of this, I will not use
C99-specific constructs in my own code when that code is required to
be portable. I have, however, modified my coding style so that it
conforms to C99 (i.e. I have eschewed C90-only constructs).





No, I say it because it's true.



In fact, he gives plenty of evidence. Perhaps you need to learn to
read.


Rubbish. There /are/ things that cannot be known or predicted. For
example, given this program:

#include <stdio.h>

int main(void)
{
  printf("hello\n") + printf("world\n");
  return 0;

}

and no other information, it cannot be known or predicted whether the
program will print

hello
world

or

world
hello

What /can/ be predicted is that one or other of those two
possibilities is very likely to be the output. (Not *certain*, of
course, because printf can fail - for example, output might be
redirected to a read-only file.)

Saying so is hardly a reason for censure.


He does know that. And C does allow one to sensibly predict what code
will do, *provided* one observes good practice - which perhaps goes a
long way towards explaining your attitude.

"Good practice" means abandoning K & R's clear implication that work
could be done in expressions, the subexpressions of which have side
effects, allowing hand optimization in assembler language style. It
means doing something that modern compilers can and should do, which
is to avoid "code motion" when the syntax of a construction shows that
it is unknown whether an expression has a side effect.

In a(b,c) where b is a constant or even a term (for example an int) it
makes sense in certain environments to "evaluate" b after a or even in
parallel. However, the natural expectation of most programmers with
computer science training and experience in other languages is left to
right evaluation and this expectation, not vendor profits, should have
been honored in the C99 standard, by reassuring, not vendor
stockholders, but programmers that their instincts would be honored.

This is because educated people, for better or worse, read left to
right in the modern world even when their original language is right
to left because of the dominance of English...especially in scientific
and technical communication.

But this would have resulted in a demand from the standards committee
to vendors that they change their compilers, and the standards
committee was in the vendor's pocket.

Not if you have your eyes shut, no.


In my experience of your Usenet articles, your experience of computer
science has taught you little, if anything, about programming.

I don't know what you mean by "programming" other than applied
computer science but post Northern Rock and the Panic of 2008 I have
my suspicions. I think it may be organized fraud.

 

[Dik T. Winter]

....
> It is true that "optimizing compilers" can reorder operands. It is
> true that parallelism can further shuffle operands and do two
> calculations simultaneously. But these code transformations have to be
> intuitionistically justified.

But Phil's remark was *not* about reordering operands, it was about the
evaluation of the operands. When 'inner2' is evaluated before 'inner1'
this does *not* mean that the result is calculated as
'result_of_inner2' + 'result_of_inner1'
as you seem to assume.

 

[Dik T. Winter]

> > int fa(int a);
> > int fb(int a, int b); /* not shown, but recurses back to fa() or fb() */
> >
> > int fa(int a)
> > {
> > int r;
> > r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;
> > return r;
> > }
> >
> > **/

....
> How is it possible that the "two function calls" "could" be executed
> in parallel? C99 standard 6.5.17: "The left operand of a comma
> operator is evaluated as a void expression: there is a sequence point
> after its evaluation. THEN [emphasis mine] the right operand is
> evaluated...".

Where in the above fragment is a comma operator used?

 

[spinoza1111]

...
 > > int fa(int a);
 > > int fb(int a, int b); /* not shown, but recurses back to fa() or fb() */
 > >
 > > int fa(int a)
 > > {
 > > int r;
 > > r = (some condition ? fb( fa(a+1), fa(a-1) ) : a;
 > > return r;
 > > }
 > >
 > > **/
...
 > How is it possible that the "two function calls" "could" be executed
 > in parallel? C99 standard 6.5.17: "The left operand of a comma
 > operator is evaluated as a void expression: there is a sequence point
 > after its evaluation. THEN [emphasis mine] the right operand is
 > evaluated...".

Where in the above fragment is a comma operator used?

It's not. I made an error.

 

[spinoza1111]

Please don't conflate "Not having taken classes" with
"Not understanding the theory".

Well, if you don't "take classes" in the university environment, and
you work in some nasty little business office, could you ever be sure
you understand the theory? I have learned alot about C from bantering
with you faggots precisely because this isn't the business world.
Whereas in the corporate world, the need for teamwork means that most
discussion is Leninist: it has to stop to get a job done.

Herb learned lessons primarily from the Microsoft world. You learned
them in a world where Microsoft is a dirty word. In both cases, there
was no free discussion of things common to both, such as stacks and
twos complement.

Absent a university education, you get environments that are in
reality *madrassahs* advancing a particular set of approaches for
personal gain, in which *taliban* learn that there are "bad books",
and their *imams* issue *fatwas*.

Nobody really understands anything in the human sense which is able to
factor out inessentials, and the result is a wild lack of perspective.
Just as the fundamentalist Islamist worries more about his wife's
dress than being compassionate or merciful, Peter Seebach tasks
Schildt for returning the wrong thing in main, implies that stacks and
twos complement are unimportant, and triumphantly presents free(NULL)
as an excuse not for balancing free() and malloc().

If a person, today, takes a job as a programmer with a music or math
degree, he will, as Seebach has, have no environment independent way
of telling the forest for the trees. He will have no exposure to the
fact that Polish notation, which produced the stack, was the first
proof that the infix notation of the Principia Mathematica could be
parsed by a machine. If he codes C on the job for an embedded system
with no stack, he won't understand the stack at all.

He will have no sense of "lexically ordering" software
responsibilities. He won't see that correctness is more important than
"speed" and he won't see that "speed" is a metaphor which easily
obscures "wrong answers arrived at quickly".

He will believe on the one hand that using toilet language is
intelligent. On the other hand, he will fail to understand vehemence
in defense of reputation independent of a crummy little job.

He won't be in Kipling's sense a "man".

 

[Dik T. Winter]

> But what the lads are saying is that the C99 standard makes "standard"
> code, with your side effects, that ran fine on old-fashioned compilers
> that evaluated left to right. If you move the code from a nonstandard
> legacy compiler to a standard compiler it breaks.

I do not really remember, but I think the old VAX Unix C compiler could
evaluate either way, depending on level of optiisation.

 

[Tim Streater]

In
<86ca92d9-8821-417f-b7fe-2b68ec749...@i12g2000prg.googlegroups.com>,

[snips]

He does know that. And C does allow one to sensibly predict what code
will do, *provided* one observes good practice - which perhaps goes a
long way towards explaining your attitude.

"Good practice" means abandoning K & R's clear implication that work
could be done in expressions, the subexpressions of which have side
effects, allowing hand optimization in assembler language style. It
means doing something that modern compilers can and should do, which
is to avoid "code motion" when the syntax of a construction shows that
it is unknown whether an expression has a side effect.

In a(b,c) where b is a constant or even a term (for example an int) it
makes sense in certain environments to "evaluate" b after a or even in
parallel. However, the natural expectation of most programmers with
computer science training and experience in other languages is left to
right evaluation and this expectation, not vendor profits, should have
been honored in the C99 standard, by reassuring, not vendor
stockholders, but programmers that their instincts would be honored.

This is because educated people, for better or worse, read left to
right in the modern world even when their original language is right
to left because of the dominance of English...especially in scientific
and technical communication.

The instinct of any competent programmer is going to be to read the
documentation and find out what it says about evaluation order. And then
tailor their code to follow the rules. Software is not mathematics, as
should be clear from the fact that I can write, e.g., x = x + 1; and
neither is it natural language.

Any programmer who thinks otherwise is clearly somewhat naive.
Personally I don't write code that relies on evaluation order.

 

[Dik T. Winter]

> For example,
> Peter Seebach hasn't taken any computer science classes whatsoever yet
> has tried to destroy the reputation of someone who has.

I have taken none either, for the simple reason that when I was at university,
computer science was not yet taught as a subject (this was from 1962-1969,
computer science was introduced around 1975). Stronger, the university were
I was had did only own computers for administrative purposes, for everything
else they used the computer of the institute where I started working in 1969,
and where I am still working.

FYI: Edsger Dijkstra didn't take any computer science class either.

 

[Dik T. Winter]

> Seebach needs to do the same thing, because
> without CS training he has no standing.

So now you appear to think that Edsger Dijkstra has no standing. Thank you
for clarifying that.

 

[Dik T. Winter]

>
> No, it would have involved just visiting a Web site to confirm the
> existence of the book. This is actionable, boyo. You are knowingly and
> maliciously spreading a rumor, that I did not write the book, when you
> can verify that I have.

Again misreading. Is English so difficult that you are not able to correctly
read it? Richard did not deny the existence of the book. What he wrote is
that he did not know whether the book was about compilation or not. How
can visiting a website clarify that?

 

[Seebs]

And your appraisal of the quality of the reviewers of your own book is
of course completely unbiased, right?

Hah.

That said, the one three-star review I got (I've only gotten 4 reviews
on my book) was totally a fair cop. I was dinged for the clash between
the book I actually wrote and the use of the word "beginning" in the
title.

-s

 

[Seebs]

(2) Implying that lack of theory is a virtue is being a stupid. Theory
is essential in programming any reasonable large system. Yes, you
don't need any if you program hello world style programs but for
more serious undertakings theory is a must.

Absolutely it is.

There is an "underground current" in this group against anything that
smells as abstraction or higher level thinking.

Not that I've noticed.

Hint: My dislike of the "container class" thing is not because I don't like
abstractions or higher-level thinking. It's because I'd rather pick
abstractions with some awareness of the specific circumstance in which I'm
using them, and because I don't think "container" is a useful abstraction
in a language without something comparable to inheritance or interfaces.

-s

 

[Seebs]

Please don't conflate "Not having taken classes" with
"Not understanding the theory".

Yes. The reason I never got back to taking CS classes is that there's no
point in trying to work through a CS program once you're a reasonably
experienced programmer -- is it really a good use of time to attend hundreds
of hours of lectures when the average lecture will contain two or three
things that are new to you? If I want to learn more about programming,
I read books, or talk to people who know different things than I do, and I
learn just fine. (It helps that I was raised by mathematicians, because
the language used for discussions of algorithmic complexity is obvious to
me. My dad was one of the math profs who started the CS program at the
college he taught at, and he used to review CS books. I may have picked up
a few bits and pieces...)

-s

 

[Seebs]

In

int x = foo();

According to you, it is possible to determine whether the above
expression has side effects. I disagree. Please present evidence to
support your assertion.

I think he may be right, at least on this specific example. You will
note that he does not refer to an expression which *does* have side
effects, only one which *may* have side effects. I'd say the above is
in the latter category, as it contains a function call, and function
calls *may* have side effects.

Examples:

int x = 3 + 4; /* known not to have side effects */
int z = x++; /* may have side effects */

Note that we are not distinguishing between "may have side effects" and
"necessarily has side effects". We can't, because function calls are
ambiguous in that regard. But if an expression has no function calls in it,
you can tell whether or not it has side effects in most cases. You can
always tell whether it may, except that in some cases the probability is zero:

int a = (x <= z) ? (++x) : (0);

I would say that strictly speaking, we know that this expression does not
have side effects, because (assuming no intervening code), we know that x is
8 and z is 7, so we necessarily don't evaluate the ++x. However, I think
this analysis proves his point incorrect. You can correctly determine that
this expression CANNOT have a side effect, but you can't do it by looking
only at the syntax.

On the other hand, it may be that for his purposes, this counts as "may have
side effects", even though the probability of the side effect occurring is
zero. You can certainly identify a category of expressions that absolutely
do not have side effects, by syntax alone -- there are some expressions where
analyzing the syntax of the expression proves that there can never be side
effects. (Actually, I'm not sure of this, either. Does access to a volatile
count as a "side effect"? If so, I don't think that counts as a syntactic
feature anymore. Syntactically, volatile's just a qualifier, it doesn't
have any unique syntactic role...)

-s

 

[Keith Thompson]

In
<c82773ab-a2b3-42c1-9aa7-d75afed73ff3@m33g2000pri.googlegroups.com>,
spinoza1111 wrote: [...]

It happens to
be possible to tell the difference between "an expression known not
to have side effects" and "an expression which may have side
effects" from syntax alone even in C,

int x = foo();

According to you, it is possible to determine whether the above
expression has side effects. I disagree. Please present evidence to
support your assertion.

[...]

Richard, it appears that one of us has misinterpreted what spinoza1111
wrote.

foo() is not "an expression known not to have side effects". It is
"an expression which may have side effects". It is possible to tell
the difference.

Any C expression is in one of three sets:
1. Expressions known not to have side effects;
2. Expressions which may or may not have side effects;
3. Expressions known to have side effects.

where the word "known" refers to what's known by a particular
compiler with a particular set of options. For a sufficiently lazy
compiler, the first and third sets could be empty, though at least
all constant expressions should be in the first set.

spinoza1111 does not appear to have claimed that it's always possible
to determine whether a given expression has side effects or not
(though he may well have done so in material which you didn't quote).

 

[jacob navia]

Seebs a écrit :

Absolutely it is.


Not that I've noticed.

Hint: My dislike of the "container class" thing is not because I don't like
abstractions or higher-level thinking. It's because I'd rather pick
abstractions with some awareness of the specific circumstance in which I'm
using them, and because I don't think "container" is a useful abstraction
in a language without something comparable to inheritance or interfaces.

-s

Maybe you should study C better. Interface is a common concept in C (as it
is in all programming languages). I presented an interface proposal
for several containers here and its implementation in C. You have the
right (of course) to disagree with that interface proposal, you can tell
me it is wrong because many reasons, but you can't deny the fact that
it is an interface!

Some examples:

Microsoft uses the interface concept in the C implementation protocol
of its COM package.

Dave Hanson, one of the authors of lcc, published a book with the title:
"C Interfaces and Implementations" that discusses several interfaces for C
programs.

The known "API" acronym, stands for Application Programmer INTERFACE"!

And I could go on enumerating examples but let's stop there.

Denying the fact that C has (as all programming languages) the
interface concept shows that you either did not give much thought
to what you were writing, or that you fail completely to grasp concepts
that go beyond churning some code!

You say that you would "rather pick abstractions with some awareness
of the specific circumstance in which I'm using them" without noticing
that precisely abstractions should be mostly independent of the exact
place where they are used, and that is why they are useful ABSTRACTIONS!

Yes, there is no inheritance in C, but you do not need any inheritance
to describe an interface to an abstract container. I fail to see
any hierarchy in those containers, at most a grouping that can be useful
and an INTERFACE that allows for maximum flexibility.

I hope I misunderstood you, and that you can clarify your position.

jacob

 

[Seebs]

Maybe you should study C better. Interface is a common concept in C (as it
is in all programming languages). I presented an interface proposal
for several containers here and its implementation in C. You have the
right (of course) to disagree with that interface proposal, you can tell
me it is wrong because many reasons, but you can't deny the fact that
it is an interface!

I used the term to refer to the common feature in OO languages of allowing
a single interface specification to be used by multiple different objects,
giving them compatibility despite having different types. This allows,
for instance, both list objects and array objects to implement the shared
interface "container", and be used interchangeably by code which relies on
the "container" interface.

This is not something that C really supports. Without the ability for objects
providing substantially different APIs to share a common subset, a "container"
is not very useful; you may want an array, and you may want a list, but if
you want one you probably don't need the other. It's only in languages that
let you express to the compiler/interpreter that there's a shared interface
that it's useful. IMHO.

Denying the fact that C has (as all programming languages) the
interface concept shows that you either did not give much thought
to what you were writing, or that you fail completely to grasp concepts
that go beyond churning some code!

That's entirely possible.

However. It seems to me that there are two likely possibilities:
1. Someone who's been using C for something over twenty years, and uses
both "API" and "ABI" correctly and in context, and is a fluent speaker of
English, does not realize that the ability to describe the set of calls
available in a given context could be called an "interface".
2. The term "interface" has another, more-specific meaning, to which that
person was referring.

Do you have a guess as to which one of these is more likely?

You say that you would "rather pick abstractions with some awareness
of the specific circumstance in which I'm using them" without noticing
that precisely abstractions should be mostly independent of the exact
place where they are used, and that is why they are useful ABSTRACTIONS!

I do actually know about this. The thing is, there is such a thing as "too
abstract to serve my purposes". Certainly, I can implement just about
any data storage with the interface:

int add_to_object(void *object, void *data, void *key);
void *retrieve_from_object(void *object, void *key);

And then I just have to do:

int sum = 0;
for (int i = 0; i < 10; ++i) {
int *p;
p = retrieve_from_object(my_array, &i);
if (p) {
sum += *p;
}
}

.... but this might actually suit my needs less well than a more specific
implementation, shocking though it may seem!

Yes, there is no inheritance in C, but you do not need any inheritance
to describe an interface to an abstract container. I fail to see
any hierarchy in those containers, at most a grouping that can be useful
and an INTERFACE that allows for maximum flexibility.

The normal way this would be done would be to have a generic "container"
interface, then more-specific "array" and "list" interfaces, which are
indicated in some way to be supersets of container, such that code which
works on "containers" can work on both arrays and lists. C really can't
express this well, and without it, "container" is a pretty poor choice
for abstraction, while "array" and "list" are very good choices for
abstractions.

I hope I misunderstood you, and that you can clarify your position.

I don't know about the clarification. I have had issues trying to communicate
with you in the past; for instance, when I pointed out that there was no
obvious reason to imagine a performance penalty for indirect calls, you
pointed at research on the performance penalty for virtual functions in C++,
which is a VERY different application than mere "calls through function
pointers".

-s

 

[jacob navia]

Seebs a écrit :

The normal way this would be done would be to have a generic "container"
interface, then more-specific "array" and "list" interfaces, which are
indicated in some way to be supersets of container, such that code which
works on "containers" can work on both arrays and lists.

That is exactly what my interface proposes. Some opeartions like
"Add" for adding an element, or "GetElement" for retrieving
contents, and some others are common to all containers I propose.

> C really can't
express this well,

????

I presented code here that implements that. C *can* express that without any
problems.

and without it, "container" is a pretty poor choice
for abstraction, while "array" and "list" are very good choices for
abstractions.

The code I presented shows that it is perfectly possible for a pure
C interface to be generic. I showed that if the binary interface
is maintained you do not even need to recompile your code...

I don't know about the clarification. I have had issues trying to communicate
with you in the past;

Sure, and that is all my fault.

for instance, when I pointed out that there was no
obvious reason to imagine a performance penalty for indirect calls, you
pointed at research on the performance penalty for virtual functions in C++,
which is a VERY different application than mere "calls through function
pointers".

Well it is different, there was a misunderstanding. And so what? What has that to do
with what we are discussing now?

 

[Phil Carmody]

This is an extra-ordinary statement. Richard Heathfield "admtted that
the standard failed"? Do you have a cite? I'd have described that C
standard as being most extra-ordinarily success story over decades of
heavy use. C runs on an astounding variety of platforms. C is the
backend to a vast array of our modern world. And the Standard has a
large part to play in this. What on earth would you characterise as
*sucessful*?!

Oh, yes I know C99 didn't catch on as well as it might. But this just
reflects, again, what a fantastic job the ANSI C89 did.

One other thing which I think demonstrates its success is the
huge period of time between all major revisions. Some languages
which were first penned after C99 are on their 5th version
already, with almost no compatability between then and now.
The intersection of C89 and C99 is so large that it's possible
to restrict yourself to that subset, and almost certainly remain
conforming with the next version of the standard when it finally
arrives. That means some actively developed and used code has 3
decades of use in it, if that isn't a success, nothing is.

Phil

 

[Phil Carmody]

In

spinoza1111 wrote: [...]
It happens to
be possible to tell the difference between "an expression known
not to have side effects" and "an expression which may have side
effects" from syntax alone even in C,

int x = foo();

According to you, it is possible to determine whether the above
expression has side effects. I disagree. Please present evidence to
support your assertion.

[...]

Richard, it appears that one of us has misinterpreted what
spinoza1111 wrote.

And it appears that it's me. Mea culpa, at least on the basis of the
quoted text. (I'm not about to go digging for this one.)

I think the fact that it was presented as a dichotomy, invites
such misinterpretation. The reality is of course not a dichotomy.
(Keith's may-be-3-may-be-1 explication in PP demonstrating this
perfectly.)

Phil