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?
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.
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 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 used to be a lot faster on x86 then non-recursive solutions (to the extent that the Microsoft C++ compiler would turn iterative code into recursive) because stack pushes and pops were a lot cheaper than any other memory addressing mode (and are still single-byte instructions, so have good i-cache usage). On modern x86 chips, there's some fairly complex interaction between store forwarding and register rename logic that makes storing values relative to the stack pointer cheap, but manipulating the stack pointer expensive. Whether an iterative or recursive implementation will be faster depends a lot on the microarchitecture and it's generally not a big enough win to make the code less readable if one form is easier to understand than the other.
I am TheRaven on Soylent News
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."