Type declarations in a subprogram

Type declarations in a subprogram

[cis.ohio-state.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland.]

Why would anyone want to declare a type in a subprogram? I have
occaisionally done it in toy programs (a single procedure) but have
never needed it in any "real" code that I have written. I was wondering
if it supports some particular programming paradigm or if it was just
included in the language for toy programs and because no one had a good
reason to exclude it.

If anyone has an example where a local type declaration makes the code
clearer or more elegant I would be particularly interested in seeing it.

Robb Nebbe
nebbe@lglsun.epfl.ch

Re: Type declarations in a subprogram

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!usenet.ins.]

In article <1993Jun16.164301@lglsun.epfl.ch> nebbe@lglsun.epfl.ch 
(Robb Nebbe) writes:

> Why would anyone want to declare a type in a subprogram? I have
> occaisionally done it in toy programs (a single procedure) but have
> never needed it in any "real" code that I have written. I was wondering
> if it supports some particular programming paradigm or if it was just
> included in the language for toy programs and because no one had a good
> reason to exclude it.
>
> If anyone has an example where a local type declaration makes the code
> clearer or more elegant I would be particularly interested in seeing it.

I do this fairly frequently in real code.  One example that I found in
my code is:

        function determine_unit_order (utable : unit_info_table)
                        return unit_info_table;

unit_info_table is an array of Ada library units; the "utable"
parameter is an array that contains information on all units in an Ada
program.  Part of this information is dependency information, i.e.
what procedures or packages "with" other procedures or packages.  The
purpose of this function is to return a sorted version of its
parameter, sorted so that if unit A depends on unit B, then B appears
before A in the table.

The algorithm used is a topological sort algorithm found in Knuth's
_The Art of Computer Programming_, section 2.2.3.  This algorithm
requires an additional data structure to be created, so I declared a
record type inside the body of determine_unit_order.  It would be
illogical to declare this record type outside the procedure, since the
record type is pertinent only to this particular algorithm, and no
other procedure would ever use objects of this type.

This is a typical example of why I'd declare a type inside a
subprogram.  In other cases, a subprogram I'm writing may use an
algorithm that needs to build a linked list of some data type.  Again,
it's logical to declare the necessary types inside the subprogram
since they're pertinent to the algorithm.  Essentially, if I create a
type in order to implement some algorithm, I define the type inside
the subprogram that implements the algorithm.

Hope this helps.

                                -- Adam

Re: Type declarations in a subprogram

[cis.ohio-state.edu!math.ohio-state.edu!magnus.acs.ohio-state.edu!csn!news.usafa.af.mil!kirk!cwarack]

In article <C8q3Ep.JM2@irvine.com>, adam@irvine.com (Adam Beneschan) writes:
|> In article <1993Jun16.164301@lglsun.epfl.ch> nebbe@lglsun.epfl.ch 
|> (Robb Nebbe) writes:
|> 
|> > Why would anyone want to declare a type in a subprogram? I have
|> > occaisionally done it in toy programs (a single procedure) but have
|> > never needed it in any "real" code that I have written. I was wondering
|> > if it supports some particular programming paradigm or if it was just
|> > included in the language for toy programs and because no one had a good
|> > reason to exclude it.
|> >
|> > If anyone has an example where a local type declaration makes the code
|> > clearer or more elegant I would be particularly interested in seeing it.
|> 
|> I do this fairly frequently in real code.  One example that I found in
|> my code is:
|> 
   [...] explanation and example deleted.

While Adam gives an example of why you might want this capability, I have
to ask why you wouldn't want it?  To prohibit it would just add additional
rules that apply to some declarative parts but not to others.  Why is this
a benefit?  It's simpler to define declarative parts the same.  Given that,
you could declare a type in the middle of a loop if you wanted to by using
a block statement.  I'll probably never do it, but it's nice to know that
the declarative part of a package spec, subprogram, and block statement
are the same.

-- 
Christopher A. Warack, Capt, USAF
Computer Science Department, US Air Force Academy

cwarack@kirk.usafa.af.mil                (719) 472-2401

Re: Type declarations in a subprogram

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!usc!elroy.j]

In article <1993Jun16.164301@lglsun.epfl.ch>, nebbe@lglsun.epfl.ch (Robb Nebbe)
 writes...
>Why would anyone want to declare a type in a subprogram? 

First of all, the distinction between a "subprogram" and a "main program"
is somewhat artificial.  If there is a reason to do it in a main, why
wouldn't there be a reason in a sub?

Here's one of a possible infinite numbe of examples:

