Discriminant computation problem

Discriminant computation problem

[Sandro Magi]

Just learning Ada and I came across this little issue. I can't perform a
computation on a discriminant. Suppose I want to create a bit vector type
that uses an array of Integers as its underlying storage type (just an
example). I want the user to provide the length of the bit vector in bits,
but I need to define the upper bound on the Integer array in Integer'Size
units.

type Int_Array is array (Positive range <>) of Integer;

type Bit_Vector (Max_Bit_Size : Positive) is
record
 Series : Int_Array (Positive'First .. Max_Bit_Size/Integer'Size);
end record;

The compiler error gnat produces: "discriminant in constraint must appear
alone". Is there something I'm doing wrong, or is the above simply not
possible?

I can solve this either by breaking the encapsulation of my type so that the
user must perform the computation ahead of time (not preferable), or by
creating a special function which computes the real upper bound. So the
user would have to instantiate:

bv : Bit_Vector(Real_Upper_Bound(1024)); --1024 bits

Instead of:

bv : Bit_Vector(1024); --1024 bits

Does anyone have a better answer?

Re: Discriminant computation problem

[Jim Rogers]

Sandro Magi <smagi@naasking.homeip.net> wrote in
news:NmTld.122$rc.97840@news20.bellglobal.com: 

> Just learning Ada and I came across this little issue. I can't perform
> a computation on a discriminant. Suppose I want to create a bit vector
> type that uses an array of Integers as its underlying storage type
> (just an example). I want the user to provide the length of the bit
> vector in bits, but I need to define the upper bound on the Integer
> array in Integer'Size units.
> 
> type Int_Array is array (Positive range <>) of Integer;
> 
> type Bit_Vector (Max_Bit_Size : Positive) is
> record
>  Series : Int_Array (Positive'First .. Max_Bit_Size/Integer'Size);
> end record;

You might want to reconsider your design.
First of all, your chosen example is a very poor way to represent
a bit vector in Ada. This appears to be an Ada translation of a C
or C++ programming approach. 

A more Ada-like way to accomplish your ends is:

type Bit_Vector is array(Positive range <>) of Boolean;
pragma Pack(Bit_Array);

If you want to hide this implementation you can provide
a package such as:

package Bit_Vectors is
   type Bit_Vector(Max_Size : Positive) is private;
   ....
private
   type Internal_Vector is array(Positive range <>) of Boolean;
   pragma Pack(Internal_Vector);
   type Bit_Vector(Max_Size : Positive) is record
      Buffer : Internal_Vector(Max_Size);
   end record;
end Bit_Vectors;

Each bit is individually addressable through array indexing.
A packed array of boolean results in each boolean element 
occupying a single bit.

There is no advantage in using an Integer type as an underlying
element size. Integer is always a signed type. You will always 
error by not accounting for the sign bit.

My second point deals with your desire to perform a calculation
on a parameterized value. The more acceptable way to accomplish
such an end is the use of a generic package rather than a
record discriminant. The use of a generic package provides
encapsulation and information hiding for your operations that
prevent you from unnecessarily exposing internal data structures.

Jim Rogers

Re: Discriminant computation problem

[Sandro Magi]

Jim Rogers <jimmaureenrogers@att.net> wrote in message news:<yjVld.906538$Gx4.504752@bgtnsc04-news.ops.worldnet.att.net>...
> You might want to reconsider your design.
> First of all, your chosen example is a very poor way to represent
> a bit vector in Ada. This appears to be an Ada translation of a C
> or C++ programming approach. 

As I said, it was just the simplest example of what I was trying to
do. It's not what I'm actually trying to do.

> My second point deals with your desire to perform a calculation
> on a parameterized value. The more acceptable way to accomplish
> such an end is the use of a generic package rather than a
> record discriminant. The use of a generic package provides
> encapsulation and information hiding for your operations that
> prevent you from unnecessarily exposing internal data structures.

I was trying to avoid the extra step of instantiating a generic
package. Furthermore, the types from one package would not be
interoperable with the types from another package would they? ie.
using my Bit_Vector example and assuming the package defines an Append
operation:

procedure Test is
  package Bit_Vector_1024 is new Bit_Vector(1024);
  package Bit_Vector_2048 is new Bit_Vector(2048);

  b1024 : Bit_Vector_1024.Bit_Vector;
  b2048 : Bit_Vector_2048.Bit_Vector;
begin
  ...
  (initialize some data in each vector)
  ...
  --this would fail to type check wouldn't it?
  Append(Data=>b1024, To=>b2048);
end Test;

Sorry for asking something so obvious, but I can't check this myself
at the moment.

Re: Discriminant computation problem

[Martin Krischik]

Sandro Magi wrote:

> Jim Rogers <jimmaureenrogers@att.net> wrote in message
> news:<yjVld.906538$Gx4.504752@bgtnsc04-news.ops.worldnet.att.net>...
>> You might want to reconsider your design.
>> First of all, your chosen example is a very poor way to represent
>> a bit vector in Ada. This appears to be an Ada translation of a C
>> or C++ programming approach.
> 
> As I said, it was just the simplest example of what I was trying to
> do. It's not what I'm actually trying to do.
> 
>> My second point deals with your desire to perform a calculation
>> on a parameterized value. The more acceptable way to accomplish
>> such an end is the use of a generic package rather than a
>> record discriminant. The use of a generic package provides
>> encapsulation and information hiding for your operations that
>> prevent you from unnecessarily exposing internal data structures.
> 
> I was trying to avoid the extra step of instantiating a generic
> package. Furthermore, the types from one package would not be
> interoperable with the types from another package would they? ie.
> using my Bit_Vector example and assuming the package defines an Append
> operation:
> 
> procedure Test is
>   package Bit_Vector_1024 is new Bit_Vector(1024);
>   package Bit_Vector_2048 is new Bit_Vector(2048);
> 
>   b1024 : Bit_Vector_1024.Bit_Vector;
>   b2048 : Bit_Vector_2048.Bit_Vector;

Hint: When you have a package and a type with the same name you can't "use"
that package without risking name clashes. That's why most packages have
name for multiples like Unbounded_Strings.

> begin
>   ...
>   (initialize some data in each vector)
>   ...
>   --this would fail to type check wouldn't it?
>   Append(Data=>b1024, To=>b2048);
> end Test;
> 
> Sorry for asking something so obvious, but I can't check this myself
> at the moment.

Deppends on how the types and the parameters are defined. If both
Bit_Vector_1024.Bit_Vector and Bit_Vector_2048.Bit_Vector are subtypes with
a common ancestor then it well could work:

In Ada, with it's extensive type system, getting the types right is more
important then getting the procedures right.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Discriminant computation problem

[Dmitry A. Kazakov]

On 15 Nov 2004 06:02:39 -0800, Sandro Magi wrote:

> I was trying to avoid the extra step of instantiating a generic
> package. Furthermore, the types from one package would not be
> interoperable with the types from another package would they? ie.
> using my Bit_Vector example and assuming the package defines an Append
> operation:
> 
> procedure Test is
>   package Bit_Vector_1024 is new Bit_Vector(1024);
>   package Bit_Vector_2048 is new Bit_Vector(2048);
> 
>   b1024 : Bit_Vector_1024.Bit_Vector;
>   b2048 : Bit_Vector_2048.Bit_Vector;
> begin
>   ...
>   (initialize some data in each vector)
>   ...
>   --this would fail to type check wouldn't it?
>   Append(Data=>b1024, To=>b2048);
> end Test;
> 
> Sorry for asking something so obvious, but I can't check this myself
> at the moment.

Bit_Vector_1024.Bit_Vector and Bit_Vector_2048.Bit_Vector are two different
types, when they are declared in Bit_Vector as types. To avoid this you
should have a common ancestor for both. There could be three variants:

1. Constrained subtypes:

package Bit_Vectors is
   type Vector is array (Integer range <>) of Boolean;
