thoughts on "holey" enumerated types

thoughts on "holey" enumerated types

[cs.utexas.edu!utnut!utcsri!csri.toronto.edu!blaak]

The thread on converting integers to a sparse enumerated type has got
me thinking.

Couldn't enumerated types always be implemented as a contiguous range, such
that use clauses to specify member ``positions'' just affected the 'POS and
'VAL functions?

That way enumerated type operations (especially loop traversal over a range,
or array indexing) can always be efficient. The only time one needs to know a
member's position is when converting to an integer. Using 'POS and 'VAL seems
safer than unchecked_conversion in these cases anyway.

Ray
blaak@csri.toronto.edu

Re: thoughts on "holey" enumerated types

[agate!howland.reston.ans.net!usc!cs.utexas.edu!csc.ti.com!tilde.csc.ti.co]

In article <1993Sep11.192353.19703@jarvis.csri.toronto.edu> blaak@csri.toronto.
edu (Raymond Blaak) writes:
>The thread on converting integers to a sparse enumerated type has got
>me thinking.
>
>Couldn't enumerated types always be implemented as a contiguous range, such
>that use clauses to specify member ``positions'' just affected the 'POS and
>'VAL functions?

The key word in the above is "always".

The short answer is "No."

The longer answer is "No, because Ada allows the programmer to override
the compiler's default assignment of values to enumerated type names."

>That way enumerated type operations (especially loop traversal over a range,
>or array indexing) can always be efficient.

Loop traversal over a range can be made efficient, by introducing a "hidden"
induction variable that traverses a translation table in the place of the
iterated enumerated type variable.  I would be very surprised to learn that
a production-quality compiler DIDN'T do this.

Array indexing cannot be helped: by definition, when one deposits a value,
what is stored must be the correct bit pattern for the value.  Rep specs
are used to control that bit pattern.  When one later reads the value,
one gets back the same (arbitrary) bit pattern, so one has no option but
to do the translation for the array index.  Good Ada programmers understand
about this and avoid combining enumerated types with rep specs and array
indexing.

Re: thoughts on "holey" enumerated types

[agate!howland.reston.ans.net!noc.near.net!inmet!bobduff]

> The thread on converting integers to a sparse enumerated type has got
> me thinking.
> 
> Couldn't enumerated types always be implemented as a contiguous range, such
> that use clauses to specify member ``positions'' just affected the 'POS and
> 'VAL functions?

You mean "representation clauses" not "use clauses".  The 'Pos and 'Val
attributes are not affected by an enumeration_representation_clause.
The clause affects the internal representations, not the position
numbers.  The only effect is on the internal representation, which can
only be noticed by a program that does Unchecked_Conversion, or
interface to other languages, etc.

> That way enumerated type operations (especially loop traversal over a range,
> or array indexing) can always be efficient. The only time one needs to know a
> member's position is when converting to an integer. Using 'POS and 'VAL seems
> safer than unchecked_conversion in these cases anyway.

But 'Pos and 'Val do something different than Unchecked_Conversion.

> Ray
> blaak@csri.toronto.edu

- Bob Duff
  Ada 9X Mapping/Revision Team

Re: thoughts on "holey" enumerated types

[Michael Feldman]

In article <1993Sep11.192353.19703@jarvis.csri.toronto.edu> blaak@csri.toronto.
edu (Raymond Blaak) writes:
>The thread on converting integers to a sparse enumerated type has got
>me thinking.
>
>Couldn't enumerated types always be implemented as a contiguous range, such
>that use clauses to specify member ``positions'' just affected the 'POS and
>'VAL functions?
They _are_ usually so implemented by default. However, the USE repspec
is very useful for mapping enumeration values to actual bit patterns
in case this is necessary. The classic example is a device that requires
exactly one "1" bit out of, say, 4, to represent a command, say,
(Up, Down, Left, Right). One would then define

  TYPE Commands IS (Up, Down, Left, Right);
  FOR Commands USE (Up=>1, Down=>2, Left=>4, Right=>8);

The device byte would somehow be "read" (memory-mapped IO, whatever).
and no conversion would be necessary at all.

More interesting is to allow _two_ mappings:

  TYPE Commands IS (Up, Down, Left, Right); -- default used within program
  --                 0     1     2      3   (probably, but we don't care)

  TYPE ExtCommands IS NEW Commands;         -- type derivation
  FOR  ExtCommands USE (Up=>1, Down=>2, Left=>4, Right=>8);

Now: how do we get from one to the other? This is simpler than many realize:
suppose we have

  C: Commands;
  E: ExtCommands;
  . . .
  C := Commands(E):
  E := ExtCommands(C);

in other words, a straightforward explicit conversion, does the trick.
This is suggested in the Ada Rationale. I have checked it on perhaps
a dozen compilers and found that it works as I have just suggested.

The bottom line: no hacking, Unchecked_Conversion, or anything else on the
part of the programmer is needed. The type system - in Ada83 - does it all.
If you think you can beat the compiler's conversion method, you're surely
welcome to try...
>
>That way enumerated type operations (especially loop traversal over a range,
>or array indexing) can always be efficient. The only time one needs to know a
>member's position is when converting to an integer. Using 'POS and 'VAL seems
>safer than unchecked_conversion in these cases anyway.

It's not even clear to me why people insist on doing these conversions,
when there are usually easier ways. My guess is that the loop you suggest
is done on the _positions_ anyway, not on the values; why would it be 
otherwise? All the repspec should do is cause the compiler to create a
little table of the mapping. So what is the problem?

In my next message I will re-post a little compilable program illustrating 
this. Understanding and running it will probably give you some insight;
I know it opened _my_ eyes, especially when I ran it under several
compilers.

Mike Feldman
------------------------------------------------------------------------
Michael B. Feldman -  co-chair, SIGAda Education Committee
Professor, Dept. of Electrical Engineering and Computer Science
The George Washington University -  Washington, DC 20052 USA
202-994-5253 (voice) - 202-994-0227 (fax) - mfeldman@seas.gwu.edu (Internet)
"We just changed our CONFIG.SYS, then pressed CTRL-ALT-DEL. It was easy."
-- Alexandre Giglavyi, director Lyceum of Information Technologies, Moscow.
------------------------------------------------------------------------

Re: thoughts on "holey" enumerated types

[Michael Feldman]

with UNCHECKED_CONVERSION;                                                     
 
with TEXT_IO; 
procedure REPDEMO is                                                           
 

  type INT_32 is range -2**31..2**31-1;
  package MY_INT_IO is new TEXT_IO.INTEGER_IO(INT_32);
  type DIRECTION is (UP, DOWN, LEFT, RIGHT);                                   
 
  type D_ARRAY is ARRAY(1..4) of DIRECTION;                                    
 
  type PD_ARRAY is new D_ARRAY; pragma PACK(PD_ARRAY);                         
 
                                                                               
 
  -- to display values in integer form
  function D_TO_INT is NEW UNCHECKED_CONVERSION                                
 
    (SOURCE => D_ARRAY,  TARGET => INT_32);
  function PD_TO_INT is NEW UNCHECKED_CONVERSION                               
 
    (SOURCE => PD_ARRAY, TARGET => INT_32);
                                                                               
 
  type NEWDIRECTION is new DIRECTION;                                          
 
  for NEWDIRECTION use (1,2,4,8);                                              
 
  type N_ARRAY is ARRAY(1..4) of NEWDIRECTION;                                 
 
  type PN_ARRAY is new N_ARRAY; pragma PACK(PN_ARRAY);                         
 
                                                                               
 
  -- to display values in integer form
  function N_TO_INT is new UNCHECKED_CONVERSION                                
 
    (SOURCE => N_ARRAY,  TARGET => INT_32);
  function PN_TO_INT is new UNCHECKED_CONVERSION                               
 
    (SOURCE => PN_ARRAY, TARGET => INT_32);
                                                                               
 
  DIR: DIRECTION := UP;                                                        
 
  NEWDIR: DIRECTION := UP;                                                     
 
                                                                               
 
  D: D_ARRAY := (UP, DOWN, LEFT, RIGHT);                                       
 
  N: N_ARRAY;                                                                  
 
  PD: PD_ARRAY;                                                                
 
  PN: PN_ARRAY;                                                                
 
                                                                               
 
begin                                                                          
 
                                                                               
 
  N := (NEWDIRECTION(D(1)), NEWDIRECTION(D(2)),                                
 
        NEWDIRECTION(D(3)), NEWDIRECTION(D(4)));                               
 
  PD := PD_ARRAY(D);                                                           
 
  PN := PN_ARRAY(N);                                                           
 
                                                                               
 
  MY_INT_IO.PUT(D'SIZE); TEXT_IO.NEW_LINE;                                     
 
  MY_INT_IO.PUT(PD'SIZE); TEXT_IO.NEW_LINE;                                    
 
  MY_INT_IO.PUT(N'SIZE); TEXT_IO.NEW_LINE;                                     
 
  MY_INT_IO.PUT(PN'SIZE); TEXT_IO.NEW_LINE;                                    
 
  MY_INT_IO.PUT(DIR'SIZE); TEXT_IO.NEW_LINE;                                   
 
  MY_INT_IO.PUT(NEWDIR'SIZE); TEXT_IO.NEW_LINE;                                
 
                                                                               
 
  -- display hex!
  MY_INT_IO.PUT(ITEM => D_TO_INT(D),BASE=>16);                                 
 
  TEXT_IO.NEW_LINE;                                                            
 
  MY_INT_IO.PUT(ITEM => PD_TO_INT(PD),BASE=>16);                               
 
  TEXT_IO.NEW_LINE;                                                            
 
  MY_INT_IO.PUT(ITEM => N_TO_INT(N),BASE=>16);                                 
 
  TEXT_IO.NEW_LINE;                                                            
 
  MY_INT_IO.PUT(ITEM => PN_TO_INT(PN),BASE=>16);                               
 
  TEXT_IO.NEW_LINE;                                                            
 
                                                                               
 
end REPDEMO;                                                                   
 

Re: thoughts on "holey" enumerated types

[john r strohm]

In article <1993Sep12.214524.13370@seas.gwu.edu> mfeldman@seas.gwu.edu (Michael
 Feldman) writes:
>The classic example is a device that requires
>exactly one "1" bit out of, say, 4, to represent a command, say,
>(Up, Down, Left, Right). One would then define
>
>  TYPE Commands IS (Up, Down, Left, Right);
>  FOR Commands USE (Up=>1, Down=>2, Left=>4, Right=>8);
>
>The device byte would somehow be "read" (memory-mapped IO, whatever).
>and no conversion would be necessary at all.
>
>More interesting is to allow _two_ mappings:
>
>  TYPE Commands IS (Up, Down, Left, Right); -- default used within program
>  --                 0     1     2      3   (probably, but we don't care)
>
>  TYPE ExtCommands IS NEW Commands;         -- type derivation
>  FOR  ExtCommands USE (Up=>1, Down=>2, Left=>4, Right=>8);
>
>Now: how do we get from one to the other? This is simpler than many realize:
>suppose we have
>
>  C: Commands;
>  E: ExtCommands;
>  . . .
>  C := Commands(E):
>  E := ExtCommands(C);
>
>in other words, a straightforward explicit conversion, does the trick.
>This is suggested in the Ada Rationale. I have checked it on perhaps
>a dozen compilers and found that it works as I have just suggested.

The catch is that the conversion from ExtCommands (1-of-4) to Commands
involves a table search operation, and there is no general way around it.
(This particular case COULD be handled by a really smart compiler
recognizing the 1-of-4 encoding.  Consider a spec that used 2,3,5,7.)

Re: thoughts on "holey" enumerated types

[David Emery]

One of the 'problems' with enumeration representation specs is that
they can be a maintenance problem when the actual ordering of the type
is not important.  

Ordering is important for some enumeration types.  For instance,
character types need a sort order, the days of the week are ordered
(Wednesday follows Tuesday and preceeds Thursday, etc.)

For other enumeration types, there is no 'abstract order', such as with
everyone's favorite:

	type Fruit is (Apple, Pear, Orange);

The problem occurs when you use an representation clause on a type
with no 'abstract order'.  So, for one implementation/representation
of type Fruit, the following works just fine:

	for Fruit use (Apple =>1 , Pear => 2, Orange => 4);

The problem occurs when the set of values is not in the correct order.
The following is NOT LEGAL:
	
	for Fruit use (Apple =>1, Pear => 4, Orange => 2);

The enumeration representation values MUST follow the ordering given
in the type definition.  

I've run into this interfacing with C a lot.  Consider:

	#define APPLE 1
	#define PEAR 2
	#define ORANGE 4

	(void) juicer (int x);	/* maybe not strictly ANSI C, but you get
				 * the idea... */

Usually the idea is to map such structures to an enumeration type.
But if another C implementation comes up with 
	
	#define APPLE 1
	#define PEAR 4
	#define ORANGE 2

You have the illegal situation I pointed out earlier.  

So my rule is to NOT use enumeration representation clauses on
enumeration types where there is no specific 'abstract' ordering
clause.  Instead, I do the following:

	package spec:

	type Fruit is (Apple, Pear, Orange);

	procedure Juicer (the_fruit : Fruit);	

	package body:

	procedure Juicer_in_C (fruit_int : integer);
	pragma interface (C, Juicer_in_C);

	type Representation_Enumeration is array (Fruit) of Integer;
	Fruit_Rep : constant Representation_Enumeration
		  := (Apple => 1, Pear => 2, Orange => 4);

	procedure Juicer (the_fruit : fruit)
	is
	begin
	  Juicer_in_C (Fruit_Rep (the_fruit));
		-- for any reasonable compiler, the cost of this
		-- is a single indirect addressing operation.
	end Juicer;

The other advantage of this scheme is that changing the representation
is hidden in the body of the package, so that a change to the values
in the representation doesn't cause a recompilation of every unit that
depends on the public definition of the enumeration type.

				dave