function Recognizer(Input : String) return Boolean is

   type State_Type is (State_1, State_2, State_3, ... );

   Current_State : State_Type := State_1;

   Return_Value : Boolean := False;

begin

   for Index in Input'range loop

      case Current_State is

         when State_1 =>
            . . .
            Current_State := . . .

         when . . .

            . . .

            Return_Value := True;

            . . .

      end case;

      exit when Current_State = State_N;

   end loop;

end Recognizer;

Re: Type declarations in a subprogram

[pipex!warwick!zaphod.crihan.fr!vishnu.jussieu.fr!univ-lyon1.fr!scsing.swi]

In article <1vnss6$dmv@usafa2.usafa.af.mil>, cwarack@kirk.usafa.af.mil (Chris W
arack <sys mgr>) writes:
: In article <1993Jun16.164301@lglsun.epfl.ch> nebbe@lglsun.epfl.ch 
: (Robb Nebbe) writes:
: 
: > Why would anyone want to declare a type in a subprogram?
: 
: ... I have to ask why you wouldn't want it?  To prohibit it would just
: add additional rules that apply to some declarative parts but not to
: others.  Why is this a benefit?  It's simpler to define declarative
: parts the same.  Given that, you could declare a type in the middle of
: a loop if you wanted to by using a block statement.  I'll probably
: never do it, but it's nice to know that the declarative part of a
: package spec, subprogram, and block statement are the same.
: 
: -- 
: Christopher A. Warack, Capt, USAF
: Computer Science Department, US Air Force Academy
: 
: cwarack@kirk.usafa.af.mil                (719) 472-2401

I was particularly interested in type declarations in procedures
because of some of the restrictions that Ada 9X is placing on tagged
types and access to subprogram types.

If I'm not mistaken tagged types may not be declared or derived in the
declarative part of a subprogram. As Tucker is fond of saying this is
an engineering decision where the benefits were weighed against the
cost (in terms of implementation difficulty) and a decision made.

As you might guess (or know) having one uniform declarative part is
nice since it makes the language more regular but it doesn't come for
free. If you add the concept of class to a language then declaring a
class or subclass in a subprogram is theoretically complex and I will
trust the 9X teams decision that it is also complex to implement.

In Ada 83 declaring a subprogram inside another subprogram  introduces
the possibility of variable aliasing (this is declared erroneous in the
LRM but that doesn't make it go away) and can lead to problems when an
local procedure is used to instantiate a generic subprogram as seen by
the inability of numerous compilers to handle this correctly.

C just avoids the problem (and any benefits) entirely by not permitting
the programmer to declare a type or functions inside a function.

In computer science people tend to fall into the trap of always asking
why not rather than why. Proving that something is not bad is entirely
different than proving that it is good.

One of the traps that many begining C programmers fall into is assuming
that anything the compiler lets them do (and which is thus not bad) is
good.

It is probably worth noting that Wirth removed the ability to declare a
module in another module when he moved from Modula 2 to Oberon. His
justification was that while submodules were not bad they weren't good
either; so he took them out.

Well, I've gone on long enough.

Robb

Re: Type declarations in a subprogram

[Tucker Taft]

In article <1993Jun17.131003@lglsun.epfl.ch> 
  nebbe@lglsun.epfl.ch (Robb Nebbe) writes:

> . . .
>I was particularly interested in type declarations in procedures
>because of some of the restrictions that Ada 9X is placing on tagged
>types and access to subprogram types.
>
>If I'm not mistaken tagged types may not be declared or derived in the
>declarative part of a subprogram. As Tucker is fond of saying this is
>an engineering decision where the benefits were weighed against the
>cost (in terms of implementation difficulty) and a decision made.

This is not the actual 9X rule.  The rule is that
any extension of a tagged type must be at the 
same "accessibility" level as the parent type.
("Accessibility" level is essentially the lexical nesting level,
but ignoring package nesting -- only subprograms and
tasks create new levels of accessibility.)

Tagged types may be declared in the declarative 
part of a subprogram, but they are then restricted to that "universe."

Similarly, a value of an access-to-subprogram type may
only designate subprograms declared at the same accessibility
level as its type (or more global than its type).  It may
not designate subprograms more deeply nested than its type.

These accessibility rules are designed to prevent
"dangling" references.  If one allowed a tagged type
to be extended in nested scopes, or if one allowed
a value of a global access type to point at a nested
subprogram, references to nested scopes might persist
past the end of the scope.

Note that unlike access-to-subprogram values,
generic formal subprograms have no accessibility restrictions,
since one can't assign the "value" of a generic formal 
subprogram to a global variable.
In this sense these two capabilities of dealing with
subprograms as "parameters" are complementary.
Access-to-subprogram values are good for storing references
to subprograms in tables or other data structures, while
generic formal subprograms allow a generic algorithm to incorporate
a call on an arbitrary subprogram provided at instantiation time.

In my own personal coding style, I tend to avoid nesting "significant"
types and subprograms inside other subprograms, since such nested 
types and subprograms are inevitably less reusable.  
The ability to declare types and subprograms in 
package bodies in Ada satisfies the need for information
hiding, while avoiding any run-time overhead associated with nesting.

Be that as it may, there are reasons to build entire subsystems
nested inside a subprogram, for example, to automatically
reclaim all storage associated with the subsystem when the enclosing
subprogram is exited.  In Ada, this is probably more naturally
done by coding the subsystem as a generic, and then instantiating
it inside a subprogram.

In any case, such "nested subsystems" are well supported in
Ada 9X, since the accessibility rules are all based on
relative accessiblity level, not on absolute accessibility level.
You can take a set of global packages that represent a subsystem,
and move them in their entirety into the declarative part of 
some subprogram and not run into problems with "accessibility"
checks.  You of course lose some of the nice advantages
of separate compilation (though generics can be used to some
extent to offset this).

> . . .
>C just avoids the problem (and any benefits) entirely by not permitting
>the programmer to declare a type or functions inside a function.

C allows types to be declared inside of functions.
It doesn't allow nested functions (though GNU C does).
GNU C goes to some trouble to allow pointers to nested
functions to work, so long as the enclosing scope remains
intact.  This is consistent with the C philosophy of 
giving the programmer plenty of rope.

The Ada philosophy is that the language features should
be inherently reliable, and only through explicit escape
hatches should reliability be compromisable.  Ada 9X has
retained (and in some cases strengthened) this focus
on inherent reliability, while also making sure that
the escape hatches (such as Unchecked_Access and
Unchecked_Conversion) have well-defined and portable semantics 
when used appropriately.

One inevitable downside of providing inherent reliability is that
the language has more compile time restrictions and run time checks.
However, if the restrictions are engineered carefully, the
typical programmer will only run into a restriction when a check is
in fact detecting a likely mistake in the submitted program.
Hence the apparent added complexity in the language description
mostly concerns the compiler-writer, while providing better
compile time error detection for the programmer, and actually
simplifying the description of the ultimate run time effect of
a piece of code.

In other words, the upside of having more consistency
checks is that the actual run time effect of a piece of Ada code,
presuming it survives the various compile time and run time checks, is
well-defined and quite easy for the "reader" of the code to predict.

If you look at a section of the Ada reference manual, you should find 
that it often reads roughly like "check this and this and this at 
compile-time, check this and this at run-time, and then do the 
obvious thing."

Hence, in Ada the puzzle is more often "is the following legal?"
whereas in languages with a more permissive set of
compile time and run time rules, the puzzle is more often 
"what does this do?"  

In Ada 9X, we have tried to remove certain "arbitrary" 
Ada 83 restrictions that didn't add to reliability,
while choosing a set of restrictions for the new 9X features that
ensure that inherent reliability remains the hallmark for Ada.

>Robb

S. Tucker Taft    stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138

Re: Type declarations in a subprogram

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!agate!doc.i]

In article <C8rt5H.76E@inmet.camb.inmet.com>, stt@spock.camb.inmet.com (Tucker 
Taft) writes:
: ...
: any extension of a tagged type must be at the 
: same "accessibility" level as the parent type.
: ("Accessibility" level is essentially the lexical nesting level,
: but ignoring package nesting -- only subprograms and
: tasks create new levels of accessibility.)
: 
: Tagged types may be declared in the declarative 
: part of a subprogram, but they are then restricted to that "universe."

So the only difference would then be that one could derive an new type
from integer but one couldn't derive a new type from a tagged type
(declared at another "accessibility" level) inside a subprogram.

Looks much more reasonable than the rule I saw. Ada 9X is really
starting to shape up nicely.

: In Ada 9X, we have tried to remove certain "arbitrary" 
: Ada 83 restrictions that didn't add to reliability,
: while choosing a set of restrictions for the new 9X features that
: ensure that inherent reliability remains the hallmark for Ada.
: 
: >Robb
: 
: S. Tucker Taft    stt@inmet.com
: Ada 9X Mapping/Revision Team
: Intermetrics, Inc.
: Cambridge, MA  02138
: 

Robb