473,890 Members | 2,038 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Is C99 the final C?

I was just thinking about this, specifically wondering if there's any
features that the C specification currently lacks, and which may be
included in some future standardization .

Of course, I speak only of features in the spirit of C; something like
object-orientation, though a nice feature, does not belong in C.
Something like being able to #define a #define would be very handy,
though, e.g:

#define DECLARE_FOO(bar ) #define FOO_bar_SOMETHI NG \
#define FOO_bar_SOMETHI NG_ELSE

I'm not sure whether the features of cpp are even included in the C
standard though (and GCC has definitely taken quite a nonstandard approach
with regards to certain token expansions and whatnot), but that's one area
of improvement I see.

I would also like to see something along the lines of C++ templating,
except without the really kludgy implementation that the C++ folks decided
to go to ( and without the OOP ).

.... Mike pauses for the sound of a thousand *plonks*

Templates save a lot of time when it comes to commonly-used data
structures, and as they are entirely implemented at compile-time and don't
include, by their definition, OOP (although they can be well suited to
it), I think they would be a nice addition and in the spirit of C.

Your thoughts? I'm sure there's some vitriol coming my way but I'm
prepared 8)

--
Mike's Patented Blocklist; compile with gcc:

i=0;o(a){printf ("%u",i>>8*a&25 5);if(a){printf (".");o(--a);}}
main(){do{o(3); puts("");}while (++i);}

Nov 13 '05
193 9704
Paul Hsieh wrote:
<snip>
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.)
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.


I have an idea: why don't you quit being such a whiner and go buy a
copy? Or, for God's sake, simply download a *free* draft of it?
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. Then tell me where in the
standard it says that strtok is not re-enterable.


If you had a copy of the standard then you wouldn't need to ask anybody
else to look things up for you, would you?

Mark F. Haigh
mf*****@sbcglob al.net

Nov 14 '05 #151
In <MP************ ************@ne ws.megapathdsl. net> Randy Howard <ra**********@F OOmegapathdslBA R.net> writes:
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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #152
On Fri, 12 Dec 2003, Paul Hsieh wrote:
Sidney Cadot wrote:
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. 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?

--
au***@axis.com
Nov 14 '05 #153
On Fri, 12 Dec 2003 06:59:12 GMT, CBFalconer <cb********@yah oo.com>
wrote:
Paul Hsieh wrote:
Sidney Cadot wrote:
> >> [snip]
> 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.
For
example, please locate for me where in the standard it says that
fgets() ignores '\0' that are consumed
Dunno what that means.
-- 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.

Implicit in the description.


--
Al Balmer
Balmer Consulting
re************* ***********@att .net
Nov 14 '05 #154
In <Pi************ *************** ****@aurer.se.a xis.com> Johan Aurer <au***@axis.com > writes:
On Fri, 12 Dec 2003, Paul Hsieh wrote:
Sidney Cadot wrote:
> 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. 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?


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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #155
In article <br**********@s unnews.cern.ch> , Da*****@cern.ch says...
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.

--
Randy Howard _o
2reply remove FOOBAR \<,
_______________ _______()/ ()_____________ _______________ _______________ ___
SCO Spam-magnet: po********@sco. com
Nov 14 '05 #156
Paul Hsieh wrote:
Care to take a quick survey of comp.lang.c patrons who own their
own copy of the standard?
Sure, I think you'd be surprised. 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.
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.
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.
You really seem a bit out of touch with current events... Since you
don't seem to have access to the C99 standard, here's the relevant
quote: 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?
Why do you need to distinguish process instances?

Reread the Lamport's bakery algorithm. One of the crucial steps is
"for each process, check their number, and pick the max, then add
1". Another is "for each process that has a lower number, wait in
line behind them." This means you have a way of knowing how many
processes there are, and how to index them. This means you have
to hook out or wrap whatever "spawn" mechanism you have in your
language (or use some other platform specific mechanism to iterate
through all running threads.)


Could you provide a reference to the description of the algorithm
you're using?

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.
Yes, but if two threads simultaneously call heap functions on the same
heap (heaps are not restricted to being distinct across threads) then
there is a race condition.


So we need to put a mutex around the critical section, no big deal. 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
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.
Go look up the source code for *ANY* multithreading supporting
malloc/free. I absolutely guarantee that every single one of them
uses some kind of platform specific exclusion object to make sure that
two simultaneous calls to the heap do not collide.


Sure. Mutexes would suffice and I contend the bakery algorithm can
provide them. 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.
One way or another the heap is some kind of quasi-linked list of
memory entries. You should have learned from your OS classes
(assuming you passed it and/or comprehended the material)


