Malcolm's new book

[Malcolm McLean]

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)

 

[Eric Sosman]

Malcolm McLean wrote On 07/24/07 16:18,:

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.

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

 

[Keith Thompson]

Malcolm McLean wrote On 07/24/07 16:18,:

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

A couple more comments. The layout on the web page makes the code
nearly unreadable. And try squareroot(1.0e6).

 

[Flash Gordon]

Keith Thompson wrote, On 24/07/07 22:27:

A couple more comments. The layout on the web page makes the code
nearly unreadable. And try squareroot(1.0e6).

The book also confuses the concepts of integers and pointer by talking
about malloc being able to return zero. In fact, malloc cannot return
zero because that is a number, what it can return is a null pointer.

It goes on to assume that int is at least 32 bits.

Uses a non-portable method of finding out the size of a binary file
implying the only problem with the method is whether the length might be
too long to represent as a long, when in fact it is non-portable for
other more basic reasons (see the comp.lang.c FAQ).

Uses lower case names for macros. I will admit that the standard does
not mandate upper case, but it is a well known convention.

Seems to recommend against keeping library functions in separate source
files and headers. To quote:
| And we are ready to go. However often if you intend code to be passed
| about, it is not a good idea to include stdsup.h. Cut and paste the
| function into your source instead and declare it static.

It at the very least implies that everything does and always has used
IEEE format when it says:
| ... In small embedded systems, or older computers, they were often
| done in software. Whether hardware or software operations are chosen,
| the memory format is the same.


Oh, and don't forget that a UK person should reference either the UK
standard or the ISO standard in preference to the American standard.

 

[pete]

Malcolm McLean wrote On 07/24/07 16:18,:

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

I'm pretty sure that the assert expression
in squareroot(), was an untested afterthought.

I didn't like the arbitrary termination conditions
invlolving magic numbers like 10 iterations in squareroot(),
or 0.000001 in exponent(), or 0.00000001 in logarithm().

The exponent and logarithm functions
could have been terminated through conditions
involving DBL_EPSILON.

A Newton-Raphson square root algorithm,
can be terminated more logically:

double sq_rt(double x)
{
if (x > 0) {
const double c = x;
double y = c / 2 + 0.5;

do {
x = y;
y = (c / x + x) / 2;
} while (x > y);
}
return x;
}

Page 55 shows pi at 3.1415926535897931160
The "1160" part, is wrong.

I uploaded some math functions written
in completely portable freestanding C code, to:

http://www.mindspring.com/~pfilandr/C/fs_math/

/* BEGIN fs_math.h */
/*
** Portable freestanding code
*/
#ifndef H_FS_MATH_H
#define H_FS_MATH_H

double fs_sqrt(double x);
double fs_log(double x);
double fs_log10(double x);
double fs_exp(double x);
double fs_modf(double value, double *iptr);
double fs_fmod(double x, double y);
double fs_pow(double x, double y);
double fs_cos(double x);
/*
** C99
*/
double fs_log2(double x);
double fs_exp2(double x);
long double fs_sqrtl(long double x);
long double fs_logl(long double x);
long double fs_expl(long double x);
long double fs_cosl(long double x);
long double fs_fmodl(long double x, long double y);

#endif

/* END fs_math.h */



This is the output from fslog_10 on my machine:

/* BEGIN fs_log10.c output */

fs_log10(10000) - 4 is 0.000000e+000
fs_pow(0.0001, -0.25) - 10 is 3.552714e-015
fs_cos(DEGREES_TO_RADIANS(-3540)) - 0.5 is 9.992007e-016
fs_sqrt(2) * fs_sqrt(2) - 2 is -4.440892e-016

log10(10000) - 4 is 0.000000e+000
pow(0.0001, -0.25) - 10 is 0.000000e+000
cos(DEGREES_TO_RADIANS(-3540)) - 0.5 is -1.060133e-015
sqrt(2) * sqrt(2) - 2 is 4.440892e-016

/* END fs_log10.c output */

 

[pete]

pete wrote:

A Newton-Raphson square root algorithm,
can be terminated more logically:

double sq_rt(double x)
{
if (x > 0) {
const double c = x;
double y = c / 2 + 0.5;

do {
x = y;
y = (c / x + x) / 2;
} while (x > y);
}
return x;
}

