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

Groups > comp.lang.c > #22800 > unrolled thread

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

Back to article view | Back to comp.lang.c

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#22800 — Variable-length arrays: should they be used at all?

In the thread "Learning C as an existing programmer", an interesting 
discussion arose over the use of variable-length arrays (VLAs), specifically 
the dangers they pose by not providing a way to detect potential memory 
allocation bugs. 

GCC's page on variable-length arrays says nothing about what to expect when 
a VLA is too large to handle.[1]  In addition, what has been said in GCC's 
mailing list about avoiding segfaults induced by huge VLAs isn't very 
reassuring.[2]

With this in mind, and considering that VLAs were made optional in C11, is 
it a good idea to simply refuse using them?


Rui Maciel

[1] http://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html
[2] http://gcc.gnu.org/ml/gcc/2007-01/msg00179.html

[toc] | [next] | [standalone]

#22804

On 6/26/2012 10:28 AM, Rui Maciel wrote:
> In the thread "Learning C as an existing programmer", an interesting
> discussion arose over the use of variable-length arrays (VLAs), specifically
> the dangers they pose by not providing a way to detect potential memory
> allocation bugs.
>
> GCC's page on variable-length arrays says nothing about what to expect when
> a VLA is too large to handle.[1]  In addition, what has been said in GCC's
> mailing list about avoiding segfaults induced by huge VLAs isn't very
> reassuring.[2]
>
> With this in mind, and considering that VLAs were made optional in C11, is
> it a good idea to simply refuse using them?

     It may come down to personal preference, and to the "kind" of
programming you're doing.  VLA's are a great notational convenience,
especially for multi-dimensional arrays.  Also, they relieve the
coder of worrying about releasing memory, which can be a help if
there are multiple ways to exit the allocating block.

     The disadvantage, of course, is that there is no portable way
to detect an allocation failure.  Even if the program is unable to
complete its work in the event of malloc() failure, the ability to
detect it allows the coder to arrange for a clean shutdown rather
than an abrupt ka-BOOM.  But undetectable allocation failure is
not unique to VLA's, as your reference [2] indicates: The problem
in that thread was an auto array of fixed size that happened to be
too large.  Pretty much any block might fail to allocate memory for
its auto variables, even if its own space requirement is modest: A
paltry four ints could be the straw that breaks the camel's stack.

     The fact that VLA's became optional with C11 may or may not
be important.  Support for IEEE floating-point has been optional
for years, but that doesn't seem to have stopped people from
relying on it.  What will happen to VLA support in future compilers
remains to be seen.[*]

     Perhaps a bigger issue than VLA's possible disappearance is
their tardy APpearance: C99 support has not been quick to arrive,
and even today it might not be unusual to encounter an implementation
that lacked VLA's.  Between "They may be going away" and "They're not
even here yet," VLA's might be seen as diminishing the portability
of code that uses them.

     Okay, so: The pros are notational convenience and relief from
some memory-management burden, the cons are additional chances for
ka-BOOM and possible portability/version issues.  Wrap it all up
in your own personal preference and your project's needs, and make
your own call.  Personally, I avoid 'em -- but YMMV.


     [*] I find it distressing that successive Standards seem to
be turning away from the principle expressed in the Rationale:

	"Beyond this two-level scheme [hosted and freestanding],
	no additional subsetting is defined for C, since the C89
	Committee felt strongly that too many levels dilutes the
	effectiveness of a standard."

That's from the C99 Rationale, but I think it's a paraphrase from
the original (which I saw once but don't have).  If the C11 Rationale
includes this text, it might be accused of being insincere.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#22817

Le 26/06/12 16:28, Rui Maciel a écrit :
> In the thread "Learning C as an existing programmer", an interesting
> discussion arose over the use of variable-length arrays (VLAs), specifically
> the dangers they pose by not providing a way to detect potential memory
> allocation bugs.
>
> GCC's page on variable-length arrays says nothing about what to expect when
> a VLA is too large to handle.[1]  In addition, what has been said in GCC's
> mailing list about avoiding segfaults induced by huge VLAs isn't very
> reassuring.[2]
>
> With this in mind, and considering that VLAs were made optional in C11, is
> it a good idea to simply refuse using them?
>
>
> Rui Maciel
>
> [1] http://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html
> [2] http://gcc.gnu.org/ml/gcc/2007-01/msg00179.html
>

VLAs are indispensable when you want to avoid unnecessary calls
to the expensive malloc function.

For instance if you have some structure X that is hidden as an opaque 
structure to avoid that client code

You can of course get the size of the hidden structure by calling a 
library function.

Example:

	int main(void)
	{
		char buffer[iList.GetSize(NULL)];
		List *L = (List *)&buffer[0];
		iList.InitList(L);

		// Here you use your list.
		
		iList.Clear(L);
		/// Here you do not need to call iList.Finalize since
		// you haven't allocated it with malloc
	}

The crucial call here is:
	char buffer[iList.GetSize(NULL)];

This allows tghe library to return the size of the structure WITHOUT 
disclosing its internal state. This is very important.

The alternatives are very bad since you would have to

#define SIZEOF_LIST_HEADER  56

and do not forget to update that each time your List structure changes.

[toc] | [prev] | [next] | [standalone]

#22824

jacob navia wrote:

> VLAs are indispensable when you want to avoid unnecessary calls
> to the expensive malloc function.

But what about the inability to gracefully recover from a memory allocation 
error?  If a VLA is defined with the wrong size at the wrong moment then it 
appears that it isn't possible to do anything about it, nor is it even 
possible to put in place any safeguard to avoid that.  In fact, are there 
any scenarios where a VLA defined with an arbitrary size is guaranteed to 
work as expected?


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#22828

Rui Maciel <rui.maciel@gmail.com> writes:
> jacob navia wrote:
>> VLAs are indispensable when you want to avoid unnecessary calls
>> to the expensive malloc function.
>
> But what about the inability to gracefully recover from a memory allocation 
> error?  If a VLA is defined with the wrong size at the wrong moment then it 
> appears that it isn't possible to do anything about it, nor is it even 
> possible to put in place any safeguard to avoid that.  In fact, are there 
> any scenarios where a VLA defined with an arbitrary size is guaranteed to 
> work as expected?

No (unless the implementation defines its own error-detection
mechanism).

But the same applies to old-style constant-size arrays.  If you declare

    double mat[100][100];

either at block scope or at file scope, there's no mechanism to detect
an allocation failure.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#22845

On 06/27/12 08:09 AM, Keith Thompson wrote:
> Rui Maciel<rui.maciel@gmail.com>  writes:
>> jacob navia wrote:
>>> VLAs are indispensable when you want to avoid unnecessary calls
>>> to the expensive malloc function.
>>
>> But what about the inability to gracefully recover from a memory allocation
>> error?  If a VLA is defined with the wrong size at the wrong moment then it
>> appears that it isn't possible to do anything about it, nor is it even
>> possible to put in place any safeguard to avoid that.  In fact, are there
>> any scenarios where a VLA defined with an arbitrary size is guaranteed to
>> work as expected?
>
> No (unless the implementation defines its own error-detection
> mechanism).
>
> But the same applies to old-style constant-size arrays.  If you declare
>
>      double mat[100][100];
>
> either at block scope or at file scope, there's no mechanism to detect
> an allocation failure.

But you can do a static analysis.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#22846

Le 27/06/12 07:50, Ian Collins a écrit :
> On 06/27/12 08:09 AM, Keith Thompson wrote:
>> Rui Maciel<rui.maciel@gmail.com>  writes:
>>> jacob navia wrote:
>>>> VLAs are indispensable when you want to avoid unnecessary calls
>>>> to the expensive malloc function.
>>>
>>> But what about the inability to gracefully recover from a memory
>>> allocation
>>> error?  If a VLA is defined with the wrong size at the wrong moment
>>> then it
>>> appears that it isn't possible to do anything about it, nor is it even
>>> possible to put in place any safeguard to avoid that.  In fact, are
>>> there
>>> any scenarios where a VLA defined with an arbitrary size is
>>> guaranteed to
>>> work as expected?
>>
>> No (unless the implementation defines its own error-detection
>> mechanism).
>>
>> But the same applies to old-style constant-size arrays.  If you declare
>>
>>      double mat[100][100];
>>
>> either at block scope or at file scope, there's no mechanism to detect
>> an allocation failure.
>
> But you can do a static analysis.
>

lcc-win was ported to a 16 bit Analog Devices chip with something like
40K RAM available.

There was no stack, and the stack was created by the compiler using
a memory array: this implied a static analaysis.

Recursion was forbidden (coudln't be analyzed well) and indirect
recursion was detected: function A calls B that calls C that calls A.

If you are doing that, VLA's are of course off limits. But, as far as
I know, recursion is allowed in C and nobody is screaming to
eliminate it because in some RAM constrained environments it could
lead to crashes.

We have to separate the C language from the implementations of C
in very constrained environments.

[toc] | [prev] | [next] | [standalone]

#22854

On Jun 27, 6:57 am, jacob navia <ja...@spamsink.net> wrote:

> Recursion was forbidden (coudln't be analyzed well) and indirect
> recursion was detected:

...

> recursion is allowed in C and nobody is screaming to
> eliminate it because in some RAM constrained environments it could
> lead to crashes.

Clearly, some people (e.g. the lcc authors) *are* eliminating
recursion - in certain cases - for *precisely* those reasons.

Like recursion, VLAs are (recursion is) fine as long as you *know* the
VLA length (recursion depth) is going to remain pretty small relative
to your stack.  If you know that, no problem.  If you don't, something
may blow in a horrible way.

[toc] | [prev] | [next] | [standalone]

#22861

jacob navia <jacob@spamsink.net> writes:
<snip>
> lcc-win was ported to a 16 bit Analog Devices chip with something like
> 40K RAM available.
>
> There was no stack, and the stack was created by the compiler using
> a memory array: this implied a static analaysis.
>
> Recursion was forbidden (coudln't be analyzed well) and indirect
> recursion was detected: function A calls B that calls C that calls A.

If recursion is forbidden, would it not be worthwhile having a single
static area for each function?  This is what some IBM compilers used to
do (and they may still do for all I know).

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#22863

On 6/27/2012 8:50 AM, Ben Bacarisse wrote:
> jacob navia <jacob@spamsink.net> writes:
> <snip>
>> lcc-win was ported to a 16 bit Analog Devices chip with something like
>> 40K RAM available.
>>
>> There was no stack, and the stack was created by the compiler using
>> a memory array: this implied a static analaysis.
>>
>> Recursion was forbidden (coudln't be analyzed well) and indirect
>> recursion was detected: function A calls B that calls C that calls A.
>
> If recursion is forbidden, would it not be worthwhile having a single
> static area for each function?  This is what some IBM compilers used to
> do (and they may still do for all I know).

     A shared stack would use less memory, unless there was some
execution path in which all functions were active simultaneously.

     Per-function (or per-block) static storage might be attractive
on machines where stack-relative addressing is cumbersome.  I recall
that Turbo Pascal on the Z80 used this technique.  It allowed
recursive functions and procedures, though: You told the compiler
which could be called recursively, it generated prologue and
epilogue code to swap the static data out to a stack and back, and
each invocation re-used the same static area. This wouldn't work
for C, of course, since you wouldn't want an auto variable to be
moved after you'd formed a pointer to it ...

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#22884

Eric Sosman <esosman@ieee-dot-org.invalid> writes:

> On 6/27/2012 8:50 AM, Ben Bacarisse wrote:
>> jacob navia <jacob@spamsink.net> writes:
>> <snip>
>>> lcc-win was ported to a 16 bit Analog Devices chip with something like
>>> 40K RAM available.
>>>
>>> There was no stack, and the stack was created by the compiler using
>>> a memory array: this implied a static analaysis.
>>>
>>> Recursion was forbidden (coudln't be analyzed well) and indirect
>>> recursion was detected: function A calls B that calls C that calls A.
>>
>> If recursion is forbidden, would it not be worthwhile having a single
>> static area for each function?  This is what some IBM compilers used to
>> do (and they may still do for all I know).
>
>     A shared stack would use less memory, unless there was some
> execution path in which all functions were active simultaneously.

Very true, and it seems that memory is scarce in this example so it's
not likely to worthwhile.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#23096

Ian Collins <ian-news@hotmail.com> writes:
> On 06/27/12 08:09 AM, Keith Thompson wrote:
> > Rui Maciel<rui.maciel@gmail.com>  writes:
> >> jacob navia wrote:
> >>> VLAs are indispensable when you want to avoid unnecessary calls
> >>> to the expensive malloc function.
> >>
> >> But what about the inability to gracefully recover from a memory allocation
> >> error?  If a VLA is defined with the wrong size at the wrong moment then it
> >> appears that it isn't possible to do anything about it, nor is it even
> >> possible to put in place any safeguard to avoid that.  In fact, are there
> >> any scenarios where a VLA defined with an arbitrary size is guaranteed to
> >> work as expected?
> >
> > No (unless the implementation defines its own error-detection
> > mechanism).
> >
> > But the same applies to old-style constant-size arrays.  If you declare
> >
> >      double mat[100][100];
> >
> > either at block scope or at file scope, there's no mechanism to detect
> > an allocation failure.
> 
> But you can do a static analysis.

Once you've solved the Halting Problem!

Phil
-- 
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

[toc] | [prev] | [next] | [standalone]

#23099

On 05/07/2012 22:55, Phil Carmody wrote:
> Ian Collins <ian-news@hotmail.com> writes:
>>
>> But you can do a static analysis.
> 
> Once you've solved the Halting Problem!
> 
> Phil
> 

Computers are finite state machines, so the Halting Problem need not be
solved.  The Halting Problem argument only applies to infinite state
machines, as any finite state machine can be tested by providing every
permutation of input, single stepping it, and asserting that the global
state never repeats for a unique input.

~Andrew

[toc] | [prev] | [next] | [standalone]

#23120

Andrew Cooper <amc96@cam.ac.uk> writes:

> On 05/07/2012 22:55, Phil Carmody wrote:
>> Ian Collins <ian-news@hotmail.com> writes:
>>>
>>> But you can do a static analysis.
>> 
>> Once you've solved the Halting Problem!
>> 
>> Phil
>> 
>
> Computers are finite state machines, so the Halting Problem need not be
> solved.  The Halting Problem argument only applies to infinite state
> machines, as any finite state machine can be tested by providing every
> permutation of input, single stepping it, and asserting that the global
> state never repeats for a unique input.

This reasoning is wrong both in principle and in practice.

It's wrong in practice because the number of possible states is
so large there is no way to keep track of which ones have been
seen for even very small processors -- four 32-bit registers, for
example, already gives a state space of 2**128 states, and that's
not even counting any RAM.  Computers are treated like Turing
Machines because the amount of state they have is so large that
treating them like FSMs is not practicable.

It's wrong in principle because computers do input/output, and that
expands the state available without any predetermined bound.  There
is no reason a program couldn't ask someone to plug in a USB drive,
or two, or twenty, or open a network connection to "the cloud",
etc.  Without a fixed bound on the state, what we have is no longer
a FSM.

[toc] | [prev] | [next] | [standalone]

#23101

On 07/ 6/12 09:55 AM, Phil Carmody wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>> On 06/27/12 08:09 AM, Keith Thompson wrote:
>>>
>>> But the same applies to old-style constant-size arrays.  If you declare
>>>
>>>       double mat[100][100];
>>>
>>> either at block scope or at file scope, there's no mechanism to detect
>>> an allocation failure.
>>
>> But you can do a static analysis.
>
> Once you've solved the Halting Problem!

Don't you remember the tool I wrote to analyse the base station code way 
back when??

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#23158

Ian Collins <ian-news@hotmail.com> writes:
> On 07/ 6/12 09:55 AM, Phil Carmody wrote:
> > Ian Collins<ian-news@hotmail.com>  writes:
> >> On 06/27/12 08:09 AM, Keith Thompson wrote:
> >>>
> >>> But the same applies to old-style constant-size arrays.  If you declare
> >>>
> >>>       double mat[100][100];
> >>>
> >>> either at block scope or at file scope, there's no mechanism to detect
> >>> an allocation failure.
> >>
> >> But you can do a static analysis.
> >
> > Once you've solved the Halting Problem!
> 
> Don't you remember the tool I wrote to analyse the base station code
> way back when??

I remember the base station code halting, so presumably your code was
just "echo 1" or similar.

Phil
-- 
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

[toc] | [prev] | [next] | [standalone]

#23187

On 07/ 8/12 02:37 AM, Phil Carmody wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>> On 07/ 6/12 09:55 AM, Phil Carmody wrote:
>>> Ian Collins<ian-news@hotmail.com>   writes:
>>>> On 06/27/12 08:09 AM, Keith Thompson wrote:
>>>>>
>>>>> But the same applies to old-style constant-size arrays.  If you declare
>>>>>
>>>>>        double mat[100][100];
>>>>>
>>>>> either at block scope or at file scope, there's no mechanism to detect
>>>>> an allocation failure.
>>>>
>>>> But you can do a static analysis.
>>>
>>> Once you've solved the Halting Problem!
>>
>> Don't you remember the tool I wrote to analyse the base station code
>> way back when??
>
> I remember the base station code halting, so presumably your code was
> just "echo 1" or similar.

:)


-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#23104

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.

[toc] | [prev] | [next] | [standalone]

#23127

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

Imagine we have a procedure called P, that will snoop in
the source code of programs to see there aren't infinite
loops that go round and around; and P prints the word
"Fine" if no looping is found.

You feed in your code, and the input it needs, and then
P takes them both and it studies and reads, to compute
whether things will all end as they should (as opposed 
to all loopy the way that they could).

Well, the truth is that P cannot possibly be, because
if you wrote it and gave it to me, I could use P to
set up a logical bind that would shatter your reason
and scramble your mind.

Here's the trick I would use, and it's simple to do.
I'd define a procedure -- we'll name the thing Q --
that would take any program and call P (of course) to
tell if it looped, by reading the source.

And if so, Q would simply print "Loop" and then stop;
but if no, Q would go right back up to the top, and start
off again, looping endlessly back, til the universe dies
and is frozen and black.

And this program called Q wouldn't stay on the shelf;
I would run it, and fiendishly feed it itself.  What
behaviour results when I do this with Q?  When it reads
its own source, just what will it do?

If P warns of loops, Q will print "Loop" and quit; yet
P is supposed to speak truly of it.  So if Q's going to
quit, then P should say, "Fine" -- which will make Q go
back to its very first line.

No matter what P would have done, Q will scoop it:  Q
uses P's output to make P look stupid.  If P gets
things right then it lies in its tooth; and if it
speaks falsely, it's telling the truth!

I've created a paradox, neat as can be, simply by using
your putative P.  When you assumed P you stepped into a
snare; this assumption has led you right into my lair.

How can we escape from this logical mess?  I don't have
to tell you -- I'm sure you can guess!  By reductio,
there cannot possibly be a procedure that acts like the
mythical P.

You can never discover mechanical means for predicting
the acts of computing machines.  Such things simply
cannot be done, so we users must find our own bugs:
our computers are losers.





(Original written by Geoffrey K. Pullum, University of
 Edinburgh.  He later wrote a revised version, but I
 like the original better, even though it has "bugs"
 in it;  the more recent version is available at:

   http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
)

[toc] | [prev] | [next] | [standalone]

#23213

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.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web