Procedure types and dynamic binding

Procedure types and dynamic binding

[Erland Sommarskog]

Bob Hathaway (rjh@cs.purdue.edu) writes:
>For yet another Ada 9X extension, I propose procedural variables.   
>...
>Procedural variables can
>avoid the redundant use of case statements by allowing an operation to be 
>stored within an Adt.     

I have stated my view before: a langauge revision should not introduce 
major changes, but stick to an overview of details that needs refining,
like character representation. There is one exception, though: if someone
comes up with a fully-fledged extention to give Ada dynamic binding to
make it a truly object-oriented langauge, I would whole-heartedily
support that proposal.

From this it is clear I think Bob Hathaway's idea should be rejected.
There are some gains with it, but not suffciently many. We will move
some tiny step against the O-O paradigm, but we will not be there.

Just for discussion: If we should make Ada an object-oriented langauge,
what should we add? Quite obvious seems package types to get classes.
If we could create several instances of a package, you have what Bob 
wanted and more. You have data *and* operations stored together. 
  But this doesn't suffice. This far we have just constructed task
types doesn't cost us a context change. We must have inheritance in
some way. How tell which other package types we inherit from? The 
WITH clause is not useful; it merely tells us which types we intend
to declare objects of. USE? Maybe. Doing USE on a package type to 
get all exported operations directly visible is of no interest. We 
should USE the package variable instead. But for inheritance we want 
all attributes, also those who do not appear in the specification 
part (or?), and particulary we probably want to have access to 
private types internal structure. So best would be a particular 
INHERIT clause.
  Multiple inheritance? That doesn't seem to be any problem. Ada
already has RENAMES which here could serve to remove clashes.
  Dynamic binding? We must be able to redefine a inherited operation.
There is no current construct for that in Ada so a REDEFINES clause
has to be added. (Rather useful is also deferred procedures that
inhereting packages *must* define, Ada more or less has this concept.) 
  We are about satisfied by now. Probably we need delaration a la
Eiffel, but if we could make all the rest, this would be no problem.
  Procedure types could be added for completeness, but doesn't feel
that necessary with all we added above.

Now, it is not as easy as this of course. Many detail rules has to
be thought out. And we would get an unnecessary big language. Would
we really need the sophisticated system with subtypes and derived
types? Well, we can't throw it away. 

Oh, one we need one more thing if go this way. Yes, you guessed it:
Garbage collection.

>It also allows individually parameterizable and 
>reprogrammable Adts since operations can be provided to alter the Adts actions
>or structure.  Generic subprogram parameters can only allow Adts to be set 
>once for any instantiation.  I use procedural variables and function pointers
>in Adts frequently when programming in languages other than Ada and am 
>convinced they are an elegant way to model Adt actions.

With the risk of saying something completely obvious: if you want variable
user-provided operations the following example with a tree-traversing
illustrates:

   Generic
      Type Data_type is limited private;
      With procedure Assign(A : in out Data_type; B : in Data_type);
      With function "<"(A, B : Data_type) return boolean is <>;
      With function ">"(A, B : Data_type) return boolean is <>;
   Package Binary_trees is
      Type Tree_type is private;        -- A tree with sorted data.
      Type Node_type is private;        -- A node in such a tree.
      ...
      Generic
         With Procedure Treat(Node : in     Node_type;  
                              Data : in out Data_type); 
      Procedure Traverse_forward(Tree : Tree_type);

(By the way, an example like the one above should be added to the validation
suite if it's not already there. A PC compiler I played with choked on the 
code above, and I believe it is/was validated.)
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Procedure types and dynamic binding

[Bob Hathaway]

Newsgroups: comp.lang.ada
Subject: Procedure types and dynamic binding
Message-ID: <4204@enea.se>
Date: 30 Dec 88 21:42:42 GMT
Organization: ENEA DATA AB, Sweden
Lines: 84

From Erland Sommarskog:
>Bob Hathaway (rjh@cs.purdue.edu) writes:
>>For yet another Ada 9X extension, I propose procedural variables.   
>>...
>>Procedural variables can
>>avoid the redundant use of case statements by allowing an operation to be 
>>stored within an Adt.     

>I have stated my view before: a language revision should not introduce 
>major changes, but stick to an overview of details that needs refining,
>like character representation. There is one exception, though: if someone

I disagree.  While it's not difficult to design new languages with powerful 
constructs and methodologies it is difficult to get them standardized 
and accepted.  Validated Ada compilers are available on almost every machine
and extending Ada with more modern constructs will at least provide one 
commonly available modern programming language, even if only for designing 
better ones ;-)

>comes up with a fully-fledged extension to give Ada dynamic binding to
>make it a truly object-oriented language, I would whole-heartedily
>support that proposal.

In "Concurrency and Programming Languages" by David Harland, as sited by
Bill, dynamic and static binding are provided as a module option.  I think
this is an excellent idea since most of the literature gives a mind set of 
one type of binding or the other, with the obvious general solution being to
provide both.  Another issue is the level of encapsulation in Ada dynamic
binding should be provided.  Dynamic binding of procedures and functions 
within a package is possible, but so is dynamic binding of packages.  Which
did you mean?

>From this it is clear I think Bob Hathaway's idea should be rejected.
>There are some gains with it, but not suffciently many. We will move
>some tiny step against the O-O paradigm, but we will not be there.

Procedural variables are orthogonal to "O-O" programming, they can
be used for a number of purposes.  Some typical uses are tables of procedural 
variables with generator functions and configuring device driver tables.
Array aggregates are easier to modify than in-line code and initializing
tables of procedural variables with aggregates using named associations would
make programs easy to read.  While tables do not always provide the best 
interface to programmers, I think some circumstances justify their use.

>Just for discussion: If we should make Ada an object-oriented langauge,
>what should we add? Quite obvious seems package types to get classes.
>If we could create several instances of a package, you have what Bob 
>wanted and more. You have data *and* operations stored together. 

Yes, this is the "Completion of the Adt paradigm" Bill mentioned earlier.
In a compilers class at Purdue, I implemented a class type structure which
contained its data and operations including initialization code, and
termination code would have been easy to provide as well.  But these
operations were hardwired into the declaration and a general facility to 
change Adt operations is desirable.  For example, I might want an instance 
to output data in one way but under other circumstances output data in 
another.  If an output operation is implemented as a procedural variable,
I could provide a change_output operation which changes the output operation 
in the Adt. Thereafter, the new print routine would be in effect whenever 
the output operation is invoked.

[ More about the virtues of inheritance... ]

>Now, it is not as easy as this of course. Many detail rules has to
>be thought out. And we would get an unnecessary big language. Would
>we really need the sophisticated system with subtypes and derived
>types? Well, we can't throw it away. 

I don't think procedural variables or class structures will make Ada 
much bigger.  Procedural variables are not complicated in Modula and
from my experience class type structures are not difficult to implement and 
do not complicate the language.  They would, however, provide an incremental 
improvement in data abstraction.

>With the risk of saying something completely obvious: if you want variable
>user-provided operations the following example with a tree-traversing
>illustrates:
>
>   Generic
>      Type Data_type is limited private;
>      With procedure Assign(A : in out Data_type; B : in Data_type);
>      With function "<"(A, B : Data_type) return boolean is <>;
>      With function ">"(A, B : Data_type) return boolean is <>;
>   Package Binary_trees is
>      Type Tree_type is private;        -- A tree with sorted data.
>      Type Node_type is private;        -- A node in such a tree.
>      ...
>      Generic
>         With Procedure Treat(Node : in     Node_type;  
>                              Data : in out Data_type); 
>      Procedure Traverse_forward(Tree : Tree_type);
>

This isn't what I had in mind.  What if variables of type Tree_Type should
be traversed in different ways depending on context?  As above, a case
statement is needed to choose the routine to parameterize Traverse_forward
whenever traversal is invoked.  A scheme is needed to allow Tree_Type Adts to
be programmed with different traversal routines after its declaration has been 
elaborated and without the need for case statements.  If Traverse_forward 
invoked a procedural variable stored within Tree_Type then instances of a
Tree_Type Adt could be reprogrammed to traverse the tree however desired and
a simple call to Traverse_forward would produce the desired result.  I think
this is in harmony with 'O-O' programming, which I usually refer to as Adt
programming, since the operation is stored in the Adt as a procedural variable.

                                           Bob Hathaway
					   rjh@purdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5753@medusa.cs.purdue.edu>, by rjh@cs.purdue.edu (Bob Hathaway):
