469,366 Members | 2,236 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,366 developers. It's quick & easy.

Malcolm's new book

The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental algorithms
used in practical programming, with a bias towards graphics. It includes
mathematical routines from the basics up, including floating point
arithmetic, compression techniques, including the GIF and JPEG file formats,
hashing, red black trees, 3D and 3D graphics, colour spaces, machine
learning with neural networks, hidden Markov models, and fuzzy logic,
clustering, fast memory allocators, and expression parsing.

(Follow the links)

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Jul 24 '07
263 7974
"Malcolm McLean" <re*******@btinternet.comwrites:
"Ben Bacarisse" <be********@bsb.me.ukwrote in message
news:87************@bsb.me.uk...
<big snip>
>Your hash table can fill up (I don't see that even commented on, but I
may have missed it) and the add function will then just loop forever.
If the table is full, both the lookup and delete functions will loop
indefinitely.
Again, the objective is not to provide correct implementations that
will be robust to every input. The problem is that it raises the
question of what to do on errors- there are answers, of course, but
the error code tends to obscure the algorithm.
I taught for a long time, so I know how tricky the balance can be, but
your hash_add function *already* handles errors -- on malloc failure.
If you added just one test to prevent the last entry being used and
returned -1 in this case too, then the algorithms would be correct.

You can't be saying that adding that one if would take the example
over the edge into incomprehensibility, and to my mind there is world
of benefit in showing correct code.
That is the case for
the queue. It is easy enough to maintain a counter, slightly more
tricky to calculate the queue length from the head and tail indices,
but the intention was to get across the idea of a circular buffer.
By not dealing with either a full or an empty queue you leave nothing.
It is not a queue. A buffer is only a queue if there are times when
you can't take anything out. Without that case (at least) it is just
an array of indeterminate values that can be accessed willy-nilly.

You say it is "easy enough" -- of course it is. That is why I see no
possible explanation for leaving out these crucial bits. I don't
think that this:

#define Q_SIZE 100

int queue[Q_SIZE];
int head = 0;
int tail = 0;

int empty(void)
{
return head == tail;
}

int add(int item)
{
int new_tail = tail + 1;
if (new_tail == Q_SIZE)
new_tail = 0;
if (new_tail == head)
return 0; /* queue is full */
queue[tail] = item;
tail = new_tail;
return 1;
}

int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.
In the case of a hash table, the algorithm breaks down when the table
gets more than about half full in any case.
But one test, a single if, and the code would be correct. Instead it
is possible for the add, get and del functions to loop indefinitely.
I don't think that is the kind of cost/benefit example you want to give.
Now Iam not committed to saying that my judgement is in every case
correct. In the case of the queue maybe there is case for expanding
the discussion. But then you fail to communicate the essential
simplicity of the idea.
More generally, look at the atan2() function I copied from Sun to see
the difference between real code and tutorial code. I am sure that
that fucntion is fast, accurate, and numerically stable, but how
useful is it as a teaching example?
You like to attack extreme positions that no one holds! No one would
suggest that Sun's atan2() is a good introductory example. Winning
an argument is easy if you can take both sides!

I don't think tutorial code should ever be buggy. I have never found
myself having to leave an error in a teaching example because
correcting it would make the example too complex.

--
Ben.
Jul 29 '07 #51
Ben Bacarisse said:

<snip>
int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.
It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.

<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Jul 29 '07 #52
Richard Heathfield <rj*@see.sig.invalidwrites:
Ben Bacarisse said:

<snip>
>int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.

It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.

<snip>
Why would that "baffle" anyone?

Many people include it as part of a standard template.

It might not be "perfect" to include it when not necessary but it's
frequently done and not breaking any rules that I am aware of.

You know, living in the real world and all.
Jul 29 '07 #53
Richard said:
Richard Heathfield <rj*@see.sig.invalidwrites:
>Ben Bacarisse said:

<snip>
>>int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.

It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.

<snip>

Why would that "baffle" anyone?
Think.

Re-read, especially the quoted code and the last sentence of my previous
reply.

Iterate until comprehension dawns.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Jul 29 '07 #54
Richard wrote:
Richard Heathfield <rj*@see.sig.invalidwrites:
>Ben Bacarisse said:

<snip>
>>int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.
It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.

<snip>

Why would that "baffle" anyone?

Many people include it as part of a standard template.

It might not be "perfect" to include it when not necessary but it's
frequently done and not breaking any rules that I am aware of.

You know, living in the real world and all.
Let's try a name change (and header change) to see
if things become clearer: What would have happened if he
had named his function `free'? Explain what happens when
the program using the queue writes

int item;
free (&item);

.... in an attempt to retrieve the next item from the queue.
(In the real world, of course.)

--
Eric Sosman
es*****@ieee-dot-org.invalid
Jul 29 '07 #55
Eric Sosman <es*****@ieee-dot-org.invalidwrites:
Richard wrote:
>Richard Heathfield <rj*@see.sig.invalidwrites:
>>Ben Bacarisse said:

<snip>

int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.
It will baffle him even more if he includes <stdio.hin his
program. The remove() function is a standard C library function.

<snip>

Why would that "baffle" anyone?

Many people include it as part of a standard template.

It might not be "perfect" to include it when not necessary but it's
frequently done and not breaking any rules that I am aware of.

You know, living in the real world and all.

Let's try a name change (and header change) to see
if things become clearer: What would have happened if he
had named his function `free'? Explain what happens when
the program using the queue writes

int item;
free (&item);

... in an attempt to retrieve the next item from the queue.
(In the real world, of course.)
Yes. I missed that. Personally I would have said

"Your remove() function is a member of the standard library and so it
would be advisable to choose another name".

--
Jul 29 '07 #56
Richard Heathfield <rj*@see.sig.invalidwrites:
Ben Bacarisse said:

<snip>
>int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.

It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.
Catch! I did not even *see* the names the OP had used.

--
Ben.
Jul 29 '07 #57
On Sun, 29 Jul 2007 14:29:30 +0200, Richard wrote:
Richard Heathfield <rj*@see.sig.invalidwrites:
>Ben Bacarisse said:

<snip>
>>int remove(int *item)
{
if (empty())
return 0;
*item = queue[head];
if (++head == Q_SIZE)
head = 0;
return 1;
}

is so complicated it obscures the basic idea. I think your example
will just baffle the learner.

It will baffle him even more if he includes <stdio.hin his program.
The remove() function is a standard C library function.

<snip>

Why would that "baffle" anyone?
gcc test.c
test.c:7: error: conflicting types for ‘remove’
/usr/include/stdio.h:152: error: previous declaration of ‘remove’ was here

Clear enough?
Jul 29 '07 #58
[snips]

