Java Forum / General / December 2005
Using exceptions for early exit
Jonathan Bartlett - 12 Dec 2005 14:57 GMT I ran across the following article on Java exceptions and noticed this little tidbit:
"Sometimes developers decide to use exception for flow-control (i.e. to throw an exception once a certain condition is met). The generation of stack-traces is expensive and developers should realise that an exception should only be used in exceptional cases."
(From http://javafoundry.ibscon.com/content/view/18/ )
A few questions:
(1) is this still true? Is a stack trace still expensive? (2) do all exceptions do this? For example, if I just inherit from "Throwable" rather than "Exception" is a stack trace still generated? (3) is there any way around this?
The reason I'm asking is that exceptions would seem to be a very good way to implement early-exit from certain deeply-nested computations.
Jon ---- Learn to program using Linux assembly language http://www.cafeshops.com/bartlettpublish.8640017
Chris Smith - 12 Dec 2005 15:43 GMT > "Sometimes developers decide to use exception for flow-control (i.e. to > throw an exception once a certain condition is met). The generation of [quoted text clipped - 6 lines] > > (1) is this still true? Is a stack trace still expensive? Yes, it's still true that generating a stack trace is a relatively expensive operation, compared to other methods of accomplishing this. Whether that justifies the generalization above is a different matter. The number of situations in which small performance costs matters enough to justify making your life harder is actually rather small.
On the other hand, just from a readability standpoint, use of exceptions for minor flow control purposes is a poor idea. The ultimate test is whether there is a substantial body of code in which the exception actually makes sense and can be given a simple descriptive name. Generally, when exceptions do get used, there is some context in which is really IS an exceptional case. Exceptional, in the context of Java, doesn't mean that it almost never happens, but rather than the code to handle it is not relevant to the purpose of the method you're writing.
> (2) do all exceptions do this? For example, if I just inherit from > "Throwable" rather than "Exception" is a stack trace still generated? > (3) is there any way around this? Yes, and no.
 Signature www.designacourse.com The Easiest Way To Train Anyone... Anywhere.
Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation
Eric Sosman - 12 Dec 2005 15:45 GMT Jonathan Bartlett wrote On 12/12/05 09:57,:
> I ran across the following article on Java exceptions and noticed this > little tidbit: [quoted text clipped - 15 lines] > The reason I'm asking is that exceptions would seem to be a very good > way to implement early-exit from certain deeply-nested computations. The first two seem the sort of questions you could answer for yourself with a little experimentation. You'd get not only answers, but quantitative answers.
The third is unclear to me. What is the "this" you're worried about, and what would it mean to get "around" it? That is, what is your problem and what are your criteria for a successful solution?
 Signature Eric.Sosman@sun.com
Jonathan Bartlett - 12 Dec 2005 19:02 GMT > The third is unclear to me. What is the "this" you're > worried about, and what would it mean to get "around" it? Producing stack traces.
> That is, what is your problem and what are your criteria > for a successful solution? Throw something that didn't generate a stack trace.
Jon
Eric Sosman - 12 Dec 2005 19:56 GMT Jonathan Bartlett wrote On 12/12/05 14:02,:
>> The third is unclear to me. What is the "this" you're >>worried about, and what would it mean to get "around" it? [quoted text clipped - 5 lines] > > Throw something that didn't generate a stack trace. As far as I know, every Throwable contains a stack trace. You don't need to display it, but it'll be there no matter what you do.
However, the stack trace is built when the Throwable is constructed, not by the "throw" action. You could therefore construct your Exception once at class-loading time, and then throw the same Exception object as often as you like:
class Perverse {
private static Exception perverseException = new Exception();
public void somethingStupid(int n) throws Exception { if (n <= 0) throw perverseException; else somethingStupid(n-1); }
public void moreStupidity(double p) throws Exception { if (Math.random() < p) throw perverseException; } }
Thus, you'd only incur the cost of creating and initializing the Exception once, instead of at every throw.
I won't reveal what I think about the advisability of the technique, but the names in the illustration above may provide a tiny clue ... Have I just given a loaded pistol to a child?
 Signature Eric.Sosman@sun.com
Chris Uppal - 12 Dec 2005 21:02 GMT > class Perverse {
> public void somethingStupid(int n) throws Exception {
> public void moreStupidity(double p) throws Exception { Just curious. If the Java language had a non-local-return feature, with appropriate syntax, and semantics that was (at worst) no harder to get right than throwing an exception (i.e. /not/ C's setjmp()/longjmp()), would you still feel the same way ?
Is the issue the "shape" of the control-flow or the syntax used to express it ?
(For me it's the latter -- I don't like the idiom either, but that's because I would expect that people reading the code would /not/ expect exceptions to be used in that way; I have no problems with a precisely controlled, but non-local, flow of control in itself. Which, come to think of it, is just as well since I don't object to exceptions...)
-- chris
Roedy Green - 12 Dec 2005 21:50 GMT On Mon, 12 Dec 2005 21:02:39 -0000, "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly quoted someone who said :
> If the Java language had a non-local-return feature, with >appropriate syntax, and semantics that was (at worst) no harder to get right >than throwing an exception (i.e. /not/ C's setjmp()/longjmp()), would you still >feel the same way ? I invented such tools in my BBL and Abundance language. I used them only for constructing early return verbs, not for jumping up many levels.
e.g. for example in Abundance you can say
aBoolean ?EXIT>>>
instead of
aBoolean IF EXIT>>> THEN
or
aBoolean ?YES>>>
instead of
aBoolean IF YES EXIT>>> THEN
(returns value yes if true, otherwise carries on)
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
Eric Sosman - 12 Dec 2005 21:52 GMT Chris Uppal wrote On 12/12/05 16:02,:
>>class Perverse { > [quoted text clipped - 14 lines] > non-local, flow of control in itself. Which, come to think of it, is just as > well since I don't object to exceptions...) The syntax doesn't bother me much, although there's a certain amount of clumsiness about try/catch/finally. The fact that each of the three blocks has its own scope means that there's no single scope for the entire construct; this makes me declare variables at a scope wider than they really ought to have, or introduce an extra level of { } simply to create a containing scope. And it's irritating to catch an IOException, say, and then put yet another try/catch inside the finally that closes the BufferedReader or whatever. But these are just cosmetic issues, nothing I can't live with.
Nor is the shape of the control flow a problem. The route taken by a Java exception has the right balance of unpredictable (the thrower doesn't know the catcher) and predictable (the catcher will necessarily be an active call frame). A goto style (e.g., PL/I or Pascal) loses the flexibility of "anonymous" (or else requires label variables, which are hard to validate), while the trust-the-programmer style of C's longjmp() all too often engenders really horrible bugs. Java exceptions unwind in a calm and orderly fashion, which I find soothing.
My objections to control-flow-by-exception are twofold. First, there's efficiency. Yes, I know it's unfashionable to talk about efficiency, but those of us who programmed in Olden Times formed the hard-to-shake habit of keeping it in mind. I'm still an efficiency addict (on, er, method-done treatment ;-), and cannot help but think of all the cycles that must be spent on a throw/catch. Even if you pre-construct the thrown exception, the JVM still needs to conduct a possibly lengthy search up the stack to find candidate catch blocks; a chain of returns -- even if a method result must be if'ed at each level -- will almost certainly be faster.
My other objection is a "right job, wrong tool" feeling. Sure, it's possible to use exceptions for control flow, but Java's control flow constructs are there because they're more convenient, more readable, and better suited to the task. One can replace a "switch" with a try/catch/catch/catch/catch... block, but that doesn't mean one ought to. Exceptions should be, well, exceptional -- they're not called Normals, after all! I like to think of a method as having a contract that in normal circumstances is "contained" in its arguments, its returned value, and the states of the objects it touches. When I call the method, I want it to return with its contract fulfilled. Exceptions are for when there's something that prevents the method from fulfilling its contract: invalid arguments or state, I/O errors, whatever.
So: My objections amount to an old-fashioned concern for efficiency combined with a Puritanical fastidiousness. Neither is binding on anyone else; follow your weird.
 Signature Eric.Sosman@sun.com
Roedy Green - 12 Dec 2005 21:44 GMT > However, the stack trace is built when the Throwable >is constructed, not by the "throw" action. You could >therefore construct your Exception once at class-loading >time, and then throw the same Exception object as often >as you like: I'm have added your technique to the pantheon at http://mindprod.com/jgloss/unmainobfuscation.html point number 19.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
Andrea Desole - 12 Dec 2005 16:52 GMT > The reason I'm asking is that exceptions would seem to be a very good > way to implement early-exit from certain deeply-nested computations. If this is your need that probably means that you have to change your code (for example, you can make methods out of your computations). If you don't, have a look at break and continue. I personally never use them (I consider them mostly an extreme solution), but that's what they are for
ricky.clarkson@gmail.com - 12 Dec 2005 18:27 GMT A particular example in the API of using exceptions for flow control is Integer.parseInt. There's no way of asking whether the int is parseable,so you have to detect it via an exception.
I think it would be better like this:
IntegerParseResult result=Integer.parseInt("5556");
if (result.hasValue()) doStuff(result.getValue()); else handleTheBadStuff();
getValue() would throw an IllegalStateException ifcalled when !result.hasValue().
Roedy Green - 12 Dec 2005 21:54 GMT On 12 Dec 2005 10:27:00 -0800, "ricky.clarkson@gmail.com" <ricky.clarkson@gmail.com> wrote, quoted or indirectly quoted someone who said :
>A particular example in the API of using exceptions for flow control is >Integer.parseInt. There's no way of asking whether the int is >parseable,so you have to detect it via an exception. that requires you to deal with errors at every use. With Exceptions you can deal with them all in one place, e.g. if your numbers are supposed to be generated by some other computer in perfect form where even one being wrong indicates a program bug.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
ricky.clarkson@gmail.com - 13 Dec 2005 00:07 GMT Roedy,
Yes, the corner case of when you actually need lots of conversions, and can't afford to write a separate method to wrap up the custom version of Integer.parseInt I gave, to again throw an exception, would possibly invalidate my suggestion.
Here is how I see the code before your suggestion:
final class LessExceptions { public static IntegerParseResult parseInt(final String string) { try { final int result=Integer.parseInt(string); return new PositiveIntegerParseResult(result); } catch (final NumberFormatException exception) { return new NegativeIntegerParseResult(); } } }
interface IntegerParseResult { boolean hasValue(); int getValue(); }
final class PositiveIntegerParseResult implements IntegerParseResult { private final int value;
public IntegerParseResult(final int value) { this.value=value; }
public boolean hasValue() { return true; }
public int getValue() { return value; } }
final class NegativeIntegerParseResult implements IntegerParseResult { public NegativeIntegerParseResult() { }
public boolean hasValue() { return false; }
public int getValue() { throw new IllegalStateException(); } }
Then the client programmer would do:
final IntegerParseResult result=LessExceptions.parseInt("5556");
if (result.hasValue()) someMethod(result.getValue()); else someErrorHandling();
Now the requirement is to be able to handle lots of numbers. Suppose it's a String[]:
final String[] inputs={"5556","blah","123","566"};
for (final String input: inputs) { final IntegerParseResult result=LessExceptions.parseInt("5556");
if (result.hasValue()) someMethod(result.getValue()); else someErrorHandling(); }
I can't see an issue with this. If you want to lazily load the Strings, you could even use a collection that lazily loads, and iterate over this, and break the loop early if you want.
Another option is to add a method to LessExceptions:
public static IntegerParseResult[] parseInts(final String... strings) { final IntegerParseResult[] results=new IntegerParseResult[strings.length];
for (final int a=0;a<strings.length;a++) results[a]=parseInt(strings[a]); }
Of course, I wouldn't be surprised if I've completely misunderstood your point.
Oliver Wong - 13 Dec 2005 14:38 GMT > Roedy, > [quoted text clipped - 105 lines] > Of course, I wouldn't be surprised if I've completely misunderstood > your point. Personally, I don't like the API you've exposed. For one thing, it's impossible to get a negative parse value, despite the existence of a "NegativeIntegerParseResult" class. For another thing, having an instance of a class doesn't imply that you actually have a legal value, because of the "hasValue()" boolean. That means that every method that takes in an instance of IntegerParseResult has to check to make sure that the value is actually present:
<code> public void methodA(IntegerParseResult ipr) { if (!ipr.hasValue()) { throw new IllegalArgumentException(); } if (conditionA) { //Do something } else { methodB(ipr); } }
public void methodB(IntegerParseResult ipr) { if (!ipr.hasValue()) { throw new IllegalArgumentException(); } if (conditionB) { //Do something } else { methodC(ipr); } }
public void methodC(IntegerParseResult ipr) { if (!ipr.hasValue()) { throw new IllegalArgumentException(); } if (conditionC) { //Do something } else { methodA(ipr); methodB(ipr); } }
public mainMethod() { methodA(LessException.parseInt("foo")); methodB(LessException.parseInt("25")); methodC(LessException.parseInt("-42")); } </code>
I'd rather just deal with the exception right away in main, then having to worry about it EVERYWHERE in my code.
- Oliver
ricky.clarkson@gmail.com - 14 Dec 2005 02:21 GMT Oliver,
You could always pass methodA, B and C the int, rather than the IntegerParseResult.
public mainMethod() { methodA(LessException.parseInt("foo").getValue()); methodB... methodC... }
This way you will get an IllegalStateException, which is an unchecked exception, but it's fairly obvious that there is more to the result of parseInt than an int based on that code snippet, so an experienced programmers shouldn't miss it.
I'd prefer the test, and there's no reason why it can't be done in mainMethod:
public mainMethod() { IntegerParseResult ipr=LessExceptions.parseInt("foo"); if (ipr.hasValue()) methodA(ipr.getValue());
ipr=LessExceptions.parseInt("25"); if (ipr.hasValue()) methodB(ipr.getValue());
ipr=LessExceptions.parseInt("-42"); if (ipr.hasValue()) methodC(ipr.getValue()); }
To get the same using Integer.parseInt you would need 3 separate try..catch blocks:
public mainMethod() { try { methodA(Integer.parseInt("foo")); } catch (final NumberFormatException exception) { logger.fine(exception); }
try { methodB(Integer.parseInt("25")); } catch (final NumberFormatException exception) { logger.fine(exception); }
try { methodC(Integer.parseInt("-42")); } catch (final NumberFormatException exception) { logger.fine(exception); } }
I know which I'd rather read/write/explain to newbies.
> For one thing, it's > impossible to get a negative parse value, despite the existence of a > "NegativeIntegerParseResult" class. I'm not sure what you mean by that. I meant a failed parse, the kind of thing parseInt("foo") would return.
Oliver Wong - 14 Dec 2005 22:17 GMT > Oliver, > [quoted text clipped - 12 lines] > parseInt than an int based on that code snippet, so an experienced > programmers shouldn't miss it. parseInt() might be an expensive operation, so you'd generally want to keep the object representing the parsed int around, in case you want to re-use it, e.g.
mainMethod() { ParsedInteger pInt = LessException.parseInt("foo"); methodA(pInt.getValue()); methodB(pInt.getValue()); //etc. }
However, now you have an object which may be in and of itself "invalid", which to me is a bad code smell. That might just be a matter of opinion, but I prefer having the exception occur right away (during the call to parseInt()) than to carry around a bad object, and only find out much later on that something went wrong.
What if your application parses the int, then serializes the object in a database.
Months later, another application running on a different computer in the other side of the world deserializes the object, and then tries to do something useful with it, only to get an exception thrown. This is obviously an extreme example, but it illustrates why it's generally better to get the exception as early as possible.
> I'd prefer the test, and there's no reason why it can't be done in > mainMethod: [quoted text clipped - 13 lines] > methodC(ipr.getValue()); > } If you take the test out of methods A, B and C, and those methods are public, then you have a fragile interface. Not too mention you also have code duplication. Conceptually, "testing that your object has a value before using it" and "using it" should be one indivisible action, which is why I'd rather the test be IN the methods. But again, that might just be a matter of opinion.
> To get the same using Integer.parseInt you would need 3 separate > try..catch blocks: [quoted text clipped - 30 lines] > > I know which I'd rather read/write/explain to newbies. No, actually the equivalent code using try/catch is:
public mainMethod() { try { methodA(Integer.parseInt("foo")); methodB(Integer.parseInt("25")); methodC(Integer.parseInt("-42")); } catch(NFE e) { logger.error(e); } }
Notice that with your unchecked exception algorithm that as soon as method A executes, the exception is thrown, and we're taken OUT of the main method. That's what the code I posted here does as well.
With your 3 try/catch blocks, what happens is that if A fails, the program still procees and tries to do B and C. This might be what you want, or it might not be what you want.
This added flexibility, BTW, is another good reason for having exceptions (for those who doubt their power), though it's irrelevant now because you've already said your problem isn't with exceptions in general, but checked exceptions.
>> For one thing, it's >> impossible to get a negative parse value, despite the existence of a >> "NegativeIntegerParseResult" class. > > I'm not sure what you mean by that. I meant a failed parse, the kind > of thing parseInt("foo") would return. The code you posted earlier for NegativeIntergerParseResult is this:
<code> final class NegativeIntegerParseResult implements IntegerParseResult { public NegativeIntegerParseResult() { }
public boolean hasValue() { return false; }
public int getValue() { throw new IllegalStateException(); } } </code>
That's what I mean by it's impossible to get a negative parse value.
- Oliver
Oliver Wong - 14 Dec 2005 22:23 GMT > though it's irrelevant now because you've already said your problem isn't > with exceptions in general, but checked exceptions. Sorry, ignore this part. I was confusing you with a different poster.
- Oliver
ricky.clarkson@gmail.com - 15 Dec 2005 20:34 GMT Oliver,
> parseInt() might be an expensive operation, so you'd generally want to > keep the object representing the parsed int around I'd generally not worry about how expensive the operation is until I'd profiled the code. If I discovered that it was expensive, I'd keep a Map<String,Integer> - NOT a ParseResult.
> However, now you have an object which may be in and of itself "invalid", > which to me is a bad code smell. There is nothing invalid about this object. It has a hasValue() and a getValue(). hasValue() will return a boolean, getValue() will throw an exception. If you ignore the contract on this object and just blindly call methods at random, then you will get an IllegalStateException. That's not a problem, that's an example of what happens when you ignore contracts.
> What if your application parses the int, then serializes the object in a > database. ParseResult is a transient object that shouldn't be serialised - an intermediate object. If it was supposed to be serialised it would implement Serializable.
> Notice that with your unchecked exception algorithm that as soon as > method A executes, the exception is thrown, and we're taken OUT of the main > method. No, that's not what happens. The exception is thrown, logged and then the method continues. Method execution continues after a catch block. Unless you meant the first bit of code.. I suppose I should have given them unique names instead of a few called 'mainMethod'.
> This added flexibility, BTW, is another good reason for having > exceptions What added flexibility? I'm confused there.
Ok, let's look at how to solve the code duplication issue.
String[] strings={"55","-42","foo"};
for (final String string: strings) { IntegerParseResult ipr=LessExceptions.parseInt(string); if (ipr.hasValue()) methodA(ipr.getValue()); }
Still not solved, because it was methodA, methodB and methodC. I don't like anonymous classes, but for the sake of brevity:
interface CustomRunnable { void run(int i); }
String[] strings={"55","-42","foo"};
CustomRunnable[] runnables= { new CustomRunnable(){public void run(){methodA();}}, new CustomRunnable(){public void run(){methodB();}}, new CustomRunnable(){public void run(){methodC();}} };
for (final int a=0;a<strings.length;a++) { IntegerParseResult ipr=LessExceptions.parseInt(strings[a]);
if (ipr.hasValue()) runnables[a].run(ipr.getValue()); }
In a real app I would make those anonymous classes into package-private classes.
Alert me if I missed something - I started posting this BEFORE I looked at the time.
Oliver Wong - 15 Dec 2005 22:44 GMT > Oliver, > [quoted text clipped - 4 lines] > profiled the code. If I discovered that it was expensive, I'd keep a > Map<String,Integer> - NOT a ParseResult. So it seems to me like the "intended usage" of this API is to immediately check the hasValue() method, and immediately extract the Integer, throwing away the ParseResult. In that case, I don't see how this is any more troublesome than working with exceptions.
>> However, now you have an object which may be in and of itself "invalid", >> which to me is a bad code smell. [quoted text clipped - 5 lines] > That's not a problem, that's an example of what happens when you ignore > contracts. Maybe it's an overly painful contract then. You could imagine a factory method whose contract were to demand that you provide a unique prime number each time it generated a new object (and yes, it has a Set to make sure you don't re-use prime numbers). The problem here, I think, is not with the client's disapproval of the contract.
>> What if your application parses the int, then serializes the object in a >> database. > > ParseResult is a transient object that shouldn't be serialised - an > intermediate object. If it was supposed to be serialised it would > implement Serializable. Okay, fair enough.
>> Notice that with your unchecked exception algorithm that as soon as >> method A executes, the exception is thrown, and we're taken OUT of the [quoted text clipped - 5 lines] > Unless you meant the first bit of code.. I suppose I should have given > them unique names instead of a few called 'mainMethod'. Yes, I was referring to the code that reads: <code> public mainMethod() { IntegerParseResult ipr=LessExceptions.parseInt("foo"); if (ipr.hasValue()) methodA(ipr.getValue());
ipr=LessExceptions.parseInt("25"); if (ipr.hasValue()) methodB(ipr.getValue());
ipr=LessExceptions.parseInt("-42"); if (ipr.hasValue()) methodC(ipr.getValue()); } </code>
And I was saying that what you claimed was the equivalent with the 3 try catch blocks actually is NOT equivalent. And the code that I gave with the single try catch block IS equivalent.
>> This added flexibility, BTW, is another good reason for having >> exceptions > > What added flexibility? I'm confused there. The added flexibility of being able to either immediately exit the method upon an exception, or to just chug along anyway. If you work only with unchecked exceptions and never catch them, then you are forced to always have the first behaviour, of always exiting.
> Ok, let's look at how to solve the code duplication issue. > [quoted text clipped - 37 lines] > Alert me if I missed something - I started posting this BEFORE I looked > at the time. This is just my personal opinion, but the code looks like it's getting more and more complicated. It seems like you're fighting the language, rather than working with it. It's like "goto" statements. They're generally frowned upon, but there are some algorithms which are more easily expressed with them than without.
When chosing between a language with goto statements versus a language without, you're deciding wether the benefit of having the expressive power of a goto statement is worth the drawback of trying to maintain code where goto statements are mis-used.
In the example program we're working with, I think exceptions ARE worth the extra expressive power.
- Oliver
ricky.clarkson@gmail.com - 16 Dec 2005 04:44 GMT <code> public mainMethod() { IntegerParseResult ipr=LessExceptions.parseInt("foo"); if (ipr.hasValue()) methodA(ipr.getValue());
ipr=LessExceptions.parseInt("25"); if (ipr.hasValue()) methodB(ipr.getValue());
ipr=LessExceptions.parseInt("-42"); if (ipr.hasValue()) methodC(ipr.getValue()); } </code>
I think you misread this code.
Just a snippet:
if (ipr.hasValue()) methodA(ipr.getValue());
If ipr has a value, then methodA will not throw an IllegalStateException, and mainMethod will continue happily. If ipr does not have a value, then methodA will not be executed, and mainMethod will continue happily.
At no point in that method is an IllegalStateException expected.
So, my three try blocks ARE equivalent to that code, and your one try block ISN'T equivalent to that code. There is as much code duplication in the three try blocks version as there is in the version quoted above (in this post).
I could equally well (or badly!) apply the Runnable idea to the 3 try blocks, and get equally verbose code. I agree it probably isn't as expressive as it could be, but sometimes duplicating code leads to more expressive code.
So the added flexibility that you mention is already there anyway, so it's not added at all.
> When chosing between a language with goto statements versus a language > without, you're deciding wether the benefit of having the expressive power > of a goto statement is worth the drawback of trying to maintain code where > goto statements are mis-used. Not quite. It is possible to use a language without using all of its features. That's why many projects/companies have coding standards, and why tools like CheckStyle exist. Many programmers choose NOT to use some features. I choose not to use autoboxing, subclassing, non-final parameters, instanceof and casts (though these last two are still present, but diminishing). If goto were present, I wouldn't choose another language. I would just not use goto.
> In the example program we're working with, I think exceptions ARE worth > the extra expressive power. The extra expressive power seems to be lost to boilerplate code (lots of try..catch blocks) to do the same thing as the program we're working with, so I disagree there.
Oliver Wong - 16 Dec 2005 20:28 GMT > I think you misread this code. You're right, I did. My bad, sorry.
>> When chosing between a language with goto statements versus a language >> without, you're deciding wether the benefit of having the expressive [quoted text clipped - 10 lines] > still present, but diminishing). If goto were present, I wouldn't > choose another language. I would just not use goto. I guess we come from different backgrounds. Because of my line of work (compiler tools), when I am "working with" a certain programming language, I have to be ready to deal with every possible legal construct from that language. I guess one of the reasons I like Java so much is that I'm very thankful it doesn't have goto statements (among other reasons).
These experiences may have inadvertently been influencing my feelings during this thread.
- Oliver
Jonathan Bartlett - 12 Dec 2005 19:04 GMT > If this is your need that probably means that you have to change your > code (for example, you can make methods out of your computations). > If you don't, have a look at break and continue. I personally never use > them (I consider them mostly an extreme solution), but that's what they > are for I was actually looking for a means of a quick escape from deeply-recursive functions. Just throw the exception to exit the recursion.
Jon
Oliver Wong - 12 Dec 2005 20:06 GMT > I was actually looking for a means of a quick escape from deeply-recursive > functions. Just throw the exception to exit the recursion. This sounds like a "Bad Idea".
Does your recursive function return a value? Does it modify some other data structure? You might be able to "get out of the recursion" more cleanly by using a "return" statement.
- Oliver
ricky.clarkson@gmail.com - 12 Dec 2005 20:26 GMT All recursive operations can be written as iterative. If stack unwinding irritates you, feel free to rewrite this algorithm to use iteration.
Chris Uppal - 12 Dec 2005 20:56 GMT > All recursive operations can be written as iterative. If stack > unwinding irritates you, feel free to rewrite this algorithm to use > iteration. Having spent the better part of two days recently rewriting a deeply recursive algorithm into a pure (no local variables) iterative formulation, and /NEVER/ wanting to do so again, I cannot but feel that this poor advice...
-- chris
Roedy Green - 12 Dec 2005 22:01 GMT On Mon, 12 Dec 2005 20:56:01 -0000, "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly quoted someone who said :
>Having spent the better part of two days recently rewriting a deeply recursive >algorithm into a pure (no local variables) iterative formulation, and /NEVER/ >wanting to do so again, I cannot but feel that this poor advice... Brings back memories. Very early in my career I converted a recursive Quicksort into non-recursive FORTRAN. What a nightmare. Recursion really simplifies some algorithms. I could not believe how much Fortran it took to do the same thing as a few lines of Journal of the ACM Algol.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
Chris Uppal - 13 Dec 2005 10:13 GMT [me:]
> > Having spent the better part of two days recently rewriting a > > deeply recursive algorithm into a pure (no local variables) [quoted text clipped - 3 lines] > Brings back memories. Very early in my career I converted a recursive > Quicksort into non-recursive FORTRAN. What a nightmare. I was praying for Gosling to descend from on high and bless us with Sather-style co-routines/iterators. Didn't happen...[*]
> Recursion > really simplifies some algorithms. I could not believe how much > Fortran it took to do the same thing as a few lines of Journal of the > ACM Algol. According to Hoare's ACM award speach, "The Emperor's Old Clothes", he orginally devised Quicksort in a non-recursive form (which made it tricky to explain) It was only when he /subsequently/ learned about recursion (at course on Algol 60 tutored by Naur, Dijkstra, and Landin !) that he found the elegant presentation.
-- chris
([*] Wouldn't have helped much anyway 'cos I wasn't working in Java, but why spoil the story ;-)
Mike Schilling - 14 Dec 2005 06:13 GMT > On Mon, 12 Dec 2005 20:56:01 -0000, "Chris Uppal" > <chris.uppal@metagnostic.REMOVE-THIS.org> wrote, quoted or indirectly [quoted text clipped - 11 lines] > Fortran it took to do the same thing as a few lines of Journal of the > ACM Algol. Back in college I took an course where the textbook used Fortran and actually implemented recursive algorithms in Fortran:
1. Declare a really big array to be used as a stack. 2. Declare labels for all the places a recursive call could be made from. 3.. Implement a recursive call by A. copying all local variables to the next available slots in the array B. copying the "index" of the next statement to the array C. Update the current array index D. GO TO the start of the subroutine 4. Implement a possibly recursive return by A. If the array is now empty, return B. Otherwise, restore the saved local variables, update the array index, and use a computed GO TO to return to the site of the "call".
Horrible, isn't it?
Roedy Green - 14 Dec 2005 06:56 GMT On Wed, 14 Dec 2005 06:13:25 GMT, "Mike Schilling" <mscottschilling@hotmail.com> wrote, quoted or indirectly quoted someone who said :
>Back in college I took an course where the textbook used Fortran and >actually implemented recursive algorithms in Fortran: Today's students use methods recursively without any sense of awe. Consider that early machines had no stacks to support recursion. Even the IBM 370 had no stacks. In PL/I you had to declare methods RECURSIVE which then used an alternate less efficient calling convention. I don't know about today, but originally FORTRAN and COBOL had no recursion or threads for that matter.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
Luc The Perverse - 14 Dec 2005 09:39 GMT > On Wed, 14 Dec 2005 06:13:25 GMT, "Mike Schilling" > <mscottschilling@hotmail.com> wrote, quoted or indirectly quoted [quoted text clipped - 9 lines] > convention. I don't know about today, but originally FORTRAN and COBOL > had no recursion or threads for that matter. My age group may be the last to have experienced this type of programming environment (back in the days of GW-Basic)
I don't know how young you define "kids" but I imagine I would probably be included. It's not completely lost :)
-- LTP
:) Roedy Green - 12 Dec 2005 21:59 GMT On Mon, 12 Dec 2005 13:04:37 -0600, Jonathan Bartlett <johnnyb@eskimo.com> wrote, quoted or indirectly quoted someone who said :
>I was actually looking for a means of a quick escape from >deeply-recursive functions. Just throw the exception to exit the recursion. Even if you did, it would not be quick. An exception interpretively combs the stack looking for a handler. Conceptually it looks as though it pops the stack in one fell swoop, but if you benchmark the code I think you will find it faster to just return recursively.
You might enjoy Abundance which has a feature to jaunt( leap backward in time to a previous execution checkpoint). It does that very rapidly by copying a stack snapshot in as the real one and restoring a few crucial system variables.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
Jonathan Bartlett - 13 Dec 2005 15:49 GMT >>I was actually looking for a means of a quick escape from >>deeply-recursive functions. Just throw the exception to exit the recursion. [quoted text clipped - 3 lines] > it pops the stack in one fell swoop, but if you benchmark the code I > think you will find it faster to just return recursively. Really? I would have thought that they would have included a dynamic link in the stack frame.
> You might enjoy Abundance which has a feature to jaunt( leap backward > in time to a previous execution checkpoint). It does that very rapidly > by copying a stack snapshot in as the real one and restoring a few > crucial system variables. Actually, my question was prompted by Scheme's "call-with-current-continuation" feature. I'm looking for a good method to introduce the feature, and was looking for similarities in other languages. Before going whole-hog into continuations, I wanted to show an example of non-local exits in a more familiar language. However, I didn't want to teach a wholly bad technique.
Continuations are amazingly powerful entities, and can be used to emulate:
* threads * generators * backtracking/logic programming * exceptions * general non-local exits * traditional program control in a web environment * dynamic variables * any other structured, non-local control feature
Exceptions are essentially very, very restricted continuations. So, I thought a good way to introduce continuations is to introduce the related concept in Java. However, it seems that I may need to find another language with less exception overhead. Or perhaps I could try Hawtin's suggestion of fillInStackTrace.
Also, since the discussion has turned to the use of recursion-vs-iteration, I thought I'd throw my own two cents into the discussion:
http://www-128.ibm.com/developerworks/linux/library/l-recurs.html
Jon ---- Learn to program using Linux assembly language http://www.cafeshops.com/bartlettpublish.8640017
Chris Uppal - 14 Dec 2005 11:01 GMT > > An exception interpretively > > combs the stack looking for a handler.[...] > > Really? I would have thought that they would have included a dynamic > link in the stack frame. Java's bytecode-level representation of exception handlers is set up very obviously for zero-cost try blocks. That's to say that /entering/ a try block has zero overhead. The downside, of course, is that if an exception is actually thrown, then finding and invoking the handler is not as cheap -- isn't even constant-time.
Implementation are free to implement throw/catch how they like, but since the hardest part of doing zero-cost try blocks is creating the stack maps, and in Java bytecode the compiler is required to do that work for you, I think it would be odd for a "normal" JVM implementations to use any other technique.
-- chris
Thomas Hawtin - 12 Dec 2005 20:32 GMT > "Sometimes developers decide to use exception for flow-control (i.e. to > throw an exception once a certain condition is met). The generation of [quoted text clipped - 6 lines] > > (1) is this still true? Is a stack trace still expensive? That article is less than two years old. Yes, it appears to still be true. It is apparently something not considered worth spending time on optimising. IIRC, I measured around ten or twenty thousand cycles with a shallow stack. The bigger the stack, the more work to do.
> (2) do all exceptions do this? For example, if I just inherit from > "Throwable" rather than "Exception" is a stack trace still generated? UTSL. If you look at the source to Throwable, you can see it calling fillInStackTrace.
> (3) is there any way around this? Override fillInStackTrace or use the same exception over again.
I timed 1.5 (or 1.4?) with -server in a loop catching an exception thrown through an interface. The benchmark got optimised away.
> The reason I'm asking is that exceptions would seem to be a very good > way to implement early-exit from certain deeply-nested computations. Probably not a good idea. Labeled break is good within the same method. You can probably rearrange the algorithm to make the exception unnecessary.
In my years of Java programming I have never (seriously) used an exception that way. Mind you when I write recursive code, I tend to rewrite it properly before the first compile.
Tom Hawtin
 Signature Unemployed English Java programmer http://jroller.com/page/tackline/
Roedy Green - 12 Dec 2005 21:31 GMT On Mon, 12 Dec 2005 08:57:39 -0600, Jonathan Bartlett <johnnyb@eskimo.com> wrote, quoted or indirectly quoted someone who said :
>(1) is this still true? Is a stack trace still expensive? Every time an exception is thrown the raw data to print a stack trace has to be collected from the stack, interpretively wending its way from top to bottom. It has to collect it before the exception destroys the stack popping in off seeking a handler. There is even more data collected that typically printed. see http://mindprod.com/jgloss/trace.html
It takes several orders of magnitude more time that a simple flow of control jump. Don't use exceptions for exceptional conditions.
I discovered that way back in 1969 when I decided to use PL/I ON units for flow control, just to experiment. I could not believe how slow it was.
 Signature Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching.
ricky.clarkson@gmail.com - 12 Dec 2005 21:44 GMT Chris,
Just because changing a recursive implementation into an iterative implementation is awkward, doesn't mean that the iterative version is wrong, or that it is bad advice to suggest to do so.
If the poster had written in an iterative way originally then I don't think there'd be an issue.
I know from my own experience that changing recursive to iterative can be a real pain, I've done it for something non-trivial.
I've never heard of this 'pure iterative' concept before, so I'm unsure why you would aim to have no local variables. I've probably misunderstood.
Chris Uppal - 13 Dec 2005 08:48 GMT > Chris, I take it you are replying to me. The threading seems to be screwed up and you haven't actually quoted anything directly.
> Just because changing a recursive implementation into an iterative > implementation is awkward, doesn't mean that the iterative version is > wrong, or that it is bad advice to suggest to do so. It does if any of the following apply:
1) the non-recursive expression of the algorithm is significantly harder to read/understand/maintain than the recursive form.
2) the time taken to remove the recursion is greater than is justified by removing the exception hack.
3) a recursive form, but without the exception hack, would be acceptably clear.
My point is that it seems likely (to me) that one or another of the above would apply.
> I've never heard of this 'pure iterative' concept before, so I'm unsure > why you would aim to have no local variables. I've probably > misunderstood. My fault. "pure iteration" isn't a recognised technical term (it would be nice though...). I was converting a highly recursive search algorithm to a form where it could be used to iterate over the solutions with an external iterator like a java.util.Iterator. That meant that all the state used by the algorithm had to be stored in the iteration object; e.g. I couldn't use local variables in a for-loop, which made it a little bit trickier[*].
-- chris
[*] Though what really threw me was that the recursive form used 2 looping variables (plus the recusion variables), but the iterative form only used one -- and not the same one, at that...
ricky.clarkson@gmail.com - 13 Dec 2005 10:15 GMT A trivial iterative thing I wrote some time ago was a BreadthFirstIterator and a DepthFirstIterator for a Tree. While depth first searching is usually implemented recursively (and could have been for my use too, via a passed-in Runnable), I found the resulting iterative design more client-programmer friendly.
I wouldn't go so far as to say recursion was an antipattern, or even a code smell, but I do find it easier to *use*, if not *write*, code that works iteratively. Both approaches are just as flexible, but iteration *looks* more flexible.
There isn't enough information from the original poster, so I wouldn't like to speculate, but in most naturally-recursive (whatever that is!) operations, it seems against the grain to want to bail out early. My speculation (I said I wouldn't like to do that!) is that the algorithm is probably better written iteratively.
In software development, time taken to implement a change isn't normally as important as the effects of that change on the simplicity of the design. That is; DoTheSimplestThingThatCouldPossiblyWork[1] means the simplest, not the fastest.
[1] http://c2.com/cgi/wiki?DoTheSimplestThingThatCouldPossiblyWork
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|