Is C99 the final C?

D

Dan Pop

In said:
the preliminary drafts, or have sprung for the $18. If you are
claiming to be a professional C programmer that can't afford $18,
you're lying to yourself.

Why should a professional C programmer care about C99 *before* it becomes
the de facto industry standard? The adoption of C99 as an ISO standard
4 years ago had next to zilch impact on the computing industry until now.

One of the most important implementation vendors, Microsoft, has publicly
anounced its lack of interest in this standard. And the GNU C people
apparently decided to continue to do the things their way, in the cases
where their way was at odds with C99 (it was a MAJOR blunder to put
GNU C features into C99, but with slightly different semantics).

Dan
 
J

Johan Aurer

The standard does not tell me how to do the job of coding. Although
it may cause the occasional portability problem, having the raw source
of the C library is surprisingly more useful. For example, please
locate for me where in the standard it says that fgets() ignores '\0'
that are consumed -- then locate where in the standard it says its the
only string function which does this.

I'm not sure what you mean when you say "fgets() ignores '\0' that are
consumed." Can you elaborate on this, please?
 
A

Alan Balmer

Paul said:
Sidney said:
What is your excuse for not having the standard? A free draft
(N869) is also available.

The standard does not tell me how to do the job of coding.
Although it may cause the occasional portability problem, having
the raw source of the C library is surprisingly more useful.

And dangerous. Programs should not depend on a knowledge of the
standard library's implementation.
Dunno what that means.
-- then locate where in
Then tell me where in the standard it says that strtok is

Implicit in the description.
 
D

Dan Pop

In said:
I'm not sure what you mean when you say "fgets() ignores '\0' that are
consumed." Can you elaborate on this, please?

Most likely, that if the input stream contains null characters, fgets
consumes them but doesn't include them in the output string.

This is a known problem with all the standard library functions that
convert stream input to strings. In principle, text streams should not
contain null characters, but if they accidentally do, their effect on
the output of [f]gets() and [f]scanf() is (or may be) disruptive.

Many terminals can generate null characters and the user may do it
inadvertently.

Dan
 
R

Randy Howard

Why should a professional C programmer care about C99 *before* it becomes
the de facto industry standard?

Forward thinking and planning? Don't do something that will conflict
with it should it ever become predominant, for example. Also, the
prior ANSI documentation shares quite a bit in common with it, if you
have both great, if you're only going to buy one version, I still
think it's the way to go. It's not going to become the industry
standard as long as the majority do not even know of its existence.
Perhaps if ISO had made it freely available (I know, shudder), it
wouldn't be so obscure today. As an alternative, but at a higher
price than the softcopy it might be as useful or more so to carry
around a copy of Harbison & Steele's "C A Reference Manual, 5th
Edition", which has a good breakdown of the various features, and
clearly identifies where C99 differs from previous versions,
including library functions.

In short, have at least some way to know what the rules are apart
from your compiler documentation. The more, the better.

I personally don't use the constructs that are "new" with C99 much, but
I do want to know what they are as well as how they might or might not
conflict with internally developed code. I can always refer back to
older docs as well if there is a conflict. Having the PDF file on my
portable external hard drive makes it very handy to always have it
around as well, although I would prefer plain text.
The adoption of C99 as an ISO standard 4 years ago had next to zilch
impact on the computing industry until now.

+/- a few percentage points, yes. :)
One of the most important implementation vendors, Microsoft, has publicly
anounced its lack of interest in this standard.

Despite having used Microsoft compilers since the dark ages, I can say
I honestly don't care anymore. I understand where they are, and they
couldn't care less about straight C code anymore, and are trying to
drag people off of C++ as fast as they can to so-called "managed code".
If they win that fight, none of the C standards will matter in their
developer community.
And the GNU C people apparently decided to continue to do the things
their way in the cases where their way was at odds with C99

Well, it's open source, I suppose if anyone was desperate enough for it
to support everything completely, it could be done, with a lot of kicking
and screaming over "gcc, the language" being jacked with. Apparently
not having 100% conformance isn't chapping anyone's posterior enough to
make it happen. gcc is available almost everywhere, and having -ansi
-pedantic is enough to write portable code today. There are some features
in C99 that are interesting, and some that I downright despise. I can't
think of a language that doesn't having anything disagreeable in it, or
I'd probably be using it now instead of C.
(it was a MAJOR blunder to put GNU C features into C99, but with
slightly different semantics).

Agreed. "Not invented Here" disease has probably cost the computer
industry more than any other single social issue. I've worked on
standards before, and the politics is usually far more of an issue
to most members than any technical product delivered. A good friend
from IBM used to say "you must leave your corporate badge at the door"
when coming to meetings. Unfortunately, most did not even begin to
do that. I wouldn't be the least bit surprised to find out that MS
deliberately jacked with the C99 efforts to
a) make life difficult for other vendors
b) add obscure items to marginalize it indirectly
c) make it easier for them to claim conformance without doing anything
if they ever decided to do so.

I've seen them do all of the above on other standards. Probably
everyone reading this can think of some on their own.
 
S

Sidney Cadot

Well the few people in here who have the standard have chimed in. Now
how do you supposed we convince everyone else in the group to chime
about the fact that they don't have it? (Look up the term "push poll"
if you don't understand what I mean.)

Now you're just being silly. Please feel free to start a top-level
thread about who has access to the standard, and who doesn't.
The standard does not tell me how to do the job of coding.

That is a strange excuse. The C standard is not supposed to do that,
that's what tutorials/books on different levels are for. The standard
addresses the features you can (and cannot) rely on to work on a
compiler that adheres to the standard.
Although it may cause the occasional portability problem, having the raw source
of the C library is surprisingly more useful.

"The" C library?
For example, please
locate for me where in the standard it says that fgets() ignores '\0'
that are consumed -- then locate where in the standard it says its the
only string function which does this. Then tell me where in the
standard it says that strtok is not re-enterable.

As for the re-entrancy, that's covered. As for the fgets(), please
provide a code snippet and some behavior you didn't expect, then we can
look why it doesn't work as you expect. It will surely be covered.
Excuse me?!?! *C99* is not portable.

Well, that's true, given a practical definition of "portable".

Would gcc be portable enough (according to this practical definition)
for you? Or would we have to define portable in a way that includes the
Microsoft compiler, or do you draw the line at C89?
Typed it into google and felt lucky. Its the first hit. Notice
language like "Process i", and statements like for (j=0; j < n; j++),
where each j indexes a process id, and n is the number of processes.
I tried to think up a way of implementing that algorithm without
specifically requiring an enumeration of processes, but it seems that
that is central to the way the algorithm works. Which is only *one*
of the reasons why that algorithm is worthless.

Typed -what- into google? Is it so hard to provide a link?

I'm not doing this to piss you off... Like with many important
algorithms, there are different formulations of the bakery algorithm
floating around. I'll look up the original Lamport papers later on, and
see if the process-id thing is truly essential.
It *is* a big deal. Mutexes, and other similar multithreading objects
are not expressible is a portable way in language like C or C++.

I already established that if you cannot portably get mutexes in C, I
will concede. This very specific point of contention is *not* decided \0
yet, in this discussion.
[...] All hinges now on whether the Lamport algorithm needs process
id's. Fortunately, there's no subjective element in that, we should
be able to sort that out.
What I don't understand is how is it that *YOU* brought up the
algorithm, and yet you are unaware of its fundamental functionality.

Hells bells, I used it 5 years ago. What I remember is that it can be
used to provide mutexes without hardware support like atomic
read/update/write cycles. At this point, I'm not sure if the process id
stuff is essential. I'll look into it.
It only took me only 30 seconds to understand it.

Well, that would surely make you quite brilliant. Took me a couple of
hours, the first time I read it, to get my head around it, and to see
that it is correct.
Well, but that's not my contention, and I would appreciate that you not put
words in my mouth, or follow the discussion (whichever one is causing
you do write things like this) --

What's the problem?
my contention is that Lamport's
Bakery algorithm is not portable (I mean relative to C, which doesn't
expose and multithreading functionality, even if implementations do.)

Yes, and for now, I contend otherwise, ...
Then again, once you open it up to non-portable code, of course,
nobody will touch Lamport's Bakery algorithm with a 10 ft pole -- its
worthless when you have far superior mechanisms for creating Mutexes
at your disposal.

Sure. Read a few posts back, I already said that it would be an
interesting idea to put your stuff in the standard library for
performance reasons. I was quite ready to leave it at that, but you
*INSISTED* that it is completely impossible to do, portably. That's the
one and only thing we're discussing now.

At this point, I'm not sure whether it can be done but my hunch is that
it is possible, based on something like the Bakery algorithm. If you
think this question is too academic, I'd be happy /not/ to spend the
effort to get to the bottom of this. Then again, in this case, the onus
would be on me to give at least an outline of how it could be done.
[...] I feel rather silly getting dragged in this line of
discussion (multithreading has little to do with the C execution
model) but we'll see where this leads us.
Then let me review the facts for you. Multithreading is inextricably
intertwined with the implementation of malloc. Thus if a compiler
vendor wants to provide a multithreading extension to C (which they
pretty much all do) discussions of implementation of malloc, or
malloc-like functions have to at least acknowledge this as a
consideration. There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place. The inevitable conclusion is that
its impossible to make a portable library for extending the heap
functions that are multithreading safe.

