Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Putting logical limitations on types

Reply
Thread Tools

Putting logical limitations on types

 
 
Eric Sosman
Guest
Posts: n/a
 
      01-26-2008
Malcolm McLean wrote:
>
> "Eric Sosman" <(E-Mail Removed)> wrote in message
>> Perhaps. But if you think about it for a while, you may
>> realize that the notion of a range-restricted sub-type would
>> complicate the language enormously. For example, what ought
>> to happen in the second line of the example above (assuming
>> the first line somehow expressed the 0..23 range limitation)?
>> Should the program silently store 23, or should it store 18
>> (42 mod 24), or should it crash, or ...? Should it be legal
>> to use an ordinary int* to point at a (0..23)int variable?
>> (If yes, how do you get scanf() to respect the range limit?)
>> Should it be legal to assign a (0..23)int* to a (-42..42)int*?
>> What rules should govern the division of a (-42..42)int by a
>> (1..16)int: For example, what is the type of the quotient?
>>

> 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."

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
 
 
 
Kaz Kylheku
Guest
Posts: n/a
 
      01-26-2008
On Jan 25, 1:56*pm, Ido Yehieli <(E-Mail Removed)> wrote:
> 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?
 
Reply With Quote
 
 
 
 
Ido Yehieli
Guest
Posts: n/a
 
      01-26-2008
On Jan 26, 3:40 pm, Kaz Kylheku <(E-Mail Removed)> wrote:
> 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.
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      01-26-2008
"Ben Bacarisse" <(E-Mail Removed)> wrote in message
> "Malcolm McLean" <(E-Mail Removed)> writes:
>
>> 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.

>
> 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 .

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      01-26-2008

"Eric Sosman" <(E-Mail Removed)> wrote in message
> Malcolm McLean wrote:
>>
>> 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
>

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.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
Bartc
Guest
Posts: n/a
 
      01-26-2008

"Malcolm McLean" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> "Eric Sosman" <(E-Mail Removed)> wrote in message
>> Malcolm McLean wrote:
>>>
>>> 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
>>

> 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);

}


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-27-2008
"Malcolm McLean" <(E-Mail Removed)> writes:
> "Eric Sosman" <(E-Mail Removed)> wrote in message
>> Perhaps. But if you think about it for a while, you may
>> realize that the notion of a range-restricted sub-type would
>> complicate the language enormously. For example, what ought
>> to happen in the second line of the example above (assuming
>> the first line somehow expressed the 0..23 range limitation)?
>> Should the program silently store 23, or should it store 18
>> (42 mod 24), or should it crash, or ...? Should it be legal
>> to use an ordinary int* to point at a (0..23)int variable?
>> (If yes, how do you get scanf() to respect the range limit?)
>> Should it be legal to assign a (0..23)int* to a (-42..42)int*?
>> What rules should govern the division of a (-42..42)int by a
>> (1..16)int: For example, what is the type of the quotient?
>>

> 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.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Kenneth Brody
Guest
Posts: n/a
 
      01-28-2008
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: <(E-Mail Removed)>

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Limitations on dataset types Tim Streater HTML 4 06-15-2012 06:13 PM
Can XSD simple types be derived from complex types? Soren Kuula XML 2 12-01-2005 07:51 PM
Where are ref types that are members of value types stored? Sathyaish ASP .Net 2 05-22-2005 07:32 PM
Difference between putting code in constructor and putting code in static{} Saurabh Java 6 05-30-2004 02:44 PM
STD types vs C++ intrinsic types Jeremy Cowles C++ 5 08-19-2003 05:33 PM



Advertisments