> Erland writes:
>>I have stated my view before: a language revision should not introduce 
>>major changes, but stick to an overview of details that needs refining,
>>like character representation. There is one exception, though: if someone
> 
> I disagree.  While it's not difficult to design new languages with powerful 
> constructs and methodologies it is difficult to get them standardized 
> and accepted.  Validated Ada compilers are available on almost every machine
> and extending Ada with more modern constructs will at least provide one 
> commonly available modern programming language, even if only for designing 
> better ones ;-)

   I have to agree with Bob.  Since old Ada and new Ada would be fairly
   similar, automatic translators would probably be highly effective
   should the need arise.  

>>comes up with a fully-fledged extension to give Ada dynamic binding to
>>make it a truly object-oriented language, I would whole-heartedily
>>support that proposal.
> 
> In "Concurrency and Programming Languages" by David Harland, as sited by
> Bill, dynamic and static binding are provided as a module option.  I think
> this is an excellent idea since most of the literature gives a mind set of 
> one type of binding or the other, with the obvious general solution being to
> provide both.  

    Um, hold on there.  I cited Harland primarily as an example of extreme
    steps which would provide maximum support for abstraction, and I support
    Harland's view that departures from the state of maximum expressiveness
    must bear the burden of proof, but I also noted that there are certain 
    situations in which I think a convincing case can be made in this
    direction.  Most languages, though, go much too far in their restriction
    of expressiveness, including Ada.  (Still, Ada is the best language 
    available, all things considered.) 

    As far as dynamic binding goes, I think there is a need to provide
    the ability to have a program edit (or generate) a piece of source
    code, compile that code (including any necessary recompilations),
    dump any necessary local knowledge for its successor to load in, 
    initiate its successor, and finally kill itself off, but I see no 
    need to go any farther than that.  Harland gives a rather eloquent
    statement of why systems must be self-modifying, and this argument
    is convincing.  But dynamic binding (as I understand the term) is
    "too changeable", like the uncontrolled change which occurs in some
    inheritance-oriented languages.  Ada's compilation control facilities
    enable controlled change; they provide firewalls against modification
    which serve to require that all aspects of the propagating change(s)
    are considered throughout the system, and this is a very good thing
    which we should not dispense with lightly.  Even the scheme I've
    described should be applied only with extreme caution.
 
> [...] a general facility to change Adt operations is desirable.  For 
> example, I might want an instance to output data in one way but under 
> other circumstances output data in another.  If an output operation is 
> implemented as a procedural variable, I could provide a change_output 
> operation which changes the output operation in the Adt. Thereafter, 
> the new print routine would be in effect whenever the output operation 
> is invoked.

    Other than doing things as I've described above, another way would
    be (assuming that New Ada expands the idea of a specification to 
    include any accesses to externally defined objects/definitions) to
    have the output procedure examine its environment to decide what to do.

> I don't think procedural variables or class structures will make Ada 
> much bigger.  Procedural variables are not complicated in Modula [...] 

    But Modula doesn't have generics.  Using the combination of generics
    and the class abstraction outlined in my earlier article, I think
    we'll get more power, with better readability.

> This isn't what I had in mind.  What if variables of type Tree_Type should
> be traversed in different ways depending on context?  

    Just make basic traversal operations a part of your abstraction.



                                             Bill Wolfe

                                      wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Bob Hathaway]

>> I don't think procedural variables or class structures will make Ada
>> much bigger.  Procedural variables are not complicated in Modula [...]
>
[Bill Wolfe responds]
>    But Modula doesn't have generics.  Using the combination of generics
>    and the class abstraction outlined in my earlier article, I think
>    we'll get more power, with better readability.
>

Yes, class structures with generics would provide good data abstraction.
This would allow classes to be statically parameterized by types, variables, 
constants, and subprograms.  Generics are good for setting an Adt once, such as
a stack which is parameterized by its element type and a print subprogram.  
But what about dynamic parameterization?  For dynamic parameterization of data,
polymorphic parameters to Adt operations are needed to allow the greatest 
expressiveness.  An example is a stack of any element type which could be
provided by polymorphic parameters to an insert subprogram.  For dynamic 
parameterization of operations, procedural variables are needed.  An example
is a stack which can change its print operation as described previously.

Now, adding polymorphic parameters to Ada would be a sizable extension but 
adding procedural variables would be almost trivial.  Admittedly, Adt 
designers can provide a plethora of operations and programmers can use case 
statements to choose among them but this puts greater burden on the programmer
since they must now select the correct operation throughout their code.  Also,
static generic parameterization is desirable in certain cases such as in the
stack example above when the element type is known in advance and the type
system can statically perform strong typechecking for correctness.  But the
flexibility of dynamic parameterization allows maximum expressiveness 
and greater power, and so "the burden of proof" has to be made against
dynamically parameterized operations.  Since static generics and dynamic
parameterization are not mutually exclusive, both could be provided.

>> This isn't what I had in mind.  What if variables of type Tree_Type should
>> be traversed in different ways depending on context?
>
>    Just make basic traversal operations a part of your abstraction.
>

But this calls for case statements throughout the program to determine which 
operation to call, as mentioned above.  For maximum expressiveness, I might
want to set instances with particular traversal operations and then use a
single operation invocation at a later point in the program which will invoke
the correct operation for all instances, reducing redundant code and allowing 
maximum expressiveness.


					Bob Hathaway
                                        rjh@purdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5790@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
> 
>>> I don't think procedural variables or class structures will make Ada
>>> much bigger.  Procedural variables are not complicated in Modula [...]
>>
> [Bill Wolfe responds]
>>    But Modula doesn't have generics.  Using the combination of generics
>>    and the class abstraction outlined in my earlier article, I think
>>    we'll get more power, with better readability.
>>
> Yes, class structures with generics would provide good data abstraction.
> This would allow classes to be statically parameterized by types, variables, 
> constants, and subprograms.  Generics are good for setting an Adt once, such as
> a stack which is parameterized by its element type and a print subprogram.  
> But what about dynamic parameterization?  For dynamic parameterization of data,
> polymorphic parameters to Adt operations are needed to allow the greatest 
> expressiveness.  An example is a stack of any element type which could be
> provided by polymorphic parameters to an insert subprogram.  For dynamic 
> parameterization of operations, procedural variables are needed.  

     No, all we need is the ability to have pointers which are not bound
     to any specific type.  Most of the time we want to say "pointer to
     SPECIFIC_TYPE", but sometimes we just want to say "pointer".  Given
     the ability to specify an unrestricted pointer, we can implement
     the desired stack (or whatever) of any element type. 
 
> Now, adding polymorphic parameters to Ada would be a sizable extension

     Not true; all we need to do is write procedures which require an
     arbitrary pointer as a parameter, and we're done.

> static generic parameterization is desirable in certain cases such as in the
> stack example above when the element type is known in advance and the type
> system can statically perform strong typechecking for correctness.  

     Quite true, and pointers should be restricted wherever it is reasonable
     to do so, just as ranges should be specified whenever appropriate.

# But the
# flexibility of dynamic parameterization allows maximum expressiveness 
# and greater power, and so "the burden of proof" has to be made against
# dynamically parameterized operations.  Since static generics and dynamic
# parameterization are not mutually exclusive, both could be provided.

     Unless, as I have shown above, a simpler mechanism will suffice.

#>> What if variables of type Tree_Type should
#>> be traversed in different ways depending on context?
#>
#>    Just make basic traversal operations a part of your abstraction.
#>
# 
# But this calls for case statements throughout the program to determine which 
# operation to call, as mentioned above.  For maximum expressiveness, I might
# want to set instances with particular traversal operations and then use a
# single operation invocation at a later point in the program which will invoke
# the correct operation for all instances, reducing redundant code and allowing 
# maximum expressiveness.

   Using the above mechanism, we've eliminated the case statements.

   Now set up your abstraction to provide a "current node" concept,
   along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND.
   This can be implemented either via parent pointers or via a secret
   stack which holds the path of descent used to reach the current node.



                                           Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Bob Hathaway]

