Concerning subscript bounds checks

Concerning subscript bounds checks

[Richard A. O'Keefe]

There was some discussion in comp.lang.misc recently about array bounds
checks.  As an exercise, I converted Algorithm AS 47 (an implementation
of the Nelder-Mead simplex minimisation procedure) from Fortran to Ada.

The Fortran original contains 85 array subscripts.
The Ada version      contains 66 array subscripts.
Of these 66, all but 4 occur within the scope of a "for" loop
which *obviously* guarantees the safety of the subscript.

The remaining 4 occur in this context:
    subtype Simplex_Range is Natural range 0 .. Point'Length;
    P: "array (Simplex_Range) of ..."
    Y: "array (Simplex_Range) of ..."
    X: Point;
    J: Simplex_Range;
    ...
    J := 0;		-- at the start, J = Simplex_Range'First
    for I in X'Range loop
	...
	P(J) := ...
	Y(J) := ...
	J := J + 1;
    end loop;		-- at the end, J = Simplex_Range'Last
    P(J) := ...
    Y(J) := ...
end;

A reasonably smart compiler should be able to tell that these four
subscripts are also safe.

-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[Robert Dewar]

Richard said

"The remaining 4 occur in this context:
    subtype Simplex_Range is Natural range 0 .. Point'Length;
    P: "array (Simplex_Range) of ..."
    Y: "array (Simplex_Range) of ..."
    X: Point;
    J: Simplex_Range;
    ...
    J := 0;             -- at the start, J = Simplex_Range'First
    for I in X'Range loop
        ...
        P(J) := ...
        Y(J) := ...
        J := J + 1;
    end loop;           -- at the end, J = Simplex_Range'Last
    P(J) := ...
    Y(J) := ...
end;

A reasonably smart compiler should be able to tell that these four
subscripts are also safe.
"

I suspect this judgment is based on informal reasoning ("well it is pretty
obvious to me that it can be figured out"). As always compiler optimizations,
particularly range analysis are always more complicated than they appear
from simple examples. Yes, a compiler could figure this out, but "reasonably
smart" is probably an underestimate. I would be surprised if many existing
compilers can figure even this particular one out.

P.S. GNAT has not even started to think about optimizing checks yet,
you get junk checks even in simple loops. It's something we plan
to start work on soon!

Re: Concerning subscript bounds checks

[Adam Beneschan]

In article <dewar.835402601@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:
 >Richard said
 >
 >"The remaining 4 occur in this context:
 >    subtype Simplex_Range is Natural range 0 .. Point'Length;
 >    P: "array (Simplex_Range) of ..."
 >    Y: "array (Simplex_Range) of ..."
 >    X: Point;
 >    J: Simplex_Range;
 >    ...
 >    J := 0;             -- at the start, J = Simplex_Range'First
 >    for I in X'Range loop
 >        ...
 >        P(J) := ...
 >        Y(J) := ...
 >        J := J + 1;
 >    end loop;           -- at the end, J = Simplex_Range'Last
 >    P(J) := ...
 >    Y(J) := ...
 >end;
 >
 >A reasonably smart compiler should be able to tell that these four
 >subscripts are also safe.
 >"
 >
 >I suspect this judgment is based on informal reasoning ("well it is pretty
 >obvious to me that it can be figured out"). As always compiler optimizations,
 >particularly range analysis are always more complicated than they appear
 >from simple examples. Yes, a compiler could figure this out, but "reasonably
 >smart" is probably an underestimate. I would be surprised if many existing
 >compilers can figure even this particular one out.
 >
 >P.S. GNAT has not even started to think about optimizing checks yet,
 >you get junk checks even in simple loops. It's something we plan
 >to start work on soon!

Maybe I'm missing something, but it seems that the compiler should be
able to figure this out easily just from the fact that J is declared
as having subtype Simplex_Range.  If the program isn't erroneous, J
can never have a value outside Simplex_Range, and therefore no array
bounds checks should be necessary.

But is this still the case with Ada95, given the new definitions of
"bounded error" and the like?

In any case, if the declaration of J is changed to

    J : Natural;

then yes, the compiler's job would be harder.

                                -- Adam

Re: Concerning subscript bounds checks

[William Clodius]

In article <4ql9eq$hdt@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU
(Richard A. O'Keefe) writes:

   From: ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe)
   Keywords: subscripts
   Newsgroups: comp.lang.ada,comp.lang.misc
   Date: 24 Jun 1996 15:35:22 +1000
   Organization: Comp Sci, RMIT, Melbourne, Australia
   Path: newshost.lanl.gov!ncar!gatech!swrinde!ihnp4.ucsd.edu!munnari.OZ.AU!news.mel.connect.com.au!news.mira.net.au!harbinger.cc.monash.edu.au!news.rmit.EDU.AU!goanna.cs.rmit.EDU.AU!not-for-mail
   Lines: 60
   References: <4qdj3e$btf@goanna.cs.rmit.EDU.AU> <dewar.835402601@schonberg>
   NNTP-Posting-Host: goanna.cs.rmit.edu.au
   NNTP-Posting-User: ok
   X-Newsreader: NN version 6.5.0 #0 (NOV)
   Xref: newshost.lanl.gov comp.lang.ada:13943 comp.lang.misc:25665

   The central point I was making was a very simple, very obvious, very
   positive one:

       I translated an algorithm from Fortran to Ada,
       and it _easily_ and _naturally_ fell out that
       62 out of 66 subscripts could _obviously_ be
       compiled without checks using purely local
       information (no data flow or range analysis needed).

   I call that a _good_ result.  (The 4 subscripts that aren't quite so
   obvious are executed with low frequency, and only the upper bound is
   not obviously safe.)

But the comparison is not complete as it is done only one way.  I
remember reading somewhere that in the 80s an experimental F77 compiler
was written that could optimize away 90% of all array bounds checks on
a large variety of codes when array bounds checking was turned on.  (I
don't know if this capability was ever implemented in a commercial
Fortran compiler, but then it hasn't been implemented in the obvious
Ada 95 compiler.)  Did you check to see what an equivalent algorithm
would do on the original F77 code?  How would it do if rewritten in
F90 stle?



-- 

William B. Clodius		Phone: (505)-665-9370
Los Alamos National Laboratory	Email: wclodius@lanl.gov
Los Alamos, NM 87545

Re: Concerning subscript bounds checks

[Richard A. O'Keefe]

clodius@hotspec.lanl.gov (William Clodius) writes:

>In article <4ql9eq$hdt@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU
>(Richard A. O'Keefe) writes:
>   I call that a _good_ result.  (The 4 subscripts that aren't quite so
>   obvious are executed with low frequency, and only the upper bound is
>   not obviously safe.)

>But the comparison is not complete as it is done only one way.

Er, *what* comparison?  Nowhere did I state or imply that Ada was
*better* than Fortran.  All I stated, and all I meant to imply, was
that
    - in an algorithm whose original coding DID NOT HAVE ADA IN MIND
    - it fell out quite naturally
    - that almost all of the subscripts in the Ada version
    - OBVIOUSLY don't need checking
    - using only local information

>Did you check to see what an equivalent algorithm
>would do on the original F77 code?  How would it do if rewritten in
>F90 stle?

There are two difficulties with doing this kind of thing in Fortran.
(1) My Ada procedure is generic, mainly because I wanted it to be
    valid Ada 83, and that was the only way to pass a function.
    But having done that, it was possible to have a generic formal
    array type as well.

generic

    type Coord is digits <>;
    type Index is (<>);
    type Point is array (Index) of Coord;
    type Value is digits <>;
    with function Funct(X: in Point) return Value;

procedure Nelder_Mead(
    Start    : in  Point;
    Step     : in  Point;
    DevMin   : in  Value;
    Konvge   : in  Positive;
    Kcount   : in  Natural;
    Ncalls   : out Natural;
    Nrestarts: out Natural;
    Xmin     : out Point;
    Ymin     : out Value;
    Good     : out Boolean
);

    This means that if the Index bounds happen to be static, the Ada
    compiler can know what they are when generating code for an instance
    of the body.  The Fortran version starts out like this:

      SUBROUTINE NELMIN(FN, N, START, XMIN, YNEWLO, REQMIN, STEP,
     *          KONVGE, KCOUNT, ICOUNT, NUMRES, IFAULT)
         REAL FN
         INTEGER N
         REAL START(N)
         REAL XMIN(N)
         REAL YNEWLO
         REAL REQMIN
         REAL STEP(N)
         INTEGER KONVGE
         INTEGER KCOUNT
         INTEGER ICOUNT
         INTEGER NUMRES
         INTEGER IFAULT

    In F77, I cannot declare a local array of the same size as XMIN.
    (One Nelder-Mead subroutine I've seen handled that by assuming
    that N <= 20 and using fixed-size local arrays; another required
    the caller to pass workspace.)  In F90, I can.  

(2) The loop control variables in Fortran, whether F77 or F90, are
    not tied to the array bounds.  They are INTEGER, not Index.


Point (2) is not actually a difficulty for the obvious algorithm, in
which (scalar) variables start out with with the empty set as their
possible interval, and the set is expanded as necessary.  The key point
is that the form of the Ada loop makes it _obvbious_ without any data
flow analysis at all that a subscript is safe.  If you have

	P: array (Simplex_Range) of Point;
	Pstar, Pbar: Point;
	...
	for I in Point'Range loop
	    PStar(I) := PBar(I) + (P(Hi)(I) - PBar(I)) * (-Reflection);
	--        #          #           #         #
	end loop;

then it is obvious that each of the flagged subscripts is safe.

These particular subscripts, of course, would vanish entirely in
APL, PL/I, or Fortran 90:

	PSTAR = PBAR + (P(Hi,*) - PBAR)*(-REFLECTION);	/*PL/I*/

Now, I _already_ eliminated a lot of these from my count, because
I wrote some inline subprograms to do special bits of vector arithmetic.

Point (1) _is_ a significant difference between Ada and Fortran 90.
In this particular example, it doesn't matter so much, because the
simple rule
	"if a subscript is a loop identifier and the range of the loop
	 identifier is the same as the range of that subscript, then
	 no subscript check is needed"
works very well.  This is what I mean by the check being local.
The Fortran equivalent would be
	"in A(...,I,...) where A was declared to have dimensions
	 (...,L:U,...) and the definition of I that is live at this
	 point is from DO[]I = L,U, no subscript check is needed for I."

In the two Fortran versions,
- the version with fixed size local arrays would need a smart compiler
  to notice that "IF (N .GT. 20)" the subroutine exits at once, so that
  it can assume N <= 20 elsewhere.
- the version with workspace provided by the caller needs _two_ size
  parameters, N and N1 (= N+1), and the compiler doesn't _know_ that
  N1 = N+1 (because it isn't told, and in F77, cannot be told).
A Fortran 90 version would not have these problems.


Just to go over the main point one more time, I was *not* saying that Ada
is *better* than anything else, only that even the simplest of local-
information-only rules is *good* for Ada numeric code.

For what it's worth, here are some times:

-- Original Fortran results on a 36-bit DEC-2060
-- Function     NCalls  NRestarts       Value of Min    Time
-- 1            177      0              1.67E-9           T1    msec
-- 2            266      0              4.03E-9          230-T1 msec
-- 3            230      0              2.79E-9           T2    msec
-- 4            712     14              5.75E-14         640-T2 msec

-- My Fortran results on a 32-bit SPARC
-- Function     NCalls  NRestarts       Value of Min    Time
-- 1            177      0              1.0E-9          0.43 msec
-- 2            213      0              2.0E-8          0.88 msec
-- 3            230      0              6.3E-9          1.1  msec
-- 4            666     13              7.1E-14         5.8  msec
-- Compiled with "f77 -native -fast -stackvar -O3"

-- My Ada results on a 32-bit SPARC
-- Function     NCalls  NRestarts       Value of Min    Time
-- 1            177      0              1.79E-9          0.40 msec
-- 2            213      0              1.98E-8          0.94 msec
-- 3            231      0              3.24E-9          2.3  msec
-- 4            736     17              9.54E-14         6.9  msec
-- Compiled with "gnatmake -cargs -gnatp -O3 -Wall"

The SPARC results were obtained on a SPARCstation-10 (sunm4)
running Solaris 2.5, f77 SC4.0, gnat 3.04, gcc 2.7.2.
Oddly enough, it was much easier to rewrite the Fortran code to Ada
than to re_type_ the Fortran code and get it working.  It was only
when I noticed the "-XlistE" flag in Sun's f77 that I made any progress
with the Fortran version.  Static checking helps a _lot_.
Why the big difference for function 4?  I've no idea.
-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[Ken Thomas]

My response to this does not concern the thread of the subject but to
suggest a technique that I have found useful in developing numerical
code that contains a subprogram in the generic formal part.

Many applications are not concerned with a single function but a family
of functions. The device I am suggesting is additional declarations to
the formal part.
> 
> generic
> 
      type USER_PARAMETERS is private;
>     type Coord is digits <>;
>     type Index is (<>);
>     type Point is array (Index) of Coord;
>     type Value is digits <>;
>     with function Funct(UP : User_Parameters; X: in Point) return Value;
> 
> procedure Nelder_Mead(UP : User_Parameters,...


-- 
Dr K.S. Thomas
Department of Electronics and Computer Science
University of Southampton
Highfield
Southampton SO17 1BJ
United Kingdom

Telephone : (+44) 01703 593029
Fax :       (+44) 01703 593903

email: kst@ecs.soton.ac.uk

Re: Concerning subscript bounds checks

[Richard A. O'Keefe]

dewar@cs.nyu.edu (Robert Dewar) writes:

>Richard said
>"The remaining 4 occur in this context:
...
>A reasonably smart compiler should be able to tell that these four
>subscripts are also safe.
>"

>I suspect this judgment is based on informal reasoning ("well it is pretty
>obvious to me that it can be figured out").

Wrong.  I worked out in some detail a straightforward method for a compiler
to handle this.  I chose not to write it up here because it's (a) obvious
and (b) old hat.

>As always compiler optimizations,
>particularly range analysis are always more complicated than they appear
>from simple examples.

Look, I was *PRAISING* Ada, not criticising anything.
I have *NO IDEA* what optimisations GNAT or any other Ada compiler does
or does not do. 

I know for a fact that the analysis required for this particular example
and for a wide range of examples like it (basically looping over a bunch
of vectors and _conditionally_ routing elements from one set of vectors
to another: APL Compress and Merge operations and a few other patterns
I've seen in Fortran code) is straightforward to specify and would take
linear time to compute (I am taking the attitude here that if a variable
outlives a goto you just throw up your hands and be pessimistic).

*Of course* doing such an analysis takes time.
*Of course* the compiler's time spent doing that could have been spent
doing other things.
*Of course* the compiler writers' time spent implementing that could
have been spent implementing other things.
*Of course* it might be beyond any reasonable dispute in some particular
case that *not* doing this optimisation might be the right choice.

>P.S. GNAT has not even started to think about optimizing checks yet,
>you get junk checks even in simple loops. It's something we plan
>to start work on soon!

The central point I was making was a very simple, very obvious, very
positive one:

    I translated an algorithm from Fortran to Ada,
    and it _easily_ and _naturally_ fell out that
    62 out of 66 subscripts could _obviously_ be
    compiled without checks using purely local
    information (no data flow or range analysis needed).

I call that a _good_ result.  (The 4 subscripts that aren't quite so
obvious are executed with low frequency, and only the upper bound is
not obviously safe.)

-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[Robert Dewar]

Richard said

"The central point I was making was a very simple, very obvious, very
positive one:

    I translated an algorithm from Fortran to Ada,
    and it _easily_ and _naturally_ fell out that
    62 out of 66 subscripts could _obviously_ be
    compiled without checks using purely local
    information (no data flow or range analysis needed).

I call that a _good_ result.  (The 4 subscripts that aren't quite so
obvious are executed with low frequency, and only the upper bound is
not obviously safe.)"

Yes, indeed for this kind of Fortran algorithm, almost all checks can
be eliminated (even if we don't get the last 4, we are certainly doing
well).

For reasonably thorough global analysis tecniques used to optimize checks
(e.g. the old Alsys technology using partial redundancy techniques), it
is reasonable to estimate that the total cost of checks is of the order
of 10%.

Even more interesting than the range checks is the issue of getting rid
of elaboration checks, and of course getting rid of overflow checks is
quite hard (you really need the full machinery of range analysis for
this, and even then you don't get very far). However in the Fortran
world, you are dealing with floating-point, and floating-point overflow
is often close to free to detect at the hardware level (e.g. by 
implementing IEEE infinities -- neither IEEE nor Ada requires exception
traps at runtime for floating-point).

So I certainly do not want to argue with Richard's "central point". It is
an important one that needs repeating, I was just commenting around the
edge on those remaining four checks. Richard have you actually implemented
a compiler that eliinates these checks? That would be interesting if so,
and it would be interesting to have the reference.

Re: Concerning subscript bounds checks

[joeuser]

I think I have the right piece of text here.


        >The remaining 4 occur in this context:
        >    subtype Simplex_Range is Natural range 0 .. Point'Length;
        >    P: "array (Simplex_Range) of ..."
        >    Y: "array (Simplex_Range) of ..."
        >    X: Point;
        >    J: Simplex_Range;
        >    ...
        >    J := 0;            -- at the start, J = Simplex_Range'First
        >    for I in X'Range loop
        >       ...
        >       P(J) := ...
        >       Y(J) := ...
        >       J := J + 1;
        >    end loop;          -- at the end, J = Simplex_Range'Last
        >    P(J) := ...
        >    Y(J) := ...
        >end;

        >A reasonably smart compiler should be able to tell that these four
        >subscripts are also safe.


and this is intuitively obvious to the most casual observer?
 
I think not.

Your problem lies in the J:=J+1; statement

You would be better off to use I as your index and not J.  (and it would work 
too.)  Here is why.

What happens the first time through this loop?

I=0
J=0

BUT guess what!!!!
J:=J+1;

That means that when I=X'Last
J will become X'Last+1

This basically equates to Simplex_Range'Last+1
                 Hence-----> your constraint error

J is now out of all it's possible ranges (and the ranges for the subscripts 
for both P and Y.

Is Point a string????

I love to bitch at the compilers too, but they are never wrong.  They cannot 
be wrong because they meet their standards.  Now WE have to meet theirs.

I just hope I got this to the right person.  I don't have the original 
message and had to kind of make this up from fragments.

Re: Concerning subscript bounds checks

[Adam Beneschan]

joeuser@satcom.whit.org (joeuser) writes:
 >I think I have the right piece of text here.
 >
 >
 >        >The remaining 4 occur in this context:
 >        >    subtype Simplex_Range is Natural range 0 .. Point'Length;
 >        >    P: "array (Simplex_Range) of ..."
 >        >    Y: "array (Simplex_Range) of ..."
 >        >    X: Point;
 >        >    J: Simplex_Range;
 >        >    ...
 >        >    J := 0;            -- at the start, J = Simplex_Range'First
 >        >    for I in X'Range loop
 >        >       ...
 >        >       P(J) := ...
 >        >       Y(J) := ...
 >        >       J := J + 1;
 >        >    end loop;          -- at the end, J = Simplex_Range'Last
 >        >    P(J) := ...
 >        >    Y(J) := ...
 >        >end;
 >
 >        >A reasonably smart compiler should be able to tell that these four
 >        >subscripts are also safe.
 >
 >
 >and this is intuitively obvious to the most casual observer?
 > 
 >I think not.
 >
 >Your problem lies in the J:=J+1; statement
 >
 >You would be better off to use I as your index and not J.  (and it would work 
 >too.)  Here is why.
 >
 >What happens the first time through this loop?
 >
 >I=0
 >J=0

Uh, no.  The definition of "Point" isn't shown here, so how can you
assume that Point'first = 0?

Just from looking at the above code, without seeing the definition of
Point, my guess is that Point is an array whose 'first is 1, and the
intent was deliberately to make P and Y arrays with one more element
than X.

 >BUT guess what!!!!
 >J:=J+1;
 >
 >That means that when I=X'Last
 >J will become X'Last+1
 >
 >This basically equates to Simplex_Range'Last+1
 >                 Hence-----> your constraint error
 
*Whose* constraint error?  Nobody ever posted this code fragment
complaining about a constraint error or about code that doesn't work.
The issue being discussed was whether the unnecessary constraint
checks could be eliminated by a smart compiler.

                                -- Adam

Re: Concerning subscript bounds checks

[Richard A. O'Keefe]

I wrote
>    subtype Simplex_Range is Natural range 0 .. Point'Length;
:    P: "array (Simplex_Range) of ..."
:    Y: "array (Simplex_Range) of ..."
:    X: Point;
:    J: Simplex_Range;
:    ...
:    J := 0;            -- at the start, J = Simplex_Range'First
:    for I in X'Range loop
:       ...
:       P(J) := ...
:       Y(J) := ...
:       J := J + 1;
:    end loop;          -- at the end, J = Simplex_Range'Last
:    P(J) := ...
:    Y(J) := ...
:end;
>A reasonably smart compiler should be able to tell that these four
:subscripts are also safe.

joeuser@satcom.whit.org (joeuser) writes:

>You would be better off to use I as your index and not J.  (and it would work 
>too.)  Here is why.

No, it would NOT work.  I and J *HAVE DIFFERENT TYPES*.
J has type Simplex_Range, which is the index range for Simplex.
I has type Point'Range,   which is the index range for Point.
They are simply different types.  For example, in one use of this
function,
	Point'Range is -1 .. +1
	Simplex_Range is 0 .. 3

>What happens the first time through this loop?
>I=0
>J=0

WRONG!  THe first time through the loop, I is Point'First, which
could be *anything*, and in none of my uses of this procedure is
it zero.  Most of the time it's 1, but one example used -1.


>BUT guess what!!!!
>J:=J+1;

>That means that when I=X'Last
>J will become X'Last+1

Completely wrong.  When I = X'Last, J will be Y'Last-1.

>This basically equates to Simplex_Range'Last+1
>                 Hence-----> your constraint error

But I haven't *GOT* any constraint error.

>J is now out of all it's possible ranges (and the ranges for the subscripts 
>for both P and Y.

>Is Point a string????
No it isn't.  It's a point in Euclidean N-space.

>I love to bitch at the compilers too, but they are never wrong.  They cannot 
>be wrong because they meet their standards.  Now WE have to meet theirs.

But I *wasn't* bitching at the compiler,
it *wasn't* making any mistake,
and *neither was I*.


For what it's worth, I had great trouble figuring out how to write that
loop.  This is the simplex construction phase of nelder-mead.  The basic
idea is
	for J from P'First as I in Basis_Vector'Range loop
	    P(J) := Origin + Delta * Basis_Vector(I);
	    Y(J) := Funct(P(J));
	end loop;
	P(P'Last) := Origin;
	Y(P'Last) := F(P(P'Last));

In Algol, Fortran, or PL/I it wouldn't be much of a problem:
if Basis_Vector'Range is L..U, take P'Range to be L..U+1.
However, in Ada, U+1 may not exist.  For example,
	type Coord is (X,Y,Z);
	type Point is array (Coord) of Float;
So Simplex_Range has to be some other type.  The obvious thing was
	subtype Simplex_Range is Natural range 0 .. Point'Length;
(note that not only is the first value of I in this case not zero,
it isn't even a number).  The next obvious thing is

	for I in Point'Range loop
	    let J be Simplex_Range'Val(
		Point'Range'Pos(I) - Point'Range'Pos(Point'Range'First))
	    P(J) := ...
	
However, I couldn't figure out any way to code that conversion from I to J.
(The immediate problem is that Point'Range is a _range_, not a _(sub)type_,
so Point'Range'Pos is inexpressible.)

-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[Robert A Duff]

In article <4r7r65$nj@goanna.cs.rmit.EDU.AU>,
Richard A. O'Keefe <ok@goanna.cs.rmit.EDU.AU> wrote:
>	type Coord is (X,Y,Z);
>	type Point is array (Coord) of Float;
>So Simplex_Range has to be some other type.  The obvious thing was
>	subtype Simplex_Range is Natural range 0 .. Point'Length;
>(note that not only is the first value of I in this case not zero,
>it isn't even a number).  The next obvious thing is
>
>	for I in Point'Range loop
>	    let J be Simplex_Range'Val(
>		Point'Range'Pos(I) - Point'Range'Pos(Point'Range'First))
>	    P(J) := ...
>	
>However, I couldn't figure out any way to code that conversion from I to J.
>(The immediate problem is that Point'Range is a _range_, not a _(sub)type_,
>so Point'Range'Pos is inexpressible.)

What's wrong with "Coord'Pos(I) - Coord'Pos(Point'First)"?

By the way, if you have an array with unknown bounds, you can construct
a subtype for those bounds like this:

    subtype The_Range is The_Index_Type range The_Array'Range;

But there's no need to do that to use the 'Pos attribute.

Note that for T'Pos, the bounds of subtype T are ignored -- all that
matters is the type of that subtype.  For example:

    subtype S is Character range 'a'..'b';
    X: Integer := S'Pos('*'); -- No problem here.

S'Pos('*') is exactly the same as Character'Pos('*').

- Bob

Re: Concerning subscript bounds checks

[Richard A. O'Keefe]

I wrote:
	type Coord is ...
	type Point is array (Coord) of Float;
	    let J be Simplex_Range'Val(
		Point'Range'Pos(I) - Point'Range'Pos(Point'Range'First))
  However, I couldn't figure out any way to code that conversion from I to J.
  (The immediate problem is that Point'Range is a _range_, not a _(sub)type_,
  so Point'Range'Pos is inexpressible.)

bobduff@world.std.com (Robert A Duff) writes:

>What's wrong with "Coord'Pos(I) - Coord'Pos(Point'First)"?

I think it was probably too obvious.
For some reason, I didn't want to use the name of the index type.
I can no longer recall why.

-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[++ robin]

	ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:

	>There was some discussion in comp.lang.misc recently about array bounds
	>checks.  As an exercise, I converted Algorithm AS 47 (an implementation
	>of the Nelder-Mead simplex minimisation procedure) from Fortran to Ada.

	>The Fortran original contains 85 array subscripts.
	>The Ada version      contains 66 array subscripts.
	>Of these 66, all but 4 occur within the scope of a "for" loop
	>which *obviously* guarantees the safety of the subscript.

---I expect that the same observations could be made about
re-writing the program in PL/I, or in Fortran 90.

   Why not post the original Fortran version, and the Ada
translation, so we can see?

	>The remaining 4 occur in this context:
	>    subtype Simplex_Range is Natural range 0 .. Point'Length;
	>    P: "array (Simplex_Range) of ..."
	>    Y: "array (Simplex_Range) of ..."
	>    X: Point;
	>    J: Simplex_Range;
	>    ...
	>    J := 0;		-- at the start, J = Simplex_Range'First
	>    for I in X'Range loop
	>	...
	>	P(J) := ...
	>	Y(J) := ...
	>	J := J + 1;
	>    end loop;		-- at the end, J = Simplex_Range'Last
	>    P(J) := ...
	>    Y(J) := ...
	>end;

	>A reasonably smart compiler should be able to tell that these four
	>subscripts are also safe.

	>Fifty years of programming language research, and we end up with C++ ???

---50 years?  Wasn't Ada (after whom the language in which this
posting also appeared first) the first programmer?  Wouldn't that
make it ~130 years?

	>Richard A. O'Keefe

Re: Concerning subscript bounds checks

[Richard A. O'Keefe]

rav@goanna.cs.rmit.EDU.AU (++           robin) writes:

>---I expect that the same observations could be made about
>re-writing the program in PL/I, or in Fortran 90.

Again, this imputes to me a claim I never made.
I did not claim that Ada was *better* in this respect than PL/I or F90.
All I claimed was that it is *good*.
There is a big difference!

Obviously, APL, PL/I, and Fortran 90 have array arithmetic (although
I used APL enough to be seriously confused by PL/I's differences there).
Equally obviously, a vector arithmetic expression all of the vectors in
which have the same declared bounds needs no subscript or length checks.

>   Why not post the original Fortran version, and the Ada
>translation, so we can see?

If there's enough interest, I'll put them on the Web.
The Fortran code has _already_ been published; it's algorithm
AS 47 from the Journal "Applied Statistics".

nelder_mead.ads		 18 non-blank-non-comment lines
nelder_mead.adb		216 non-blank-non-comment lines
nelmin.f		204 non-blank-non-comment lines (my F77 version)

(rav: look in goanna:~ok/Ada.d/ if you want to see them.)

The difference between the Ada and Fortran line counts is entirely due
to my Ada style being one declaration per line, with the Fortran code
still having several grouped declarations.

>	>Fifty years of programming language research, and we end up with C++ ???

>---50 years?  Wasn't Ada (after whom the language in which this
>posting also appeared first) the first programmer?  Wouldn't that
>make it ~130 years?

I did not write "fifty years of _programming_ research" by
"fifty years or programming _language_ research".
-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Re: Concerning subscript bounds checks

[William Clodius]

In article <4qncnv$i94@goanna.cs.rmit.EDU.AU>
rav@goanna.cs.rmit.EDU.AU (++           robin) writes: 

   From: rav@goanna.cs.rmit.EDU.AU (++           robin)
   Keywords: subscripts
   Newsgroups: comp.lang.ada,comp.lang.misc,comp.lang.pl1,comp.lang.fortran
   Date: 25 Jun 1996 10:43:43 +1000
   Organization: Comp Sci, RMIT, Melbourne, Australia
   Path: newshost.lanl.gov!ferrari.mst6.lanl.gov!tesuque.cs.sandia.gov!lynx.unm.edu!newshub.tc.umn.edu!spool.mu.edu!munnari.OZ.AU!news.unimelb.EDU.AU!news.rmit.EDU.AU!goanna.cs.rmit.EDU.AU!not-for-mail
   Lines: 45
   References: <4qdj3e$btf@goanna.cs.rmit.EDU.AU>
   NNTP-Posting-Host: goanna.cs.rmit.edu.au
   NNTP-Posting-User: rav
   X-Newsreader: NN version 6.5.0 #0 (NOV)
   Xref: newshost.lanl.gov comp.lang.ada:14004 comp.lang.misc:25683 comp.lang.pl1:1161 comp.lang.fortran:40726


   ---50 years?  Wasn't Ada (after whom the language in which this
   posting also appeared first) the first programmer?  Wouldn't that
   make it ~130 years?

The fifty years undoubtably refers to the first high level language,
Plankalkul, designed in 1945 by the unemployed (for obvious reasons)
German computer engineer Konrad Zuse.  From the Language List
(http://cuiwww.unige.ch/langlist) 

   Plankalkul 
         Konrad Zuse, ca. 1945. The first programming language,
         implemented for the Z3 computer. Included arrays and
         records. Much of his work may have been either lost or
         confiscated in the aftermath of WWII. "The Plankalkul of
         Konrad Zuse", F.L. Bauer et al, CACM 15(7):678-685 (Jul 1972).

I believe that the language list is mistaken in saying that it was
implemented, although its design may have been planned for
implementation on the Z3.

Ada was a machine language programmer.

-- 

William B. Clodius		Phone: (505)-665-9370
Los Alamos National Laboratory	Email: wclodius@lanl.gov
Los Alamos, NM 87545