The extra bit of analysis here is that for any positive N
and any positive Guess,
((N / Guess + Guess) / 2) is ***greater than or equal to***
the square root of N.
So, if the first Guess is greater than or equal
to the square root of N,
then each subsequent Guess will be lower,
until at some point the Guess will be low enough so that
((N / Guess + Guess) / 2) isn't less than Guess;
And when that happens,
then Guess is the greatest double value
that is less than or equal to the square root of N.
The choice for first guess being (N / 2 + 0.5), follows from this:
The square root of N, is somewhere between N and 1.0,
so the first two candidates for first guess are N and 1.0.

((N / N + N) / 2) and ((N / 1.0 + 1.0) / 2)
happen to both be equal to (N / 2 + 0.5),
and (N / 2 + 0.5) is greater than or equal
to the square root of any positive N,
making (N / 2 + 0.5) be a good value for first guess.

 

[Ben Bacarisse]

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

Did you compile and test the code? Is the code in the book the same
as that on the web pages? I am worried by a book that contains:

if(x & 0x7FFFFFFFF < y & 0x7FFFFFFF)

I'd have thought that all compilers would tell you about the
(probable) extra F and that the simplest testing would have shown up
the missing parentheses (I don't think you really meant what you
wrote).

 

[Ben Bacarisse]

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

Since there seem to be significant errors, I decided to have another
look. I do not want to be unkind, but I can't see how, as an
academic, you can publish a book you are clearly not qualified to
write. The smattering of typographical errors is unfortunate (and not
really forgivable since I'd have thought that most publishers will
take your actual compilable source code) but to claim that queue might
be implemented like this:

int queue[100];
int head;
int tail;

void add(int x)
{
if(tail == 100]
tail = 0;
queue[tail++] = x;
}

int remove(void)
{
int answer = queue[head];
head++;
if(head == 100)
head = 0;
return answer;
}

is absurd. I have improved the formatting but left in the silly
mistakes like ] closing the first 'if'.

I have been reticent in the past to post bad code from online lecture
notes because I am sympathetic to some of the pressures that teachers
are, at times, put under[1], but you are asking that people, who want
to learn, should pay over £16 for this kind of stuff. You chose to
write and publish it.

This is may be the biggest howler, but there are so many, I would hope
that you consider withdrawing it and correcting the worst of them
before put this before the public. I note that it is privately
published (by you) so this would not be a problem for you.

[1] "Last one in teaches the programming for accountants course. You
don't know C? -- well you've got a couple of days before the course
starts!"

 

[mstorkamp]

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

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure",
which performs IO.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

 

[osmium]

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure",
which performs IO.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

I had been holding an open mind on the book.

But I now join the people who think the book is awful. There is no
justification for the statement you quote; at best, it is terribly clumsy.
A procedure has side effects, a function does not, one *possible* side
effect is I/O. There are tons of other side effects which do not involve
I/O.

Yes, a pure function returns a value with no side effects.

 

[Richard Tobin]

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

Basic used the term "subroutine" - hence GOSUB.

But the correct conclusion to draw is that there isn't a consistent
convention for the terms "function" and "procedure". Different
computer languages use them differently. Usually it's clear from
context what is meant. But even when someone uses the term "pure
function" you can't always be sure whether they mean

(a) has a result depending only on the inputs,
(b) has no side-effects, or
(c) both.

-- Richard

 

[Eric Sosman]

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure",
which performs IO.

He says there's no distinction, tries to draw one,
and ends up spreading confusion.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

Different programming languages use different terms
to describe various flavors of functions, subroutines,
procedures, methods, lambda expressions, and so on. When
you're dealing with definitional niceties, you need to do
so in the context of a particular language; the next in
line may use the same word but with a different meaning.

In the specific case of C, "procedure" is a word with
no meaning. The Standard does not define it; the Standard
does not even use the word. So there's no way for C to
clear up any confusion you may have about the precise meaning
of "procedure;" one might just as well ask about the precise
meaning of "coroutine."

