Type and Range checking

[FIRTH%TARTAN at CMU-CS-C.ARPA]

In case any of you have been confused by the recent posts on C "improvements":

Type checking of course causes no runtime overhead at all, since it is done
entirely at compile time.  This is the whole point of strongly typed
languages.  If, in addition, the language has a generic facility, as does
Ada, then it is possible to write things like storage allocators, list
processing packages, &c that are also type checked at compile time.  The
security is almost free (if you don't mind waiting a bit - a lot? - longer
for the compiler)

Array bound checking in Pascal is almost never necessary, since the array
index is usually of the correct type:

	type RowIndex is 1..80

	Row : array (RowIndex) of Char

However, TANSTAAFL, we now have to have range checking:

	var I : RowIndex
	...
	I := I+1

on the above assignment, for instance.  Getting rid of this overhead
takes cooperation between programmer and compiler: the programmer must
declare his scalar variables of the (logically) corect range, and
the compiler must perform range tracking.  The result, as Walsh's
Pascal compiler shows ["Economical range Checking in Pascal" - pub
in Software many years ago] is that the runtime overhead can be reduced
to about 5%.  One reason is that most array index operations happen
in loops:

	for I in 1..80 do ... Row[I] ...

where it is obvious the index cannot go out of bounds.  

Another source of security without compromise of efficiency is the
scalar type:

	type Color is (Red, Orange, Yellow, Green, Blue, Indigo, Violet)

where a typical array of Colors spans all the values of the type, and
so bounds checking is again never necessary, since all possible (logical)
index values are valid.

Of course, if you use a language with no subranges, no concept of a
scalar type, For loops whose control variables are writeable, and that
generally is as backward in its semantic model as Fortran, then I
agree you are rather stuck.

Robert Firth
-------