On Mon, 12 Nov 2001, CBFalconer wrote:

...

--mirsad05.pas------------------------------------------------------------ PROGRAM setranges5(output); { Written by: Mirsad Todorovac Nov 2001; copying by GPL. ------------------------------------------------------------ Stresses setrange construction and adding; checks if there's more in SET than we've put in. lasts few seconds where I've tested it.} CONST maxN = 255; VAR seta, setb, setc: SET OF 0..maxN; i, j, len, start, endr: Cardinal; failed: Boolean = false;

BEGIN FOR i:= 0 TO maxN DO IF ((i IN seta) OR (i IN setb) OR (i IN setc)) THEN writeln('Failed: SET not initialized empty!');

There is no automatic initialization in Pascal, without some sort of extension. Thus this test is not valid.

I admit my error: I used default behavior spotted on available systems as a standard, which doesn't have to be true. As Frank said in other message, we can modify test by adding explicit initialization to SET decl.

However, maybe there should be a third result of a test, 'warning'; which would test non-portable behavior?

And second, shouldn't compiler *WARN* me about accessing the value of non-initialized variable with IN operator? I've tried and even with -Wall gpc was quiet.

mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.

On Tue, 13 Nov 2001, Frank Heckenbach wrote:

...

However, maybe there should be a third result of a test, 'warning'; which would test non-portable behavior?

What a coincidence, just yesterday I implemented `WARN' as a test suite flag!

We may be the same Zodiac sign or somethin'? :-)

...

And second, shouldn't compiler *WARN* me about accessing the value of non-initialized variable with IN operator? I've tried and even with -Wall gpc was quiet.

It's a known issue that the uninitialized-warnings don't work with global variables and some non-simple types (strings, sets, ...). I hope we can fix this sometime (but currently, there are more important issues) ...

I will always vote for that when asked, since this warnings help a lot when writting complex programs and save tons of time of debugging.

In the mean time, with your permission, I just might submit a test that gives a WARN if a variable of non-simple type is not initialized on platform?

2. BTW, I've seen FPC bindist shiping with Mandrake 8.* ... How is the situation with GPC and Linuxes? I mean with Mandrake 8.1 CD's you get even Haskell functional language HUGS interpreter, which is IMHO far more exotic than GPC compiler. IMHO, with such extensive testsuite that passes without complaint on Solaris box - GPC may be just enough stable to include in official Linux releases?

Of course, users (and admins) can always build the compiler from source dist - but having it out of the box and running immediatelly might just be the difference between using it or not!!

And BTW, in my not so humble opinion GPC is much better than FPC, at least in the area which I love most in PASCAL: SETS! FPC can't be convinced easily to construct SET with more than 256 elements, so I can't see any use beyond testing character ranges.

I was thinking also about the issue - sparsely filled sets of large numbers; and now when I saw then on TODO list I was very excited. I think that they are definitely a good thing, worth implementing (I offer my assistance, as an experienced programmer in C and C++, even worked on great commercial projects for banking software, also knowing PASCAL).

On the other hand, I'd agree with '??' remark in TODO list, because sparse sets bring difficult and vexing algorythmic problems; so I thought of multiple ways of internal representation: from items numbered in a simple list; to multiple ranges of bits representing set items (a very simple extension to current algorythm with MedCards in p/rts/sets.pas) - to some SF features such as something resembling UNIX filesystem internal structure and organization (of course optimized for in-memory operation). Of course, the emphasys would be on speed and conservative memory use - so making all ends meet might be an art!?!

Actually, I had in mind a combination of all above, with a number on head representing the version of algorythm used to represent particular set (extra byte or word or long), with also "negative image set" - this would be representation of the complement of the set (used only when this would be opportune - in situation such as "full_set - [one_lement] and like).

But off course, these is just rough thinking - a true analisys of the problem *should* involve simulations of average use etc. etc. ...

Then again, that would lead to increase in code complexity comparing to elegance shown in p/rts/sets.pas ...

However, SPARSE SETs seem to me like an excellent challenge for a programmer, but they *do* introduce new issues, for example memory allocation problems - since their size can't be computed at compile time since it depends on actual # of set members; and so on and so on ...

Frank, what do you think of these thoughts of mine? Anybody?

mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.

Mirsad Todorovac wrote:

... snip ...

However, SPARSE SETs seem to me like an excellent challenge for a programmer, but they *do* introduce new issues, for example memory allocation problems - since their size can't be computed at compile time since it depends on actual # of set members; and so on and so on ...

Frank, what do you think of these thoughts of mine? Anybody?

I am a crusty old conservative when it comes to Pascal. I don't think it should be extended to do everything. I don't even believe in sets of over 256 items. The code generation should be kept simple and accurate. If you want a sparse set you can build it yourself, probably out of linked lists of subsets. If you really want large sets an array of subsets is quite adequate.

These are NOT items you use every day. However, SET OF ['0'..'9'] is.

I consider the lack of comprehensive range checking to be a very serious failing. This makes a mockery of taut typing with subranges. With such there is no need to check indices, instead you can rely on the programmer to specify a suitable type for them.

With proper subranging you can keep the cost of run-time checks way down. Studies have shown it to be in the order of 5%.

CBFalconer wrote:

Expanding, all that is required is a single routine (or in line instruction sequence) as long as chars and booleans are represented by integers, which is called or emitted just before assignment or indexing. The value to be checked is already on the stack, and it would look like:

push min
push max
call chk

which would normally simply absorb min and max, and let the code continue to the assignment, indexing, function call, etc. For failure, it aborts with appropriate messages. In C terms it would look like:

inline int chk(value, min, max) { if ((value < min) || (value > max)) abort(value, min, max); return value; }

which is adequate because Pascal has no concept of unsigned, outside of subranges of integer. As far as possible everything is passed in registers, but that is only an implementation detail.

For booleans (common) I created an additional routine, chkb, which implied the 0 and 1 limits and avoided the overhead of pushing parameters. I also created chkp, which only checked for a non-NIL pointer and a value known to lie somewhere within the system heap. chkb and chkp need no parameters, but must normally leave the top-of-stack value unaltered. Of course proper use of chkp means the compiler has to distinguish between pointers and VAR references, and is the reason such things are not feasible in C.

The hard part is deciding when *NOT* to emit it. One case is when run-time checks have been disabled, and is easy. The basic idea is to keep track of the possible range of expressions (including unknown). For example:

TYPE ix = 1..maxix; whatever = ....

VAR a : ARRAY[ix] OF whatever; x : ix; y : whatever; i : integer;

.... y = a[x];

needs no checking because x is of type ix, already checked, and a[x] is of type whatever, again already checked. y = a[3] can be checked (for index) at compile time, but y = a[i] needs a check call.

Thanks for trying to help, but I don't think these are the main issues we'd have to deal with.

For one, when we do it, we'll certainly use inline comparisons, so we won't need to worry about parameter passing and optimizing special cases in this regard.

Secondly, the ranges of all expressions are already kept track of. I also don't think there are any "unknown" ranges. If, e.g. an operation is done on Integers, the result generally has the range MinInt .. MaxInt.

The main thing seems to be to find all places where to do it (assignments, parameters passing, array indexed, initializers, ...)

I think I'll look into it after 2.1 ...

Frank

Mirsad Todorovac wrote:

On Thu, 15 Nov 2001, CBFalconer wrote:

...

Expanding, all that is required is a single routine (or in line instruction sequence) as long as chars and booleans are represented by integers, which is called or emitted just before assignment or indexing. The value to be checked is already on the stack, and it would look like:

push min
push max
call chk

inline definitelly:

  cmp min
  branch_less :range_error
  cmp max
  branch_greater :range_error

But when it has to be emited after every add or subtract operation, it can produce significant overhead even if it's only 4 instructions.

You can go even further and reduce this to:

  ld r0, x
  ld r1, y
  add r1, r0
  jump_on_overflow :range_error

(of course, instructions do not match an actual assembler).

I don't understand the latter example, but in general, assembler level suggestions are not really needed, anyway. The back-end (code generation and optimizer) is working well, I might remind you all. We only have to use it. E.g., it's possible to do a check like the first one with only one comparison and branch, and the back-end knows how to do it (this is on a generic CPUs; some CPUs might have even better mechanisms).

It's therefore better to describe what should be done on a higher level, e.g. by equivalent Pascal (or C) code. Of course, in the range checking case, that's quite clear (it's either `(x >= Min) and (x <= Max)' or just one of the comparisons, if the other bound is safe).

There are many good points there. But with range checking there is many room for optimization. For example, in some FOR loops compiler could determine the possible range of a variable.

For expensive loops that don't have constant upper and lower band but variable, this could be done (at the beginning of the expensive loop):

1. compiler checks the minimum bounds for arrays inside loop

I.e., it has to resolve equations!? (If a is an array [1 .. 20] and in the loop it says `a [i * i - 3]', it should find that i is allowed to be in the range 2 .. 4 and -4 .. -2?

2. compiler asserts two versions of loop: one with range-checking, onw without
3. at run-time check finds the maximum bounds for loop variable;
   • if it's safe for minimum bounds found in 1, loop without
   bound-checking is called (fast)
   • if it's determined algorythmic that range-error will
   occur inevitably in the loop, runtime exception is raised

Not necessarily correct (side-effects might occur before the range error happens).

- if neither is true, (for example, there is an
  conditional exit from the loop) the version of the
  loop compiled with range checking is performed (slow)

What if the loop calls any routine which might (directly or indirectly) call Halt conditionally?

But this may be too much for the compiler to decide,

I think so. If the programmer really cares for speed, he should help the compiler, e.g., as Chuck said, by declaring variables of correct type. If the programmer knows that it makes only sense for the counter to be between 1 and 10, he should just declare it as 1 .. 10 so (some or all) checks in the loop can be avoided, while at the beginning of the loop there will be checks (if necessary) that the loop bounds are both between 1 and 10.

Frank

CBFalconer wrote:

Frank Heckenbach wrote:

...

Mirsad Todorovac wrote:

...

... snip ...

...

...

For expensive loops that don't have constant upper and lower band but variable, this could be done (at the beginning of the expensive loop):

  1. compiler checks the minimum bounds for arrays inside loop

I.e., it has to resolve equations!? (If a is an array [1 .. 20] and in the loop it says `a [i * i - 3]', it should find that i is allowed to be in the range 2 .. 4 and -4 .. -2?

Horrors. If i is a subrange, the compiler can calculate (mini * mini - 3) and (maxi * maxi - 3). If these are satisfactory then it omits the range checks on the index operation.

Nice, but wrong (e.g.: i: -4 .. 4)!

This is simply pushing the calculated index, a min and a max from the array declaration, and calling chk.

As I said, we'll do inline checks which are faster (and probably even easier). That's really not the problem.

...

What if the loop calls any routine which might (directly or indirectly) call Halt conditionally?

So what? A halt is a halt is a halt.

If the analysis finds that a `for' loop has an "inevitable" range error, but `Halt' is called before it, the error is not that inevitable.

My pseudo code probably looks nothing like yours, I am not familiar with GCCs intermediate forms, which I believe are designed for optimization analysis. So I am limiting myself to prodding, having been there in the past.

You don't have to know about the intermediate forms ("tree nodes" and "rtl"). Just describing things in terms of Pascal (or C) code should be enough -- we can translate it into tree nodes then.

Frank

On Fri, 16 Nov 2001, Frank Heckenbach wrote:

...

This is simply pushing the calculated index, a min and a max from the array declaration, and calling chk.

As I said, we'll do inline checks which are faster (and probably even easier). That's really not the problem.

I'd also vote for inline check instead of function call -it may not even inflate the code on some processors.

...

...

What if the loop calls any routine which might (directly or indirectly) call Halt conditionally?

So what? A halt is a halt is a halt.

If the analysis finds that a `for' loop has an "inevitable" range error, but `Halt' is called before it, the error is not that inevitable.

Then compiler should decide that it cannot determine that it's an "inevitable" range error and should generate inline code to check each array indexing.

If an integer expression is simple enough, compile time min-max analisys can be performed, if all inputs to the expression are traceable to some values in determinable range (sort of value flow analisys).

Or to make it simple: if the range of expression is determinable at compile time, range checking can be put at the beginning of "expensive" loop. If it can be determined at runtime before entering "expensive" part of program, then do range-checking analysis before entering it, and enter "fast" version of compiled routine. If it can't tell for sure, enter "slow" version of compiled routine with inline range-checking.

At compile time heuristics determine whether routine fits the criteria for making two versions of it and doing sort of "run-time smart virtual range-checking and linking" (:-) at least it sounds good).

But, then again, it's PHASE 3. First comes PHASE1, to introduce solid range-checking and make it work. Optimizations probably come as PHASE 2, and proposed "dynamic routine version choosing" last.

Maybe it belongs in optimizer to do it, so it may be out of the scope of GPC and fit into backend? Maybe a lot of this ideas of pre-loop range checking could be done by LSR (lop strength reduction) and CSE (common subexpression elimination) passes of optimizer.

...

My pseudo code probably looks nothing like yours, I am not familiar with GCCs intermediate forms, which I believe are designed for optimization analysis. So I am limiting myself to prodding, having been there in the past.

You don't have to know about the intermediate forms ("tree nodes" and "rtl"). Just describing things in terms of Pascal (or C) code should be enough -- we can translate it into tree nodes then.

Is there a way to generate text file with this rtl intermediate representation, to see what's going on? Maybe it could be clearer to read than assembler(s)?

mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.

On Fri, 16 Nov 2001, Frank Heckenbach wrote:

...

...

I.e., it has to resolve equations!? (If a is an array [1 .. 20] and in the loop it says `a [i * i - 3]', it should find that i is allowed to be in the range 2 .. 4 and -4 .. -2?

Horrors. If i is a subrange, the compiler can calculate (mini * mini - 3) and (maxi * maxi - 3). If these are satisfactory then it omits the range checks on the index operation.

Nice, but wrong (e.g.: i: -4 .. 4)!

IMHO such min-max analisys is feaible: for exmaple, compiler knows (or can be made that way) that by multiplying x*x you get a positive number (except for complex numbers, of course).

So, if range is -4 .. 7, x*x falls into 0 .. max(abs(x))

mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.

On Thu, 15 Nov 2001, CBFalconer wrote:

Mirsad Todorovac wrote:

...

... snip ...

...

However, SPARSE SETs seem to me like an excellent challenge for a programmer, but they *do* introduce new issues, for example memory allocation problems - since their size can't be computed at compile time since it depends on actual # of set members; and so on and so on ...

Frank, what do you think of these thoughts of mine? Anybody?

I am a crusty old conservative when it comes to Pascal. I don't think it should be extended to do everything. I don't even believe in sets of over 256 items. The code generation should be kept simple and accurate. If you want a sparse set you can build it yourself, probably out of linked lists of subsets. If you really want large sets an array of subsets is quite adequate.

Maybe. But (Visual) Basic, C++ and FORTRAN also evolve, don't they? For example, consider Visual Basic's "collections", which are basically sets of members which can have various types (also mentioned in gpc info's TODO list as ???).

Besides, for example, when UNICODE comes into play, you will need at least set of range 65536 to test ranges in Chinese Big5 set, won't you? And using current representation of bit-array it takes 8kb per set, so alternate forms of representation might be and probably will be considered.

Besides, compiler programmers on average have higher coding skills than program writters that use those compilers, so if it's built-in in language, there's less repetative work that each and every programmer has to do.

Besides, sparse sets I have to debug in each program, while sparse sets in debugger are made correct (or even state-of-the-art) once and then reused many times.

Besides, sparse sets wouldn't put too much of a hard burden on compiler itself, since 95% of the stuff required to make it work belongs to RTS library anyway, doesn't it?

Besides, it can be done without compiler and language interface change, just by making RTS functions more sophisticated.

This would mean preserving compiler elegant, simple and accurate, while doing additional stuff in RTS library.

These are NOT items you use every day. However, SET OF ['0'..'9'] is.

Yup, but for a Chinese programmer this ['0'..'9'] may run well beyond your 256 elements per set (since their glyphs number about 3000 to read daily newspapers). With i18n issues, all design based on assumption that people will never want to use anything outside US-ASCII will eventually have to be rewritten IMHO, and that might be a very close future.

You will probably agree with me that programming languages somewhat shape the way we think and program: so, even before C++ X Windows were object oriented, but with C++ OO design comes natural. (Also with OO Pascal.) So, it's hard to estimate how useful is feature of comp.lang. before it's implemented.

I consider the lack of comprehensive range checking to be a very serious failing. This makes a mockery of taut typing with subranges. With such there is no need to check indices, instead you can rely on the programmer to specify a suitable type for them.

I remember wonderful {$R+} and {$R-} in UCSD Pascal back then in '87 when I was writting high-school gradutation thesis program. With range checking I was able to debug very fast program of 1500 lines (but then I was younger also :-) ... ). I meant to say how range-checking in Pascal cuts bugs much sooner than debugging in C.

With proper subranging you can keep the cost of run-time checks way down. Studies have shown it to be in the order of 5%.

5% less, or 95% eliminated? Didn't quite catch that.

Anyway, range checking can be life saving. For example, remember Arianne launch failure when a 16-bit counter that was there for years rolled-over into negative when something was speeded-up. (In the time of design they said it can never go over 16 bits.) So, the unit failed, after which rendundant unit was consultet only to have the same result (of course, using the same software and same 16-bit counter). Then the rocket's computer thought it started to fall down and activated self-destruct sequence, even though it was climbing.

This story makes me agree that extensive range-checking, especially with arrays, sets and (last but not the least) implicit precision conversions is very important. That's also a weakness of C language which C++ hasn't eliminated (but I'm slightly off-topic maybe?) ...

I'm way of out line (for a short reply) this time, so I'm ending message without final conclusion.

mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.

Mirsad Todorovac wrote:

...

... snip ...

...

However, SPARSE SETs seem to me like an excellent challenge for a programmer, but they *do* introduce new issues, for example memory allocation problems - since their size can't be computed at compile time since it depends on actual # of set members; and so on and so on ...

Frank, what do you think of these thoughts of mine? Anybody?

I am a crusty old conservative when it comes to Pascal. I don't think it should be extended to do everything.

This is an implementation detail, so not an extension. I however agree that the features suggested (notable sparse sets) are somewhat over the top.

I don't even believe in sets of over 256 items. The code generation should be kept simple and accurate.

I do. Problem is that otherwise code that relies on set of an enumeration type doesn't scale too well. Tokenizers, parsers and symboltables often use this.

The simple settype should get dynamic beyond a certain size (support can probably get created on top of schemata for extended Pascal compilers, en on dynamic arrays for e.g. FPC).

The sethandling will get slower than, if it goes beyond 256 elements, and binary writing them to files will be different, but at least you don't have to redesign your working program.

If you want a sparse set you can build it yourself, probably out of linked lists of subsets. If you really want large sets an array of subsets is quite adequate.

Agree.

These are NOT items you use every day. However, SET OF ['0'..'9'] is.

Agree too, but as said, I would like to be able to go beyond 256, otherwise for some applications one would have to avoid sets, because it doesn't scale beyond 256 chars.

Also charsets that are larger than 256 chars are rapidly getting more important, so even for chars the 256 elements limits could get problematic.

On Tue, 13 Nov 2001, Frank Heckenbach wrote:

Mirsad Todorovac wrote:

...

Also initialization fails, but IMHO all this bugs have something in common; so I went forth with these examples only in hope that they will help nail the bug.

In Pascal, normal variables are not guaranteed to be initialized. Though the sets are in fact empty on my system, I think that's more the OS feature of clearing a new process's storage rather than a language feature. So I'm adding an explicit declaration:

VAR seta, setb, setc: SET OF 0..maxN value [];

This applies to mirsad0[245].

Got that. And have tested it on both Solaris and Alpha OSF/1. Initializations passed on both systems.

mirsad0[45]: I'm changing the type of start to endr to 0 .. maxN. This is just to avoid the `constructing limited set' warning. That's a known issue, and we don't need yet another test program that exhibits it ...

I've synced with your version, so if there will be more examples/tests, I will adopt that practice as a standard ...

Apart from this, the tests run ok on IA32 (Linux and DJGPP) as well, and I'll look at them on the Alpha soon.

Modified versions run ok on Solaris too.

Mirsad

-- This message has been made up using recycled ideas and language constructs. No plant or animal has been injured in process of making this message.