>> Yes, class structures with generics would provide good data abstraction.
>> This would allow classes to be statically parameterized by types, variables,
>> constants, and subprograms.  Generics are good for setting an Adt once, 
>> such as
>> a stack which is parameterized by its element type and a print subprogram.  
>> But what about dynamic parameterization?  For dynamic parameterization of
>> data,
>> polymorphic parameters to Adt operations are needed to allow the greatest 
>> expressiveness.  An example is a stack of any element type which could be
>> provided by polymorphic parameters to an insert subprogram.  For dynamic 
>> parameterization of operations, procedural variables are needed.  
>
>     No, all we need is the ability to have pointers which are not bound
>     to any specific type.  Most of the time we want to say "pointer to
>     SPECIFIC_TYPE", but sometimes we just want to say "pointer".  Given
>     the ability to specify an unrestricted pointer, we can implement
>     the desired stack (or whatever) of any element type. 

But this assumes no type or error checking at all.  By dynamic 
parameterization I meant with runtime type and error checking.  For static
typechecking of data we can use a pointer to a tagged variant record to
distinguish types.  This assumes foreknowledge of the types in the variant
but at least allows subprograms to distinguish objects.   With unbound
pointers, there is no built-in type or error checking mechanism.  This
covers the case of "pseudo" polymorphic parameters but what about
dynamically parameterized operations?  Ada has an address type applicable
to function and task type addresses but this is implementation dependent
and there is no defined typechecking mechanism for the subprogram parameter
structure as there is with procedural variables.  Unbound pointers to
functions have the same consequences.  While tasks can allow procedural
abstraction, better is a higher order construct such as procedural
variables.

>> 
>> Now, adding polymorphic parameters to Ada would be a sizable extension
>
>     Not true; all we need to do is write procedures which require an
>     arbitrary pointer as a parameter, and we're done.

I meant with runtime typechecking and how this should be done is another 
point.  Milner's type system uses static typechecking for polymorphic 
parameters but doesn't seem to provide the necessary power for arbitrary 
polymorphism.  More powerful is a scheme which invokes operations on 
arbitrary types at runtime with dynamic type and error checking mechanisms
and not just simple statically checked invocation.  This requires a more
elaborate mechanism but adding polymorphism to Ada's static type system
would allow programmers to fully specify types for static checking and 
efficiency or choose a more powerful parameter passing mechanism for
greater expressiveness however polymorphic parameters and variables would 
entail major changes to the LRM.  On dynamically parameterized operations, 
if incremental improvement is the goal of the Ada-9X standard then 
simple statically checked dynamically parameterized operations can be
provided with procedural variables.  Dynamic typechecking of procedural
variables is also possible but I was advocating statically checked
procedural variables as an extension.

># But the
># flexibility of dynamic parameterization allows maximum expressiveness 
># and greater power, and so "the burden of proof" has to be made against
># dynamically parameterized operations.  Since static generics and dynamic
># parameterization are not mutually exclusive, both could be provided.
>
>     Unless, as I have shown above, a simpler mechanism will suffice.

But this "proof" doesn't apply to dynamically parameterized operations
with type and error checking as defined above, could you comment on that
also?


>#>> What if variables of type Tree_Type should
>#>> be traversed in different ways depending on context?
>#>
>#>    Just make basic traversal operations a part of your abstraction.
>#>
> 
> But this calls for case statements throughout the program to determine which 
># operation to call, as mentioned above.  For maximum expressiveness, I might
># want to set instances with particular traversal operations and then use a
># single operation invocation at a later point in the program which will invoke
># the correct operation for all instances, reducing redundant code and allowing
># maximum expressiveness.
>
>  Using the above mechanism, we've eliminated the case statements.
>

I'm not sure what this means.  With pointers to functions there should
be typechecking of parameter structures and this is the essence of
procedural variables.


>   Now set up your abstraction to provide a "current node" concept,
>  along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND.
>  This can be implemented either via parent pointers or via a secret
>  stack which holds the path of descent used to reach the current node.
>

Yes this would work, but leaves programmers to build their own traversal 
routines.  My idea was to provide a mechanism allowing programmers to specify
a procedural invocation in a single, simple statement and have the Adt
select and carry out the operation implicitly.


                                           Bob Hathaway
                                           rjh@purdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5793@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
>>     all we need is the ability to have pointers which are not bound
>>     to any specific type.  Most of the time we want to say "pointer to
>>     SPECIFIC_TYPE", but sometimes we just want to say "pointer".  Given
>>     the ability to specify an unrestricted pointer, we can implement
>>     the desired stack (or whatever) of any element type. 
> 
> But this assumes no type or error checking at all.  By dynamic 
> parameterization I meant with runtime type and error checking.  

    The same runtime type and error checking will occur with
    the unrestricted pointers.  When an operation is applied
    to the object pointed to, the type of that object will
    be used to determine which code to invoke or to prove
    the existence of a run-time error.  Now I see no reason
    why we can't say "pointer to TYPE_1 or TYPE_2 (etc.)",
    thus introducing a new form of restricted pointer, but
    what we are dealing with here is the need to store 
    any type of object whatsoever.  Clearly, unrestricted 
    pointers, with their associated run-time costs, should 
    only be used when their power is absolutely necessary. 

> For static typechecking of data we can use a pointer to a tagged variant 
> record to distinguish types.  This assumes foreknowledge of the types in 
> the variant but at least allows subprograms to distinguish objects.   

    What you describe is a hack which would provide (less cleanly) the
    power provided by the form of restricted pointer described above.

    This is inappropriate to the problem under discussion, which 
    assumes the need to program a polymorphic stack without foreknowledge
    of the types of objects to be stacked.

> but what about dynamically parameterized operations?  Ada has an address 
> type applicable to function and task type addresses but this is 
> implementation dependent and there is no defined typechecking mechanism 
> for the subprogram parameter structure as there is with procedural 
> variables.  Unbound pointers to functions have the same consequences.  
> While tasks can allow procedural abstraction, better is a higher order 
> construct such as procedural variables.

     I have described in earlier articles mechanisms by which the
     desired effects can be achieved in a more intuitive manner.

     Please provide a concrete example in which the provided
     mechanisms would prove inadequate.

>>  Now set up your abstraction to provide a "current node" concept,
>>  along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND.
>>  This can be implemented either via parent pointers or via a secret
>>  stack which holds the path of descent used to reach the current node.
> 
> Yes this would work, but leaves programmers to build their own traversal 
> routines.  My idea was to provide a mechanism allowing programmers to specify
> a procedural invocation in a single, simple statement and have the Adt
> select and carry out the operation implicitly.

   But wasn't the basis of your argument the claim that the usual
   preorder, postorder, and inorder traversal schemes may not be
   enough?  The solution to this question is clearly to proceed
   as I have described.  Perhaps you could clarify the problem
   under consideration and the precise nature of your solution...



                                    Bill Wolfe

                             wtwolfe@hubcap.clemson.edu
 

Re: Procedure types and dynamic binding

[Bob Hathaway]

> 
> But this assumes no type or error checking at all.  By dynamic 
> parameterization I meant with runtime type and error checking.  
>
>    The same runtime type and error checking will occur with
>    the unrestricted pointers.  When an operation is applied
>    to the object pointed to, the type of that object will
>    be used to determine which code to invoke or to prove
>    the existence of a run-time error.  Now I see no reason
>    why we can't say "pointer to TYPE_1 or TYPE_2 (etc.)",
>    thus introducing a new form of restricted pointer, but
>    what we are dealing with here is the need to store 
>    any type of object whatsoever.  Clearly, unrestricted 
>    pointers, with their associated run-time costs, should 
>    only be used when their power is absolutely necessary. 

I'm still not sure what this means.  Do you mean passing 
unrestricted pointers to procedures and then selecting the 
procedure via overloading (ad-hoc polymorphism) at runtime?
I meant allowing polymorphic parameters to a particular subprogram, 
such as
        procedure test (parameter : polymorphic; ...) is ...
which defeats static typechecking of parameter and uses a 
type attribute in the body of test.  This also brings up the issue of 
name vs. structural equivalence of runtime typechecking in both cases,
but the usual Ada rules could apply.   Either approach allows 
considerable power but adding runtime typechecking is not a trivial
extension, as discussed earlier.  But I agree a more powerful parameter
passing mechanism is highly desirable.

>> For static typechecking of data we can use a pointer to a tagged variant 
>> record to distinguish types.  This assumes foreknowledge of the types in 
>> the variant but at least allows subprograms to distinguish objects.   
>
>    What you describe is a hack which would provide (less cleanly) the
>    power provided by the form of restricted pointer described above.
>
>    This is inappropriate to the problem under discussion, which 
>    assumes the need to program a polymorphic stack without foreknowledge
>    of the types of objects to be stacked.

