🚀 go-pugleaf

In article <4l5d2q$22v@solutions.solon.com> I noted:
>>... an implementation may, but is not required to, verify that each
>>subscript is in range ...

In article <4lbaon$llc@solutions.solon.com> ct <ct@ecs.ox.ac.uk> wrote:
>Eh? Surely that's impossible at compile time? Computed subscripts cannot be
>bound checked in general.

True, though many can -- for instance:

	for (i = 0; i < n; i++)
		... use a[i] without modifying i...

only requires proving that for all i, 0 <= i < n is valid.  Since 0
valid by definition, if n is a valid constant, the proof is complete.

>Or did you mean they do range checking at run-time?

They can.

>A different proposition entirely, and one which imposes nasty overheads
>all over the place.

Again, a clever compiler can mitigate these.  For instance, if `n'
above is not constant, a single pre-loop verification (that n >=
0 and n-1 is in range -- if n is unsigned or the most negative int,
both tests may be necessary) would suffice.  (If n is *not* in
range, the compiler must analyze further, in case the loop does
not run to completion.)

Some C systems that are sold as debugging aids add such overhead
freely, and people do buy these systems.  It often turns out that
spending many computer cycles (which may often take several whole
minutes!) is cheaper than spending a couple of programmer hours
searching for stray pointers or broken indices. :-)
-- 
In-Real-Life: Chris Torek, Berkeley Software Design Inc
El Cerrito, CA	Domain:	torek@bsdi.com	+1 510 234 3167