| 
|
Topic: range checking
topics >
computer science >
data >
arrays
Topic:
consistency testing
Topic:
constraints
Topic:
debugging techniques
Topic:
defensive programming
Topic:
dynamic type checking
Topic:
range data type
Topic:
run-time assertions
Topic:
variables for array bounds
Summary
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: array bounds
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: optimizing range checks
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: variable vs. fixed array bounds
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: examples
Quote: arrays referenced by local Java variables cannot change size Quote: PASCAL should allow variable array bounds; e.g., ALGOL or FORTRAN [»knobB4_1976]
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
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)