Topic: range checking

topics > computer science > data > Group: type checking

consistency testing
debugging techniques
defensive programming
dynamic type checking
range data type
run-time assertions
variables for array bounds


The value of many variables is confined to a range of possible values. The typical example is index variables for arrays. Checking for range conformability provides early detection of program errors. Array index checking is widely implemented and many languages define a range predicate. Some languages, such as Pascal, allows a variable's value to be limited to a range. This works as long as the range is fixed over the entire program. Named ranges can guarantee matching index variables and array bounds by moving range checking to the compiler, but checking for correct variable modification still requires runtime range checks. (cbb 5/80)
Subtopic: range analysis up

Quote: can reduce the cost of runtime checking by a simple range-analysis system [»welsJ1_1978]
Quote: optimize range checks using strength reduction, code motion, and common subexpression elimination; reduced cost to 2% [»markV6_1982]

Subtopic: array bounds up

Quote: efficient array bound checking across procedure calls; reports name and dimension of erroneous array; uses source-to-source Fortran compiler and convex array regions [»nguyTV5_2005]
Quote: in Java, array bounds and object types are absolute; you can not lie about the identity of an object [»allmE7_2004]
Quote: Cyclone identified array bound violations in three benchmarks [»jimT6_2002]
Quote: check all pointer and array accesses with an extended safe pointer representation; 2-6x time cost, less than 2x space cost [»austTM6_1994]
Quote: CLU arrays do not contain uninitialized elements; they grow and shrink on either end with bounds checking as needed [»liskB_1996]
Quote: a covariant rule for subtyping arrays requires a run time type check for array stores; otherwise can copy a larger element into a smaller element [»deanD5_1996]
Quote: symbolic bounds analysis for static race detection, automatic parallelization, array bounds analysis, size of computed values; determines upper and lower bounds for array indices and pointers [»rugiR3_2005]

Subtopic: optimizing range checks up

Quote: optimize a program to eliminate redundant checks of array bounds and to propagate checks out of loops; greatly reduces number of checks [»guptR3_1993]
Quote: ABCD-eliminate array bounds checks on demand; sparse SSA analysis; removes 45% of bounds checks [»bodiR6_2000]
Quote: use related field analysis to remove 50% of array bounds checks; proves relationships between fields of an object [»aggaA6_2001]
Quote: SafeTSA includes safe-ref that cannot be null, and safe-index-arr that cannot be out of range; via runtime checks [»ammeW6_2001]

Subtopic: variable vs. fixed array bounds up

Quote: arrays referenced by local Java variables cannot change size
Quote: PASCAL should allow variable array bounds; e.g., ALGOL or FORTRAN [»knobB4_1976]

Subtopic: examples up

QuoteRef: bekiH_1971 ;;150 n := v does range checking on v
QuoteRef: kosyDK_1973 ;;Lowry: declare ranges and check that all objects fall in these ranges
QuoteRef: baglPR_1969 ;;27 "Standing orders" eg PL/1 ON statement or in data definition a range check for reasonableness
QuoteRef: sammJE_1969 ;;221 postconditionals and range tests by a<b<c
QuoteRef: storEF_1970 ;;27 range (x,y,z) true iff x=<y=<z

Related Topics up

Topic: arrays (58 items)
Topic: consistency testing (60 items)
Topic: constraints (35 items)
Topic: debugging techniques (23 items)
Topic: defensive programming (22 items)
Topic: dynamic type checking (43 items)
Topic: range data type (17 items)
Topic: run-time assertions (25 items)
Topic: variables for array bounds
(7 items)

Updated barberCB 11/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.