Slashdot Mirror
Developer Argues For 'Forgotten Code Constructs' Like GOTO and Eval (techbeacon.com)
mikeatTB quotes TechBeacon:
Some things in the programming world are so easy to misuse that most people prefer to never use them at all. These are the programming equivalent of a flamethrower... [But] creative use of features such as goto, multiple inheritance, eval, and recursion may be just the right solution for experienced developers when used in the right situation. Is it time to resurrect these four forgotten code constructs?
The article notes that the Linux kernel uses goto statements, and links to Linus Torvalds' defense of them. ("Any if-statement is a goto. As are all structured loops...") And it points out that eval statements are supported by JavaScript, Python, PHP, and Ruby. But when the article describes recursion as "more forgotten than forbidden," it begs the inevitable question. Are you using these "forgotten code constructs" -- and should you be?
The article notes that the Linux kernel uses goto statements, and links to Linus Torvalds' defense of them. ("Any if-statement is a goto. As are all structured loops...") And it points out that eval statements are supported by JavaScript, Python, PHP, and Ruby. But when the article describes recursion as "more forgotten than forbidden," it begs the inevitable question. Are you using these "forgotten code constructs" -- and should you be?
Recursion is an easy way to implement solutions to a number of problems. But if you don't have a clearly finite depth then it can be dangerous. There is often a way to use a loop that doesn't pile on the stack the way recursion can.
That said, it doesn't seem like it belongs in this list.
Frankly, it doesn't seem like a great article. Yup, those things can be misused. Yup, if something can be misused, it will be. I use ruby, so I have access to at least 3/4 of these dark techs. Whatever.
Also forgot to add to this, memory cleanup is another big one. Instead of having to free in every single possible 'if error return' block you can have it always do a check and free in the goto
It gives you a chance to unwind something (like taking a lock) before the return.
No but there are plenty of scenarios that require far more code an complexity when you don't use recursion, when the limits are well understood recursion is a valuable tool.
See: Ackermann function
You know, it might be a pretty good idea to not use recursion and just implement your own stack in many of those cases, because recursion locks you into one traversal algorithm, namely depth-first.
If instead you collect the new nodes to visit to a list, you are able to choose whichever order to traverse those nodes easily. Such as in the order of "most promising prospect".
With a list you can also wait until its size is larger than n and then split the list for multiple cores to execute, merge the resulting lists and gain some concurrency benefits this way.
It's just a few lines of code to do the stack anyways in modern programming languages anyway.
Stack frame allocation costs exactly: nothing.
So why do you care?
You fear an endless loop and running out of stack space?
Well, most compilers convert most recursions into loops anyway: it is called tail recursion optimization.
I don't remember when I saw recursion the last time in production code, likely decades ago, and you care about the raw cases where a manually written loop is "better" than recursion ... wow.
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
"I don't let lousy programmers touch my code. Problem solved."
Nice thought, but that's not real life. As a cynical estimate, at least half of the people working as programmers are lousy. Companies hire them, because they're cheap, or because the company can't find anyone better, or because the company has no clue about programmer quality. There's more code to write than there are good programmers to write them, and that's not going to change any time soon.
Enjoy life! This is not a dress rehearsal.
Am I not supposed to use recursion? Am I missing something?
Recursion has a whole host of negative consequences that make it an undesirable programming construct. The most basic ones don't apply universally, but are nonetheless relevant.
The number one reason not to use recursion is because it is very easy to exhaust the stack in system with more limited memory like embedded systems.
The next most important reason to not use recursion is because it is slower. Iterative loops are easy for a compiler to optimize, and the branch instructions used for iterative loops are single cycle (or on some architectures less than 1 cycle) instructions. This makes them fast. Compare that with function calls which are always more than 1 cycle per call (at least 1 cycle for the call, and another one for the return). It is also extremely difficult for a compiler to unroll a recursive calling structure whereas loop unrolling is almost trivial. Compiler that can do recursion unrolling will hate you if the recursion depth is greater than about a thousand levels deep, as the compiler will eventually exhaust memory and fail.
Recursion is a maintenance nightmare. Trying to ferret out what a recursive function is doing can be difficult even in relatively trivial implementations. The maintenance phase of the software lifecycle is more than half of the total effort, so give those guys a fighting chance and avoid "elegant" solutions unless you have an overriding reason, which you will never have when it comes to recursion.
Recursion uses more memory. Each pass through the recursive function, you have to pile return vectors and function parameters into new locations on the stack. These data have nothing to do with your algorithm and represent pure overhead. iterative loops do not have this overhead penalty.
In the end, recursion is one of those things that makes a great teaching tool, because it forces programmers to think about the consequences in non-linear program space. In practice it is a bad idea and will get you into trouble sooner or later. It is in fact so troublesome that recursion is expressly forbidden in safety critical systems.
I wish I had a good sig, but all the good ones are copyrighted
I was there.
Circa 1980, GOTOs in early BASIC and also 6502 Assembly were appropriately used to maximize the limited resources of early desktop computers. A particularly elegant technique on the Apple II was to POKE instruction codes into the keyboard buffer and GOTO it (the Lamb technique IIRC). While the KB buffer was only something like 128 bytes, it was long enough that a GOTO to a computed destination could be built in it and, wowsa, suddenly Applesoft BASIC had a very powerful CASE emulation.
Naked GOTOs were no longer needed when disk drives replaced tape drives, and RAM grew from 4, 8, or 16 kilobytes to the incredible size of 640 kilobytes. We still used GOTOs that were clothed within Structured Programming constructs (IF-THEN, DO-UNTIL, WHILE-DO, etc) but those were tamed GOTOs. The wild, naked GOTOs became much more rare and good programmers charged with maintaining legacy software would savagely hunt them down and destroy them.
Meanwhile, Gee-Whiz BASIC (arguably the only really good thing to ever come out of Microsoft) let us replace line numbers with labels and brought about the Business BASIC revolution circa 1985.
Dijkstra first used the phrase "GOTO considered harmful" in 1968, only 3 years after BASIC was written and about 7 years before BASIC was widely used (the costs associated with moving from Big Iron using centralized card and tape readers to minicomputers with networks of remote terminals slowed BASIC's adoption.) He was talking about FORTRAN and COBOL practices. His work was part of the slowly dawning recognition that it was not sufficient to write a program that solved the problem; that you also had to write it in such a way that you could maintain it or repurpose it next month or next year. That was the dawning of what became known as structured programming practice.
Bringing this back to the present, using recursion makes a great deal of sense when time to production, long term costs of code maintenance, or repurposing are things that need to be considered.
Obviously if the code is one-off throw-away, like a tool that will be used in converting the accounting system database from warehouse inventory to just in time purchasing, then maintenance is not a consideration but neither is efficiency. Slap together whatever will work and get on to something else asap; don't take time to rework a recursion into something faster or more robust unless the software breaks on a pre-production trial run. And then look for a quick and dirty fix.
But if the code is likely to still be in use five years in the future, then write it so the poor bastard whose got to maintain it can understand it as quickly as possible. That could well mean using recursion. The same goes if chunks of the code might be re-used in some other way, say for example taking chunks from an inventory application to build a library system for maintenance manuals.
Also keep in mind that today's hardware limitations will not apply to tomorrow's problems. It is perfectly acceptable to use a recursion that you know will fail on the 20th iteration if you also are assured that there will never be a need for more than 19 iterations in the next 5 years. In other words, don't waste yourself trying to fix tomorrow's problem, which may no longer be a problem when tomorrow rolls around.
Recursion is undesirable because it doesn't scale - you run out of stack pretty quickly. There isn't really ever any need for recursion anyway as there's nothing you can do recursively that you can't do non-recursively.
While that's basically true, as a former LISP programmer, I can attest that recursion can be simpler and more elegant to code, understand and maintain. It's really good for prototyping and proof-of-concept work, where speed and scaling may not matter. For example, coding a tree search is about 3 lines of recursive code vs. 2 pages of non-recursive code. I sometimes even use a recursive version of a function to verify the operation of a non-recursive function.
It must have been something you assimilated. . . .
Most c compilers. Take this program: #include
int recurse(int x) {
if(x<=0) return 42;
return recurse(x - 1);
}
int main() {
return printf("%d\n", recurse(6502));
}
Then we compile it, adding -S so we can look at the assembly output:
$ clang -S -O3 test.c The compiler recognizes that the printf() call is a tail call, and uses a jmp (which places nothing on the stack in x86), but it also recognizes that recurse() evaluates to a constant and returns that. I was going to post the assembly output for you to look at, but Slashdot said it had too many junk characters.
There is a lot to complain about in terms of efficiency in clang and gcc, but tail recursion is a well-understood problem with a lot of research behind it, and they both do it well.
"First they came for the slanderers and i said nothing."