Putting logical limitations on types

[Eric Sosman]

We could add valid ranges to C without complicating things. Simply declare

int i 0 to N;

(means that i can hold any integer between zero and N, assuming N is a
variable in scope). There are no other changes to the language. If the
restraint is violated, beahviour is undefined. Which means that a decent
compiler will give you a crash, a bad one will plough on regardless.
Often the strategy adopted will be to abandon any checks for the final
release, hence you have a powerful debugging tool with no impact on
performance.

Observe that this is not the behavior the O.P. was looking
for. His (imperfect) illustration showed a "clamping" behavior,
where an attempt to assign a too-small or too-large value had
the effect of assigning the minimum or the maximum.

The problem is that to honour the restrictions, the compiler needs to
check every assignment. This isn't particularly complicated, but will
approximately halve the speed of the program.

The speed estimate is surprising; how did you derive it?
Especially, how did you calculate it for a case like

int i 0 to N;
scanf ("%d", &i);

.... where the assignment and (presumably) the range check occur
inside a separately-compiled library function that doesn't know
about the range limitation? Unless you've invented a whole new
system of decorated pointer types, I don't see how you can get
this to work at all -- and adding decorations to pointers doesn't
strike me as "without complicating things."

 

[Kaz Kylheku]

Hi,
    can I define types with a limitation on the data the type contain,
rather than just the size it will have in memory?

Don't you think you need a better reference manual, if it cannot
answer simple questions about what the language can or cannot do?

 

[Ido Yehieli]

Don't you think you need a better reference manual, if it cannot
answer simple questions about what the language can or cannot do?

I knew the exact thing I asked is probably not possible, but hoped
someone know an elegant solution I didn't think about.

-Ido.

 

[Malcolm McLean]

To honour the restriction it has to re-implement pointers in a new
way, too, or ban the usual permission to convert pointers.

memcpy(&i, &j, sizeof(int 0 to N)); /* OK or not? */

Of course. I'd forgotten about that.
It can retrieve the range information from a plain pointer, but it makes the
whole thing very non-trivial. Honouring the restriction on straight writes
is not too difficult .

 

[Malcolm McLean]

The speed estimate is surprising; how did you derive it?
Especially, how did you calculate it for a case like

We need two conditional jumps on every write. Conditional jumps tend to be
fairly expensive as machine operations go. If we assume that the program
spends about a fifth to a quarter of its time assigning, and the conditional
jumps increase the write workload by a factor of three to four, then you'd
expect roughly to halve the speed of the program.

 

[Bartc]

We need two conditional jumps on every write. Conditional jumps tend to be
fairly expensive as machine operations go. If we assume that the program
spends about a fifth to a quarter of its time assigning, and the
conditional jumps increase the write workload by a factor of three to
four, then you'd expect roughly to halve the speed of the program.

This must depend on the proportion of bounded-int assignments there are. The
little program below does virtually nothing else except assign to a bounded
integer (clipping the value which takes a bit longer then discarding out of
range or failing). In this example, the bound-checked code did take about
double the time of the straight assignment.

But this program is unrealistic: not all assignments need to be
bound-checked (and the bound-checking can be made more efficient I'm sure),
and not all the program time is spent in assignments (or in fact in your
program at all (in libraries, doing OS calls, and so on.).

And, if this was actually a feature of the language, a program would
typically be assigning between bounded ints of the same bounds, so no check
is needed at all. (Assuming compile-time bounds; your suggestion of dynamic
bounds is probably not in the spirit of C.)

My estimate would be 0 to 10% slowdown in practical cases. In other words
usually not significant.

--
Bart

#include <stdio.h>
#include <time.h>

int main(void)
{int i,j;
int t;
#define A 0
#define B 1000

printf("Start...");
t=clock();

for (i=0; i<1000000000; ++i)
{
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};

if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
if (i<A) j=A; else { if (i>B) j=B; else j=i;};
};

printf("Done. Time %d j = %d\n",clock()-t,j);

}

 

[Keith Thompson]

We could add valid ranges to C without complicating things. Simply declare

int i 0 to N;

(means that i can hold any integer between zero and N, assuming N is a
variable in scope). There are no other changes to the language. If the
restraint is violated, beahviour is undefined. Which means that a
decent compiler will give you a crash, a bad one will plough on
regardless. Often the strategy adopted will be to abandon any checks
for the final release, hence you have a powerful debugging tool with
no impact on performance.

The problem is that to honour the restrictions, the compiler needs to
check every assignment. This isn't particularly complicated, but will
approximately halve the speed of the program.

It's unlikely to be that bad, particularly if the range checking is
defined in the language.

Suppose you have:

typedef int<0..42> my_int; /* or whatever syntax you like */
my_int a, b;

a = b; /* no check needed */
a = 10; /* no check needed */
a ++; /* no check needed if the compiler does decent data flow
analysis */

And so forth.

 

[Kenneth Brody]

Malcolm McLean wrote:
[...]

We could add valid ranges to C without complicating things. Simply declare

int i 0 to N;

(means that i can hold any integer between zero and N, assuming N is a
variable in scope). There are no other changes to the language. If the
restraint is violated, beahviour is undefined.

In which case, I claim that the behavior is satisfied by using the
current behavior for "int i;". (Assuming that the range is limited
to a subset of the range for "int".)

[...]

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>