* Procedure types and dynamic binding
@ 1988-12-30 21:42 Erland Sommarskog
1988-12-31 17:46 ` Bob Hathaway
1989-01-05 7:38 ` William Thomas Wolfe,2847,
0 siblings, 2 replies; 29+ messages in thread
From: Erland Sommarskog @ 1988-12-30 21:42 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1988-12-30 21:42 Procedure types and dynamic binding Erland Sommarskog
@ 1988-12-31 17:46 ` Bob Hathaway
1989-01-05 10:02 ` William Thomas Wolfe,2847,
1989-01-05 7:38 ` William Thomas Wolfe,2847,
1 sibling, 1 reply; 29+ messages in thread
From: Bob Hathaway @ 1988-12-31 17:46 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1988-12-30 21:42 Procedure types and dynamic binding Erland Sommarskog
1988-12-31 17:46 ` Bob Hathaway
@ 1989-01-05 7:38 ` William Thomas Wolfe,2847,
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-05 7:38 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1988-12-31 17:46 ` Bob Hathaway
@ 1989-01-05 10:02 ` William Thomas Wolfe,2847,
1989-01-07 18:05 ` Bob Hathaway
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-05 10:02 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
@ 1989-01-06 23:04 Erland Sommarskog
1989-01-07 22:20 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Erland Sommarskog @ 1989-01-06 23:04 UTC (permalink / raw)
Bill Wolfe writes:
> 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
This is half-true. Thus, we don't want them to be modifyable, but we
want them to be readable. As far as I am concerned, writeable variable
in packages should be prohibited today, but, alas, wouldn't be a change
to rhyme with backwards compability. It should be avoided anyway.
>> 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.
But can you as ADT designer always find out exactly what I want? Say
you hand me a linked-list package. I discover that I need to reverse
a list, but does not have such an operation. With Ada today I have
three possibilies:
1) Write Reverse_list using the existing primitives and place it
in my own package.
2) Write my own extended list package, which calls yours and adds my own
Reverse_list.
3) Re-hack your package, which gives me the possiblility to write a more
efficient version.
1) has the disadvantge that my code contains something that does not belong
there. 2) Causes redundancy and duplicated declarations. 3) is maybe not
available for various reasons. It resides in a library I cannot write to,
and you are holiday. Besides other users would have a lot of recompilation
triggered just before deliverance and get mad.
With inheritance there is a fourth possibility. I can write my extended
list package to solely inherit all from yours and then add Reverse_list.
Depending if I want to be saved from changes, or need efficiency I
use your primitives, or the implementation.
For more info on this, the "open-closed principle", I once again refer
to Bertrand Meyer's "Object-Oriented Software Construction" where he
discusses these ideas.
> Seriously though, there *is* a comp.lang.eiffel. Perhaps you
> would feel more at home there rather than in comp.lang.ada.
I feel at home both here and there. Wouldn't say I found that comment
very serious, :-)
>> Generic
>>...
>> Package Binary_trees is
>> ...
>> 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.
You shouldn't work as a compiler. Whether Node is anything useful or
not could be discussed, but it's certainly perfectly legal Ada. If
it is not, tell me why and I write an error report about our Unix
compiler that accepts this. (The use for Node is that the user
may want a quick reference to some data, which he saves somewhere
else.)
--
Erland Sommarskog
ENEA Data, Stockholm This signature is not to be quoted.
sommar@enea.se
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-05 10:02 ` William Thomas Wolfe,2847,
@ 1989-01-07 18:05 ` Bob Hathaway
1989-01-07 21:21 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Bob Hathaway @ 1989-01-07 18:05 UTC (permalink / raw)
>> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-07 18:05 ` Bob Hathaway
@ 1989-01-07 21:21 ` William Thomas Wolfe,2847,
1989-01-08 1:49 ` Bob Hathaway
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-07 21:21 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-06 23:04 Erland Sommarskog
@ 1989-01-07 22:20 ` William Thomas Wolfe,2847,
0 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-07 22:20 UTC (permalink / raw)
From article <4223@enea.se>, by sommar@enea.se (Erland Sommarskog):
> But can you as ADT designer always find out exactly what I want? Say
> you hand me a linked-list package. I discover that I need to reverse
> a list, but does not have such an operation. With Ada today I have
> three possibilies:
> 1) Write Reverse_list using the existing primitives and place it
> in my own package.
> 2) Write my own extended list package, which calls yours and adds my own
> Reverse_list.
> 3) Re-hack your package, which gives me the possiblility to write a more
> efficient version.
> 1) has the disadvantge that my code contains something that does not belong
> there. 2) Causes redundancy and duplicated declarations. 3) is maybe not
> available for various reasons. It resides in a library I cannot write to,
> and you are holiday. Besides other users would have a lot of recompilation
> triggered just before deliverance and get mad.
Proceed with either 2) or 3), whichever you prefer, and use it until
procedures can be invoked whereby the library is upgraded to satisfy
this requirement. Probably there is a mechanism for submitting new
requirements, and you can go ahead and submit your workaround along
with your request; the workaround's spec will probably be placed into
immediate service, perhaps with minor revisions, and the implementation
will be updated with an optimized version as time permits. Other users
will not have recompilation triggered because they are depending on
the version which does not provide list reversal, which remains in
the library. If no increase in efficiency is possible as a result of
omitting list reversal, then probably a note will be placed in the
library saying that programmers should use the new version instead,
and eventually all software depending on the old version will be
rewritten (shifting to the new version in the process), or abandoned,
and the old version will then be removed from the library. If your
local installation prefers, they can instead purchase a more powerful
version of the ADT, and then apply the same phasing-out procedure
if there is no efficiency bonus in the less comprehensive ADT.
> With inheritance there is a fourth possibility. I can write my extended
> list package to solely inherit all from yours and then add Reverse_list.
> Depending if I want to be saved from changes, or need efficiency I
> use your primitives, or the implementation.
>
> For more info on this, the "open-closed principle", I once again refer
> to Bertrand Meyer's "Object-Oriented Software Construction" where he
> discusses these ideas.
I have read about this in Meyer's book, and do not agree with it.
We do not first create the abstract concept of FRUIT and then
specialize into APPLEs and ORANGEs; it is the other way around!!
Additionally, Meyer's approach creates all manner of compilation
dependencies and inefficiencies, and is in general a very messy
way to go about doing things. Instead, let us proceed along the
lines of a synthesis-oriented approach, as I have described.
We should describe FRUIT as an abstraction, and the characteristics
of FRUIT permit us to decide whether a given real object falls
into this class or not. We can then construct packages which operate
over the abstraction FRUIT, knowing that our APPLEs and ORANGEs
will satisfy the abstraction and therefore be compatible with the
package. We can even discover PLUMs at a later date, design the
implementing specification to be compatible with the FRUIT abstraction,
and then freely insert PLUMs into the stream of FRUIT being handled
by our packages. This is a far more natural paradigm; it corresponds
much more closely to the natural processes of human thought.
>>> Generic
>>>...
>>> Package Binary_trees is
>>> ...
>>> 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.
>
> You shouldn't work as a compiler. Whether Node is anything useful or
> not could be discussed, but it's certainly perfectly legal Ada. If
> it is not, tell me why and I write an error report about our Unix
> compiler that accepts this. (The use for Node is that the user
> may want a quick reference to some data, which he saves somewhere
> else.)
But the problem is that Node is not the user's property; it is the
property of the generic package. As such, the user is not free to
stick arbitrary data in some secret place within the Node. If the
user wants to store "a quick reference to some data", then the user
can define Data as a record with two fields: one will provide the
REAL data, and the other will provide the user's secret cache. Then
the procedure Treat which the user writes can access the user's cache
freely, and now we see that Node really is a useless parameter.
(I'm not concerned with the deficiencies of one compiler or another
as much as I am with the goodness of the ADT; I see no reason why
the PC should have rejected the code, but I saw a more important
question which needed to be taken care of first.)
Bill Wolfe
wtwolfe@hubcap.clemson.edu
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-07 21:21 ` William Thomas Wolfe,2847,
@ 1989-01-08 1:49 ` Bob Hathaway
1989-01-08 19:01 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Bob Hathaway @ 1989-01-08 1:49 UTC (permalink / raw)
>> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-08 1:49 ` Bob Hathaway
@ 1989-01-08 19:01 ` William Thomas Wolfe,2847,
1989-01-08 23:10 ` Bob Hathaway
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-08 19:01 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-08 19:01 ` William Thomas Wolfe,2847,
@ 1989-01-08 23:10 ` Bob Hathaway
1989-01-09 1:47 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Bob Hathaway @ 1989-01-08 23:10 UTC (permalink / raw)
>
> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-08 23:10 ` Bob Hathaway
@ 1989-01-09 1:47 ` William Thomas Wolfe,2847,
1989-01-09 20:19 ` Bob Hathaway
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-09 1:47 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-09 1:47 ` William Thomas Wolfe,2847,
@ 1989-01-09 20:19 ` Bob Hathaway
1989-01-10 3:01 ` William Thomas Wolfe,2847,
1989-01-10 3:06 ` Bob Hathaway
0 siblings, 2 replies; 29+ messages in thread
From: Bob Hathaway @ 1989-01-09 20:19 UTC (permalink / raw)
> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-09 20:19 ` Bob Hathaway
@ 1989-01-10 3:01 ` William Thomas Wolfe,2847,
1989-01-10 3:06 ` Bob Hathaway
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-10 3:01 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-09 20:19 ` Bob Hathaway
1989-01-10 3:01 ` William Thomas Wolfe,2847,
@ 1989-01-10 3:06 ` Bob Hathaway
1989-01-10 19:11 ` William Thomas Wolfe,2847,
1 sibling, 1 reply; 29+ messages in thread
From: Bob Hathaway @ 1989-01-10 3:06 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-10 3:06 ` Bob Hathaway
@ 1989-01-10 19:11 ` William Thomas Wolfe,2847,
1989-01-11 2:08 ` Bob Hathaway
1989-01-11 2:10 ` Procedure types and dynamic binding Bob Hathaway
0 siblings, 2 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-10 19:11 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-10 19:11 ` William Thomas Wolfe,2847,
@ 1989-01-11 2:08 ` Bob Hathaway
1989-01-11 14:24 ` William Thomas Wolfe,2847,
1989-01-11 14:48 ` Submitting Ada 9X revision requests William Thomas Wolfe,2847,
1989-01-11 2:10 ` Procedure types and dynamic binding Bob Hathaway
1 sibling, 2 replies; 29+ messages in thread
From: Bob Hathaway @ 1989-01-11 2:08 UTC (permalink / raw)
> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-10 19:11 ` William Thomas Wolfe,2847,
1989-01-11 2:08 ` Bob Hathaway
@ 1989-01-11 2:10 ` Bob Hathaway
1 sibling, 0 replies; 29+ messages in thread
From: Bob Hathaway @ 1989-01-11 2:10 UTC (permalink / raw)
> 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-11 2:08 ` Bob Hathaway
@ 1989-01-11 14:24 ` William Thomas Wolfe,2847,
1989-01-11 17:51 ` Barry Margolin
1989-01-11 14:48 ` Submitting Ada 9X revision requests William Thomas Wolfe,2847,
1 sibling, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-11 14:24 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Submitting Ada 9X revision requests
1989-01-11 2:08 ` Bob Hathaway
1989-01-11 14:24 ` William Thomas Wolfe,2847,
@ 1989-01-11 14:48 ` William Thomas Wolfe,2847,
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-11 14:48 UTC (permalink / raw)
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)
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-11 14:24 ` William Thomas Wolfe,2847,
@ 1989-01-11 17:51 ` Barry Margolin
1989-01-11 22:54 ` William Thomas Wolfe,2847,
1989-01-12 0:58 ` William Thomas Wolfe,2847,
0 siblings, 2 replies; 29+ messages in thread
From: Barry Margolin @ 1989-01-11 17:51 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-11 17:51 ` Barry Margolin
@ 1989-01-11 22:54 ` William Thomas Wolfe,2847,
1989-01-12 13:57 ` Robert Firth
1989-01-12 0:58 ` William Thomas Wolfe,2847,
1 sibling, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-11 22:54 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-11 17:51 ` Barry Margolin
1989-01-11 22:54 ` William Thomas Wolfe,2847,
@ 1989-01-12 0:58 ` William Thomas Wolfe,2847,
1989-01-12 6:12 ` Barry Margolin
1 sibling, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-12 0:58 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-12 0:58 ` William Thomas Wolfe,2847,
@ 1989-01-12 6:12 ` Barry Margolin
0 siblings, 0 replies; 29+ messages in thread
From: Barry Margolin @ 1989-01-12 6:12 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-11 22:54 ` William Thomas Wolfe,2847,
@ 1989-01-12 13:57 ` Robert Firth
1989-01-12 19:09 ` William Thomas Wolfe,2847,
1989-01-14 0:46 ` Scott Moody
0 siblings, 2 replies; 29+ messages in thread
From: Robert Firth @ 1989-01-12 13:57 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-12 13:57 ` Robert Firth
@ 1989-01-12 19:09 ` William Thomas Wolfe,2847,
1989-01-14 0:46 ` Scott Moody
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-12 19:09 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-12 13:57 ` Robert Firth
1989-01-12 19:09 ` William Thomas Wolfe,2847,
@ 1989-01-14 0:46 ` Scott Moody
1989-01-15 18:28 ` William Thomas Wolfe,2847,
1989-01-24 4:07 ` Paul Stachour
1 sibling, 2 replies; 29+ messages in thread
From: Scott Moody @ 1989-01-14 0:46 UTC (permalink / raw)
>
> > 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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-14 0:46 ` Scott Moody
@ 1989-01-15 18:28 ` William Thomas Wolfe,2847,
1989-01-24 4:07 ` Paul Stachour
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-15 18:28 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Procedure types and dynamic binding
1989-01-14 0:46 ` Scott Moody
1989-01-15 18:28 ` William Thomas Wolfe,2847,
@ 1989-01-24 4:07 ` Paul Stachour
1 sibling, 0 replies; 29+ messages in thread
From: Paul Stachour @ 1989-01-24 4:07 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
end of thread, other threads:[~1989-01-24 4:07 UTC | newest]
Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1988-12-30 21:42 Procedure types and dynamic binding Erland Sommarskog
1988-12-31 17:46 ` Bob Hathaway
1989-01-05 10:02 ` William Thomas Wolfe,2847,
1989-01-07 18:05 ` Bob Hathaway
1989-01-07 21:21 ` William Thomas Wolfe,2847,
1989-01-08 1:49 ` Bob Hathaway
1989-01-08 19:01 ` William Thomas Wolfe,2847,
1989-01-08 23:10 ` Bob Hathaway
1989-01-09 1:47 ` William Thomas Wolfe,2847,
1989-01-09 20:19 ` Bob Hathaway
1989-01-10 3:01 ` William Thomas Wolfe,2847,
1989-01-10 3:06 ` Bob Hathaway
1989-01-10 19:11 ` William Thomas Wolfe,2847,
1989-01-11 2:08 ` Bob Hathaway
1989-01-11 14:24 ` William Thomas Wolfe,2847,
1989-01-11 17:51 ` Barry Margolin
1989-01-11 22:54 ` William Thomas Wolfe,2847,
1989-01-12 13:57 ` Robert Firth
1989-01-12 19:09 ` William Thomas Wolfe,2847,
1989-01-14 0:46 ` Scott Moody
1989-01-15 18:28 ` William Thomas Wolfe,2847,
1989-01-24 4:07 ` Paul Stachour
1989-01-12 0:58 ` William Thomas Wolfe,2847,
1989-01-12 6:12 ` Barry Margolin
1989-01-11 14:48 ` Submitting Ada 9X revision requests William Thomas Wolfe,2847,
1989-01-11 2:10 ` Procedure types and dynamic binding Bob Hathaway
1989-01-05 7:38 ` William Thomas Wolfe,2847,
-- strict thread matches above, loose matches on Subject: below --
1989-01-06 23:04 Erland Sommarskog
1989-01-07 22:20 ` William Thomas Wolfe,2847,
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox