Dr. Dobb's Journal July 2000
Dear DDJ,
Jonathan Erickson's May 2000 "Editorial" on patents touched a bit of a nerve. We are a consultancy, and a growing part of our business is evaluating patent portfolios for high-tech companies. In evaluating several thousand high-tech patents, we have encountered perhaps five for which we could say "now THIS is something truly novel."
If you ever need proof that the U.S. Patent and Trademark Office has gone over the edge, you should check out patent 5,443,036. I'd like to give you all the gory details, but I think the effect is better if you read it from an official source. Ever have a cat? Ever tease the cat with a laser pointer? If so, then you have infringed U.S. patent 5,443,036; see http://www.patents .ibm.com/details?&pn=US05443036__.
Tim Roberts
timr@probo.com
Dear DDJ,
I just read Al Stevens' column in the April 2000 issue of DDJ. Having just left a position where I was the chief implementor of the CodeWarrior x86 C/C++ compiler, I can assure you there is another reason to reserve C++ identifiers with an embedded "__" for implementation beyond Standard Library selfishness.
The name mangling scheme used in CFront, and later adopted with changes by gcc and the nonWin32 Metrowerks compilers decorates the names with a type string that starts with a double underscore. Allowing user identifiers with an embedded "__" could cause problems with type-safe linking, especially if you use an extern "C" name that would not be further decorated.
The Win32 scheme used by VC++ and the Win32 CodeWarrior compiler uses characters not legal in C identifiers to delimit the identifier from the type information.
This scheme was also used in C99 to introduce new keywords into the language with _Bool, _Complex, and _Imaginary. Without reserving the underscore-capital namespace, these additions probably would break much more code.
Ben Combee
combee@techwood.org
Dear DDJ,
Jim Ledin's article, "Digital Filtering and Oversampling" (DDJ, April 2000) was a great introduction to the complex field of signal aliasing and antialiasing. However, Jim's description of the FIR's linear phase properties was a little misleading.
Jim states that "An important feature of FIR filters is that they possess linear phase." While FIR filters can be designed to possess linear phase, they do not automatically do so. Specifically, a FIR filter possesses linear phase if and only if its coefficients are symmetric (that is, they read the same backwards as they do forwards). I hope this helps to clarify matters.
Eddie Edwards
eddie@naughtydog.com
Dear DDJ,
I saw Al Stevens' remarks about the neglected pay phones in the Atlanta airport in his April 2000 DDJ column. The Atlanta Journal/Constitution has reported that the revenue from pay phones at the airport dropped from $1.0-1.2 million a month in September 1999 to $800,000 per month in 2000 -- and seems to be in continuing decline. The newspaper writer noticed the correlation between the first offerings of 100+ minutes per month free plans in Atlanta and the start of the decline. Sell all stock in companies providing pay phones now. The increase in pay phone prices (from 25 to 35+ cents) and the declining price of cell phone minutes have reached the economic crossover point where cell is cheaper.
Keith McBride
kmcbride@topform.com
Dear DDJ,
I've enjoyed Al Stevens' column for several years now and I was particularly interested in his March 2000 "C Programming" column because I worked at Lockheed Martin in Houston as a contractor for NASA, working on the software for the Shuttle and International Space Station (ISS) for 2 1/2 years. The reason why the Shuttle was grounded during the Y2K fiasco is because it's not "Y" compatible. The shuttle can never be up between December 31 and January 1, as its on-board equipment doesn't handle the transition. I was present during many of the Y2K tests NASA put on in the Mission Control Center to make sure everything would continue to work after January 1. For the most part, everything was Y2K safe in the ground systems (there was at least one system I was aware of that was not Y2K compliant, but it was for a future addition to the ISS). I've since left Lockheed for greener, less government, pastures. But I just wanted to spread the word that NASA isn't too bad. Just a little paper heavy is all.
Matt Albrecht
matt.albrecht@trilogy.com
Dear DDJ,
Thanks to Jonathan Erickson in his April 2000 editorial "Getting The Lead Out" for taking what will probably be seen as an antiindustry stance on this issue. It's very important for everybody to do their part to raise the consciousness about the environment because our so-called leaders won't.
Paul Kinzelman
pkinz@timesync.com
Dear DDJ,
I've been impressed by Arch D. Robison's work on scientific computing and C++. However, in his article "Considering Recursion" (DDJ, March 2000), he seems to have an unfortunate bias against using recursion, even in cases where it is quite natural. This is despite, or because, of his roots in functional programming.
Listing Two shows a binary tree walk, the analysis of which takes most of the remainder of the article:
struct node {
node* left, right;
}
void walk0(node* p) { // Version 0.
if (p) {
.. process node* p ..
walk0(p->left);
walk0(p->right); // Tail call.
}
}
Robison's first version mixes recursion and iteration:
void walk1 (node* p) { // Version 1 - Arch // D. Robison's
while(p) {
// .. process node* p ..
if (p->left) {
if (p->right) {
walk1(p->left); // General case - // recurse to left
p = p->right; // and iterate to // right.
} else p = p->left; // Special case - // iterate to left only.
} else p = right; // Special case - // iterate to right only.
}
}
Unfortunately, this version does unnecessary comparisons. Consider this alternative:
void walk2(node* p) { // Version 2.
if (p) walk2_0(p); // Tail call.
}
void walk2_0(node*p) {
if (p->left) walk2_0(p->left);
if (p->right) walk2_0(p->right); // Tail call.
}
While requiring two procedures, this version is shorter and does less work than version 1. It follows from version 0 by partially inlining the calls to walk0(). Last call optimization can be applied by hand if your language does not provide it.
This version, or even version 0, would keep me quite happy. The iterator versions in the article seem larger and more complicated than necessary.
Ken Anderson
kanderso@bbn.com
Arch replies: Ken's recursive walk2 is a big improvement over my recursive walk0, particularly with the tail recursion ("last call") optimized into iteration. However, whether or not walk2 does "less work" than walk1 depends upon assumptions about the tree. In particular, consider what happens if a large fraction of the tree nodes have a left child but no right child. For such nodes, walk1 avoids recursing to the left, whereas walk0 does recurse so, and that call is not an optimizable tail recursion. The intent to optimize the case complicated some of my examples, and I should have explained that it was on my mind.
My other point was not efficiency, but reuse, and walk0 demonstrates that problem. It is not reusable except by copying the pattern (or turning it into a visitor). The iterator is more complicated to implement, but once implemented, can be reused via the obvious for-loop idiom at ease. So perhaps the argument is who gets the benefit of "more natural" -- implementor or client. Obviously, recursing is more natural for the implementor, but for many (but certainly not all) clients iteration is more natural. As the article mentions, language features play a role here. A language with coroutines (or lazy evaluation) would make a recursive implementation with an iterative interface possible.
The trees in the article were trivial, for the sake of space. When trees have a dozen kinds of nodes, the recursive pattern becomes much larger and harder to follow. One of the iterators in our old C++ optimizer is implemented in over 400 lines. And yes, it is hard to follow. But it is reused about 30 times. For a tree of that complexity, the consideration of "more natural" loses out to consideration of reuse. So the programming-in-the-small versus in-the-large is a factor too in recursion versus iteration. If I had used my naive walk0, and later wanted to replace it with the more efficient walk2, I would have over 30 routines to fix, and the recursive flow control would be tangled in each routine's internal operation.
Look at past winners of the International Obfuscated C Code Contest (http:// www.ioccc.org/). My impression is that far more of the winners boast about using recursion to obfuscate than iteration.
My bias against recursion is similar to my bias against the goto statement -- both are quite useful, but if all other considerations balance, I prefer to use structured iterative approaches.
DDJ