Could you refrain from the silly ad hominems? I am trying to take you
seriously, even though you seem to deny the importance of standards,
and even though you are advocating an (in my opinion) confused
"operator introduction" feature. Maintaining a basic level of
respect helps in any discussion.

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!" :-)
How does your example invalidate the "upper bound" idea? 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?
If no way can be found to address this, we can no longer give an upper
bound, and the proposal is dead in the water. However, I'm not conviced
it can't be handled. 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.
The alloca() calls can be in a loop. Knowing how much memory a set of
alloca's will perform in any function is equivalent to solving the
halting problem.


So what? Why is this relevant? Most of the time you can still give an
upper bound.

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? :-)
This versus just living with runtime stack checking? I'll take the
runtime stack checking.


Then define a proposal to formalize "runtime stack checking" in
standard-like language. 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... :-)
There is a possibility of error caused by bad design (which isn't
trimmed to the type of mistakes we fallible humans make) in your
operator introduction scheme.

Same is true with free form function names, of course.


The risks of errors are minute, in comparison. 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_p oll 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! :-)
I listed some specific objections with regards to disambiguation of
the grammer that the parser would have to be able to handle.

Even without a full grammar being specified? That's a pretty good trick.


Yes, it's called "abstract thinking". It's a cousin of "thought
experiment" . 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.
>OF is never the important flag. Its not relevant at all.

I guess that's why everything since the 4004 supports it.

That's because OF is used for <,>,<=,>= comparisons. Outside of
this, I have never seen OF being used for any purpose. I.e., I would
surmise that the only relevant usage of OF is already encoded in the
language semantics of C (and just about any other language with
integers.) But I could be wrong -- can you name at least one other
purpose which isn't really just an encoding of <,>,<=,>= ?


Adding, subtracting, multiplying, dividing. Basically anything
arithmetic you can do that can map the result of an operation on signed
ints to a value that doesn't correspond to the mathematical
interpretatio n of what the result should be. 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);
}
So again (as with the carry vs. overflow), you're going to perform an
instructi on that works on UNsigned integers even on signed integers.

Yes.


That doesn't rhyme well with C.


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
architectur e 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.
Are you aware that the C standard allows for other representations
than 2-complement? Assume 1-complement representation for a moment
(the standard is specifically worded to allow this).

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 "intellectu al 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).
Having signed and non-signed versions of every operator may be
something that fit C when it was first designed, but that doesn't
make it necessarily correct for all relevant computations.


Well, if (and that's a big if) something resembling your wide-mul
would ever make it in the standard, I'd be disappointed if it didn't
for instance allow me to multiply two big signed integers. It would
be messy to only support unsigned ones.

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

Nov 14 '05 #157
On 5 Dec 2003 04:06:19 -0800, qe*@pobox.com (Paul Hsieh) wrote:
Sidney Cadot <si****@jigsaw. nl> wrote:

<snip>
[...] 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.ne t
Nov 14 '05 #158

On Fri, 12 Dec 2003, Sidney Cadot wrote:

Paul Hsieh wrote:
[Sidney Cadot wrote:]
>Why do you need to distinguish process instances?

Reread the Lamport's bakery algorithm. One of the crucial steps is
"for each process, check their number, and pick the max, then add
1". Another is "for each process that has a lower number, wait in
line behind them." This means you have a way of knowing how many
processes there are, and how to index them. This means you have
to hook out or wrap whatever "spawn" mechanism you have in your
language (or use some other platform specific mechanism to iterate
through all running threads.)

Could you provide a reference to the description of the algorithm
you're using?
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...ex/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.

Yes, but if two threads simultaneously call heap functions on the same
heap (heaps are not restricted to being distinct across threads) then
there is a race condition.

So we need to put a mutex around the critical section, no big deal.
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
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] 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.


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.programmin g (IIRC) quite a lot before.

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? :-)


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.programmin g 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.
<gigantic snip> 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
Nov 14 '05 #159
In article <br**********@n ews.tudelft.nl> , si****@jigsaw.n l says...
Paul Hsieh wrote:
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.
You really seem a bit out of touch with current events... Since you
don't seem to have access to the C99 standard, here's the relevant
quote:
Excuse me?!?! *C99* is not portable.


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 incompatibiliti es 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".
>Why do you need to distinguish process instances?

