Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #23219

Re: Variable-length arrays: should they be used at all?

Show all headers | View raw

gwowen <gwowen@gmail.com> writes:

> On Jul 7, 2:11 am, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> gwowen <gwo...@gmail.com> writes:
>> > On Jul 5, 10:55 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
>> > wrote:
>>
>> >> > But you can do a static analysis.
>>
>> >> Once you've solved the Halting Problem!
>>
>> > You only need solve the Halting Problem if you need to do static
>> > analysis using the same algorithm on arbitrary programs / inputs.
>> > Algorithmically determining the stack usage of a small finite number
>> > of  programs / modules with constrained inputs is very much *not* the
>> > Halting Problem.
>>
>> No program can say what others will do.  Now I won't
>> just assert that, I'll prove it to you.  We will see
>> that although you might work til you drop, no code
>> can decide which others will stop.
>
> TRUE: "no code can decide which others will stop"
> FALSE: "Given a program, it is impossible to determine whether it will
> stop"
>
> Static analysis is not the Halting Problem, because we do not require
> our methods of static analysis to work on arbitrary programs, and in
> fact, as good programmers, we structure our code not only to make
> static analysis possible  but, whenever possible, to make it
> straightforward.
>
> So the generality of the Halting Problem does not preclude the
> possibility of specific static analysis.
>
> For example, let me provide a counterexample to your assertion that
> doing static analysis requires solving the Halting Problem.
>
> This non-pathological program:
>
> int main(int,char**)
> {
>   return(0);
> }
>
> terminates.
>
> I don't need to solve the Halting Problem to determine *that*
> *specific* case, and no construction of pathological counter-examples,
> which prove the impossibility of deciding the Halting Problem *in
> general* say anything about *specific* programs.
>
> inline int mysum(x,n)
> {
>    if(n==0) return(x);
>    return mysum(x+n,n-1);
> }
>
> int main()
> {
>     printf("%d\n",mysum(0,10));
> }
>
> We know how deep that program will recurse. If we know the stack
> limits, we know whether it will overflow. A suitably excitable
> compiler could even unroll the loop and statically calculate the
> answer at compile time.
>
> The general uncomputability of the Halting Problem does not preclude
> specific static analysis.

Certainly it is true that, given a finite set S of programs,
there exists a program P that can decide whether program s
will terminate, for all programs s in S.  (I'm talking here
about the question of running s starting on a blank tape,
ie, with no input, but the same result holds if an input,
or a finite set of inputs, is specified in each case (and
program inputs are always finite).)

However, saying that P exists and saying that we know how
to write program P are two very different things.  For
example, consider the set S consisting of one program
(written here in a C-ish pseudocode)

   n = 6;
   do {
      n = n + 2;
   } while(  there are two primes that add up to (n)  );

   print "A counterexample for Golbach's conjecture is", n;

Here the variables and the arithmetic is understood to encompass
integers that can be as large as needed.  Note also that it's
easy to write the test that controls the loop exit in a way that
obviously terminates.  The only question is, is there an even n
(greater than six) for which n is not the sum of two primes?
No one knows the answer to this question.  So, at least for the
present, no one knows how to write the program P that decides
(in finite time) whether the above program will terminate.

In a technical sense what you say is right:  if the set of
programs under consideration is known in advance and finite, that
is not the same as the Halting Problem, and is theoretically
decidable.  However, that statement doesn't provide any guidance
as to how we might try to write a static analysis program that
would actually work, or even a guarantee that we will be able to
find one in a finite time -- as opposed to just knowing that one
exists even though we have no idea what it is or how to find it.
The theoretical result is no help to the practical result being
sought.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 15:28 +0100
  Re: Variable-length arrays: should they be used at all? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-26 11:54 -0400
  Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-26 21:05 +0200
    Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 21:04 +0100
      Re: Variable-length arrays: should they be used at all? Keith Thompson <kst-u@mib.org> - 2012-06-26 13:09 -0700
        Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-27 17:50 +1200
          Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 07:57 +0200
            Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-06-27 00:49 -0700
            Re: Variable-length arrays: should they be used at all? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-06-27 13:50 +0100
              Re: Variable-length arrays: should they be used at all? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-27 10:21 -0400
                Re: Variable-length arrays: should they be used at all? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-06-27 19:56 +0100
          Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:55 +0300
            Re: Variable-length arrays: should they be used at all? Andrew Cooper <amc96@cam.ac.uk> - 2012-07-05 23:37 +0100
              Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 16:53 -0700
            Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-06 18:26 +1200
              Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-07 17:37 +0300
                Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-08 08:03 +1200
            Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-07-06 02:58 -0700
              Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 18:11 -0700
                Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-07-09 02:33 -0700
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-09 11:35 -0700
                Re: Variable-length arrays: should they be used at all? Ike Naar <ike@iceland.freeshell.org> - 2012-07-09 22:33 +0000
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-10 10:52 -0700
                Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-07-09 12:03 -0700
                Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-10 09:19 +1200
        Re: Variable-length arrays: should they be used at all? Gareth Owen <gwowen@gmail.com> - 2012-06-27 07:25 +0100
    Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 07:10 +0200
      Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 20:48 +0200
  Re: Variable-length arrays: should they be used at all? Jens Gustedt <jens.gustedt@loria.fr> - 2012-06-26 21:13 +0200
    Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 20:47 +0100
      Re: Variable-length arrays: should they be used at all? Keith Thompson <kst-u@mib.org> - 2012-06-26 13:05 -0700
      Re: Variable-length arrays: should they be used at all? David Resnick <lndresnick@gmail.com> - 2012-06-26 13:51 -0700
        Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-06-26 17:10 -0700
        Re: Variable-length arrays: should they be used at all? Gareth Owen <gwowen@gmail.com> - 2012-06-27 07:27 +0100
        Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-27 20:23 +0100
  Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-27 11:20 -0700
    Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-28 09:35 +1200
      Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-27 17:23 -0700
        Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-28 13:06 +1200
          Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-29 10:48 -0700
            Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-30 21:58 +1200
              Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-06-30 03:37 -0700
              Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-01 19:31 -0700
            Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:54 +0300
              Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 17:58 -0700
        Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:49 +0300
          Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 16:38 -0700
            Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-07 18:00 +0300
              Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-07 12:40 -0700
                Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-08 02:54 +0000
                Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-07-08 13:33 +0200
                Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-08 22:18 +0000
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-09 10:57 -0700
                Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-09 21:38 +0000
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-10 11:12 -0700
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-08 11:28 -0700

csiph-web