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.
|