Ok, except that "There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place" is not a fact. That's what we're
arguing about, now.
Well, if you are sensitive about being admonished in public, then can
I ask that you have a little bit of intellectual honesty? I am trying
to put forward hard core analytical ideas, and I have made efforts to
distill your own proposals is a very serious way. The response is not
supposed to be "oh but you can't prove its impossible to implement".
This is like Ari Fleischer telling the anti-war sympathizers that its
up to them to prove that there are no WMDs in Iraq. If you have a
problem with what I am saying why can't you limit it to an analytical
response?

I acknowledge that with the portable mutex stuff, the burden of proof
rests with me. However, you did't seem to think this was the case with
your "operator introduction" parser, expecting to get away with the
premise that it could surely be solved (which is not at all obvious).
Why the double standard?
See the problem with your suggestion of using the Lamport's bakery
algorithm, is not just that it obviously doesn't satisfy the
conditions of the original problem (portably extending malloc/etc),

It's not obvious. Perhaps you're right, perhaps I'm right. We'll get to
that.
but that the next thing you are going to do is throw some other
algorithm at it that also won't work in some vain attempt to throw me
off yet again. You did it full well expecting that I wouldn't chase
it down and find the flaw.

That's quite a strange accusation, given that we didn't establish yet
that the bakery algorithm or something similar can't provide mutexes,
using portable C.
Are you going to do it again, or are you
going at least take my arguments more seriously?

I don't do cheap rhetorical tricks, and I will take seriously-looking
arguments serious.
You see its not *UP* to me to analyze bogus algorithms to prove that
you can't implement a mutex portably. That's retarded -- even if I do,
its not actual proof of anything. If you have a serious contention
against my very technical claim, then don't you think that its at
least somewhat incumbant upon your to wade through the details
yourself?

Will do. Will you do the same with the operator-introduction parser
problems? Like provide a semantics that you can show not to lead to
parsing ambiguities? Quid pro quo.
[...] that does this will be out of luck. Not because the proposal
wouldn't work, mind you, but because the ULMU is a very loose bound.
But hey, it beats having no bound whatsoever.

No it doesn't. Dealing with the stack is an area that clearly
should be platform specific. For example, it could be that an
embedded system has fast and slow ram. Certain data types might
be best suited to being mapped into fast RAM, whether they are
local or not, but you might have a lot more slow RAM, so you'd put
all the rest of the stuff in there.

To what does "no it doesn't" refer?
The last statement "... it beats having no bound ..."

Well, in that case: "oh yes it does!" :)
Look, if you have two stacks, then the right way to bound it is to
have two bounds.

That's a better way, that (unfortunately) seems to be rather hard to
formalize. I am proposing to forego the difficulties be defining (for
these rare cases) a very loose upper bound.
If one of your stacks has very limited amount of
memory (fast RAM is likely to be more expensive) then in order to
properly implement a single bound (you proposal) you need to assume
the worst case and say that you only have as much stack space of the
smaller stack (otherwise it wouldn't be a correct bound.)
Yes.

This is completely worthless to systems that want to expose really really deep
call stacks but fairly shallow floating point stacks, for example

For such architectures it would be difficult to write code that honours
the upper bound metric. I don't think that's a problem; rather the
opposite. It would force programmers to consider the issue.
(look up the Ackerman function again, and try to imagine attempts at
mathematical simplifications, to be able to output at least *some* of
the reasonable computable values in reasonable time.)

I don't understand this, why would you have to do this?
I can see once again I'll be trying to prove that the are no WMDs in
Iraq ...

I agree that this would have to be fixed. I don't see an easy way,
except perhaps:
[...] For one thing, your proposal to make macro's available outside
the function scope that give the fnctions stack usage upper bound
may come in handy.
See how that worked out? You had a proposal, I found something wrong
with it, so I offered something *CONSTRUCTIVE* to try to save it,
rather than pretending it would fail because of an issue that I can
work around even if you might have missed it. Its called intellectual
honesty.

Why thank you. I think I dislike the proposition that I would not do the
same thing, though.
Perhaps you do not know the true nature of the halting problem. You
can't know if a piece of code ends, which is equivalent to knowing if
it takes one branch or another, or how many times it executes a given
code fragment. There's no shortage of open mathematical problems for
which the output of a given function is just completely unboundable,
calculatable, or estimatable (the famous "+3 on odd, /2 if even"
problem which I can't recall the details of comes to mind) with any
current knowledge.

It's called the Collatz problem, which asks if this list ends at 1 for
all n. As I said, "most of the time" you can still give an upper bound,
which is fine the vast majority of practical recursive functions. For
example, in the count_nodes() example, you could establish that it would
be guaranteed to work if the tree were not to exceed a certain depth (as
expressed in a number of macro's that are available at runtime). I think
it would be like this for 99% of practical recursive problems.
[...] In cases where you can't (few and far inbetween) you don't
have the guarantee, which is a pity; the code can no longer be
written in a way that's fully portable. It would still be much
better than what happens now (standard-compliant programs
segfaulting without so much as a hint in the standard).
It means you are expecting compilers to come as close to solving the
halting problem as they can.

No. I don't expect the compiler to do anything with this information.
It's there for the programmer to use, for checks at runtime (e.g. at the
start of main() in heavy recursive programs). It can't be done at
compile time since, in general, you don't know the stack size at that point.
And you think variable length operators based on a grammar is an
> impossible, intractible problem in practice?!?!

I think it's very difficult, and it may be even impossible, yes. But
surely, you're going to demonstrate that I am wrong? :)
The implementation may exit or take any other defined action which halts
the execution on any function call. But it may not create undefined
behaviour from the action of performing the call itself alone.

Ok, that would be an alternative way of preventing the UB. I'd much
prefer it to the current situation, and when I think of it, it's
probably better than my proposal which has a lot of practical problems.
The 'stack exception' could also occur on alloca().
There's a proposal that's compatible with many implementations today
(if we presume that turning stack checking *off* would be an
extension, and that leaving it on is the default conforming behavior)
and should be easy to understand and implement.

I agree. How's that for intellectual honesty.
[...]
My opionion is determined largely by the psychological objections (to
which you don't subscribe.)
Says who? You see, unlike some people, by idea isn't driven by an
opinion. Its driven by a consideration for design. Since you *CAN'T*
add just any old operator to satisfy everyone, then how do you satisfy
the demand for more operators? Some variation on redefinable
operators or operator overloading is the logical conclusion -- just
fix its problems (since type-index functions don't really exist in C,
so you just add in a bunch of them so that you don't lose any of the
ones you have). For all I know, I might not ever use such a feature,
even if it *WERE* to be endorsed by the standard.

I fail to see the point you want to make here.
Just that I am trying analyze problems, and you are just spouting
opinion.

My point is that symbols have an order of magnitude less menmonic value
than symbols. Well yes, you can call that an 'opinion', but it's also a
testable hypothesis (and it has probably been tested in research). Don't
have a reference, though. Can we just leave it at that?
Well I don't know what to make of this -- you can't see a race
condition when its staring you in the face, and you can't imagine
problems with knowing the size of a function's stack usage.
Be careful not to presume things that are not there. [...]
Yeah, thanks for the warning. I'll be sure to purchase some duct tape
to deal with my neighbors who might be terrorists too.

You don't know me, I don't know you. Probably if we met in person we
could get along just fine, given the fact that we seem to share some
interests.... Why is it silly to ask that you don't pass judgement from
5000 miles away on someone whom you don't know?
The race is there. I reduced it to the standard notions that you are
supposed to learn about in an OS class. I've explained everything you
need to know to understand its there. Any research you do into the
subject will confirm what I'm saying. But I'm supposed to worry that
I might be wrong based on your flimsy non-arguments.

We'll see. Have some patience... :)
An opinion you will back up how ... ?

I won't back it up. It's an opinion that could easily be turned into
fact, though. Here's an experiment for you:

count_nodes counts the nodes in the tree
@* do a matrix multiply
insert_element insert element in the list
?> take the maximum
is_prime determine if number is prime
=%= see if two numbers are in the same residue class
log take the natural logarithm
<#> count the elements in the list
event_handler_poll poll the event handler
<^ left-associative power
mutexP take the mutex
%# calculate a percentage

....Now turn away from the screen, and have somebody read the
_descriptions_. Reproduce the function name / operator symbol from
memory. How many operators did you get? How many symbols? Let's have a
bit of this intellectual honesty! :)
Yeah, well believing that there are parsable grammars doesn't take very much
"abstract thinking", there millions of examples.

Sure, but the question is if the operator introduction feature that you
loosely proposed will be guaranteed to yield an unambiguous parser, when
you make the rules for operator intruduction more concrete.
[snipped the smartcard stuff]
CPU companies have laid out the decent semantics. I and others have
written bignum routines -- the carry flag is where its at as far as
this is concerned.

That's fine. Now here's a big idea: hardware design and general-purpose
language design are two different things.
And so which category do you think "bignum libraries" falls into?

Neither, but if you put a gun to my head I'd say the former.
I mean given that every platform supports it, and that in fact an
implementation (the GMP) purports to be a software library with a
portable interface up to software, supporting just about every popular
desktop/server/workstation platform under the sun.

Hmmmm. Still neither, I'm afraid.
No, we all understand what produces an OF,
I mean, name an actual agorithm that uses it, that can't extract the
> semantics from one of <,>,<=,>=.

What is that supposed to prove? The same is true for your carry:

/* adding with carry, presuming 2-complement repr. */

unsigned a, b, result;
int carry;

result = a+b;
carry = a>(UINT_MAX-b);

/******/

Here's an algorithm that uses overflow:

int add_signed(int a, int b, int *overflow);

{
int a,b,r,ov;

get_ab(&a, &b);
r = add_signed(a, b, &ov);
if (ov)
printf("sorry, can't add those.\n");
else
printf("result = %d\n", r);
}
Well that's right -- *bignums* don't rhyme well with C. *STRINGS*
don't rhyme well with C. *BITS* don't rhyme well with C. That
doesn't mean its not worth having them.

But the point is: C doesn't have (real) strings. C doesn't provide
bignums. It provides rather mundane support for bit-twiddling, but only
on a per-byte-or-more basis. That's the essence of my "rhyme" claim:
things that collide with the core language shouldn't be forced in there,
just out of convenience for some specific application.
[...] There are many subtle issues with
signed/unsigned representation and operations, and the standard is
careful to find a compromise; not assuming too much on the
architecture side, while at the same time maintaining a sound
semantics for both signed and unsigned operations. Your semantics
just doesn't fit in.
There's your deep analysis again "... just doesn't fit in ...". I
just can't argue with that. Wow, I guess I am just wrong.

Perhaps you should download the standard and read it (especially the
naughty parts on signed and unsigned integers), to see what I mean.
Yes, but the semantics of what a carry is, is not crucially tied to
this. Even if you use ones complement, or something else, you can
still *compute* the carry, even if you don't automatically have it from
the built-in representation.

Hold on a minute... Where's your famed "intellectual honesty" now? You
made a claim that I disproved, and now you're just moving along as if it
didn't happen? At least an acknowledgement would be nice.

To address your point though.

I'm really interested to see how you would write a big number multiply
that doesn't presuppose 2-complement, but works in 1-complement as well.
For the sake of argument, feel free to introduce a wide-mul operation
(but let's have a semantics for it... The x86 MUL obviously won't do).
But I didn't precisely say that. In fact losing the (un)signedness
semantics is really something you need for the carry flag idea. The
"almost like widening multiplies", that exist in C retain the sign as
you would expect, and obviously you probably wouldn't want to change
that in an extension to C.

Ok.

Best regards,

Sidney
 
D

Dave Thompson

Sidney Cadot <sidney@jigsaw.nl> wrote:
[...] You mentioned that actual languages exist
that do this sort of thing; are they also compiled languages like C, or
are they interpreted languages of the functional variety?

No, actually I am unaware of any language that has infinite operators.
Someone mentioned mathematica, but I am unaware of its language
semantics. I mentioned ML as the inspiration of quaternary operators,
but that's about it.

LISP and FORTH blur the boundary because they allow most or all
special/punctuation characters in identifiers; to them + is simply the
name of a function that happens to be builtin and do addition. ++ or
+: could be a user-defined operation which does the same thing or
something completely different.

Fortran has (long? always?) had some language-defined operators using
the syntax .blah. (e.g. .EQ. .AND.) as well as those using special
characters like +, and as of F90 allows nonconflicting user-defined
operators in this syntax, with fixed lowest precedence if binary.
(Also overloading builtin operators for user-defined types.)

(Neither of these is actually infinite because there is still some
limit on the length of identifiers, but the number of distinct
identifiers of even modest length is practically enormous. And even
the number of comprehensible identifiers is much more than enough.)

- David.Thompson1 at worldnet.att.net
 
A

Arthur J. O'Dwyer

Paul Hsieh wrote:
[Sidney Cadot wrote:]
Typed it into google and felt lucky. Its the first hit. Notice
language like "Process i", and statements like for (j=0; j < n; j++),
where each j indexes a process id, and n is the number of processes.
I tried to think up a way of implementing that algorithm without
specifically requiring an enumeration of processes, but it seems that
that is central to the way the algorithm works. Which is only *one*
of the reasons why that algorithm is worthless.

Typed -what- into google? Is it so hard to provide a link?

Typed "Lamport bakery algorithm," naturally, and then clicked the
button labeled "I'm Feeling Lucky." It takes you right to
http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Bakery.html
I'm not doing this to piss you off... Like with many important
algorithms, there are different formulations of the bakery algorithm
floating around. I'll look up the original Lamport papers later on, and
see if the process-id thing is truly essential.

Well, you obviously don't need access to UNIX "pids" to do the
algorithm, but you *do* need a reliable source of unique integer
identifiers for each thread. And that's something that standard
C simply cannot give you without specific language support.

I already established that if you cannot portably get mutexes in C, I
will concede. This very specific point of contention is *not* decided
yet, in this discussion.

I agree with Paul that this is a very basic and very obvious fact
that shouldn't be too hard to grasp. If you've done any thread-based
programming (nothing complicated, just anything that requires a
shared resource), you've noticed that every time two threads want
access to the same bit of memory at the same time, you need some
kind of mutex to block out one of the threads while the other one
does its thing, and then block out the other one while the first one
does *its* thing.
Mutexes cannot be expressed in standard C, because standard C has
no way of specifying "this block of data behaves like a mutex." I'm
sorry if that sounds circular, but it's hard for me to describe the
effect of a mutex except by jargon. Suffice it to say that you can
feel free to post snippets illustrating anything you think qualifies
as a mutex algorithm written in standard C, and I will be only too
glad to poke holes in it.

It only took me only 30 seconds to understand [the bakery
algorithm].

Well, that would surely make you quite brilliant. Took me a couple of
hours, the first time I read it, to get my head around it, and to see
that it is correct.

Maybe it's the changing times. Or maybe it's the way that web
page explains it -- it's intuitively obvious to me from their
description that if Thread A has a lower number than Thread B, then
Thread A naturally goes first. It just makes sense.

[...] I feel rather silly getting dragged in this line of
discussion (multithreading has little to do with the C execution
model) but we'll see where this leads us.
Then let me review the facts for you. Multithreading is inextricably
intertwined with the implementation of malloc. Thus if a compiler
vendor wants to provide a multithreading extension to C (which they
pretty much all do) discussions of implementation of malloc, or
malloc-like functions have to at least acknowledge this as a
consideration. There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place. The inevitable conclusion is that
its impossible to make a portable library for extending the heap
functions that are multithreading safe.

Ok, except that "There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place" is not a fact. That's what we're
arguing about, now.

Well, Paul's right and you're wrong. That's all.


[re: the rest of the miscellaneous arguments in this subthread]

[re stack bounds checking]
No. I don't expect the compiler to do anything with this information.
It's there for the programmer to use, for checks at runtime (e.g. at the
start of main() in heavy recursive programs). It can't be done at
compile time since, in general, you don't know the stack size at that point.

This proposal sounds both reasonable and possible to me. I do
agree that it requires a *lot* more thought, though; and you'll see
if you search Google Groups that this topic has been discussed both
here and in comp.programming (IIRC) quite a lot before.

I think it's very difficult, and it may be even impossible, yes. But
surely, you're going to demonstrate that I am wrong? :)

Of course it's *possible* to create an arbitrary-operator-parsing
grammar! But it would require work, and it's not going to make it
into C, so IMHO that discussion should move to comp.programming or
comp.lang.misc, where someone will no doubt be glad to demonstrate
how their magic compiler compiler will handle arbitrary operator
syntaxes with ease.


I'm really interested to see how you would write a big number multiply
that doesn't presuppose 2-complement, but works in 1-complement as well.
For the sake of argument, feel free to introduce a wide-mul operation
(but let's have a semantics for it... The x86 MUL obviously won't do).

Why do you say that? It's not dishonest to use the well-thought-out
and publicly-reviewed specification of an x86 operation in this
context. I myself am not familiar enough with the MUL opcodes anymore
to give a nice description, so here's my proposal, without any x86
jargon, which I think *would* rhyme fairly well with C. It's a
library function.

#include <math.h>

unsigned long lmulu(unsigned long p, unsigned long q,
unsigned long *hi, unsigned long *lo);

The 'lmulu' function accepts arguments 'p' and 'q', multiplies
them using normal integer arithmetic, and stores the high-order
bytes of the result in '*hi' and the low-order bytes in '*lo'.
Specifically, if ULONG_MAX = 2**N - 1, then mathematically
(*hi << N) + *lo == (p * q); but note that this expression
invokes undefined behavior as a C expression.
'lmulu' may be implemented as a macro.
'lmulu' returns the value stored in '*hi'.


signed long lmuls(signed long p, signed long q,
signed long *hi, signed long *lo);

The 'lmuls' function accepts arguments 'p' and 'q', multiplies
them using normal integer arithmetic, and stores the high-order
bytes of the result in '*hi' and the low-order bytes in '*lo'.
[Needs someone more familiar with bitwise representations, and
more awake, to define exact semantics in mathematical terms.]
'lmuls' may be implemented as a macro.
'lmuls' returns the value stored in '*hi'.


It would have been nice to add defined behavior for when 'hi' or
'lo' were NULL, but that would have killed the whole point of
making the function in the first place -- the ability to optimize
away a lot of code on many popular systems.
[And before Paul contradicts that last sentence, I re-iterate: This
is *not* about adding functionality to C; it's about giving the compiler
better optimization hints. The ability to do wide multiplies already
exists in C; language support for them will only make them faster.]

That said, I think this thread needs to start splitting up. :)

-Arthur
 
P

Paul Hsieh

As for the re-entrancy, that's covered. As for the fgets(), please
provide a code snippet and some behavior you didn't expect, then we can
look why it doesn't work as you expect. It will surely be covered.



Well, that's true, given a practical definition of "portable".

Given any definition of portable. There are no C99 compilers, compliant or
otherwise.
Would gcc be portable enough (according to this practical definition)
for you?
No.

[...] Or would we have to define portable in a way that includes the
Microsoft compiler, or do you draw the line at C89?

Portable in C means C89 minus the incompatibilities with C++. I mean portable
in the same sense that the implementors of the Lua language considered C to be
portable, but not to the degree that the JPEG people considered C to be
portable (they wrote code that works on K&R C as well as ANSI C -- but K&R is
something we need to leave behind.) And of course not what the GMP or Python
people consider portable (i.e., "we ported it".)

And of course you have to pay deference to the C++ people because there is
scarcely a C compiler in existence today that isn't also a C++ compiler, and
users of that language will not understand your pedantry when explaining that
"my code is portable, its just that your compiler is not".
Typed -what- into google? Is it so hard to provide a link?

Are there any braincells operating in your head? I typed "Lamport's Bakery
Algorithm" into google. What do you possibly imagine I could have considered
typing in other than that?
I'm not doing this to piss you off...

Then you are just braindead? There's no lee way here. There's no other
possible thing that I could possibly type into google to help me look this up.
What were you expecting me to type in? "Worthless non-solutions to critical
section?" "The idiots guide to multitasking incorrectly?" "Race conditions
are us?" "Good looking algorithms laced with (not-so-well) hidden weaknesses?"
[...] Like with many important algorithms, there are different formulations
of the bakery algorithm floating around.

But my assertion is independent of any reformlation. That's part of my claim,
as I have posted. In other words, *YOU* could pick any reformulation you like \0
and test it against my claim. "Iterating over all processes", or self-
identifying processes is central to the way the algorithm works.
[...] I'll look up the original Lamport papers later on, and see if the
process-id thing is truly essential.

You brought it up without being familliar with it? We're like 6 posts into
this and you still haven't addressed the very simple and obvious assertion that
its not portable.
I already established that if you cannot portably get mutexes in C, I
will concede.

And your banking everything on your ability to attempt to argue this fact with
me?
[...] This very specific point of contention is *not* decided yet, in this
discussion.

You just have no perspective on this. It does not even occurr to you that I'm
not just spouting some "theory" that I just made up. Refereed papers are
written about "lockless" or "semi-locked" ADTs. Still other are written about
minimal hardware support (like just shared memory, or a 2-write atomic memory
operation) ADTs. Now why would they bother if portable mutex implementations
existed? Why does the VxWorks manual complain that some older PPCs have sub-
standard support for multitasking? If it were emulatable, why wouldn't they
just write software mutexes -- why wouldn't just explain that it might be a
little slower?
[...] All hinges now on whether the Lamport algorithm needs process
id's. Fortunately, there's no subjective element in that, we should
be able to sort that out.
What I don't understand is how is it that *YOU* brought up the
algorithm, and yet you are unaware of its fundamental functionality.

Hells bells, I used it 5 years ago.

If you are implying that you don't remember the details then why bring it up as
the center point of your "counter-example" to my claim of the obvious? I'd be
curious (though only minorly so) as to what kind of possible toy example you
actually made work in an acceptable way with such a mechanism.
[...] What I remember is that it can be used to provide mutexes without
hardware support like atomic read/update/write cycles.

But that's not true either. Another mechanism that is used by the algorithm is
the idea of shared variables. This requires atomic-by-type based
implementations hardware implementations. For example, suppose on a multi-
processor system, that 32-bit (or 64-bit) word sized datum was actually updated
on a shared bus one 8-bit byte at a time in sequence. Then you can't declare
the shared variables required to implement the "taken numbers", unless you
appeal to some other mechanism to lock the bus. You will notice that "shared"
is not a recognizable concept in ANSI C.

Implementing correct mutexes have a *LOT* of requirements of the
implementation. None of the typical "attempted" critical section algorithms
that you are supposed to learn in an OS CS class as being examples of stuff
that may or may not work satisfy *all* the requirements. Even the all hallowed
Petersen algorithm requires an implementation of shared variables and only
solves the case for two tasks. No matter what, multithreading support boils
down to using some kind of hardware support, and there's none to be found in
the ANSI C standard, implicit or otherwise.
[...] At this point, I'm not sure if the process id stuff is essential. I'll
look into it.
It only took me only 30 seconds to understand it.

Well, that would surely make you quite brilliant.

No ... it would make me someone who has actually visited a bakery with a "take
a number" service system and participated in it. The algorithm described is
exactly analogous to that (that's why is called that) so reading and
understanding it is almost instantaneous.

But all the same questions you have while waiting in line to place your order
for rolls apply: 1) What happens if two people try to grab the same number at
the same time? (shared variables) 2) What happens when they run out of numbers?
(overflow/wrap-around) 3) What prevents someone from grabbing a number on
behalf of someone else (analogous to how do you rigorously identify a process
to a unique access to one number at a time.)?

30 seconds -- its too much time to spend on this triviality, especially
considering its an inadequate solution.
[...] Took me a couple of hours, the first time I read it, to get my head
around it, and to see that it is correct.

If I had to spend an hour waiting for service at a bakery, I would have taken
my business elsewhere.
What's the problem?


Yes, and for now, I contend otherwise, ...

Do you also contend that the moon landing was faked ... for now? Its not like
there's any open or controvertial issue left with this dead horse. You only
have to listen and understand what I am saying. Look up *ANY* description of
the Lamport Bakery Algorithm -- my exposition of its flaws are inescapable and
clearly there. And a transformation of it is not going to save it.
Sure. Read a few posts back, I already said that it would be an
interesting idea to put your stuff in the standard library for
performance reasons.

Which is only a good side-effect of it -- the real reason for putting it into
the standard library is for functionality reasons, and because of portability
reasons you *HAVE* to put them in there if you want to use such functionality
universally.
[...] I was quite ready to leave it at that, but you *INSISTED* that it is
completely impossible to do, portably.

I also insist that 1 + 1 == 2.
[...] That's the one and only thing we're discussing now.

At this point, I'm not sure whether it can be done but my hunch is that
it is possible, based on something like the Bakery algorithm.

There we go, just as predicted ... "something like ..."
[...] If you think this question is too academic, I'd be happy /not/ to
spend the effort to get to the bottom of this.

When did I say that? You have put forth an example that you claim counters my
oh so questionable claim that you can't implement Mutexes portably. I spent
the requisite 30 seconds of analysis to bust it and you are dancing around the
issue like you have ants in your pants.
[...] Then again, in this case, the onus would be on me to give at least an
outline of how it could be done.

The onus was on you the second you offered a counter example to my statement.
Ok, except that "There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place" is not a fact.

You mean its something you are just unaware of. I offer for you to seek any
authority or any resource to counter such a claim. And just citing yet another
algorithm doesn't count -- I'm not here to do random research to debunk your
misconceptions.
I acknowledge that with the portable mutex stuff, the burden of proof
rests with me. However, you did't seem to think this was the case with
your "operator introduction" parser, expecting to get away with the
premise that it could surely be solved (which is not at all obvious).
Why the double standard?

Because you offered your argument before I argued a fully flushed out proposal.
I have already admitted that I am not an expert on parsable grammars, but at
least I am aware that parsable grammars exist. You said that my proposal was
all but impossible based on this alone.

If I propose a grammar that has a mistake in it, that doesn't mean my general
idea is flawed, its just a reflection of the fact that I am not an expert on
this one narrow field. So, so far I have refrained from doing that. Contrast
and compare that with your suggesting the Lamport Bakery Algorithm as a
proposal for a portable Mutex. Besides the fact that its stupid and I was able
to kill it instantly, it doesn't *prove* anything either way, which I think was
probably your intention all along.
It's not obvious. Perhaps you're right, perhaps I'm right. We'll get to
that.

Its obvious to someone who understands multitasking. Spending hours trying to
learn a "take a number" based service system is perhaps indicative of something
otherwise.
That's quite a strange accusation, given that we didn't establish yet
that the bakery algorithm or something similar can't provide mutexes,
using portable C.

There we go ... "or something similar". Right down the expected path. So when
I bust some modification that you are inevitably going to make, will that
"prove" something to you? Or will you simply offer amendment after amendment
knowing that my 30 second kills don't prove anything?
I don't do cheap rhetorical tricks,