I agree, I thought you were talking about unbound pointers; insufficient
semantics of unrestricted pointers was given.

>> but what about dynamically parameterized operations?  Ada has an address 
>> type applicable to function and task type addresses but this is 
>> implementation dependent and there is no defined typechecking mechanism 
>> for the subprogram parameter structure as there is with procedural 
>> variables.  Unbound pointers to functions have the same consequences.  
>> While tasks can allow procedural abstraction, better is a higher order 
>> construct such as procedural variables.
>
>     I have described in earlier articles mechanisms by which the
>     desired effects can be achieved in a more intuitive manner.
>
>     Please provide a concrete example in which the provided
>     mechanisms would prove inadequate.

Ok.  Here is an (uncommented fast prototype) example which could easily 
apply to Ada Adts as well.  This is similar to a project I once worked 
on here and similar constructs have appeared throughout the literature.
This does not however, give away any trade secrets.  There are many 
possibilities such as type inference of the generic parameters (ML), 
full static declarations of generics (current Ada), or dynamic checking 
via arbitrary polymorphism but these are superfluous to procedural 
variables.  For the Ada-9X extension, generic declarations would be used.
Now, ignoring interface boundaries below, SHORT_PRINT and LONG_PRINT can 
be statically typechecked with the declaration of PRINT_ELEMENT, a 
procedural variable.  For an Ada example, parameterize the visible 
operations with a stack type and add the usual interfaces and declarations.

--=========================================================================
-- class STACK
--
--    Provides a simple example of procedural variables.
--=========================================================================
class STACK (ELEMENT_TYPE, FCFS, LCLS, SHORT_PRINT, LONG_PRINT) is

  procedure INSERT (ELEMENT : ELEMENT_TYPE); -- INSERT (ELEMENT : polymorphic);
  procedure POP () return ELEMENT_TYPE;
  procedure MAKE_SHORT_PRINT ();
  procedure MAKE_LONG_PRINT ();
  procedure PRINT ();
  procedure MAKE_fCFS ()...
    ...

on entry  ...   -- called at block entry.
on exit   ...   -- called at block exit.
exception ...
private   ...
end STACK;

class body STACK is
    --
    -- PRINT_PROCEDURE_TYPE
    --
    --    A procedural type used to implement the print operation.
    --    These could be in the private part of the class.
    --
    type  PRINT_PROCEDURE_TYPE is procedure (ELEMENT : ELEMENT_TYPE) 
                                          := SHORT_PRINT;
    -- 
    -- PRINT_ELEMENT
    --
    --  A procedural variable invoked by the PRINT operation.
    --
    PRINT_ELEMENT            : PRINT_PROCEDURE_TYPE;

    type INTERNAL_STACK_TYPE is
                record
                        BODY : array ... of ELEMENT_TYPE;
                        TOP  : NATURAL;
                end record;

    INTERNAL_STACK           : INTERNAL_STACK_TYPE;

procedure PRINT is
    begin
        -- 
        -- For each element in the stack
        --      print element
        -- 
        for  INDEX in INTERNAL_STACK .BODY'FIRST .. INTERNAL_STACK .TOP  loop
            PRINT_ELEMENT (INTERNAL_STACK .BODY (INDEX));
        end loop;
    end insert;

--
-- MAKE_SHORT_PRINT
--
--    Set procedural instance variable PRINT_ELEMENT to parameter 
--    SHORT_PRINT so subsequent calls to PRINT by this instance 
--    will invoke SHORT_PRINT.   Could also use a generic 
--    subprogram parameter to supply a new print routine, or ...
--    Parameters SHORT_PRINT and LONG_PRINT will have to be assignment
--    compatible with type PRINT_PROCEDURE_TYPE;
--
procedure MAKE_SHORT_PRINT is
    begin
        PRINT_ELEMENT := SHORT_PRINT;
    end MAKE_SHORT_PRINT;

procedure MAKE_LONG_PRINT is
    begin
        PRINT_ELEMENT := LONG_PRINT;
    end MAKE_SHORT_PRINT;

...
end STACK;


Now, a call to print an instance of this class will at first result in 
invocation of the SHORT_PRINT parameter.  But programmers can make
subsequent calls to PRINT for this instance use long_print
through a call to MAKE_LONG_PRINT.  Each instance can parameterize
its print subprogram to output its data as desired.   Other tricks 
could be used but this method avoids the use of case statements and 
is a simple use of procedural variables.  It also provides static 
typechecking of the print operation since only procedures with the 
same parameter structure as PRINT_ELEMENT will match.

In more complicated examples parameterizable operations for each Adt 
instance could simplify the program considerably, such as by avoiding
nested case statements.

>>  Now set up your abstraction to provide a "current node" concept,
>>  along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND.
>>  This can be implemented either via parent pointers or via a secret
>>  stack which holds the path of descent used to reach the current node.
> 
>> Yes this would work, but leaves programmers to build their own traversal 
>> routines.  My idea was to provide a mechanism allowing programmers to specify
>> a procedural invocation in a single, simple statement and have the Adt
>> select and carry out the operation implicitly.
>
>   But wasn't the basis of your argument the claim that the usual
>   preorder, postorder, and inorder traversal schemes may not be
>   enough?  The solution to this question is clearly to proceed
>   as I have described.  Perhaps you could clarify the problem
>   under consideration and the precise nature of your solution...
>

I hope the example above clarified the idea.  On the subject of
classes, another construct to change operations could be invented but
procedural variables provide a simple mechanism.


                                    Bob Hathaway
                                    rjh@purdue.edu 

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5796@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
>> [Discussion of unrestricted pointers]
> 
> Do you mean passing unrestricted pointers to procedures and then 
> selecting the procedure via overloading (ad-hoc polymorphism) at runtime?
> I meant allowing polymorphic parameters to a particular subprogram, 
> such as
>         procedure test (parameter : polymorphic; ...) is ...

    Yes, that's what I had in mind, although I would also provide
    
          procedure INSERT_ITEM (TARGETED_STACK : in out STACK;
                                 NEW_ITEM       : in     OBJECT);

    to avoid making the user set up a pointer just to get a parameter passed.

    The resulting situation would be the same as if an unrestricted pointer
    had been used and POINTER.all had been made to serve the same function.
 
>  [An extended example of toggling between two print procedures]
>
>   procedure MAKE_SHORT_PRINT ();    -- sets PRINT up to call SHORT_PRINT,
>                                     --   a user-supplied generic parameter 
>
>   procedure MAKE_LONG_PRINT ();     -- sets PRINT up to call LONG_PRINT,
>                                     --   a user-supplied generic parameter 
>
>   procedure PRINT ();               -- a service provided to the user  

> Now, a call to print an instance of this class will at first result in 
> invocation of the SHORT_PRINT parameter.  But programmers can make
> subsequent calls to PRINT for this instance use long_print
> through a call to MAKE_LONG_PRINT.  Each instance can parameterize
> its print subprogram to output its data as desired.   Other tricks 
> could be used but this method avoids the use of case statements and 
> is a simple use of procedural variables.  

> In more complicated examples parameterizable operations for each Adt 
> instance could simplify the program considerably, such as by avoiding
> nested case statements.

     But you've designed your ADT to handle only two types of printing
     situations: SHORT_PRINT and LONG_PRINT (or at least this would seem
     to be the case to anyone who takes your generic parameter structure
     at face value).  What we REALLY want is for ANY type of printing
     operation to occur, depending on the user's needs, which we cannot
     forecast in advance.  But now look at the trap we've walked into:
     we must provide MAKE_*_PRINT, where * represents an indefinite set
     of cases.  We now see that our old friend, the case statement, is
     not gone; it has simply taken on a new form. 

     Verdict: a bad ADT design idea.

     Now let us step back for a moment and consider our situation.  We
     wish to accept a PRINT procedure from our user, which we will use 
     in the course of printing out the contents of the stack.  But how
     do we know that the method we choose for encapsulating the stacked
     objects in the printout will make our user happy?  Perhaps our idea
     is to print each object, separated by a blank line, but our user
     wants to see each object surrounded by a rectangular box of :-)s...

     We now see that our entire approach to the problem is wrong.  We must
     provide a method whereby our user can access his/her stacked objects,
     and allow the user to implement any arbitrary print procedure.  But,
     you object, the user must be given some sort of standard print procedure
     which can be used as a default!  And so he/she must; we achieve this
     by supplying in a utilities package the following:

         with TEXT_IO;

         generic  
 
            type DATA_STRUCTURE is limited private;

            type STORED_OBJECT is limited private;

            with procedure NEXT_POSITION (STRUCTURE : in out DATA_STRUCTURE);

            with function GET_CURRENT_ITEM 
                                  (STRUCTURE : in DATA_STRUCTURE)
                                                       return STORED_OBJECT;

            with procedure PRINT (TO_FILE  : in TEXT_IO.FILE_TYPE;
                                  THE_ITEM : in STORED_OBJECT    );

         procedure STANDARD_PRINT_ROUTINE (INTO_FILE : in TEXT_IO.FILE_TYPE;
                                           STRUCTURE : in DATA_STRUCTURE);

     Our user is now provided with maximal power and convenience.

     Note that the above utility applies to any class of structures
     for which the user can construct a procedure to sequentially 
     access every stored object in some user-defined order.

     Still waiting for a situation in which procedural variables should 
     be used in order to formulate an intuitively natural solution...



                                            Bill Wolfe

                                     wtwolfe@hubcap.clemson.edu
 