Reread the Lamport's bakery algorithm. One of the crucial steps is
"for each process, check their number, and pick the max, then add
1". Another is "for each process that has a lower number, wait in
line behind them." This means you have a way of knowing how many
processes there are, and how to index them. This means you have
to hook out or wrap whatever "spawn" mechanism you have in your
language (or use some other platform specific mechanism to iterate
through all running threads.)

Could you provide a reference to the description of the algorithm
you're using?


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?


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
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.
> Yes, but if two threads simultaneously call heap functions on the same
> heap (heaps are not restricted to being distinct across threads) then
> there is a race condition.

So we need to put a mutex around the critical section, no big deal.
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.


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.
Go look up the source code for *ANY* multithreading supporting
malloc/free. I absolutely guarantee that every single one of them
uses some kind of platform specific exclusion object to make sure that
two simultaneous calls to the heap do not collide.

Sure. Mutexes would suffice and I contend the bakery algorithm can
provide them.
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, ...


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


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


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


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


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


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 ...
How does your example invalidate the "upper bound" idea?
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.


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


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


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.
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? :-)


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".
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 *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.
>There is a possibility of error caused by bad design (which isn't
>trimmed to the type of mistakes we fallible humans make) in your
>operator introduction scheme.

Same is true with free form function names, of course.

The risks of errors are minute, in comparison.
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


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_p oll 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)?
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);


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.
>So again (as with the carry vs. overflow), you're going to perform an
>instructi on that works on UNsigned integers even on signed integers.

Yes.

That doesn't rhyme well with C.


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.


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


Because the standard has nothing to offer me?
Are you aware that the C standard allows for other representations
than 2-complement? Assume 1-complement representation for a moment
(the standard is specifically worded to allow this).


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 "intellectu al 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(hig h(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.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Nov 14 '05 #160

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
3456
by: Anthony Martin | last post by:
I've been reading the Java Language Specification, and in Chapter 16 there's an interesting topic called Definite Assignment. http://tinyurl.com/3fqk8 I'm wondering about the idea of "Deferred Final Automatic Variables" like the following: void unflow(boolean flag) { final int k;
14
23153
by: Medi Montaseri | last post by:
Hi, I think my problem is indeed "how to implement something like java's final in C++" The long version.... I have an abstract base class which is inherited by several concrete classes. I have a group of methods that I'd like to implement in the base class
48
8734
by: David J Patrick | last post by:
I'm trying to rewrite the CSS used in http://s92415866.onlinehome.us/files/ScreenplayCSSv2.html. using the w3.org paged media standards as described at http://www.w3.org/TR/REC-CSS2/page.html The ScreenplayCSS is flawed, for several reasons; -overuse of <div id= tags -doesn't scale screen resolutions (convert from px to in, pt ?) -no media="print" (how much coule be shared between "screen" & "print") -no automatic page breaks (with...
10
5126
by: Bezalel Bareli | last post by:
I know I have seen some threads on the subject long time ago and it was using a virtual base class ... in short, what is the nicest way to implement the Java final class in c++ Thanks.
14
1780
by: My4thPersonality | last post by:
Has the fact that both Java and C# are garbage collected, and C++ in not, anything to do with the fact that there is no language item to prevent a class from being inherired from? I once read that Java and C# implement this feature for preformance, but the C++ creators said it was not worse the effort. So because Java and C# are garbage collected, in their case is it worse the effort? What is the connection?
1
8625
by: silverburgh.meryl | last post by:
I am trying to convert this code from java to c++: public final class Type { public static final int DEFAULT = 1; private static int index = 2; public static final int COLUMN1 = (int) Math.pow(2, index++); public static final int COLUMN2 = (int) Math.pow(2, index++); public static final int COLUMN3 = (int) Math.pow(2, index++); public static final int COLUMN4 = (int) Math.pow(2, index++);
5
1403
by: Anthony Baxter | last post by:
On behalf of the Python development team and the Python community, I'm happy to announce the release of Python 2.4.3 (final). Python 2.4.3 is a bug-fix release. See the release notes at the website (also available as Misc/NEWS in the source distribution) for details of the more than 50 bugs squished in this release, including a number found by the Coverity Scan project. Assuming no major bugs pop up, the next release of Python will be...
14
3004
by: Rahul | last post by:
Hi Everyone, I was searching for final class in c++, and i came across few links which suggests to have the constructor of the, to be final class, as private so that any derived class's constructors can't access the same. class C { private:
1
1710
by: Rajib | last post by:
Not that this serves any real purpose, but gcc allows me to do some hack like this: class hide_A { public: class A { public: virtual int final() { return 42; } };
0
9810
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10794
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10896
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10443
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
8000
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6031
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4652
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4251
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3259
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.