- Reversing a Linked List using Recursion - 1 Update
- RAII design question - 5 Updates
| Manfred <noname@invalid.add>: Jun 24 06:24PM +0200 On 06/22/2017 09:07 PM, Tim Rentsch wrote: > Manfred <noname@invalid.add> writes: >> On 6/20/2017 7:27 PM, Tim Rentsch wrote: [...] > separate translation unit (ie, so at least one stack frame is > needed in either case, rather than functions being expanded > inline). What can we say about what behavior we might observe? [...] > machine is concerned, the semantics in the two cases are > identical. Under the rules laid out in the language standard, > they are therefore completely interchangeable. No they are not. Even without practical considerations (which I will explain below), a formal look already sees clearly that there is a substantial difference between the two - look at the rules for automatic storage variables: In the iterative case the loop body is a block, and storage for variables declared inside the block is destroyed at the end of the block /before/ being recreated when re-entering the block. In the recursive case, storage for variables declared inside the block (the recursive function body) is destroyed at the end of the block /after/ recreating new variables by the recursive call (which is inside the block) So, in terms of the abstract machine there is a substantial difference between the two solutions in terms of data /storage/: for the the iterative case it is O(1) and for the recursive case it is O(n) Now, your point is based on the fact that the standard does not dictate a one to one relationship between storage and memory allocation, in fact it defines the storage duration as "minimum potential lifetime of the storage containing the object". But this is because the standard defines the behaviour of an /abstract/ machine. Real implementations deal with real memory constraints, and assuming that an implementation will allocate new storage at each loop is just perverse, and you know it. In fact, a > or neither is. The issue here is not one of correctness in the > language but a practical consideration related to quality of > implementation. Do you see what I mean when I say that? Others have already answered why your statement above is wrong. I will only add here another comment about language "correctness" (i.e. code which is legal according to the standard) and code correctness. C++ is not a language which is fool-proof, i.e. if you want to write correct C++ code, in addition to knowing the language rules, you have to know what you are doing. It is trivial to understand that, while it is true that code which is malformed (by the standard's rules) is also incorrect code, it is /not/ true that code which is legal (according to the standard's rules) is also guaranteed to be correct, in terms of the results it produces. In this case, code which can result in stack overflow is just wrong, even if it is syntactically and semantically correct (seems trivial to me, but appearently it needs saying). [...] > fact very much the opposite - I am advocating /informed/ use of > tail recursion, including automated static checks to ensure > things don't get out of hand. It depends on what you mean for informed use. Testing is definitely not enough, and the same applies to static tests (see below), if you do not also have formal proof of defined and bounded usage of stack space. This means a formal proof of defined and bounded recursion depth and stack frame size of each recursion. [...] > generated assembly to verify there are no recursive calls. It's > simple to use (one extra line in the makefile), and very effective > at weeding out bad cases. This only holds if you are delivering /compiled/ code, but in this case you are not delivering C++ code, you are delivering a machine executable. If you are delivering C++ source code, your own check of the compilation result does not guarantee the same result when your code will be compiled by your employer or by your customer (possibly with different compiler settings, or a different version or a different compiler itself or on a different machine or architecture). This is expecially true since you are relying on compiler behaviour which is /not/ dictated by the standard. More complicated algorithms (eg binary > scan is very good as a first line of defense - ie, most uses of > recursion can and should be written so they compile into assembly > that does not recurse. In addition to the above, others have already noted that a maintenance action on your code might change an iterative compilation into a recursive compilation (e.g. triggering a destructor call). If and when this happens, it is still your code's fault, because it is you who wrote the recursive C++ source. |
| leigh.v.johnston@googlemail.com: Jun 24 03:41AM -0700 Nonsense. There are not different sizes of infinity if infinities in question are unbounded. /Flibble |
| Ian Collins <ian-news@hotmail.com>: Jun 24 11:29PM +1200 > Nonsense. There are not different sizes of infinity if infinities in question are unbounded. Who or what are yo replying to? -- Ian |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Jun 24 03:12PM +0100 > Nonsense. There are not different sizes of infinity if infinities in > question are unbounded. As a statement in natural language, that's a defensible position. But if you mean that all pairs of infinite sets can be put into one-to-one correspondence with each other (the mathematician's meaning of "the same size"), then that's false. You may choose to define a set theory in which it is not false, but then you will have (a) a lots of work to do, and (b) some trouble with things like power sets and real analysis. -- Ben. |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jun 24 03:39PM +0100 On 24/06/2017 15:12, Ben Bacarisse wrote: > size"), then that's false. You may choose to define a set theory in > which it is not false, but then you will have (a) a lots of work to do, > and (b) some trouble with things like power sets and real analysis. Nope. /Flibble |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Jun 24 04:43PM +0100 >> which it is not false, but then you will have (a) a lots of work to do, >> and (b) some trouble with things like power sets and real analysis. > Nope. What, /all/ of those statements were wrong? You /don't/ think your statement was defensible? And you /do/ think every pair of infinite sets can be bijected? And you /don't/ think you can define a set theory where that is possible? At the very least, the last two are contradictory. Anyway, I'm happy to leave it that you disagree with something in my post and anyone who is still reading can pick what it is they think it might be. -- Ben. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment