Re: Detecting endless recursion?

Torben Ęgidius Mogensen <torbenm@diku.dk> wrote:
>>
>> 1: Unless tail recursion removal is specified in the language, you are
>> immediately relying on an implementation-dependent feature and so are
>> writing non-portable code. This is the same problem as relying on
>> garbage collection, writ small.
>
>Many languages (e.g., Scheme or SML) specify that tail-recursion must
>be done in constant space. These also specify GC or other automatic
>memory reclaiming method, so relying on both is no problem.


And many don't - such as Lisp, Fortran 90 or C++. But I think that
you have missed the point. In order to rely on the feature, the
language must specify WHEN it is used (for tail recursion, the
syntactic constructions that invoke it) and WHAT it does. The latter
is trivial for tail recursion, but very difficult indeed for garbage
collection, and rarely attempted.


My point isn't that either technique is unreasonable but that, if a
PORTABLE program is to use them, their PROPERTIES must be specified by
the LANGUAGE in enough detail to be usable. Similarly, if a program
is to be even CORRECT, any features that it uses that are not
specified by the language must be specified by the IMPLEMENTATION.


In my life, I have reported bugs hundreds of times to dozens of
vendors in half-specified constructions, and 90% of the time have had
the response "Because the standard says nothing about its details,
mere unusability is no bug." Remember that a language specification
is the conditions of a contract between implementor and programmer.


>Obviously, the programmer has to understand the limitations of both
>tail-recursion and GC. Since the original poster invented his own
>language, he is free to speficy what the assumptions are.


Right. And my point is that, in order to make them usable, he must
specify their properties in enough detail. "There shall be tail
recursion removal" is not a useful specification ....


>> 2: Recompile for debugging, or insert your own tracing of function
>> returns, and the program fails before it reaches the code you are
>> testing. The best 'solution' to this that I was told was to use a
>> supercomputer for debugging the codes you are intending to run on a
>> low-end PC :-)
>
>Now you're trolling. Scheme has many debugging tools that don't break
>tail-recursion (or GC).


I am afraid that YOU are. There is no way that ANY debugging tool can
display a full call chain, trap on specific returns and so on, unless
it keeps the relevant data. Whether it is is kept by the program or a
semi-separate debugger is irrelevant.


The problem I am referring to is one where tail recursion was used to
implement iteration - a standard technique. The program than ran in
(say) 16 MB, but failed after an hour or so in a way that tracing the
calls AND RETURNS was rather important. Unfortunately, maintaining
that data needed (say) 8 GB, and I didn't have it :-(


The root problem was that the program RELIED on that data NOT being
kept for its functionality, but that it had a design error where it had
slipped up by assuming that something was an invariant, and it wasn't.
Unfortunately, because of these, the naive solution of rewriting the
tail recursion as iteration made no difference! This was a simple
mistake, but was one where the programmer was led into that mistake
by his incorrect assumption that tail recursion removal is (a) always
good and (b) always available.


And denying that is the place at which I came in :-)


>> 3: Don't recompile for debugging, and try to unpick a dump, and you
>> are faced with the problem of failing in a utility function called
>> from everywhere and not a clue of how you got there. So you add some
>> tracing to find that out, and you mutually recurse into problem 2.
>
>Languages that requires you to look at coredumps to understand where
>you went wrong were outdated 20 years ago.


And ones that require you to run interactively to do so were, too.
There are MANY circumstances where investigations can be done only
post-hoc, including most of HPC, process control (not excluding Mars
missions), security-related work and so on.


For the past 35 years, I have held to the view that a competent language
implementation should not constrain how the user works more than
strictly necessary. It should PERMIT interactive debugging, the
creation and analysis of dumps (perhaps in its own format), the control
of what events constitute failure and the diagnostics to be produced on
failure, similar control of tracing and so on.


This is much easier to do than most people believe, but is surprisingly
heretical. In those 35 years, I have been flamed from at least half a
dozen dogmatic viewpoints. Few modern systems allow that flexibility,
which causes a LOT of wasted effort.




Regards,
Nick Maclaren.

Return to the comp.compilers page.
Search the comp.compilers archives again.