Re: Procedure types and dynamic binding

[Bob Hathaway]

> In more complicated examples parameterizable operations for each Adt 
> instance could simplify the program considerably, such as by avoiding
> nested case statements.
>
Bill Wolfe responds:
>     But you've designed your ADT to handle only two types of printing
>     situations: SHORT_PRINT and LONG_PRINT (or at least this would seem
>     to be the case to anyone who takes your generic parameter structure
>     at face value).  What we REALLY want is for ANY type of printing
>     operation to occur, depending on the user's needs, which we cannot
>     forecast in advance.  But now look at the trap we've walked into:
>     we must provide MAKE_*_PRINT, where * represents an indefinite set
>     of cases.  We now see that our old friend, the case statement, is
>     not gone; it has simply taken on a new form. 
>

This is not entirely correct, since I commented another more general solution.
It is possible to parameterize the Adt with a generic MAKE_PRINT_PROCEDURE
as described in the comment which I'll repeat below.  This is accomplished
with a nested generic subprogram declaration in the visible part of the 
package specification allowing any visible type compatible procedure
to be passed to a "MAKE_PRINT_PROCEDURE".  This satisfies the constraint 
above by dynamically assigning the generic parameter to the internal 
procedural variable, if desired.
--
-- MAKE_SHORT_PRINT
--
--    Set procedural instance variable PRINT_ELEMENT to parameter
--    SHORT_PRINT so subsequent calls to PRINT by this instance
** Please Note ***
--    will invoke SHORT_PRINT.   Could also use a generic
--    subprogram parameter to supply a new print routine, or ...
***           ***
--    Parameters SHORT_PRINT and LONG_PRINT will have to be assignment
--    compatible with type PRINT_PROCEDURE_TYPE;
--

Also, it appears unrestricted pointers to subprograms, if thats what
you propose, would provide dynamically checked operations at runtime.
This mechanism is more powerful than statically checked procedural
variables.  Analogous to the use of generics and arbitrary polymorphism
where generics should be used whenever applicable and arbitrary polymorphism
with care, procedural variables should be used whenever applicable and
unrestricted pointers with care.  Since the previous example used generics,
corresponding procedural variables are applicable and provide an
elegant general solution.  I'll let Harland, if we're lucky enough to
have him read this, provide an example with arbitrary polymorphism
and unrestricted pointers:-)

Mats Weber writes:
>I think there is one good reason why procedure types should not be included in
>the Ada language: A secure implementation of procedure types must restrict
>their use to global procedures (that is, procedures that are not nested in
>other procedures or tasks), as is the case in Modula-2.
>
>Such a rule would violate the uniformity of the language (in Ada 83, anything
>can be declared in any declarative region, no matter how deeply nested the
>region is).

I'm aware of this argument but after several years of Modula-2 programming
this simply doesn't cause concern.   This is like the "else" construct
argument where disambiguating rules must be applied to allow if-then-else
constructs.  It is not consequential that rules must be applied to 
grammars, as with the else construct, or that semantic rules must be applied
to objects, as with procedural variables.  As a programmer, the only 
procedures I would assign to a procedural variable are top-level procedures
and since the nested case doesn't occur, I don't see a problem.  I agree 
constraints restricting orthogonality should only be applied when necessary 
but procedural variables present such a case in a stack based-model since
assignment could allow access to inactive environments global to a procedure
and the assignment restriction to top-level procedures is safe, appropriate,
and general.

Also, the rule for disallowing procedural variable assignment to nested 
subprograms which are passed as generic subprogram parameters must still 
be statically checked.

Bill Wolfe writes:
>     We now see that our entire approach to the problem is wrong.  We must
>     provide a method whereby our user can access his/her stacked objects,
>     and allow the user to implement any arbitrary print procedure.  But,
>     you object, the user must be given some sort of standard print procedure
>     which can be used as a default!  And so he/she must; we achieve this
>     by supplying in a utilities package the following:
>

But this is the old scheme again since the Adt cannot be parameterized at
any point in the program and allow a single subsequent operation to invoke 
the desired subprogram.  This sheme requires the work of writing
an output procedure inline.  Yes, the user can call MY_PRINT (STACK .POP ...)
for maximum flexibility as they can with the presented example but
this was not desired.  The output example was kept simple to abstract the 
desired method and real applications are easy to construct, as shown 
below.


>     Still waiting for a situation in which procedural variables should 
>     be used in order to formulate an intuitively natural solution...

Graphical environments provide one example where dynamically parameterizable
objects can be of great assistance.  One could parameterize graphical objects 
with operations for displaying output, windows, etc., with each instance using
the correct subprogram to implement its display operations.

                                            Bob Hathaway
                                            rjh@purdue.edu 

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5804@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
>> In more complicated examples parameterizable operations for each Adt 
>> instance could simplify the program considerably, such as by avoiding
>> nested case statements.
>>
>>> [...] we must provide MAKE_*_PRINT, where * represents an indefinite set
>>> of cases.  We now see that our old friend, the case statement, is
>>> not gone; it has simply taken on a new form. 
> 
> This is not entirely correct, since I commented another more general solution.

     Then let's have a concrete example of this other, more general solution.

     Be generous with the comments.

% Also, it appears unrestricted pointers to subprograms, if thats what
% you propose, would provide dynamically checked operations at runtime.
% This mechanism is more powerful than statically checked procedural
% variables.  

     No, I haven't yet been convinced that subprograms should constitute
     a separate type; my current position is that subprograms should only
     be a means by which ADTs and tasks (think of a "main program" as an
     isolated task...) can be specified.  If you can convince us that there
     is a legitimate need for a subprogram type, then variables of the type
     and pointers to objects of the type will follow automatically.  

> Mats Weber writes:
>>I think there is one good reason why procedure types should not be included in
>>the Ada language: A secure implementation of procedure types must restrict
>>their use to global procedures (that is, procedures that are not nested in
>>other procedures or tasks), as is the case in Modula-2.

     Quick question: assuming the idea of a specification is expanded to
     include all externally accessible objects, what is the source of
     the insecurity?

% Graphical environments provide one example where dynamically parameterizable
% objects can be of great assistance.  One could parameterize graphical objects 
% with operations for displaying output, windows, etc., with each instance using
% the correct subprogram to implement its display operations.

     Specific examples, please...



                                           Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Bob Hathaway]

Another more direct way to parameterize a change operation is
to use a procedural variable as a parameter.  Such as:

generic
    type ELEMENT_TYPE is private;
package ...
    type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE);
    procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE);

This allows dynamic specification of statically checked print procedures per 
instance while the previous example assumed the user knew all allowable 
procedures during instantiation.

					 Bob Hathaway
                                         rjh@purdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5806@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
> 
> Another more direct way to parameterize a change operation is
> to use a procedural variable as a parameter.  Such as:
> 
> generic
>     type ELEMENT_TYPE is private;
> package ...
>     type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE);
>     procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE);
> 
> This allows dynamic specification of statically checked print procedures per 
> instance while the previous example assumed the user knew all allowable 
> procedures during instantiation.

    But now we have a highly changeable system.  What I am asking is,
    "Is there any reason we need this extremely high level of changeability?"

    We are essentially getting into the realm of programs which modify
    themselves, and I tend to think that this power requires extraordinary
    regulation due to the ease with which such a program could modify itself
    to the point that nobody can figure out how it got there in less than
    omega (Ackermann's function) time, much less how to fix it.

    I've suggested earlier that programs should theoretically be able to
    edit source files, cause a recompilation, dump their local knowledge
    into a transition file, invoke the successor on the local knowledge,
    and finally commit suicide, but that this should be done with extreme
    caution. 

    Is there any reason why we need procedural variables in addition to this?



                                           Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Bob Hathaway]

> Another more direct way to parameterize a change operation is
> to use a procedural variable as a parameter.  Such as:
> 
> generic
>     type ELEMENT_TYPE is private;
> package ...
>     type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE);
>     procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE);
> 
> This allows dynamic specification of statically checked print procedures per 
> instance while the previous example assumed the user knew all allowable 
> procedures during instantiation.

>    But now we have a highly changeable system.  What I am asking is,
>    "Is there any reason we need this extremely high level of changeability?"
>

I think the answer is yes, and I'll provide a summary of the method under
discussion instead of another example.  As I mentioned to Bill about a month
ago, I have been working on a generic class structure for about a year.
Other simpler languages have emerged and provided classes but I am not aware
of any extending the idea with generics.  If Ada is to continue remaining
viable as a state-of-the-art programming language then incremental extensions
such as procedural variables and generic classes are necessary.  Ada is often
considered a general purpose programming language, a systems programming 
language, and an object-oriented programming language and its use has far
surpassed its original intention.  Grady Booch has presented an elegant
object-oriented design strategy for Ada and since most programmers are
using this style of programming, Ada should be extended to provide first
class constructs supporting this methodology.  Classes provide an incremental
improvement in abstract data types and together with procedural variables
they provide an elegant solution to parameterized operations.  I owe some
credit to Chris Torek, who posted a method for "the right way to do object
oriented programming in C" (his words as I remember) by storing data and
operations together.  I extended his idea with dynamically parameterized
operations in Adts as the need arose and am sure one "right way to do this"
is in Ada with generics.  Again, the presented example of procedural 
variables allows abstract data types to dynamically (at runtime) alter 
thier operations so each instance can be individually parameterized with
an appropriate subprogram to perform that operation.  Previous postings
presented other uses as well.

The first posted example used type inference and provided a method
to specify all allowable subprogram invocations per instance during 
instantiation.  This method insures controlled operations during and
after instantiation and the Adt state will not be hard to trace.  

The second method allows Adt operations to be dynamically parameterized during
and after instantiation and can be used as the need arises.  A history can be
kept within the Adt for mission critical applications or complex debugging.
I will let the method stand on its own merits and it has been my experience
that parameterized operations are frequently an appropriate solution.  Here
is a simple example of parameterization via procedural variables using a 
single operation Adt:

generic 
   type ELEMENT_TYPE is limited private;
package STACK is
  type ADT is limited private;
  type OPERATION_TYPE is procedure (ELEMENT : in out ELEMENT_TYPE);
  procedure OPERATION (INSTANCE : in out ADT; ELEMENT : in out ELEMENT_TYPE);
  procedure CHANGE_OPERATION (INSTANCE      : in out ADT; 
                              NEW_OPERATION : in OPERATION_TYPE);
end STACK;

or

generic 
   type ELEMENT_TYPE is limited private;
package STACK is
  type ADT is limited private;
  procedure OPERATION (INSTANCE : in out ADT; ELEMENT : in out ELEMENT_TYPE);
  generic
	with procedure NEW_OPERATION (ELEMENT : in out ELEMENT_TYPE);
  procedure CHANGE_OPERATION (INSTANCE : in out ADT);
end STACK;

Here is a recommended class based approach:

generic 
    type ELEMENT_TYPE is limited private;
class
  type OPERATION_TYPE is procedure (ELEMENT : in out ELEMENT_TYPE);
  procedure OPERATION (ELEMENT : in out ELEMENT_TYPE);
  procedure CHANGE_OPERATION (NEW_OPERATION : in OPERATION_TYPE);
  procedure INITIALIZE;	-- These can be dynamically parameterized, if desired
  procedure FINISH;     -- or declared in the private part.
  -- exception declarations --
private
  pragma  NO_ENTRY;	-- If Bill wants to call these explicitly
  pragma  NO_EXIT;
  on entry  INITIALIZE;
  on exit   FINISH;
end STACK;

The reader is referred to previous articles for discussions on more powerful
parameter passing mechanisms which require a runtime type system.  Here is
an example within a class construct:

class STACK is
  type OPERATION_TYPE is procedure (ELEMENT : polymorphic);
  procedure OPERATION (ELEMENT : in polymorphic);
  procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE);
  function  GET_OBJECT return polymorphic;
end STACK;

class body STACK
	-- see previous class example.
end STACK;

And here is an example of Bill's proposal with unrestricted pointers
(*If* unrestricted pointers can to apply to subprograms):

class STACK is
  type OPERATION_TYPE is procedure;
  procedure OPERATION (ELEMENT : in polymorphic;...);
  procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE);
  function  GET_OBJECT return polymorphic;
end STACK;

But this last method requires considerable thought.  I'll assume any procedure
can be passed to CHANGE_OPERATION and calls to OPERATION will require
runtime elaboration.  All packages assign the new operation to an internal 
procedural variable.

As shown above, generics co-exist with procedural variables.  Another issue
is default parameters; what if the supplied procedure doesn't have the same
default parameters?  The simplist solution is to enforce a new rule, such
as during assignment of a subprogram to a procedural variable any default
parameters in the procedural variables parameter structure must be matched
by corresponding default parameters in the supplied subprogram.  But for now
I'll assume assignment is legal as long as subsequent invocations of the
procedural variable don't reference default parameters not supplied by the
subprogram.  Such cases should be avoided, however.

I will let the idea stand on its own merits for now since there is time for
consideration before the next extension.  Is there any way to get
feedback or proposal information for the Ada 9X extension?  I think there
have been several worthwhile ideas presented so far.


                                              Bob Hathaway
                                              rjh@apurdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <5816@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
> [much verbiage deleted...] 
> 
> class STACK is
>   type OPERATION_TYPE is procedure;
>   procedure OPERATION (ELEMENT : in polymorphic;...);
>   procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE);
>   function  GET_OBJECT return polymorphic;
> end STACK;

    First, let's clarify the terminology: a STACK is an example of a type.
    A class is a group of related types.  Thus, APPLE and ORANGE are types,
    and FRUIT is a class of types.  OBJECT is the class of all possible types.

    Despite the request that you be generous with the comments, no indication
    was given as to what OPERATION has to do with the stack.  Let's assume
    that it is some operation that one wishes to apply to every item in the
    stack.  Then we encounter problems in that OPERATION has only an "in"
    parameter, and therefore cannot modify its parameter.  But we'll overlook
    this too, and ask: If we're looking at objects which need to be modified,
    1) what are they doing hidden away inside a stack?  2) why can't we just
    have a stack of pointers, and write a procedure which will serially read
    the stacked objects and update what they point to? and 3) what if the user
    wants to keep N different operations which could be applied to all items
    in the stack, without the bother of continuously invoking CHANGE_OPERATION?

    The mechanism whereby a program could edit source files, cause a rec
    recompilation, transfer its local knowledge to its successor, and
    then destroy itself is appropriate to an environment where code
    modifications are infrequent; the system transitions from one well-defined
    state to another, and the source code always represents the current
    state of the system.  Additionally, optimized code can be generated.
    Procedural variables would encourage excessive rates of change, and
    would greatly complicate the problem of code optimization.

    The idea of modifying the display routine of a graphical object 
    through procedural variables has no merit.  What should be modified
    is a standardized data structure such as a bit-map or list of endpoints.
    This is analogous to the inappropriate use of recursion (vs. iteration).

> If Ada is to continue remaining viable as a state-of-the-art programming
> language then incremental extensions such as procedural variables [...]

    Ada is a state-of-the-art applications programming language, not
    a state-of-the-art research language.  Perhaps a more appropriate
    approach to procedural variables would be to incorporate them into
    a research language and look for a) efficient implementations,
    including code optimization, and b) realistic situations in which 
    the use of procedural variables is effectively not optional.   



                                            Bill Wolfe

                                     wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Barry Margolin]