By the way, "pure function" is another phrase not defined
or used by the C Standard. The term is in general use, with
a meaning somewhat along the lines Malcolm mentions: most
people describe a function as "pure" if it has no "visible"
side-effects. Section 7.5 paragraph 3 of the C Standard
explicitly permits strlen() to have an externally-visible
side-effect, so strlen() need not be "pure" at all!

 

[pete]

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

(Follow the links)

On page 21, it says "Normally we typedef structures."
Most of the regulars on this newsgroup usually don't.

 

[regis]

On page 21, it says "Normally we typedef structures."
Most of the regulars on this newsgroup usually don't.

So what ? I do not see the point.
Most common libraries I find on my system typedef them:
- X11 Window system: (/usr/include/X11/Xlib.h)
- Gimp ToolKit library GTK and Glib: (/usr/include/gtk-2.0/*.h)
- Tcl-Tk C library (/usr/include/{tk,tcl}.h)
- Audio library ALSA: (/usr/include/alsa/*.h)
- Simple Direct Media Layer SDL: (/usr/include/SDL/*.h)
- Image manipulation library Image-Magick: (/usr/includemagick/*.h)
- Freetype truetype library: (/usr/include/freetype2/freetype/*.h)
- t1lib Postscript Type1 library: (/usr/include/t1lib.h)
- Ncurses Screen handling library: (/usr/include/ncurses/*.h)
- readline library: /usr/include/readline/*.h)
- Regular Expressions : (/usr/include/regex.h)
- linux headers: (/usr/include/linux/*.h)
- JPEG library jpeglib: (/usr/include/jpeglib.h)
- PNG library libpng: (/usr/include/libpng/png.h)
- zlib compression library: (/usr/include/zlib.h)
- my stdio.h implements FILE with a typedef'ed struct,
- its Posix counterpart for directories DIR as well, in dirent.h

unistd.h, inet sockets interface do not typedef struct...
GL do not typedef structs but typedef pointers to structs...

 

[Keith Thompson]

(e-mail address removed) wrote On 07/25/07 10:56,: [...]

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure",
which performs IO.

He says there's no distinction, tries to draw one,
and ends up spreading confusion.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

Different programming languages use different terms
to describe various flavors of functions, subroutines,
procedures, methods, lambda expressions, and so on. When
you're dealing with definitional niceties, you need to do
so in the context of a particular language; the next in
line may use the same word but with a different meaning.

In the specific case of C, "procedure" is a word with
no meaning. The Standard does not define it; the Standard
does not even use the word. So there's no way for C to
clear up any confusion you may have about the precise meaning
of "procedure;" one might just as well ask about the precise
meaning of "coroutine."

By the way, "pure function" is another phrase not defined
or used by the C Standard. The term is in general use, with
a meaning somewhat along the lines Malcolm mentions: most
people describe a function as "pure" if it has no "visible"
side-effects. Section 7.5 paragraph 3 of the C Standard
explicitly permits strlen() to have an externally-visible
side-effect, so strlen() need not be "pure" at all!

I don't have too much of a problem with a C book defining and using
terms like "procedure" and "pure function", as long as it (a) defines
them clearly, (b) defines them in ways that don't conflict too badly
with common usage, and (c) make it very clear that the terms are being
defined by the book, not by the C standard.

It could also be argued that a C book should just use the terminology
defined by the standard, but Malcolm's book isn't really *about* C;
it's primarily about algorithms, using C to present them. In that
context, distinguishing "procedures" and "pure functions" from other
functions is probably sensible.

<OT>
An early draft version of Ada (from 1979) had "procedures" that
perform actions without returning a value, "value-returning
procedures" that perform actions and return a value, and "functions"
that return a value and are tightly restricted in their side effects.
For example, you couldn't add I/O statements to a function. In later
revisions, value-returning procedures were dropped, and the
restrictions on functions were loosened.
</OT>

But I've never heard of the term "procedure" being defined in terms of
I/O. Normally a "procedure" would be what C calls a function
returning void. A lot of C functions also have a primary purpose of
causing side effects, but return a result that indicates whether it
succeeded or not; some other languages might, for example, use a
procedure that raises an exception on failure. (qsort() is a good
example.)

 

[Alan Curry]

So what ? I do not see the point.
Most common libraries I find on my system typedef them:
- X11 Window system: (/usr/include/X11/Xlib.h)

Which also gives us the lovely "typedef char *XPointer" as a generic pointer
type - I don't think Xlib is the place to look for examples of good style in
modern C.

- Gimp ToolKit library GTK and Glib: (/usr/include/gtk-2.0/*.h)

glib is the worst typedef abuser I've ever seen. "gint" has been discussed
here before, and the defense for it seems to be "sure it adds no semantics
that int didn't already have, but, we already had a typedef for everything
else so why not".

- Tcl-Tk C library (/usr/include/{tk,tcl}.h)
- Audio library ALSA: (/usr/include/alsa/*.h)

The horrible programming interface, compared to the traditional unix
/dev/audio (which you can actually use without a complicated library by just
fopen()'ing it and fwrite()'ing your sound data) does not make ALSA a good
example either. OSS/Linux is still alive, despite the wishes of the ALSA
people, for good reason.

Skipping ahead a bit...

- Simple Direct Media Layer SDL: (/usr/include/SDL/*.h)
- Image manipulation library Image-Magick: (/usr/includemagick/*.h)
- Freetype truetype library: (/usr/include/freetype2/freetype/*.h)
- t1lib Postscript Type1 library: (/usr/include/t1lib.h)
- Ncurses Screen handling library: (/usr/include/ncurses/*.h)
- readline library: /usr/include/readline/*.h)
- Regular Expressions : (/usr/include/regex.h)
- linux headers: (/usr/include/linux/*.h)

Linux kernel Documentation/CodingStyle says:

In general, a pointer, or a struct that has elements that can reasonably
be directly accessed should _never_ be a typedef.

Some extremely low-level objects in the kernel are typedef'd. And some
areas have maintainers who rebel against the common wisdom and typedef
excessively. But the vast majority of structs in the kernel are not
typedef'd.

typedef'ing a struct in the kernel sends the message "a lot of code will have
to refer to this data type, but it is so freakin opaque you shouldn't even
need to know whether it's a struct or an integer." Which also applies to FILE
from stdio.h and several of your other examples.

- JPEG library jpeglib: (/usr/include/jpeglib.h)
- PNG library libpng: (/usr/include/libpng/png.h)
- zlib compression library: (/usr/include/zlib.h)
- my stdio.h implements FILE with a typedef'ed struct,
- its Posix counterpart for directories DIR as well, in dirent.h

unistd.h, inet sockets interface do not typedef struct...

I wouldn't claim sockets as a design (too much casting, not enough union'ing)
but then there are these better examples of POSIX system interfaces using
struct, none of them being typedef'd:

<sys/stat.h>: struct stat
<sys/resource.h>: struct rusage
<sys/time.h>: struct timeval
<pwd.h>: struct passwd
<sys/poll.h>: struct pollfds
(as opposed to the older, clunkier, typedef'd fd_set in <sys/select.h>)

oh and in ANSI C:

GL do not typedef structs but typedef pointers to structs...

typedef'd pointers are even worse.

 

[regis]

Which also gives us the lovely "typedef char *XPointer" as a generic pointer
type - I don't think Xlib is the place to look for examples of good style in
modern C.

I did not cite these libraries as places to look for
good style or modern C.
And whether typedef'ing structs, numeric types or pointers
is good or bad practice is not my point.
My point is: typedef'ing structs is a wide practice.

typedef'd pointers are even worse.

( here we agree... )

 

[Ivar Rosquist]

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.

Congratulations! Your books provide a shiny, lucid example on how
books ought not to be written. Please keep up the good work.

 

[Richard Bos]

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure",
which performs IO.

Well, that goes to show that whoever originally wrote that has no idea
what he's talking about. What is called a "function" and what a
"procedure" varies wildly - for example, in Pascal, a function returns a
value, a procedure does not, and that is _all_ the difference - and
separating function/procedure/routines into "things that calculate
something" and "things that perform IO", with nothing in between and no
provision for "things that calculate something _and_ perform IO" is
short-sighted as well as less than useful.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.

That's Pascal. BASIC originally had only subroutines, no functions _or_
procedures. C has only functions, which may or may not return a value
and may or may not perform calculation and/or IO.

Richard

 

[Mark Bluemel]

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/