On Thu, 26 Jul 2007 22:19:04 +0100, Malcolm McLean wrote:
Most posters have been negative, but mainly it's been trivia - a few typing
errors, one actual buggy line. They somethimes invest huge significance in
this - "why write a book for which you are not qualified". In fact it would
be a miracle if not a single error crept into a 600 page book.
True but irrelevant. The book doesn't contain the occasional error; it
contains consistent, repeated failures to grasp basic concepts, then uses
those failures to build code.

The most obvious examples are using int where size_t (or, at the *very*
least, unsigned) would be proper, and assuming ints have 32 or more bits.
Jul 29 '07 #59

"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:vd************@spanky.localhost.net...
[snips]

On Thu, 26 Jul 2007 22:19:04 +0100, Malcolm McLean wrote:
>Most posters have been negative, but mainly it's been trivia - a few
typing
errors, one actual buggy line. They somethimes invest huge significance
in
this - "why write a book for which you are not qualified". In fact it
would
be a miracle if not a single error crept into a 600 page book.

True but irrelevant. The book doesn't contain the occasional error; it
contains consistent, repeated failures to grasp basic concepts, then uses
those failures to build code.

The most obvious examples are using int where size_t (or, at the *very*
least, unsigned) would be proper, and assuming ints have 32 or more bits.
That was a writing decision.
unsigned integers have certain problems that can make algorithms with them
more difficult. For that reason they were excluded from Java. There is of
course some dispute about this, because ANSI mandates a size_t to hold
amounts of memory.
The other problem is that once you admit one size_t it poisons everything it
touches. So I decided not to use size_t at all, except once in the
introduction.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Jul 29 '07 #60
Malcolm McLean wrote:
>
"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:vd************@spanky.localhost.net...
The book doesn't contain the occasional error; it
contains consistent, repeated failures to grasp basic concepts,
then uses those failures to build code.
The other problem is that once you admit one size_t
it poisons everything it touches.
size_t isn't hard to use.

It really seems like a failure to grasp a basic concept,
then using that failure to build code.

--
pete
Jul 29 '07 #61
Malcolm McLean said:
>
"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:vd************@spanky.localhost.net...
>[snips]

The book doesn't contain the occasional error;
it contains consistent, repeated failures to grasp basic concepts,
then uses those failures to build code.

The most obvious examples are using int where size_t (or, at the
*very* least, unsigned) would be proper, and assuming ints have 32 or
more bits.
That was a writing decision.
Then it was a poor one.
unsigned integers have certain problems that can make algorithms with
them more difficult.
So do signed integers - for example, their behaviour on overflow. So if
you can't use signed and you can't use unsigned, what does that leave?
For that reason they were excluded from Java.
I have no comment on Java. They were not excluded from C.
There is of course some dispute about this, because ANSI mandates a
size_t to hold amounts of memory.
The only dispute is in your head. I've never heard anyone else, ever,
arguing that unsigned integer types are a bad thing.
The other problem is that once you admit one size_t it poisons
everything it touches.
No, the trick is to know when to use them and why to use them. Use the
right type for everything, and it all tends to come out in the wash.

For example, consider graphics. A frame buffer has a non-negative number
of rows (each representing a row of pixels) and a non-negative number
of columns (each representing a column of pixels). Since offsets into a
frame buffer represent row and column counts, it makes sense to use an
unsigned type.

On the other hand, sometimes you want to construct a world in which
negative co-ordinates make sense (e.g. a graph of tan theta). Since the
world needs negative co-ordinates, you need a signed type.

The frame buffer need *not* pollute the world, nor the world the frame
buffer. One simply determines that they represent different concepts,
and one then provides a mapping between them that doesn't violate the
integrity of either. Rendering a world view within the frame buffer
must involve mapping those negative values to non-negative values at
some point, so there is no real problem here at all. It's perfectly
okay to assign an int value to a size_t, you know.
So I decided not to use size_t at all, except once in the
introduction.
That decision was a mistake.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Jul 29 '07 #62

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:Ia******************************@bt.com...
Malcolm McLean said:
>>
"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:vd************@spanky.localhost.net...
>>[snips]

The book doesn't contain the occasional error;
it contains consistent, repeated failures to grasp basic concepts,
then uses those failures to build code.

The most obvious examples are using int where size_t (or, at the
*very* least, unsigned) would be proper, and assuming ints have 32 or
more bits.
That was a writing decision.

Then it was a poor one.
>unsigned integers have certain problems that can make algorithms with
them more difficult.

So do signed integers - for example, their behaviour on overflow. So if
you can't use signed and you can't use unsigned, what does that leave?
>For that reason they were excluded from Java.

I have no comment on Java. They were not excluded from C.
>There is of course some dispute about this, because ANSI mandates a
size_t to hold amounts of memory.

The only dispute is in your head. I've never heard anyone else, ever,
arguing that unsigned integer types are a bad thing.
They were excluded from Java.

Gosling: For me as a language designer, which I don't really count myself as
these days, what "simple" really ended up meaning was could I expect J.
Random Developer to hold the spec in his head. That definition says that,
for instance, Java isn't -- and in fact a lot of these languages end up with
a lot of corner cases, things that nobody really understands. Quiz any C
developer about unsigned, and pretty soon you discover that almost no C
developers actually understand what goes on with unsigned, what unsigned
arithmetic is. Things like that made C complex. The language part of Java
is, I think, pretty simple. The libraries you have to look up.

(Gosling was the designer of Java).
http://www.gotw.ca/publications/c_family_interview.htm

(I am not saying I absolutely agree with him. It's just a complexity we can
usually do without. Very rarely do you need that exta bit.)

Jul 29 '07 #63
Malcolm McLean wrote:
>
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:Ia******************************@bt.com...
>Malcolm McLean said:
>>>
"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:vd************@spanky.localhost.net...
[snips]

The book doesn't contain the occasional error;
it contains consistent, repeated failures to grasp basic concepts,
then uses those failures to build code.

The most obvious examples are using int where size_t (or, at the
*very* least, unsigned) would be proper, and assuming ints have 32 or
more bits.

That was a writing decision.

Then it was a poor one.
>>unsigned integers have certain problems that can make algorithms with
them more difficult.

So do signed integers - for example, their behaviour on overflow. So if
you can't use signed and you can't use unsigned, what does that leave?
>>For that reason they were excluded from Java.

I have no comment on Java. They were not excluded from C.
>>There is of course some dispute about this, because ANSI mandates a
size_t to hold amounts of memory.

The only dispute is in your head. I've never heard anyone else, ever,
arguing that unsigned integer types are a bad thing.
They were excluded from Java.
<snip quote from Gosling>
(I am not saying I absolutely agree with him. It's just a complexity we
can usually do without. Very rarely do you need that exta bit.)
I sometimes find the modulo 2^n arithmetic of unsigned integers useful. In
many programming areas, you only need to consider positive values and zero.
In such cases using a signed type is not optimal.

Jul 29 '07 #64
Richard Heathfield <rj*@see.sig.invalidwrites:
Malcolm McLean said:

>There is of course some dispute about this, because ANSI mandates a
size_t to hold amounts of memory.

The only dispute is in your head. I've never heard anyone else, ever,
arguing that unsigned integer types are a bad thing.
I would say at at least 90% of the time I use "ints" is using unsigned
ones. Especially when one takes into account Malcolm's previous claims
that ints are usually used to access memory - not much call for signed
offsets there. So, agreed.
Jul 29 '07 #65
Malcolm McLean wrote:
[...]
The other problem is that once you admit one size_t it poisons
everything it touches. [...]
Aw, fer cryin' out loud-- It's been only a week or so
since we had our latest extended and unpleasant ride on this
hobby horse of yours; can't you give us a respite of at least
a month between rockings? Let the "decent interval" elapse,
I beg.

Sheesh!

--
Eric Sosman
es*****@ieee-dot-org.invalid
Jul 29 '07 #66

"Eric Sosman" <es*****@ieee-dot-org.invalidwrote in message
news:Ja******************************@comcast.com. ..
Malcolm McLean wrote:
>[...]
The other problem is that once you admit one size_t it poisons everything
it touches. [...]

Aw, fer cryin' out loud-- It's been only a week or so
since we had our latest extended and unpleasant ride on this
hobby horse of yours; can't you give us a respite of at least
a month between rockings? Let the "decent interval" elapse,
I beg.

Sheesh!
The problem is that I have to write the code with either ints or size_t's.
Being an int should fit all man, I chose int.
This then leads to accusations of not having grasped the concept of size_t.
Of course it is pretty unlikely that someone would churn out 600 pages of C
code but lack the intellectual capacity to understand that size_t is the
ANSI recommended way of representing amounts of memory. I even discuss the
issue briefly in chapter 1. But I have to explain my reasons, whether you
accept them or not, rather than be thought ignorant of the existence of such
a type.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Jul 29 '07 #67
"Malcolm McLean" <re*******@btinternet.comwrites:
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:Ia******************************@bt.com...
>Malcolm McLean said:
[...]
>>unsigned integers have certain problems that can make algorithms with
them more difficult.

So do signed integers - for example, their behaviour on overflow. So if
you can't use signed and you can't use unsigned, what does that leave?
>>For that reason they were excluded from Java.

I have no comment on Java. They were not excluded from C.
>>There is of course some dispute about this, because ANSI mandates a
size_t to hold amounts of memory.

The only dispute is in your head. I've never heard anyone else, ever,
arguing that unsigned integer types are a bad thing.
They were excluded from Java.
[...]

So maybe you should write a book about Java.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Jul 29 '07 #68
Malcolm McLean said:

<snip>
The problem is that I have to write the code with either ints or
size_t's. Being an int should fit all man, I chose int.
Why not just use the right type for the right use? The int type clearly
does not fit all. You use chars and doubles and arrays and structs
where appropriate, yes? Well then, why not unsigned integer types when
appropriate too?
This then leads to accusations of not having grasped the concept of
size_t.
Alas, such accusations do seem to be justified. You don't seem to have
grasped the idea at all.
Of course it is pretty unlikely that someone would churn out
600 pages of C code but lack the intellectual capacity to understand
that size_t is the ANSI recommended way of representing amounts of
memory.
Schildt didn't have any trouble turning out large amounts of material,
ostensibly about C, without actually understanding the language.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Jul 29 '07 #69
Malcolm McLean wrote:
[...] Of course it is pretty unlikely that someone would churn out 600
pages of C code but lack the intellectual capacity to understand that
size_t is the ANSI recommended way of representing amounts of memory.
The few pages I read did not encourage me to read the rest
of the six hundred. Nor did they demonstrate overpowering
intellectual capacity; rather, they demonstrated slipshod
workmanship.

Seriously: If the code in your book (such of it as I had
stomach for) had been turned in by a student, I would have
given failing marks for the second square root function: code
that doesn't compile doesn't get good grades. Fix the two
obvious errors and it would still get a failing mark for not
implementing the specification (the one in the text immediately
following the code). Fix that third error, and it would get a
low pass: it works, but there are too many magic numbers and too
little thought.

When this shoddy code comes from a supposedly professional
programmer -- well, what am I to suppose? It seems unlikely that
you are actually so deluded that you thought the code was good,
so my guess is that you just didn't think about it at all. An
intellectual capacity that is not used just as effective as
none at all.

"Let us be thankful that we are persons of no capacity
whatever." -- Lord Tolloller

--
Eric Sosman
es*****@ieee-dot-org.invalid
Jul 29 '07 #70
On Sun, 29 Jul 2007 17:17:16 -0400, Eric Sosman wrote:
>Malcolm McLean wrote:
>[...]
The other problem is that once you admit one size_t it poisons
everything it touches. [...]
it is possible i wrong anhother time but there is something not return
me well in size_t (the same for const etc etc )
possibly because i'm not very smart and not understand well
Aw, fer cryin' out loud-- It's been only a week or so
since we had our latest extended and unpleasant ride on this
hobby horse of yours; can't you give us a respite of at least
a month between rockings? Let the "decent interval" elapse,
I beg.

Sheesh!

and so if you code overflow a size_t variable your programme what has
to do?

is there something that can catch this? (and so **slow down** all the
executable from a c source too)

i think it is better "int" than "size_t" because i can see if it is ok
in the begin of some function and write something like

char* malloc(int a)
{if(a<0) return 0;
etc
}

yes i know the standard say "size_t" and if another type it will break
all existing c code but this is summer time and i have to say
something

Jul 30 '07 #71
On Thu, 26 Jul 2007 22:19:04 +0100, Malcolm McLean wrote:
"Mark Bluemel" <ma**********@pobox.comwrote in message
news:f8**********@aioe.org...
>Malcolm McLean wrote:
>>The webpages for my new book are now up and running.
Given the amount of criticism raised so far, would you comment on how
the book was edited and reviewed.
Most posters have been negative, but mainly it's been trivia - a few
typing errors, one actual buggy line. They somethimes invest huge
significance in this - "why write a book for which you are not
qualified". In fact it would be a miracle if not a single error crept
into a 600 page book.

The brave new world of the internet disintermediates. That's why the
book costs sixteen pounds instead of the thirty to fifty you'd pay for
the same thing in a bookshop.
Methinks the low price is because this is a book that fills a
well-needed gap.

Jul 30 '07 #72
In article <f8**********@news6.zwoll1.ov.home.nl>,
Harald van =?UTF-8?B?RMSzaw==?= <tr*****@gmail.comwrote:
>Alternatively, I wouldn't necessarily object if getNemployees returned
unsigned long, and -1UL signifies an error, because it's not possible for a
company to have 0xFFFFFFFF or more employees.
a) 0xFFFFFFFF is less than the human population of the Earth.
b) employees are not necessarily human ;-)