In article <4062@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>    Ada is a state-of-the-art applications programming language, not
>    a state-of-the-art research language.  Perhaps a more appropriate
>    approach to procedural variables would be to incorporate them into
>    a research language and look for a) efficient implementations,
>    including code optimization, and b) realistic situations in which 
>    the use of procedural variables is effectively not optional.   

I'm really beginning to wonder what universe you're coming from. :-)

Procedure variables are hardly a research topic these days.  They've
been in production use for decades.  And I can't think of any reason
why any decent compiler implementor wouldn't be able to implement them
efficiently (the only inefficiency I know of is minor - procedures
assigned to variables must get their own stack frame, rather than
being able to share its parent block's stack frame - and does not
exist if procedure assignment is restricted to top-level procedures).

They've been in use in the Lisp programming world for years.  They are
great for AI applications in which objects must have highly variable
active properties.  Simple object-oriented systems can be implemented
using either "upward closures" (functions that remember the lexical
environment from which they were returned) or structures that contain
data and a procedure object.

They are used quite effectively on Multics, which has extended PL/I to
support procedure variables.  The most obvious use is in the
device-independent I/O library.  The structure that represents an I/O
stream mostly contains procedure objects that implement the
device-specific portion of each I/O operation.  When you call the
device-independent routines they dispatch through the appropriate
component of the stream structure.  The components that represent
operations that are not appropriate (either because of the type of
device or the state of the stream) can be filled in with procedures
that return appropriate error indications.  But all of the above can
be done with extra flags in the structure and CASE statements.  Where
it really comes in handy is when you allow new device drivers to be
linked in on the fly (Multics has been doing dynamic linking for over
twenty years, and there's a system call to explicitly invoke the
dynamic linking mechanism and return a procedure object).

I guess this doesn't provide any more fundamental capabilities than
the runtime recompilation mechanism you've mentioned.  But I sure
wouldn't want to use a system that implemented dynamic linking by
automatic editing, recompilation, linking and invocation of the
application.  True dynamic linking is often criticized as being too
slow, but it must be several orders of magnitude than the most
well-optimized recompilation scheme.

Algol-68 (or was it Algol-60?) had procedure variables, at least in
the form of call-by-name parameters.  And there are many good uses for
them in C, such as the parameter to the signal() subroutine, which
associates a procedure with a software interrupt.

I could probably go on and on.  Procedure variables are an elegant way
to reduce the complexity of an enormous number of programs.  When I
first saw Ada I noticed two things: 1) the syntax is excessively
verbose and contorted (I really hate the way the verb "IS" is used,
for some reason even I don't understand), and 2) no procedure
variables.


Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin):
> Procedure variables are hardly a research topic these days.  They've
> been in production use for decades.  

    The Rationale for the Design of Ada lists it as a research topic
    which was not sufficiently well-understood at the time (particularly
    in terms of efficient implementations) to be acceptable for inclusion.

    Additionally, Paul N. Hilfinger, one of the designers of Ada, discussed
    procedural variables in his ACM Distinguished Dissertation; last I
    heard, dissertations were considered research.

    I haven't done an extended investigation of the literature, but
    procedural variables in Algol-family languages would appear to
    be a research topic, or at least would seem to have recently
    been such a topic.


                                        Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu
 

Re: Procedure types and dynamic binding

[Robert Firth]

In article <4071@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:

>    I haven't done an extended investigation of the literature, but
>    procedural variables in Algol-family languages would appear to
>    be a research topic

I hardly think so.  Procedure variables have been around for over
20 years, and the implementation issues are pretty well understood.
As for Algol, when I had to write an Algol-60 compiler in the late
'70s, the only "research" required was reading the literature from
the early '60s that told me how to do it.  My most valued source
was the early volumes of "Annual Reviews in Automatic Programming",
supplemented by Hopgood's old monograph "Compiler Construction".

There is just one problem with procxedure variables that has not
quite been completely solved.  It is illustrated by this:

	type proc_type is procedure;

	procvar : proc_type;

	procedure outer is
	  X : integer;

	  procedure inner;
	  begin
	    X := X+1;
	  end;

	begin
	  procvar := inner;
	end;

	outer;
	procvar;

The final statement invokes the value of procvar, which is, of course,
"inner".  The call of inner references the variable X declared in outer,
which no longer exists.  This is the equivalent of the "dangling reference"
problem when the address of a local variable is assigned to a global
pointer.

Many solutions have been proposed; the cleanest in my opinion is that of
Modula-2, which does not allow an "inner" procedure to be assigned to a
variable.  If that were combined with reasonable visibility rules (so
that a procedure could be unnested without perforce being made visible),
I think it would be a definitive solution.

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <8178@aw.sei.cmu.edu>, by firth@sei.cmu.edu (Robert Firth):
> There is just one problem with procxedure variables that has not
> quite been completely solved.  It is illustrated by this:
> 
> 	type proc_type is procedure;
> 
> 	procvar : proc_type;
> 
> 	procedure outer is
> 	  X : integer;
> 
> 	  procedure inner;
> 	  begin
> 	    X := X+1;
% 	  end;
% 
% 	begin
% 	  procvar := inner;
% 	end;
% 
% 	outer;
% 	procvar;
% 
% The final statement invokes the value of procvar, which is, of course,
% "inner".  The call of inner references the variable X declared in outer,
% which no longer exists.  This is the equivalent of the "dangling reference"
% problem when the address of a local variable is assigned to a global
% pointer.
% 
% Many solutions have been proposed; the cleanest in my opinion is that of
% Modula-2, which does not allow an "inner" procedure to be assigned to a
% variable.  If that were combined with reasonable visibility rules (so
% that a procedure could be unnested without perforce being made visible),
% I think it would be a definitive solution.

     Why not something along the lines of the "restricted" clause present
     in Preliminary Ada?  Then inner's specification would require that
     an integer named X be visible in the environment; the attempt to call
     procvar would then result in an error which would be similar to 
     a "missing parameters" situation.  This would have the added benefit
     of completing the idea of a specification such that ALL interactions
     between a procedure and its environment are fully documented (and
     compiler-enforced) in the specification, considerably simplifying
     program debugging and maintenance.

     Also, since Barry was unable to give an answer, for what situations
     would the use of procedural variables be intuitively natural and
     necessary?   Just some example of a realistic applications program
     for which current Ada would prove inadequate, some motivating reason
     for wanting to have procedural variables which would justify such
     a change.

     By the way, would this extend also to packages?  Package variables? 



                                        Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Scott Moody]

> 
> >    I haven't done an extended investigation of the literature, but
> >    procedural variables in Algol-family languages would appear to
> >    be a research topic
>  <code not included> 
> 
> The final statement invokes the value of procvar, which is, of course,
> "inner".  The call of inner references the variable X declared in outer,
> which no longer exists.  This is the equivalent of the "dangling reference"
> problem when the address of a local variable is assigned to a global
> pointer.
> 

The C language solves this problem by not allowing 'inner' procedures at all.
Of course in C any address could be used and called, but it might not
point to anything meaningful.

I would thing the bigger problems with procedure parameters is in the 
parameters to those procedures; especially in Ada where there might be
overloaded procedures with very complex arguments. The syntax for 
specifying - and then checking at runtime that the user supplies
the arguments correctly can get very complex. 

I think Ada's  solution of requiring procedures to be supplied
to generics is a good compromise between allowing a users code to suddenly
jump to somewhere (hopefully not hitting any stars), and not having
them at all. I for one wouldn't mind procedure parameters and varaiables, 
ala C, but I can see that they go against the non goto rational behind Ada.

-- scott

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <1089@shuksan.UUCP>, by scott@shuksan.UUCP (Scott Moody):
> I for one wouldn't mind procedure parameters and varaiables, 
> ala C, but I can see that they go against the non goto rational behind Ada.

   Speaking of the non-goto rationale behind Ada, can anyone tell me
   why Ada has a goto statement??  (See LRM 5.9...)  The Rationale for 
   the Design of Ada conveniently fails to discuss it.


                                          Bill Wolfe

                                   wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Paul Stachour]