Well, then why have I spent half a dozen long winded posts trying to explain
the completely obvious, without one iota of success? The entire onus is on
you, yet every post I try to make it clearer and clearer what is so
ridiculously obvious.
[...] and I will take seriously-looking arguments serious.

Why don't you try taking all arguments seriously, then decide if they are
actually serious or not *after* you have looked at them?
Will do. Will you do the same with the operator-introduction parser
problems? Like provide a semantics that you can show not to lead to
parsing ambiguities? Quid pro quo.

You mean you want me (an admitted non-expert, and therefore intentionally side
stepping it) to come up with a parsable grammar as proof that there exists a
parsable grammar on arbitrary symbols? Well, if tht's what it takes ...
That's a better way, that (unfortunately) seems to be rather hard to
formalize. I am proposing to forego the difficulties be defining (for
these rare cases) a very loose upper bound.

You are forgoing legitimate platforms. See, screwing over VAX and old CDCs for
choosing 1s complement -- that's one thing. They are both obsolete, and
*everyone* understands that that was just a design mistake. But multiple
stacks? Its not obvious in any way that multiple stacks are necessarily
incorrect. You see many pure RISCS such as Alpha, PPC, and MIPS have nothing
in their architecture that fits a unified stack (not true of x86, AMD64, IA64
or Sparc.) This is especially true of embedded systems, as I mentioned, that
can have non-uniform data stores.

So if you want to screw over architectures by proposing amendments to the
standard, doesn't it make sense to limit the problems to the minimum possible
number of architectures, and ideally, on architectural ideas that won't be
moving forward?
For such architectures it would be difficult to write code that honours
the upper bound metric. I don't think that's a problem; rather the
opposite. It would force programmers to consider the issue.


I don't understand this, why would you have to do this?

The purpose of a generic programming language is not to dictate what algorithms
can or can't be implemented in it. I'm merely proposing that having multiple
stacks may be the best solution for certain kinds of problems so a proposal
which models the system with a unified stack will mischaracterize an otherwise
acceptable and valuable computational platform that *isn't* so hampered with
the way the specification exists today.
Why thank you. I think I dislike the proposition that I would not do the
same thing, though.

Well I'm waiting ...
[...] In cases where you can't (few and far inbetween) you don't
have the guarantee, which is a pity; the code can no longer be
written in a way that's fully portable. It would still be much
better than what happens now (standard-compliant programs
segfaulting without so much as a hint in the standard).
It means you are expecting compilers to come as close to solving the
halting problem as they can.

No. I don't expect the compiler to do anything with this information.

You don't understand. The compiler has to try to solve the halting problem
just to *provide* the information.
It's there for the programmer to use, for checks at runtime (e.g. at the
start of main() in heavy recursive programs). It can't be done at
compile time since, in general, you don't know the stack size at that point.


I think it's very difficult, and it may be even impossible, yes. But
surely, you're going to demonstrate that I am wrong? :)

Either you know even less than I do about parsable grammars or you just have no
comprehension of what I've just said. You start with a number of symbols (+,-
,<,>,=, ... etc) and you wish to create a non-ambiguously parsable grammar on
them. This is not in the realm of "open problems" this is in the realm of
"homework exercise".
My point is that symbols have an order of magnitude less menmonic value
than symbols. Well yes, you can call that an 'opinion', but it's also a
testable hypothesis (and it has probably been tested in research). Don't
have a reference, though. Can we just leave it at that?

Well ... I *do* have a reference. Its called the C++ standard. As far as *I*
can tell, there is no outcry in that community against operator overloading --
STL would lose a lot of its potency without them.
Well I don't know what to make of this -- you can't see a race
condition when its staring you in the face, and you can't imagine
problems with knowing the size of a function's stack usage.
Be careful not to presume things that are not there. [...]
Yeah, thanks for the warning. I'll be sure to purchase some duct tape
to deal with my neighbors who might be terrorists too.

You don't know me, I don't know you. Probably if we met in person we
could get along just fine, given the fact that we seem to share some
interests.... Why is it silly to ask that you don't pass judgement from
5000 miles away on someone whom you don't know?

You can't imagine just the littlest bit of frustration on my part? I've spent
a half dozen posts trying to explain a very simple point, and you are just not
getting it at all.
I won't back it up. It's an opinion that could easily be turned into
fact, though. Here's an experiment for you:

count_nodes counts the nodes in the tree

How many parameters does this take? What is a tree, and what about this
function name tells me that these are nodes of a tree?
@* do a matrix multiply
insert_element insert element in the list

List? A global list? A list supplied as a parameter? Again, how many
parameters does this function take?
?> take the maximum
is_prime determine if number is prime

Do you mean prime polynomial? Prime over a specific ring?
=%= see if two numbers are in the same residue class
log take the natural logarithm

This is a standard library function. Why didn't you also include a standard
operator such as "+" in this list?
<#> count the elements in the list

# has special meaning to the preprocessor and probably should not be included.
@| would be better.
event_handler_poll poll the event handler

Does this use coroutine, message passing, self-blocking, or mutex semantics?
And again how many parameters does such a function take?
<^ left-associative power

^ means exclusive or in the C language.
mutexP take the mutex
%# calculate a percentage

% has the meaning of modulo.
...Now turn away from the screen, and have somebody read the
_descriptions_. Reproduce the function name / operator symbol from
memory. How many operators did you get? How many symbols? Let's have a
bit of this intellectual honesty! :)

Well, the fact that you didn't chose the operators very carefully, and that
even reciting the function names wont tell you their semantics/limitations or
even how many parameters they take. At least with operators you know the
number of parameters no matter what.

You see with operators its possible, for example, to partition them into unary
versus binary. So using regex notation (ignoring the need to \ escape +, *, ?
and ^ inside of a [...]), imagine that we start with a grammar such as:

Associative binary operators:

[@$%^<>]*[@$%][|^+*&]
[@$%^<>]*[^<>][|^]

Not (necessarily) associative binary operators:

[@$%^<>]*[@$%^][-/<>]
[@$%^<>]*[^<>][/]

Unary operators:

[@$%^<>]*[@$][~!]

Three inputs (like the (a ? b : c) operator):

[@$%^<>|+*&]*[%^<>|+*&][?]+ [@$%^<>|+*&]*[:]+

Two inputs, two outputs (for the carry, or high word multiplies)

[@$%^<>|+*&]*[%^<>|+*&][:]+ [@$%^<>|+*&]*[?]+

So in a sense you would know something about them without looking at their
actual definition. So one could omit the "like" or "before/after" clauses from
my original definition and say that the operator inherits the order of
precendence from the operator they are most closely derived from (the rightmost
character, excluding : or ?.)

The trick in describing the two output operator scheme is that the second
output parameter would be treated as if it had a C++ & ref operator on it.
Example:

int _Operator @: unsigned int low *? (int a, int b) {
long long unsigned x = ((long long) a) * ((long long) b);
low = (unsigned int) x;
return (unsigned int) (x >> 32);
}

so this "output parameter" could not have a "const" on it. And the syntax for
usage would be:

high @: low = a *? b;

with the idea of the "=" being there to mark a clear division between what's
written to and what's read from. And the degenerate form:

high @:= a *? b;

follows a familliar C-like pattern.

Of course, I was trying to be conservative but I may have missed a parsing
ambiguity in there somewhere. I also almost certainly have missed entire
patterns of symbols, and I think it would just be a matter of adding them in
there. Assuming I made no errors, or assuming that they are easily fixed, does
it still look impossible or even all that challenging to add these to the
parser, or even lexer (as someone else mentioned)?
What is that supposed to prove? The same is true for your carry:

/* adding with carry, presuming 2-complement repr. */

unsigned a, b, result;
int carry;

result = a+b;
carry = a>(UINT_MAX-b);

Ok -- I'll give you that one. In my own primitives I use this:

#define ADD_GEN(dst, s1, cf) { \
dst += s1; \
cf = s1 > dst; \
}

(where typ is some unsigned integral type) which I always assumed only worked
because of 2s complement. In any event, I am unaware of any C compiler that
can reduce this to one instruction by the "as-if" rule. And of course carries
also come out of shifts, and a simple comparison operation isn't going to help
there.
Here's an algorithm that uses overflow:

int add_signed(int a, int b, int *overflow);

{
int a,b,r,ov;

get_ab(&a, &b);
r = add_signed(a, b, &ov);
if (ov)
printf("sorry, can't add those.\n");
else
printf("result = %d\n", r);
}

But this isn't an *algorithm* its tautology.
But the point is: C doesn't have (real) strings.

But you can add them with no trouble (http://bstring.sf.net/,
http://www.and.org/vstr/, http://www.annexia.org/freeware/c2lib/.) In
particular there were no real extensions I needed to the language to make "the
better string library" work well. I could have used an expand() heap function
as an alternative to realloc(), but I found a mostly reasonable asymptotic
alternative solution. And besides a lot of people are under the impression
that you can use C's built-in strings adequately for real strings, and for
trivial cases, or ridiculous investments into programming around their
limitations, you can.
[...] C doesn't provide bignums.

But the point is that it also doesn't provide a way to implement them that is
practical or useful from a performance point of view. Writing such libraries
will give solutions that are either ridiculously slow (using public-school
algorithms only), or extremely convoluted and non-portable. Thus there is a
real different between bignums and strings.
[...] It provides rather mundane support for bit-twiddling, but only
on a per-byte-or-more basis. That's the essence of my "rhyme" claim:
things that collide with the core language shouldn't be forced in there,
just out of convenience for some specific application.

But how is it forced if every hardware platform supports it?
Perhaps you should download the standard and read it (especially the
naughty parts on signed and unsigned integers), to see what I mean.

Because the standard has nothing to offer me?
Hold on a minute... Where's your famed "intellectual honesty" now? You
made a claim that I disproved, and now you're just moving along as if it
didn't happen? At least an acknowledgement would be nice.

I've gone round and round on the potential for 1s complement with other people
in this or the comp.std.c newsgroup in the past. My conclusion is that it
should be treated like 8088, and 68k were treated by the C standard on the
issue of including float point -- i.e., where the functionality is compelling
enough and enough platforms support it, it is acceptable to push it in there
anyway and force the weaker platforms to emulate it. In general, there is no
forward looking reason to pay deference to 1s complement for any practical
reason.
To address your point though.

I'm really interested to see how you would write a big number multiply
that doesn't presuppose 2-complement, but works in 1-complement as well.

I'm really interested in seeing you make contributions of a technical nature
here too -- I mean besides the occasional function that is obviously wrong, or
specifications that include fundamental logic errors in them.
For the sake of argument, feel free to introduce a wide-mul operation
(but let's have a semantics for it... The x86 MUL obviously won't do).

I already gave the formula:

((a << 32) + b)*((c << 32) + d)

is the same as:

((a*c) << 64) + ((a*d + b*c) << 32) + b*d

So long as we are capable of a widening multiply and a carry capturing adder,
its not hard to organize these:

result[0] = low(b*d)
result[1] = high(b*d) + low(a*d) + low(b*c)
result[2] = carry(high(b*d) + low(a*d) + low(b*c))
+ high(a*d) + high(b*c) + low (a*c)
result[3] = carry(carry(high(b*d) + low(a*d) + low(b*c))
+ high(a*d) + high(b*c) + low (a*c))
+ high(a*c)

So you can see, that all it takes is the ability to capture carries out of
additions and the both the high and low part of a widening multiply. This
transforms two entry long "bignums" into a 4 entry long result for
multiplication. The more general answer is just more of the same.
 
P

Paul Hsieh

(e-mail address removed) says...
I'm not sure what you mean when you say "fgets() ignores '\0' that are
consumed." Can you elaborate on this, please?

1) Write a program that takes input from stdin line by line using fgets(), and
accumulates the result into an MD5 hash.

2) Now redirect an arbitrary file into it (assuming UNIX or Windows-like
redirection facilities.)

Ok, first step, of course, is to reopen the stdin as binary. (If all this
seems hoakey to you, just open any file in which someone previous performed an
fwrite with some number of '\0' s in it instead.) But after that you discover
that its impossible to know for sure exactly how much data each fgets()
operations reads!

- strlen() is just plain wrong because earlier encountered '\0's don't
correspond to the where the first '\n' or bufferlength-1 is encountered.
- scanning for '\n' is insufficient on the very last line of the file because
it might really have early terminated by an earlier '\0'

In short, fgets() does not leave you with a deterministic way of knowing how
much data was really read unless you outlaw '\0' from the input stream.
 
C

CBFalconer

Arthur J. O'Dwyer said:
I agree with Paul that this is a very basic and very obvious fact
that shouldn't be too hard to grasp. If you've done any
thread-based programming (nothing complicated, just anything that
requires a shared resource), you've noticed that every time two
threads want access to the same bit of memory at the same time,
you need some kind of mutex to block out one of the threads while
the other one does its thing, and then block out the other one
while the first one does *its* thing.

Mutexes cannot be expressed in standard C, because standard C has
no way of specifying "this block of data behaves like a mutex."
I'm sorry if that sounds circular, but it's hard for me to
describe the effect of a mutex except by jargon. Suffice it to
say that you can feel free to post snippets illustrating anything
you think qualifies as a mutex algorithm written in standard C,
and I will be only too glad to poke holes in it.

Once more I am trying to cut this monstrous thread up into
identifiable sub-threads, dealing with single subjects, and with
reasonably sized articles and subjects :)

Conceding the chicken and egg nature of the problem, all is solved
once we can provide exclusive access to something, which in turn
allows setting and clearing of flags for whatever scheme we
prefer. The one thing that C provides is atomic access to
objects. It seems to me that this suffices to implement Dekkers
algorithm, and thus implement critical sections. The solution may
not be efficient, but it is a solution, IMO.
 
L

lawrence.jones

Randy Howard said:
I wouldn't be the least bit surprised to find out that MS
deliberately jacked with the C99 efforts to
a) make life difficult for other vendors
b) add obscure items to marginalize it indirectly
c) make it easier for them to claim conformance without doing anything
if they ever decided to do so.

Nope. In fact, Microsoft almost completely ignored the C99 effort. The
only major implementor who participated less was GCC.

-Larry Jones

Please tell me I'm adopted. -- Calvin
 
A

Arthur J. O'Dwyer

Once more I am trying to cut this monstrous thread up into
identifiable sub-threads, dealing with single subjects, and with
reasonably sized articles and subjects :)

Conceding the chicken and egg nature of the problem, all is solved
once we can provide exclusive access to something, which in turn
allows setting and clearing of flags for whatever scheme we
prefer. The one thing that C provides is atomic access to
objects. It seems to me that this suffices to implement Dekkers
algorithm, and thus implement critical sections. The solution may
not be efficient, but it is a solution, IMO.

Using the description provided on this site:
http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Dekker.html
I think you're speaking of a mutex algorithm that would look something
like this. And I must admit that at the moment I don't see any holes
in it, so obviously I was wrong when I said I could poke holes in any
algorithm you devised. (Doesn't mean I'm not missing something here,
of course... :)
Now of course this algorithm still depends on the ability to give
a unique process-ID to each thread -- and you have to do that *without*
a mutex (chicken-and-egg problem)! But for some reason that problem
seems *less* obviously impossible than the mutex problem, and, well,
you've just shown me where I was wrong on that... ;-)


struct DekkerMutex
{
int flags[2]; /* Expects only two threads, with IDs 0 and 1 */
int whose_turn;
};

void DMutex_init(struct DekkerMutex *mut)
{
mut->flags[0] = mut_flags[1] = 0;
mut->whose_turn = 0;
}

void DMutex_lock(struct DekkerMutex *mut, int thread_id)
{
mut->flags[thread_id] = 1;
while (mut->flags[1 - thread_id] != 0) {
if (mut->whose_turn != thread_id) {
mut->flags[thread_id] = 0;
while (mut->whose_turn != thread_id)
continue;
mut->flags[thread_id] = 1;
}
}
}

void DMutex_unlock(struct DekkerMutex *mut, int thread_id)
{
mut->whose_turn = 1 - mut->whose_turn;
mut->flags[thread_id] = 0;
}


So, what bugs have I introduced?
-Arthur
 
C

Chris Torek

Now of course this algorithm still depends on the ability to give
a unique process-ID to each thread -- and you have to do that *without*
a mutex (chicken-and-egg problem)! ...

Sort of, anyway.
But for some reason that problem seems *less* obviously impossible
than the mutex problem ...

Any system that provides threads (or whatever you want to call
processes that share memory and therefore need some kind of mutual
exclusion mechanism) must also provide some way to identify them.
This "way", whatever it is, is guaranteed not to be portable, but
it must exist. If the threads are not distinguishable in *any*
way -- if both are absolutely identical -- it becomes impossible
to talk about them in any meaningful manner other than as if there
were no separate threads. After all, if they are *absolutely*
identical, they must also execute the same instructions at the same
time, on the same data at the same time, producing the same results
at the same time. What, then, is the point? (Possibly: redundancy
in a safety-critical system, where external hardware compares the
results and produces an alarm if they differ. But that external
hardware does not exist as far as the identical-threads are concerned,
and they have no need for mutexes.)

Given this -- that the two threads must necessarily have some
distinguishing marks, so that we can tell each "clone" from the
"original" and/or from each other -- it is a short, but also
nonportable, step to unique numeric identifiers.

These two steps are, as I said, nonportable. They do not *need*
to be portable either, for a reason I will address in a moment.
It might be nice in some ways if they were portable, but "portability"
is merely a component in a cost/benefit equation. Whether to put
something like this in a future C standard is also part of a
(separate) cost/benefit equation. I contend that it is the wrong
place to look. Here is why:

In systems that make heavy use of threads, there is usually a strong
performance constraint on the mutex mechanism. (Indeed, we often
look for mutex-free atomicity algorithms, such as clever use of
load-(locked|linked)/store-conditional instructions to create atomic
queues, so as to avoid paying for a mutex on each queue insert or
delete.) The reason is that access to any shared data structure
requires using these mutexes (unless sidestepping them with atomic
queues and the like). In general -- at least once the system is
properly tuned -- the "get mutex" operation is largely uncontested:
blocking (or otherwise deferring) on a mutex is, or at least should
be, rare.

Assuming mutex contention *is* rare, suppose we compare the
performance of the system to that of one without mutexes. What do
the mutexes do, besides add correctness? Answer: they mainly slow
the system down. Every "get" and "release" operation that turns
out not to have been required for correctness, also turns out to
be nothing but a drag on performance. If 97% of the operations
are uncontested, 97% of them are "just" performance-drag. (This
is half of a more general rule about computers: "The fastest and
most reliable code in any program is the code that is not there.")

Since speed sells -- even more than correctness, in most cases;
people are in general much more willing to buy a fast system that
"almost always" works than a slow one that *always* works --
uncontested mutex operations must be fast. And, as it turns out,
the fastest such mechanisms on existing CPUs are invariably
CPU-specific, i.e., non-portable.

What people writing these threaded systems want, then, is not a
portable way to implement mutexes. What they want is already-implemented
mutexes -- no matter how non-portable -- that can be *used* in a
portable manner. That is, an implementation will provide some
abstract "mutex" type (some ADT, including operations) that is not
itself portable, but one which is used the same way no matter how
it is implemented underneath.

I do not think there is any need to add this to any C standard
today. There are additional standards one can use, and at least
one of them -- POSIX -- provides a mutex ADT. POSIX mutexes are
not my favorite, but they get the job done, at least. And if
for some reason this particular standard is unsuitable, the
usual rule about standards applies: they are great because there
are so many to choose from, and if you do not like any of those,
you can just invent your own. :)
 
K

Keith Thompson

Given any definition of portable. There are no C99 compilers, compliant or
otherwise.

I don't believe that's true.

[...]
And of course you have to pay deference to the C++ people because
there is scarcely a C compiler in existence today that isn't also a
C++ compiler, and users of that language will not understand your
pedantry when explaining that "my code is portable, its just that
your compiler is not".

Many compilation systems can act as either C compilers or C++
compilers, depending on how they're invoked. (gcc, for example, has
distinct frontends for the two languages; I don't know how other
compilers handle it.) That doesn't imply a need to write C code
that's also legal C++ code.

Any compiler that rejects a C program that uses "new" and "class" as
identifiers, or that doesn't cast the result of malloc(), simply is
not a C compiler.

[...]
You are forgoing legitimate platforms. See, screwing over VAX and
old CDCs for choosing 1s complement -- that's one thing. They are
both obsolete, and *everyone* understands that that was just a
design mistake.
[...]

The VAX uses two's-complement.

[...]
I've gone round and round on the potential for 1s complement with
other people in this or the comp.std.c newsgroup in the past. My
conclusion is that it should be treated like 8088, and 68k were
treated by the C standard on the issue of including float point --
i.e., where the functionality is compelling enough and enough
platforms support it, it is acceptable to push it in there anyway
and force the weaker platforms to emulate it. In general, there is
no forward looking reason to pay deference to 1s complement for any
practical reason.

Emulating floating-point on a platform that doesn't support it in
hardware is reasonable (and fairly common). Emulating 2's-complement
on a platform with 1's-complement hardware is not.

The real question is whether limiting C to 2's-complement has enough
benefits to outweigh the disadvantage of cutting off support for
non-2's-complement hardware. I don't know the answer, but I'm
inclined to assume that it's "no" unless there's strong evidence to
the contrary.
 
S

Sidney Cadot

Typed "Lamport bakery algorithm," naturally, and then clicked the
button labeled "I'm Feeling Lucky." It takes you right to
http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Bakery.html

Ah yes! The "I feel lucky" button. Forgot about that. Would have saved
some time if Paul would have just provided the reference, instead of
turning it into a game.
Well, you obviously don't need access to UNIX "pids" to do the
algorithm, but you *do* need a reliable source of unique integer
identifiers for each thread. And that's something that standard
C simply cannot give you without specific language support.

This is pretty much the crux, I agree.

However, this entire discussion seems a but weird to me. At some point,
the program will have to do something inherently non-portable, i.e.,
fork a thread. Further, we're assuming a functioning, thread-safe
malloc(), also under multithreading. Perhaps something as simple as this
could portably provide a unique process identifier:

char *thread_id;

if (thread_fork()==-1)
{
thread_id = malloc(1);
}
else
{
thread_id = malloc(1);
}

I agree with Paul that this is a very basic and very obvious fact
that shouldn't be too hard to grasp. If you've done any thread-based
programming (nothing complicated, just anything that requires a
shared resource), you've noticed that every time two threads want
access to the same bit of memory at the same time, you need some
kind of mutex to block out one of the threads while the other one
does its thing, and then block out the other one while the first one
does *its* thing.
Mutexes cannot be expressed in standard C, because standard C has
no way of specifying "this block of data behaves like a mutex." I'm
sorry if that sounds circular, but it's hard for me to describe the
effect of a mutex except by jargon. Suffice it to say that you can
feel free to post snippets illustrating anything you think qualifies
as a mutex algorithm written in standard C, and I will be only too
glad to poke holes in it.

I'm afraid I will have to spend some time on this (that's a lesson for
next time I get dragged into a particular thread of discussion), and
your poking-holes offer is appreciated.

The basic idea of piggybacking on the malloc() may be useful, even to
save the Bakery algorithm.
It only took me only 30 seconds to understand [the bakery
algorithm].

Well, that would surely make you quite brilliant. Took me a couple of
hours, the first time I read it, to get my head around it, and to see
that it is correct.
Maybe it's the changing times. Or maybe it's the way that web
page explains it -- it's intuitively obvious to me from their
description that if Thread A has a lower number than Thread B, then
Thread A naturally goes first. It just makes sense.

[...] I feel rather silly getting dragged in this line of
discussion (multithreading has little to do with the C execution
model) but we'll see where this leads us.
Then let me review the facts for you. Multithreading is inextricably
intertwined with the implementation of malloc. Thus if a compiler
vendor wants to provide a multithreading extension to C (which they
pretty much all do) discussions of implementation of malloc, or
malloc-like functions have to at least acknowledge this as a
consideration. There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place. The inevitable conclusion is that
its impossible to make a portable library for extending the heap
functions that are multithreading safe.

Ok, except that "There is no such thing as a portable mutex in pure C
that actually encodes all the expected notions of a mutex unless tied
specifically to the extension mechanisms that are used to provide the
multitasking in the first place" is not a fact. That's what we're
arguing about, now.


Well, Paul's right and you're wrong. That's all.

I wouldn't mind being wrong. Mind you, I wouldn't mind being right! :)

My main quarrel with Paul is the confidence he displays when dismissing
the possibility. I think the issue is much too complicated for that.

I am not sure whether the bakery algorithm (or other algorithms that try
to do similar tricks) cannot be made to work. I'd be willing to invest
some thought in that; but I think the issue is just too difficult to
merit an out-of-hand dismissal.
[re stack bounds checking]
This proposal sounds both reasonable and possible to me. I do
agree that it requires a *lot* more thought, though; and you'll see
if you search Google Groups that this topic has been discussed both
here and in comp.programming (IIRC) quite a lot before.
Ok.
Of course it's *possible* to create an arbitrary-operator-parsing
grammar!

The problem would be to define a set of rules that would guarantee that
the grammer is unambigous.
Why do you say that? It's not dishonest to use the well-thought-out
and publicly-reviewed specification of an x86 operation in this
context.

Sure, but the MUL only covers unsigned multiplies. Now you could solve
bignum simply by adding a separate sign marker, and be done with just
unsigneds, I realize that now. So this _was_ a bit silly - though not as
silly as proposing x86 MUL semantics even on signed integers as Paul
would have it, I would say.
> [unsigned variant snipped, no contention there]
signed long lmuls(signed long p, signed long q,
signed long *hi, signed long *lo);

The 'lmuls' function accepts arguments 'p' and 'q', multiplies
them using normal integer arithmetic, and stores the high-order
bytes of the result in '*hi' and the low-order bytes in '*lo'.

I think it's better to have 'lo' as an unsigned long. Anyway, I am all
in favor of having this kind of functionality in the library (where you
can properly put constraints on the argument types). What I reacted
against is the introduction of an operator (which should be able to
handle both signed and unsigned arguments).

[snipped a bit]

That said, I think this thread needs to start splitting up. :)

Okay. I'll do my best to reroute the Mutex part here. As I said, I think
it is not over.

Best regards,

Sidney
 
S

Sidney Cadot

Portable in C means C89 minus the incompatibilities with C++.

I can live with that (although you could receive some flak on the C++
bit, but not from me). Ok, 64 bit integers are out, then.
Are there any braincells operating in your head?

Right. This is the last post of you where I will tolerate insult. If you
cannot conduct a civil discussion, I'm out.
Then you are just braindead? There's no lee way here. There's no other
possible thing that I could possibly type into google to help me look this up.
What were you expecting me to type in? "Worthless non-solutions to critical
section?" "The idiots guide to multitasking incorrectly?" "Race conditions
are us?" "Good looking algorithms laced with (not-so-well) hidden weaknesses?"

Wouldn't it have been simpler for all involved just to provide a link?
[...] Like with many important algorithms, there are different formulations
of the bakery algorithm floating around.
But my assertion is independent of any reformlation. That's part of my claim,
as I have posted. In other words, *YOU* could pick any reformulation you like
and test it against my claim. "Iterating over all processes", or self-
identifying processes is central to the way the algorithm works.
[...] I'll look up the original Lamport papers later on, and see if the
process-id thing is truly essential.


You brought it up without being familliar with it? We're like 6 posts into
this and you still haven't addressed the very simple and obvious assertion that
its not portable.

We'll come to that. Why the rush? It's complicated subject matter. You
have to give me some time to think.

In the mean time, while I cook up a portable mutex implementation, there
is one thing we have to get out of the way. The program will contain at
least one non-portable item: the thread instantiation. In a strict
sense, it is therefore impossible to make a portable program using
threads. It would be easy to get a process identifier for the memory
manager at that point. I suppose you wouldn't consider it acceptable if
we did that?
And your banking everything on your ability to attempt to argue this fact with
me?

Yes. Silly me.
[...] This very specific point of contention is *not* decided yet, in this
discussion.
You just have no perspective on this. It does not even occurr to you that I'm
not just spouting some "theory" that I just made up. Refereed papers are
written about "lockless" or "semi-locked" ADTs. Still other are written about
minimal hardware support (like just shared memory, or a 2-write atomic memory
operation) ADTs. Now why would they bother if portable mutex implementations
existed? Why does the VxWorks manual complain that some older PPCs have sub-
standard support for multitasking? If it were emulatable, why wouldn't they
just write software mutexes -- why wouldn't just explain that it might be a
little slower?

Well, it would probably be a lot slower. Better to support the native
facilities for that reason alone. Otherwise, I'm not going to second-guess.
[...] All hinges now on whether the Lamport algorithm needs process
id's. Fortunately, there's no subjective element in that, we should
be able to sort that out.
What I don't understand is how is it that *YOU* brought up the
algorithm, and yet you are unaware of its fundamental functionality.

Hells bells, I used it 5 years ago.
If you are implying that you don't remember the details then why bring it up as
the center point of your "counter-example" to my claim of the obvious?

I think that the algorithm could support portable mutexes. Doh.
I'd be curious (though only minorly so) as to what kind of possible toy example you
actually made work in an acceptable way with such a mechanism.

It was a toy example. What has that got to do with anything?
[...] What I remember is that it can be used to provide mutexes without
hardware support like atomic read/update/write cycles.
But that's not true either. Another mechanism that is used by the algorithm is
the idea of shared variables. This requires atomic-by-type based
implementations hardware implementations. For example, suppose on a multi-
processor system, that 32-bit (or 64-bit) word sized datum was actually updated
on a shared bus one 8-bit byte at a time in sequence. Then you can't declare
the shared variables required to implement the "taken numbers", unless you
appeal to some other mechanism to lock the bus. You will notice that "shared"
is not a recognizable concept in ANSI C.

Yes, there has to be a shared variable. Let's presume that char-type
variables can be used, and see if that suffices.
Implementing correct mutexes have a *LOT* of requirements of the
implementation. None of the typical "attempted" critical section algorithms
that you are supposed to learn in an OS CS class as being examples of stuff
that may or may not work satisfy *all* the requirements.

Before I go and spend some of my precious free time on this, do you have
a list of these requirements somewhere, that would satisfy you? Wouldn't
want to leave anything out.
Even the all hallowed
Petersen algorithm requires an implementation of shared variables and only
solves the case for two tasks. No matter what, multithreading support boils
down to using some kind of hardware support, and there's none to be found in
the ANSI C standard, implicit or otherwise.

Well, there's some guarantees on volatile variables and sequence points,
but that won't help with multithreading.
>> [snip]
Yes, and for now, I contend otherwise, ...
Do you also contend that the moon landing was faked ... for now? Its not like
there's any open or controvertial issue left with this dead horse. You only
have to listen and understand what I am saying. Look up *ANY* description of
the Lamport Bakery Algorithm -- my exposition of its flaws are inescapable and
clearly there. And a transformation of it is not going to save it.

We'll see. I really hope I can come up with a solution now, you will
feel all silly. Otherwise, I will apologise for waisting your time.
[...] I was quite ready to leave it at that, but you *INSISTED* that it is
completely impossible to do, portably.
I also insist that 1 + 1 == 2.

Well, 1+1 and 2. have different types, for one thing... :)
[...] That's the one and only thing we're discussing now.

At this point, I'm not sure whether it can be done but my hunch is that
it is possible, based on something like the Bakery algorithm.
There we go, just as predicted ... "something like ..."

Yes, you're a visionary. I hope you will still accept a solution that
isn't based on the lamport algorithm, when push comes to shove.
[...] If you think this question is too academic, I'd be happy /not/ to
spend the effort to get to the bottom of this.
When did I say that? You have put forth an example that you claim counters my
oh so questionable claim that you can't implement Mutexes portably. I spent
the requisite 30 seconds of analysis to bust it and you are dancing around the
issue like you have ants in your pants.
:)
[...] Then again, in this case, the onus would be on me to give at least an
outline of how it could be done.
The onus was on you the second you offered a counter example to my statement.

(...clears throat...) *** I AGREE ***
You mean its something you are just unaware of. I offer for you to seek any
authority or any resource to counter such a claim. And just citing yet another
algorithm doesn't count -- I'm not here to do random research to debunk your
misconceptions.

I appreciate the effort, though.
Because you offered your argument before I argued a fully flushed out proposal.
I have already admitted that I am not an expert on parsable grammars, but at
least I am aware that parsable grammars exist. You said that my proposal was
all but impossible based on this alone.

*HONK* Deliberate misrepresentation. My point is that it is at least
very complex, perhaps impossible, to define a set of rules which will
yield an *unambiguous* grammer (at compile time) every time.
If I propose a grammar that has a mistake in it, that doesn't mean my general
idea is flawed, its just a reflection of the fact that I am not an expert on
this one narrow field.

Right. And if my future mutex proposal doesn't stand up, that doesn't
mean the general concept of having a portable mutex is flawed, either.
So, so far I have refrained from doing that. Contrast
and compare that with your suggesting the Lamport Bakery Algorithm as a
proposal for a portable Mutex. Besides the fact that its stupid and I was able
to kill it instantly, it doesn't *prove* anything either way, which I think was
probably your intention all along.

I am honestly sorry I brought it up. I don't like having this discussion
with you at all, but I feel obliged to show there may be merit in the
idea of portable mutexes.
Its obvious to someone who understands multitasking. Spending hours trying to
learn a "take a number" based service system is perhaps indicative of something
otherwise.

We'll see. I haven't brought my entire intellectual capacity to bear on
the problem, be sure to keep tuned when I do ;-)
There we go ... "or something similar". Right down the expected path.

Yes. It may well be that Lamport won't work, but something else does.
What's the problem?
So when
I bust some modification that you are inevitably going to make, will that
"prove" something to you? Or will you simply offer amendment after amendment
knowing that my 30 second kills don't prove anything?

I will only try to amend if I think it has merit.

Now I'm skipping the rest of the post, that's just to-and-fro rehashing.
I hope you don't mind. If there is anything particular that you'd like
to discuss from it, please let me know. I'd be more interested in
exploring the mutex path, and this is going to take more time than I
like anyway.

Best regards,

Sidney
 
M

Mark McIntyre

Given any definition of portable. There are no C99 compilers, compliant or
otherwise.

Thats a red herring. The existence or otherwise of C99 compilers
doesn't make C99 importable. It merely makes it unimplemented yet on
many platforms to which its portable.
 
C

CBFalconer

Paul said:
.... snip ...

In short, fgets() does not leave you with a deterministic way of
knowing how much data was really read unless you outlaw '\0' from
the input stream.

IF this is a potential problem, you are allowed to build your
input around fgetc, getc, or even getchar.
 
N

nrk

Paul said:
(e-mail address removed) says...

1) Write a program that takes input from stdin line by line using fgets(),
and accumulates the result into an MD5 hash.

2) Now redirect an arbitrary file into it (assuming UNIX or Windows-like
redirection facilities.)

Ok, first step, of course, is to reopen the stdin as binary. (If all this
seems hoakey to you, just open any file in which someone previous
performed an
fwrite with some number of '\0' s in it instead.) But after that you
discover that its impossible to know for sure exactly how much data each
fgets() operations reads!

- strlen() is just plain wrong because earlier encountered '\0's don't
correspond to the where the first '\n' or bufferlength-1 is encountered.
- scanning for '\n' is insufficient on the very last line of the file
because
it might really have early terminated by an earlier '\0'

In short, fgets() does not leave you with a deterministic way of knowing
how much data was really read unless you outlaw '\0' from the input
stream.

Since we are talking about a binary input stream, use of ftell, some simple
arithmetic, and the contents of the buffer returned by fgets will provide
all the information you want.

-nrk.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,176
Messages
2,570,947
Members
47,498
Latest member
log5Sshell/alfa5

Latest Threads

Top