--
Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson
Jul 30 '07 #73
In article <f8**********@registered.motzarella.org>,
santosh <sa*********@gmail.comwrote:
>Does any extant company have 0xFFFF employees?
http://en.wikipedia.org/wiki/Wal-Mart

"With 1.8 million employees worldwide [...]"
--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26)
Jul 30 '07 #74
santosh <sa*********@gmail.comwrites:
Does any extant company have 0xFFFF employees?
From http://www.ibm.com/ibm/us/en/:
Number of employees (worldwide): 355,766
--
"When I have to rely on inadequacy, I prefer it to be my own."
--Richard Heathfield
Jul 30 '07 #75
Harald van Dijk <tr*****@gmail.comwrites:
[...]
More to the point, I don't think I agree with your use of a positive value
to indicate an error in a function returning the number of employees. How
do you distinguish a company with UINT_MAX employees, from one of which the
number you cannot represent? If getNemployees returns an int, then it is
clear: either the number is negative, which is an obvious error result, or
it is non-negative, which signifies exactly the number of employees. It is
true that UINT_MAX employees also cannot be represented if the function
returns int, but at least in that case, the function unambiguously tells
you so.
You choose a type that's big enough that its maximum value exceeds any
reasonable number of employees, and you write the code so that it can
be easily changed if the assumption of what's "reasonable" changes.

Client code should never assume that the invalid value is UINT_MAX.
You provide a named constant that's specified to be an invalid value,
and probably a typedef for the type itself (which I initially didn't
bother to do):

typedef unsigned long employee_count_t;
const employee_count_t INVALID = -1;

(though (employee_count_t)-2 is also likely to be invalid).

Or you could use a signed type and treat actual negative values as
invalid (but the presence of multiple negative values must be dealt
with somehow).

Or you could use a structure type with a member that indicates whether
the value is valid.

And so forth.

Many solutions are possible, and all of them require some care to get
things right. But the need for a distinguished error value does not
by itself argue against using an unsigned type.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Jul 30 '07 #76
Keith Thompson said:

<snip>
You choose a type that's big enough that its maximum value exceeds any
reasonable number of employees, and you write the code so that it can
be easily changed if the assumption of what's "reasonable" changes.
Or you just take a pointer to the object that is to receive the value,
and return 0 if all was well and the object was correctly populated, or
some non-zero value if something went awry.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Jul 30 '07 #77
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
In article <f8**********@registered.motzarella.org>,
santosh <sa*********@gmail.comwrote:
Does any extant company have 0xFFFF employees?

http://en.wikipedia.org/wiki/Wal-Mart

"With 1.8 million employees worldwide [...]"
Day-waged villeins don't count.

Richard
Jul 31 '07 #78
In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:
>typedef struct error_size {
unsigned int error : 1;
unsigned int value : sizeof(size_t) * CHAR_BIT - 1;
} Maybe_size;
Your use of size_t there is not compatible with your use
of unsigned int. It would make more sense with size_t
replaced by unsigned int .
--
Programming is what happens while you're busy making other plans.
Jul 31 '07 #79
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:
In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:
>>typedef struct error_size {
unsigned int error : 1;
unsigned int value : sizeof(size_t) * CHAR_BIT - 1;
} Maybe_size;

Your use of size_t there is not compatible with your use
of unsigned int. It would make more sense with size_t
replaced by unsigned int .
Good point. I should not have posted an edited version! The example
it was taken from just had an error flag and a size_t member. I was
preparing for the "but you waste so much space" reply and did not
think it through. The type, from whose (bit) size one is subtracted
should be unsigned int -- or the value filed should be a plain size_t
and hang the space.

--
Ben.
Jul 31 '07 #80
In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:
>ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:
>In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:
>>>typedef struct error_size {
unsigned int error : 1;
unsigned int value : sizeof(size_t) * CHAR_BIT - 1;
} Maybe_size;
>Your use of size_t there is not compatible with your use
of unsigned int. It would make more sense with size_t
replaced by unsigned int .
>Good point. I should not have posted an edited version! The example
it was taken from just had an error flag and a size_t member. I was
preparing for the "but you waste so much space" reply and did not
think it through. The type, from whose (bit) size one is subtracted
should be unsigned int -- or the value filed should be a plain size_t
and hang the space.
I'm left a little uncertain about what you mean by "a plain size_t".

C89 does not clearly define a minimal maximum bitfield size; it
says that the maximum size is implementation dependant, but does not
make clear what the minimum size is. From some of the C89 examples,
we can deduce that the intention is that a bitfield at least as wide as
an int should supported, but the text doesn't really say.

So.... if what you had meant was something like,

typedef struct error_size {
unsigned int error : 1;
size_t value;
} Maybe_size;

then no problem (and heck, the implementation might even manage to
use less than a full int's width for error). But if you meant,

typedef struct error_size {
unsigned int error : 1;
size_t value : sizeof(size_t) * CHAR_BIT - 1;
} Maybe_size;

then you can't be sure that a bitfield that wide is supported.
Well, that and the fact that C doesn't define size_t as being one
of the types that the implementation is required to support
for bitfielding (which is pretty nearly the same concern but with
a different emphasis.)
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
Jul 31 '07 #81
On Mon, 30 Jul 2007 18:17:00 +0200, "a\\/b" <al@f.gwrote:
>On Sun, 29 Jul 2007 17:17:16 -0400, Eric Sosman wrote:
>>Malcolm McLean wrote:
>>[...]
The other problem is that once you admit one size_t it poisons
everything it touches. [...]

it is possible i wrong anhother time but there is something not return
me well in size_t (the same for const etc etc )
possibly because i'm not very smart and not understand well
> Aw, fer cryin' out loud-- It's been only a week or so
since we had our latest extended and unpleasant ride on this
hobby horse of yours; can't you give us a respite of at least
a month between rockings? Let the "decent interval" elapse,
I beg.

Sheesh!


and so if you code overflow a size_t variable your programme what has
to do?

is there something that can catch this? (and so **slow down** all the
executable from a c source too)

i think it is better "int" than "size_t" because i can see if it is ok
in the begin of some function and write something like
better too a unsigned type that detect overflow
but for all you this not seems to be important
>char* malloc(int a)
{if(a<0) return 0;
etc
}

yes i know the standard say "size_t" and if another type it will break
all existing c code but this is summer time and i have to say
something
Aug 1 '07 #82
Eric Sosman <Er*********@sun.comwrote:
Malcolm McLean wrote On 07/26/07 17:19,:
Most posters have been negative, but mainly it's been trivia - a few typing
errors, one actual buggy line. They somethimes invest huge significance in
this - "why write a book for which you are not qualified". In fact it would
be a miracle if not a single error crept into a 600 page book.

That would, indeed, be miraculous. On the other hand,
the "run rate" of three obvious errors in one eleven-line
function suggests that we may be about to witness a different
miracle: a book thinner than its own errata.
It's happened before, most notably to certain theological and political
authors in the late Middle Ages when a. printing and particularly
proofreading were not yet established professions and b. certain
misprints, when taken for the author's actual opinions, could lead to
severe and sometimes decapitative problems.

Richard
Aug 2 '07 #83
[snips]

On Sun, 29 Jul 2007 22:36:39 +0100, Malcolm McLean wrote:
The problem is that I have to write the code with either ints or size_t's.
Being an int should fit all man, I chose int.
Bad choice.

int get_buff_len( buffer_t buff )

Quick: what happens if the length of the buffer is INT_MAX? Hmm...
could be held in a size_t, which can handle the size of the largest
allowable object, but pukes on int.

Yeah, well. int.
This then leads to accusations of not having grasped the concept of
size_t.
Obviously, you haven't.
Of course it is pretty unlikely that someone would churn out 600
pages of C code but lack the intellectual capacity to understand that
size_t is the ANSI recommended way of representing amounts of memory.
Yet you get it wrong consistently.
I
even discuss the issue briefly in chapter 1.
Then you should know better.
But I have to explain my
reasons, whether you accept them or not, rather than be thought ignorant
of the existence of such a type.
If you know it, you should use it. Since there is *no* possible
justification for using int in such cases, as sizes are never negative and
can overflow the range of an int, you simply cannot use int reliably in
such cases - which is *exactly* why size_t exists in the first place.

Since you don't use size_t, one must conclude you're unaware of what it
is, what it's for and why it exists. If you *did* know, you'd have used
it, instead of int.
Aug 2 '07 #84

"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:qr************@spanky.localhost.net...
[snips]

On Sun, 29 Jul 2007 22:36:39 +0100, Malcolm McLean wrote:
>The problem is that I have to write the code with either ints or
size_t's.
Being an int should fit all man, I chose int.

Bad choice.

int get_buff_len( buffer_t buff )

Quick: what happens if the length of the buffer is INT_MAX? Hmm...
could be held in a size_t, which can handle the size of the largest
allowable object, but pukes on int.

Yeah, well. int.
In a 32-bit environment that is most unlikely. In a 64-bit environment,
well, that's a different story.
>
>This then leads to accusations of not having grasped the concept of
size_t.

Obviously, you haven't.
There is a difference between not understanding and disagreeing.
>
>Of course it is pretty unlikely that someone would churn out 600
pages of C code but lack the intellectual capacity to understand that
size_t is the ANSI recommended way of representing amounts of
memory.

Yet you get it wrong consistently.
I explain in the opening paragraphs why size_ts will not pollute my C code.
You don't disagree with this reasoning, you either haven't read it or fail
to engage with it.
(Needless to say I wouldn't say it is beyond dispute. Some pretty
intelligent people disgree with me.)
>I
even discuss the issue briefly in chapter 1.

Then you should know better.
>But I have to explain my
reasons, whether you accept them or not, rather than be thought ignorant
of the existence of such a type.

If you know it, you should use it. Since there is *no* possible
justification for using int in such cases, as sizes are never negative and
can overflow the range of an int, you simply cannot use int reliably in
such cases - which is *exactly* why size_t exists in the first place.
Intermediate size or index calculations can easily be negative.
>
Since you don't use size_t, one must conclude you're unaware of what it
is, what it's for and why it exists. If you *did* know, you'd have used
it, instead of int.
One problem with algorithm books is that they are written to the latest
fashion in languages. It might be Fortran, or C, or C++, or Java. I expect
my book to be still useful in a hundred years time. I'll be dead by then,
but the fundamental algorithms that make computers work won't have changed.
However languages change. I can't imagine C without int, but size_t could
well be obsolete by then. I can't see a language that insists on a type
called "size_t" as a general-purpose index lasting for long. Programmers
simply won't accept it. But I don't think it will take down C.
People do disagree on what should go in textbooks.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Aug 2 '07 #85
[snips]

On Thu, 02 Aug 2007 20:03:59 +0100, Malcolm McLean wrote:
>int get_buff_len( buffer_t buff )

Quick: what happens if the length of the buffer is INT_MAX? Hmm...
could be held in a size_t, which can handle the size of the largest
allowable object, but pukes on int.

Yeah, well. int.
In a 32-bit environment that is most unlikely. In a 64-bit environment,
well, that's a different story.
In a 16-bit environment, entirely possible.
I explain in the opening paragraphs why size_ts will not pollute my C
code
Because they exist for a reason, they do a job ints don't do, they do it
properly, in cases where ints simply are the *wrong* type - and thus you
choose int.

As I said, a complete failure to grasp basic concepts.
>. You don't disagree with this reasoning, you either haven't read it
or fail to engage with it.
I will, of course, disagree with any argument which leads to provably
wrong results, such as concluding int is the appropriate type for size
arguments where size_t is the correct choice.
>If you know it, you should use it. Since there is *no* possible
justification for using int in such cases, as sizes are never negative
and can overflow the range of an int, you simply cannot use int
reliably in such cases - which is *exactly* why size_t exists in the
first place.
Intermediate size or index calculations can easily be negative.
In which case, use ints for those, if applicable. Using them to pass or
return the size of a buffer is simply wrong, as a buffer will never have a
negative size, but can have a size larger than the range of an int, making
int the wrong type to use.
One problem with algorithm books is that they are written to the latest
fashion in languages. It might be Fortran, or C, or C++, or Java. I
expect my book to be still useful in a hundred years time.
I haven't read the whole thing, but the example chapters say it's not
particularly useful *now*, since it contains your fundamental inability to
grasp basic concepts and thus persistently does the Wrong Thing. Well,
okay, it might be useful as kindling, but it is bad enough, based just on
those examples shown, that it should never be allowed anywhere near a
programmer's hands, for fear it will taint them with the same illogic and
poor designs you employ in it.
by then, but the fundamental algorithms that make computers work won't
have changed. However languages change. I can't imagine C without int,
but size_t could well be obsolete by then.
Why would size_t be obsolete, since it does a job int does not do?
I can't see a language that
insists on a type called "size_t" as a general-purpose index lasting for
long.
So? It exists now, it has reasons for existing now, and you are ignoring
them and as a result producing bad, broken, amateurish code.
Aug 2 '07 #86
Malcolm McLean wrote:
>
[...] I
expect my book to be still useful in a hundred years time. [...]
"I wouldn't touch a straight line like that for a free
weekend at Pismo Beach." -- Johnny Hart

--
Eric Sosman
es*****@ieee-dot-org.invalid
Aug 3 '07 #87

"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:aa************@spanky.localhost.net...
[snips]

Why would size_t be obsolete, since it does a job int does not do?

So? It exists now, it has reasons for existing now, and you are ignoring
them and as a result producing bad, broken, amateurish code.
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than the
range of an int. Of course such buffers should seldom arise, if you obey the
convention that int is the "natural" integer size of the machine.

If we allow that any array can overflow the size of an int we get the
folowing

void payroll(struct Employee *emplloyees, size_t N)
{
size_t i;

for(i=0;i<N;i++)
/* so something */
}

Now N is arguably a size, though it is a slightly confusing term. However
the type of i is downright misleading. It does not hold a size at all. In
fact this won't be acceptable, and something will be done. Either size_t
will have to be deprecated / quietly dropped, or C itself will be regarded
as an "advanced" language unsuitable for beginners, and gradually be
squeezed out.
I'm hoping for 1.
size_t is a kludge, and code is clearer without it. It has no place in my
book, except in the introduction where I explain the conventions used, and
why the code is written as it is - to show algorithm, not to be robust to
extreme inputs as you would get in production code. Hence the memory
allocation codes take int because the algorithms operate on integers.

If you disagree with this choice, I include an example of "real" code, an
atan2 routine form Sun, so that the reader has some exposure to what
production code can look like.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Aug 3 '07 #88
Malcolm McLean wrote, On 03/08/07 07:18:
>
"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:aa************@spanky.localhost.net...
>[snips]

Why would size_t be obsolete, since it does a job int does not do?

So? It exists now, it has reasons for existing now, and you are ignoring
them and as a result producing bad, broken, amateurish code.
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than
It was part of the original C standard, so if you take the earliest year
for the start of C, 1969, and the latest time for size_t entering the
language, 1989, it has been part of the language for almost half of its
history. If you are more sensible and for the start take 1972 which was
"the most creative period" then size_t has been part of the language for
over half the time it has existed. I would not call that relatively new.
the range of an int. Of course such buffers should seldom arise, if you
obey the convention that int is the "natural" integer size of the machine.
Many processors have many different "natural sizes". In any case, Intel
themselves specified that for the IA64 processors int should be 32 bits.
I've posted the URL for that before and you either ignored or did not
see that argument. You have also either ignored or not seen the links
posted for the Unix group choosing 32 bit int. I find it *very* hard to
believe you have not seen any of the links to respected groups, so I
suspect you are deliberately ignoring the evidence because it does not
fit your prejudices.
If we allow that any array can overflow the size of an int we get the
folowing

void payroll(struct Employee *emplloyees, size_t N)
{
size_t i;

for(i=0;i<N;i++)
/* so something */
}

Now N is arguably a size, though it is a slightly confusing term.
No one other than you here seems to find it confusing.
However the type of i is downright misleading. It does not hold a size
at all.
That is arguable at most. You don't use mm for the length of a line and
then some other measurement for how far along the line you are.
In fact this won't be acceptable, and something will be done.
Either size_t will have to be deprecated / quietly dropped,
It's almost 20 years on and it has not been dropped. Why do you ignore
the point that has been repeatedly made that it is NOT new to the language.
or C itself
will be regarded as an "advanced" language unsuitable for beginners, and
gradually be squeezed out.
Introducing abstractions early is a good thing, and size_t is an
abstraction.
I'm hoping for 1.
size_t is a kludge, and code is clearer without it.
That is a matter of opinion, not a matter of fact.
It has no place in
my book,
Then it is very arguable that C has no place in your book. I suggest
using a language you understand properly, such as the dialect of BASIC
you wrote.
except in the introduction where I explain the conventions
used, and why the code is written as it is - to show algorithm, not to
Some of your attempts to show algorithms have been pointed out by others
to have major flaws.
be robust to extreme inputs as you would get in production code. Hence
the memory allocation codes take int because the algorithms operate on
integers.
My opinion is that C is the wrong language for you because you disagree
with the design of it.
If you disagree with this choice, I include an example of "real" code,
an atan2 routine form Sun, so that the reader has some exposure to what
production code can look like.
What does an implementation of atan2 have to do with the usage of size_t?

In your previous post you also said
I can't see a language that insists on a type called "size_t" as a
general-purpose index lasting for long.
I'm not sure you can say that almost 20 years is not long, and it is at
least almost 20 years since size_t was added to the language.
Programmers simply won't accept
it.
This is clearly factually incorrect. Many programmers here accept and
even *embrace* it, namely all those here who have been saying you are
wrong. Even if the only programmers who accept it are the ones here who
have actively disagreed with you your statement is still incorrect, but
from the number of more strongly typed languages I think a significant
number of programmers *like* having types for specific purposes.
--
Flash Gordon
Aug 3 '07 #89
"Malcolm McLean" <re*******@btinternet.comwrites:
[...]
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than
the range of an int.
[...]

It's been in the language at least since 1989. C has had size_t
longer than it didn't have size_t.

Get real; you lost this argument years before you started it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 3 '07 #90
Flash Gordon <sp**@flash-gordon.me.ukwrote:
Malcolm McLean wrote, On 03/08/07 07:18:

"Kelsey Bjarnason" <kb********@gmail.comwrote in message
Why would size_t be obsolete, since it does a job int does not do?

So? It exists now, it has reasons for existing now, and you are ignoring
them and as a result producing bad, broken, amateurish code.
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than

It was part of the original C standard, so if you take the earliest year
for the start of C, 1969, and the latest time for size_t entering the
language, 1989,
1988. It's in K&R 2, which predates the published Standard by a year.
I don't know if it's in K&R 1.

Richard
Aug 3 '07 #91
On Aug 3, 1:18 am, "Malcolm McLean" <regniz...@btinternet.comwrote:
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than the
range of an int. Of course such buffers should seldom arise, if you obey the
convention that int is the "natural" integer size of the machine.
I understand this is a software group, and people here may not be as
familiar with hardware as either a hardware group or assembly language
group would be. But that statement is totally incorrect. Historically
memory address range has almost always been larger than native data
size. One particular bit-slice processor had a native data size of 4-
bits, yet an address bus 20 bits wide. The popular 8085 has a 16-bit
address bus but only an 8-bit native data size. The 8086 that the IBM-
PC was based on had a 20-bit address bus with a 16-bit native data
size. I could go on with further examples. The point is that it is
actually very rare that the "natural" integer size is as large as the
addressable memory range. Thus the need for a special type to hold the
size of address ranges.

FYI the one counter-example I can think of is the Data General Eclipse
S/140 that had a 15 bit address bus and a 16 bit data size, but it
used memory paging to access more than 32K words. And for those who
may wonder why not just add that 1 extra bit, bit #0 (the MSB) was
used for indirect addressing.

Aug 3 '07 #92
[snips]

On Fri, 03 Aug 2007 07:18:13 +0100, Malcolm McLean wrote:
size_t didn't use to be part of the language. It's a relatively new
invention designed to solve the problem of memory buffers bigger than the
range of an int. Of course such buffers should seldom arise, if you obey the
convention that int is the "natural" integer size of the machine.
How about obeying the convention that C defines its rules and they're
defined for good reasons, so one should pay attention to them?
>
If we allow that any array can overflow the size of an int we get the
folowing

void payroll(struct Employee *emplloyees, size_t N)
{
size_t i;

for(i=0;i<N;i++)
/* so something */
}
Now N is arguably a size, though it is a slightly confusing term.
Actually, it's a count, but either way.
However the type of i is downright misleading. It does not hold a size
at all.
In fact this won't be acceptable, and something will be done.
Huh? You're not using it as a size, so something isn't acceptable?
Either size_t will have to be deprecated / quietly dropped, or C itself
will be regarded as an "advanced" language unsuitable for beginners, and
gradually be squeezed out.
A language is a tool and a tool takes practice to master. If C is too
hard, you should stick to BASIC.
size_t is a kludge, and code is clearer without it.
The code in the example chapters is neither clearer nor good; it is broken
by design, because the author doesn't grasp basic concepts.

Simple example: using size_t to specify the size of the buffer to compress
makes sense; the buffer size will be 0..N. Using int makes it *less*
clear:: the developer obviously intended to allow negative values
specifying the length of the buffer; if he hadn't, he wouldn't be using a
plain int, he'd be using the proper type: size_t. Since he *is* expecting
negative values, the actual intent of the function is no longer clear, as
you cannot compress (or even create) a negatively-sized buffer, so there
must be a special meaning to such negative values, so let's haul out the
reference manual to see what the heck the code does in such cases.
Meanwhile we now have to also worry that our buffer might be too big and
overflow the length parameter, despite there being not a single good
reason for such a case to ever exist with properly-written code that uses
the proper types.

Yeah, sure makes it clearer.
It has no place in
my book,
"It" being "good coding practice".
If you disagree with this choice, I include an example of "real" code,
an atan2 routine form Sun, so that the reader has some exposure to what
production code can look like.
I assume it's ugly. All I can say is I'll take ugly code that works over
pretty code that's broken, any day.
Aug 3 '07 #93
Kelsey Bjarnason said:

<snip>
All I can say is I'll take ugly code that works
over pretty code that's broken, any day.
I'll take readable code that doesn't *quite* work over unreadable code
that does work, any day. Readable code can be fixed.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 3 '07 #94
Richard Bos wrote:
>Malcolm McLean wrote, On 03/08/07 07:18:
>>"Kelsey Bjarnason" <kb********@gmail.comwrote in message
Why would size_t be obsolete, since it does a job int does not do?
It was part of the original C standard, so if you take the earliest year
for the start of C, 1969, and the latest time for size_t entering the
language, 1989,

1988. It's in K&R 2, which predates the published Standard by a year.
I don't know if it's in K&R 1.
Its not in K&R 1 as far as I could see. Which means that it was created
sometime between 1978 and 1988.

Kevin.
Aug 3 '07 #95
>Richard Bos wrote:
>[size_t is] in K&R 2 ... I don't know if it's in K&R 1.
In article <jW******************@newsfe7-gui.ntli.net>
Kevin Bagust <ke**********@ntlworld.comwrote:
>Its not in K&R 1 as far as I could see. Which means that it
was created sometime between 1978 and 1988.
Yes. The need was clear enough as soon as C was in use for larger
programs on the PDP-11 (even before the first split-I&D versions
of Unix, for those models that supported it): user programs could
be as large as 48 to 56 K, but plain "int" topped out at 32767.

In C-as-it-stood-in-the-late-1970s, "unsigned" was still new and
kind of untried. Up until the keyword appeared, if you wanted
unsigned integers, you used pointers:

char *u1, *u2;
u1 = 42;
u2 = 65520; /* or some other value above 32767 */
...
while (u1 < u2)
... do something ...

Since "int" was signed, "int" would not support this; but since
integers and pointers were easily converted with no warnings --
the kernel used code like:

0177440->bar = addr;
0177440->bcr = -256; /* really, word count */
0177440->csr = RK_READ | RK_GO;

-- you could just declare a few pointer variables and use those,
because pointer comparisons were done as unsigned.

(In its early days, "unsigned" could not be applied to "char" and
"short" either, I think. I am not sure if "unsigned long" existed
at first. It was regularized, to apply to all kinds of integers,
around the time Phototypesetter V6 came out, along with Stephen
Johnson's "PCC": Portable C Compiler.)

As for when the spelling "size_t" was first invented, I am not sure.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Aug 4 '07 #96
On Fri, 03 Aug 2007 19:16:10 +0000, Richard Heathfield wrote:
Kelsey Bjarnason said:

<snip>
>All I can say is I'll take ugly code that works
over pretty code that's broken, any day.

I'll take readable code that doesn't *quite* work over unreadable code
that does work, any day. Readable code can be fixed.
If it's unreadable and works, it still works - you can ignore it. :)

My problem with code such as Malcolm's is more fundamental; if he's made
this egregiously bad decision here, what other egregiously bad decisions
has he made elsewhere, ones which are not necessarily so easy to spot?

Bugs is one thing; we all have those. This, to me, is more like using
void main(); there's absolutely no good reason for it, and a coder who
does it probably has other bad habits - just how much can you actually
trust anything he's written, without an in-depth analysis which, in
theory, you shouldn't have to perform were it professionally done in the
first place?
Aug 4 '07 #97
On Thu, 02 Aug 2007 20:03:59 +0100, Malcolm McLean wrote:
I expect my book to be still useful in a hundred years time.
Sure it will - just as it is today: As an example of a useless
text, written by someone who lacks the necessary competence to realize
that he is not competent to write a decent book on the subject.
Aug 5 '07 #98

"Kelsey Bjarnason" <kb********@gmail.comwrote in message
news:30************@spanky.localhost.net...
On Fri, 03 Aug 2007 19:16:10 +0000, Richard Heathfield wrote:
>Kelsey Bjarnason said:

<snip>
>>All I can say is I'll take ugly code that works
over pretty code that's broken, any day.

I'll take readable code that doesn't *quite* work over unreadable code
that does work, any day. Readable code can be fixed.

If it's unreadable and works, it still works - you can ignore it. :)

My problem with code such as Malcolm's is more fundamental; if he's made
this egregiously bad decision here, what other egregiously bad decisions
has he made elsewhere, ones which are not necessarily so easy to spot?

Bugs is one thing; we all have those. This, to me, is more like using
void main(); there's absolutely no good reason for it, and a coder who
does it probably has other bad habits - just how much can you actually
trust anything he's written, without an in-depth analysis which, in
theory, you shouldn't have to perform were it professionally done in the
first place?
If the writer says "here I am departing from the offical standard" then
either the standard writers are utter fools, or there has to be quite a
strong argument that he is making a mistake. I am not wedded to the idea
that my choice on size_t is the right one.
However there are some thigns you fail to appreciate. For instnace I suggest
using negative sizes to indicate "data fialed to compress". This has the
advantage that the algorithm can never inflate data by more than four bytes.
There are of course other ways of indicating this, which may be better.

Another thing you fail to appreciate is that compressed data is inherently a
binary format, and ought to be a portable binary format. So the size integer
has to be stored as a fixed number of bytes, with fixed endianness. So a
size_t, with size unknown, isn't an appropriate type. It makes a promise
that might not be fulfilled. If you are determined to pass in a size_t
nevertheless there are of course ways round this, like storing the number of
bits before the size, but that's the sort of detail and complication that is
not appropriate for the type of book it is.

However you draw the conclusion that because you disagree with the decision
over size_t, there are weaknesses, which you lack the ability to discover,
within the rest of the work. That seems to me pure bluster.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Aug 6 '07 #99
Malcolm McLean wrote On 08/06/07 15:55,:
[...]

However you draw the conclusion that because you disagree with the decision
over size_t, there are weaknesses, which you lack the ability to discover,
within the rest of the work. That seems to me pure bluster.
Malcolm has justifiably complained that the overall
quality of "Basic Algorithms" may be mis-estimated due
to a few prominent errors discussed elsewhere in this
thread. If readers took a wider view, a more comprehensive
sample, they would realize that the few much-deplored
pimples are really just beauty spots. "Oh rash, that
judgest from half the whole!" as Katisha puts it. So I've
taken a longer look, reading the entirety of the book's
opening chapter, "Some Simple Functions." Herewith, my
report of what I found:

The book begins with a non-conforming implementation of
strlen(). It's kind enough to point out the nonconformity,
and goes on to provide a conforming replacement -- but one
wonders what purpose the bogus version serves, other than
to add thickness to the book.

It also claims that strlen() is a "pure function" in
contrast to a "procedure," and gives an unusual definition
for the latter. Nowhere does it mention that the claim of
purity applies only to the two implementations he exhibits,
and need not apply to the Standard strlen() function.

The book's implementation of mystrdup() compels a C99
compiler to emit diagnostics. It also misses out on a
chance at better performance by using strcpy() instead of
memcpy(). But then, the book says that the code it offers
is not highly optimized; perhaps that disclaimer should be
in a more prominent, introductory spot instead of buried
in the commentary on strlen().

At about this point, the text draws attention to some
coding conventions. Among them: the use of the identifier
`answer' to hold a function's return value. Oddly enough,
this mention is the last appearance of "answer" in the
chapter; the rest of the functions do not follow the
stated convention.

There's an fgets() replacement that seems never to
have been tested. Aside from the diagnostics the compiler
is required to emit, there's a backwards test that results
in double-freeing or in dereferencing NULL. Then there are
some baffling stylistic decisions: Why use fgetc() instead
of getc(), why invite bugs by writing buffer sizes and size
increments twice instead of once, why spell NULL as 0, why
put up with the slowness on very long lines when effective
countermeasures are easy?

Next, the book offers a function that is supposed to
remove all white space from a string. As seems to be the
usual case, the compiler must greet this code with a cheery
diagnostic message. Also, the code has a bug that should
not entrap an experienced C programmer. A function to remove
leading and trailing white space from strings elicits the
usual compile-time diagnostic, repeats the bug of the previous
function, and adds a new bug of its own. A remark in the text
indicates that the author was aware of the second bug, but
chose to print it rather than to fix it. Well, he did warn
that the code was not intended to handle "extreme or unusual
inputs" -- another warning that ought to have been written in
a prominent place and in large, bold type rather than buried
in the middle of a paragraph. By defining "extreme and unusual"
as "anything that exposes bugs in the code," the author
absolves himself of all responsibility -- and respectability.

A function to condense runs of white space to single
space characters elicits the usual compiler diagnostic and
repeats the beginners' bug a third time.

Next, the book offers a function to determine whether
a year is or is not a leap year. For a change, no compile-
time diagnostics are required. On the other hand, the
function takes a hopelessly naive view of a complex topic:
the adoption of changes to calendar standards took place at
different times in different regions. For instance, the
book announces that 1900 was not a leap year -- but in
Russia and Greece, 1900 *was* a leap year!

The book makes a fuss about respecting the Standard's
name space by not naming this function isleapyear() -- why
this same fastidiousness does not extend to the strxxx()
functions remains a mystery.

There follows a peculiarity: A day-of-the-week function
that the author confesses he does not understand. The code
was "lifted from the net," says the book, but does not say
whether it was lifted from a reliable or from an unreliable
source. The text says it's all right to use a function you
don't understand, provided you "trust the author" -- but
since the author is unnamed, we do not have the means to
tell whether he is trustworthy.

There follows an explanation of a procedure for finding
the date of Easter, credited to Gauss. This reader had not
heard of Gauss having worked on the problem, and finds it
hard to imagine that it would have interested Gauss: after
all, the best Gauss could hope to do with a formula already
in use would be to simplify it. But perhaps he did do so;
the formula given in the book certainly looks shorter than
the algorithm invented by Aloysius Lilius and Christopher
Clavius almost two centuries before Gauss' birth; I admit
I have not taken the time to ascertain whether the brevity
is merely notational (nor whether the book's formula agrees
with the official one).

The book next offers two macros (mentioning two more,
but not implementing them). The most obvious thing about
the book's macros is that their names consist entirely of
lower-case letters. While this is legal in C, it is far
more usual to name macros in upper-case -- some coding
standards, in fact, insist on this. The macros the book
offers aren't wrong, exactly, just in poor taste.

Oh, and the two that are shown are not safe from side-
effects. There is no mention whatsoever of this rather
important fact: The upshot is that we are offered macros
that have the potential to misbehave *and* are disguised to
look like non-macros (the book even refers to them as
"functions").

The chapter closes with an argument that putting code
in libraries that can be shared by many programs is a Bad
Thing; the "right" way to re-use code is to paste a copy
wherever you happen to need one. (No, I am not making this
up!) And just for laughs, the chapter ends with an English
error.

Statistical summary of "Some Simple Functions:"

- Number of function implementations shown: ten

- Number of functions that require compile-time
diagnostics: five

- Number of functions with bugs (beyond required
diagnostics) spotted by this reader: four

- Number of functions with bugs known to the author
(but published anyhow): one

- Number of macro implementations shown: two

- Number of bad macro implementations shown: two

- Influence of this more extensive reading on the
reader's opinion of the book: negative

--
Er*********@sun.com
Aug 6 '07 #100

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

9 posts views Thread by anonymous | last post: by
12 posts views Thread by Guido Mureddu | last post: by
16 posts views Thread by Robert Zurer | last post: by
11 posts views Thread by www.douglassdavis.com | last post: by
6 posts views Thread by Hello | last post: by
1 post views Thread by jrw133 | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by suresh191 | last post: by
1 post views Thread by Marylou17 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.