-- or
   type Vector (Size : Natural) is private;
   procedure Append (Data : Vector; To : in out Vector);
      -- Note, Append is defined here. The common "ancestor"
      -- is unconstrained Vector
   ...
end Bit_Vectors_Base;

generic
   Size : Positive;
package Bit_Vectors.Fixed_Size is
   subtype Bit_Vector is Vector (1..Size);
   ...
end Bit_Vectors.Fixed_Size;

procedure Test is
   package Bit_Vector_1024 is new Bit_Vectors.Fixed_Size (1024);
   package Bit_Vector_2048 is new Bit_Vectors.Fixed_Size (2048);
 
   b1024 : Bit_Vector_1024.Bit_Vector;
   b2048 : Bit_Vector_2048.Bit_Vector;
begin
   Append (Data => b1024, To => b2048); -- This is OK

2. Tagged types derived from the same base:

package Bit_Vectors is
   type Vector is abstract tagged ...
   procedure Append (Data : Vector'Class; To : in out Vector) is
      abstract;
      -- Note, at least one of the parameters should be
      -- class-wide. There is no full multiple dispatch in Ada!
      -- The common ancestor there is abstract Vector.
   ...
end Bit_Vectors_Base;

generic
   Size : Positive;
package Bit_Vectors.Fixed_Size is
   type Bit_Vector is new Vector with record
      -- Here the body uses Size
   end;
   procedure Append (Data : Vector'Class; To : in out Bit_Vector);
      -- You have to implement it here for the case when To
      -- is Bit_Vector, where Data is anything possible.
end Bit_Vectors.Fixed_Size;

procedure Test is
   package Bit_Vector_1024 is new Bit_Vectors.Fixed_Size (1024);
   package Bit_Vector_2048 is new Bit_Vectors.Fixed_Size (2048);
 
   b1024 : Bit_Vector_1024.Bit_Vector;
   b2048 : Bit_Vector_2048.Bit_Vector;
begin
   Append (Data => b1024, To => b2048); -- This is OK

3. Do not use generics! Ada's unconstrained types are powerful and
efficient.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Discriminant computation problem

[Nick Roberts]

"Sandro Magi" <smagi@naasking.homeip.net> wrote in message 
news:NmTld.122$rc.97840@news20.bellglobal.com...

> Just learning Ada and I came across this little issue. I can't perform a
> computation on a discriminant. Suppose I want to create a bit vector type
> that uses an array of Integers as its underlying storage type (just an
> example). I want the user to provide the length of the bit vector in bits,
> but I need to define the upper bound on the Integer array in Integer'Size
> units.
>
> type Int_Array is array (Positive range <>) of Integer;
>
> type Bit_Vector (Max_Bit_Size : Positive) is
> record
> Series : Int_Array (Positive'First .. Max_Bit_Size/Integer'Size);
> end record;
>
> The compiler error gnat produces: "discriminant in constraint must appear
> alone". Is there something I'm doing wrong, or is the above simply not
> possible?

You are not doing anything wrong, as such. It's unfortunately necessary for 
Ada to
restrict the usage of discriminants in component constraints, so that all 
compilers
can be assured of being able to compute the size of a record from its 
discriminants
at any point without having to perform a computation of (potentially) 
unlimited
complexity or which might have side effects.

> I can solve this either by breaking the encapsulation of my type so that 
> the
> user must perform the computation ahead of time (not preferable), or by
> creating a special function which computes the real upper bound. So the
> user would have to instantiate:
>
> bv : Bit_Vector(Real_Upper_Bound(1024)); --1024 bits
>
> Instead of:
>
> bv : Bit_Vector(1024); --1024 bits
>
> Does anyone have a better answer?

I don't have a better answer. I can only additionally suggest that you could 
declare
an access type, and then an allocator function, as well as interrogation 
functions.
For example:

   Bits_Per_Element: constant := Integer'Size; -- say
   Max_Element_Index: constant := 1023; -- say
   Max_Bit_Number: constant := Max_Element_Index*Bits_Per_Element-1;

   subtype Bit_Number is Integer range 0..Max_Bit_Number;

   type Bit_Vector_Element is mod 2**Bits_Per_Element;
   subtype Element_Index is Integer range 0..Max_Element_Index;

   type Element_Array is array (Element_Index range <>) of 
Bit_Vector_Element;

   type Bit_Vector (Max: Element_Index) is
      record
         Max_Bit: Bit_Number;
         Elements: Element_Array(0..Max);
      end record;

   type Dynamic_Bit_Vector is access Bit_Vector;

   function New_Bit_Vector (Max_Bit: in Bit_Number)
         return Dynamic_Bit_Vector;

   ...

   function New_Bit_Vector (Max_Bit: in Bit_Number)
         return Dynamic_Bit_Vector is
      Max: constant Element_Index := Max_Bit/Bits_Per_Element;
   begin
      return new Bit_Vector'(
         Max      => Max,
         Max_Bit  => Max_Bit,
         Elements => (0..Max => 0) );
   end New_Bit_Vector;

I've found this problem to be a pain myself, in the past. You just just have 
to
'program around it'.

-- 
Nick Roberts

Re: Discriminant computation problem

[tmoran]

Another approach is to make the type controlled, then have the
Initialize routine do the size calculations based on the discriminant
and call an allocator for the actual data.  Finalize then deallocates
the data, of course.

>I've found this problem to be a pain myself, in the past. You just just have
>to 'program around it'.
  Yes.

Re: Discriminant computation problem

[Nick Roberts]

<tmoran@acm.org> wrote in message news:aVamd.100382$R05.30042@attbi_s53...

> Another approach is to make the type controlled, then have the
> Initialize routine do the size calculations based on the discriminant
> and call an allocator for the actual data.  Finalize then deallocates
> the data, of course.

Illustration of this technique:

   with Ada.Finalization;
   package Bit_Vectors is
      ...
      type Bit_Vector (Bit_Max: Bit_Number) is private;
      ...
   private
      ... -- declare Element_Array etc. as before

      type Vector_Payload (Max: Element_Index) is
         record
            ... -- as for Bit_Vector before
         end record;

      type Payload_Access is access Vector_Payload;

      type Bit_Vector (Bit_Max: Bit_Number) is
         new Ada.Finalization.Controlled with
         record
            Payload: Vector_Access;
         end record;

      procedure Initialize (Vector: in out Bit_Vector);
      procedure Finalize   (Vector: in out Bit_Vector);
   end;

   package body Bit_Vectors is
      ...

      procedure Free is
         new Unchecked_Deallocation( Bit_Vector_Payload,
                                    Dynamic_Bit_Vector );

      procedure Initialize (Vector: in out Bit_Vector) is
      begin
         Vector.Payload := new Bit_Vector_Payload'(
            Max => Vector.Bit_Max/Bits_Per_Element,
            ... -- as before
            );
      end;

      procedure Finalize (Vector: in out Bit_Vector) is
      begin
         Free( Vector.Payload );
      end;

      ...
   end Bit_Vectors;

This technique has the disadvantage that the type Bit_Vector is tagged, and 
that controlled types use up some extra memory (to store the list of objects 
needing finalisation). But I would guess that this unlikely to be a problem 
in pratice. It has the advantage of being a little neater to use.

-- 
Nick Roberts

Re: Discriminant computation problem

[tmoran]

More quibbling:
>     type Bit_Vector (Bit_Max: Bit_Number) is
>        new Ada.Finalization.Controlled with
>        record
>           Payload: Vector_Access;
>        end record;
  Since there's an access type around, Bit_Vector should be either
"limited" or there should be an Adjust to do a deep copy (or whatever).

>     procedure Initialize (Vector: in out Bit_Vector) is
>     begin
>        Vector.Payload := new Bit_Vector_Payload'(
  Is it possible for Initialize to be called more than once?  (Say
by an explicit call.)  If so, there should be a Free(Vector.Payload)
before assigning a "new" access value.