In article <1089@shuksan.UUCP> scott@shuksan.UUCP (Scott Moody) writes:
>> 
>> >    I haven't done an extended investigation of the literature, but
>> >    procedural variables in Algol-family languages would appear to
>> >    be a research topic
>>  <code not included> 
>> 
>> The final statement invokes the value of procvar, which is, of course,
>> "inner".  The call of inner references the variable X declared in outer,
>> which no longer exists.  This is the equivalent of the "dangling reference"
>> problem when the address of a local variable is assigned to a global
>> pointer.
>> 
>
In the Multics Implementation of PL/I, an procedure variable was
(not unsuprisingly) two items.  One was a pointer to the code
which was the procedure.  The 2nd was the "environment" of the
procedure at the point of the assignment.

Note that this allows:
   1) The code will thus update the correct "X" at any time,
      even when called from a highly-nested point, as it can find
      its "stack" and thus the "right x" to update.
   2) The code given in its original form to "detect" that there
      is no-such "X" to update, since there is no longer the
      version of "inner" that is "procvar" on the stack.  Detection
      of this stack-mismatch is easy in the example given, it is
      merely the fact that the stack is now "below" what it was at
      the point when the assignment "had effect".

  Of course, in the general case, where there may have been many calls
      in between, such a simple check would not work.  However, the simple
      matter of "gravestones", as used to detect dangling references,
      could be used with procedure-variables just as with naturals,
      or strings, or ...    ...Paul
     

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin):
> 
> [Procedural variables] are great for AI applications in which objects 
> must have highly variable active properties.  

     Could you expand on these situations?  I'll be happy to support
     procedural variables if you can describe a general class of applications
     in which they are intuitively natural and necessary...



                                       Bill Wolfe

                                wtwolfe@hubcap.clemson.edu

Re: Procedure types and dynamic binding

[Barry Margolin]

In article <4072@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin):
>> [Procedural variables] are great for AI applications in which objects 
>> must have highly variable active properties.  
>     Could you expand on these situations?  I'll be happy to support
>     procedural variables if you can describe a general class of applications
>     in which they are intuitively natural and necessary...

Unfortunately, I'm not an AI programmer, so I don't have concrete
examples.  I merely imagined that paradigms such as message-passing
and actors would be implemented using procedure objects.

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Submitting Ada 9X revision requests

[William Thomas Wolfe,2847,]

From article <5816@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway):
> Is there any way to get
> feedback or proposal information for the Ada 9X extension?  I think there
> have been several worthwhile ideas presented so far.

    Below is an excerpt from AJPO's 9X announcement at Tri-Ada '88:

----------------------------- cut here -----------------------------------

   "Requests should be focused on language changes that have significant
    utility to a wide group of Ada users.  All requests must be accompanied
    by sound, well-articulated justifications.  Ada commentaries previously
    approved by the AJPO will automatically be considered during this
    revision process and need not be resubmitted.  [...] Requests should 
    be sent either via electronic mail to Ada9X@ajpo.sei.cmu.edu or 
    via surface mail to:


                Ada Joint Program Office
                Ada 9X Project
                Room 3E114, Pentagon
                Washington, D.C.  20301-3080

    All requests will be made available to the public via electronic
    means through the Ada Joint Program Office."


----------------------------- cut here -----------------------------------


                    Ada 9X Revision Request
                    ======================= 


   DATE:    (Provide date that the request is prepared)


   NAME:    (Provide name of the individual who has prepared the request)


   ADDRESS:    (Provide the name of the individual's organization and
                mailing address, including an e-mail address if applicable) 


   TELEPHONE:   (If request is from outside the US, please include the
                 appropriate country and city codes)


   ANSI/MIL-STD-1815A REFERENCE:    (If no chapter is particularly
                                     relevant, please so state)


   PROBLEM:  (Briefly state the problem.  Indicate the most critical
              aspects to be kept in mind for arriving at a solution,
              particularly if only a partial solution is possible) 


   IMPORTANCE (Scale of 1 - 10, with 10 being the most important):

       (Provide a rating for the importance of the request with respect
        to the overall Ada community, and discuss the consequences if
        the request is not satisfied by the revision) 

   WORKAROUNDS:  (Provide specific examples of workarounds currently
                  being used that allow a partial solution to the problem)


   POSSIBLE SOLUTIONS (Optional):

      (Discuss possible solutions for addressing the stated problem)

Re: Procedure types and dynamic binding

[Bob Hathaway]

>    We are essentially getting into the realm of programs which modify
>    themselves, and I tend to think that this power requires extraordinary
>    regulation due to the ease with which such a program could modify itself
>    to the point that nobody can figure out how it got there in less than
>    omega (Ackermann's function) time, much less how to fix it.
>
>    I've suggested earlier that programs should theoretically be able to
>    edit source files, cause a recompilation, dump their local knowledge
>    into a transition file, invoke the successor on the local knowledge,
>    and finally commit suicide, but that this should be done with extreme
>    caution. 
>
>    Is there any reason why we need procedural variables in addition to this?

This method is not unusual and can be accomplished by providing an operating 
system dependent package with the necessary operations.  Your suggestion 
would move this operation into the higher-order domain and could
be useful in AI and program generation applications.  Retargetable compilers 
are a case in point.

And, speaking of letting proposals stand on their own merits, could we please
put the garbage collection issue to rest.  Each party could state a final
summary of their position, and leave time for consideration before Ada 9X.

                                          Thanks,
                                              Bob Hathaway
                                              rjh@purdue.edu

Re: Procedure types and dynamic binding

[William Thomas Wolfe,2847,]

From article <4204@enea.se>, by sommar@enea.se (Erland Sommarskog):
> Just for discussion: If we should make Ada an object-oriented langauge,
> what should we add? Quite obvious seems package types to get classes.

    I'd think classes would be defined a bit differently!  A package
    could contain declarations of variables, and we certainly don't want
    variables included in a class definition (where class is defined as
    an abstraction over types, e.g., FRUIT as an abstraction over APPLEs,
    ORANGEs, etc.).  A class of types would consist of the name of the class,
    in conjunction with a set of operations which must be available over
    a given type in order for it to be considered a member of the class.

    Then the use of generics would be reduced substantially; we could 
    simply write

       function MAKE_JUICE (OUT_OF : in out FRUIT) return JUICE;
 
    and this would operate on any type of object (APPLEs, ORANGEs, etc.)
    which satisfied the definition of a FRUIT.  There would still be a
    need for generics in situations where values or objects are required
    as generic parameters.

    (BTW, the above example is also an example of why the stupid rule
    about functions having only "in" parameters needs to be repealed...) 
           
> But for inheritance we want all attributes, also those who do not 
> appear in the specification part (or?), and particulary we probably 
> want to have access to private types internal structure. 
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

    One of the most fundamental aspects of the ADT paradigm is that
    an object is known to the outside world only as a type definition
    and a set of predefined operations.  This provides the independence
    which allows us to compile specifications and implementations separately.
    Access to the internal structure of a private type violates the entire
    concept of a "private" type.  

    To achieve this effect, one can simply declare the type in question 
    as a visible type rather than a private type.  In other words, simply 
    avoid using private types.  Be warned, however, that terrible compilation 
    dependencies will result, and you will lose the freedom to replace one 
    implementation with another; in short, the method is NOT recommended 
    for serious use, and is presented only as a theoretical means of achieving 
    what you seek (in my view, misguidedly).
 
> Probably we need delaration a la Eiffel, [...]

    Gee, why don't we just make "Ada" an alias for "Eiffel"?   :-)  :-(

    Seriously though, there *is* a comp.lang.eiffel.  Perhaps you 
    would feel more at home there rather than in comp.lang.ada.

> With the risk of saying something completely obvious: if you want variable
> user-provided operations the following example with a tree-traversing
> illustrates:
> 
>    Generic
>       Type Data_type is limited private;
>       With procedure Assign(A : in out Data_type; B : in Data_type);
>       With function "<"(A, B : Data_type) return boolean is <>;
>       With function ">"(A, B : Data_type) return boolean is <>;
>    Package Binary_trees is
>       Type Tree_type is private;        -- A tree with sorted data.
>       Type Node_type is private;        -- A node in such a tree.
>       ...
>       Generic
>          With Procedure Treat(Node : in     Node_type;  
>                               Data : in out Data_type); 
>       Procedure Traverse_forward(Tree : Tree_type);
> 
> (By the way, an example like the one above should be added to the validation
> suite if it's not already there. A PC compiler I played with choked on the 
> code above, and I believe it is/was validated.)

     Why does Node need to be a parameter of Treat?  All you need is
     something that will treat Data once Traverse_Forward has extracted
     it from the Node.  Once you've removed the unnecessary parameter,
     your package should compile perfectly.



                                            Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu