Re: Comments on generic stack?

[wheeler@aphrodite.csed.ida.org (David Wheeler)]

Michel Gauthier (gauthier@unilim.fr) wrote:
: In article <4i6l2t$j1q@dmsoproto.ida.org>, wheeler@aphrodite.csed.ida.org
: (David Wheeler) wrote:
....
: >>  It's a generic that requires the Item to have := and =, but since the
: >>  stack itself has those operations it is composable (you can have a
: >>  Stack of Stacks of Integers).

: Sorry to disturb, but I cannot understand what is a stack of stacks.

There are two issues here: (1) generality of a reusable component, and
(2) usability of stacks of stacks.  Let's talk about them one at a time.

(1) I strive to make reusable components general enough so that they can be
reused in many different contexts.  One way to _test_ the generality of
a component is to see if it's composable (i.e. can you build more
complex structures using it), and the simplest way to check that is
to try to compose it using itself.  I've written a paper that includes a 
discussion on the subject: "Analysis and Guidelines for Reusable Ada
Software", IDA Paper P-2765, August 1992.

Is composability of reusable components useful?  Well, are arrays of arrays
useful? If you believe the answer is "yes", then you know your answer.

(2) Are stacks of _stacks_ useful?  Well, not as useful as arrays of arrays.
However, if I can support stacks of stacks, I can also support other
combinations that are more likely to be useful.  And I _can_ imagine
"stacks of stacks" being useful in certain complicated parsing systems.

: Stacks are designed to organise values, not objects. 
: Stacks are objects, not values.

Not true.  This stack organizes Items. Items might be values, or they might
be references.  There is no reason to assume they must be one or the other.
For performance reasons you might choose to stack references instead of
the actual values, but there's no reason they MUST be one or the other.

: How can you define stacks of stacks ?

-- Easy; here's a stack of stacks of Integers:

with Generic_Stack, Stack_Int;

package Stack_Stack_Int is new Generic_Stack(Stack_Int.Stack);


with Generic_Stack;

package Stack_Int is new Generic_Stack(Integer);

: David probably means either stacks of (item=>references to stacks) or
: stacks of
: (item=> some implementation of the stack abstract type with an initial algebra
: behaviour).
: The latter actual type is an academic feature that has strictly no 
: practical use.

Disagree; see my example of arrays of arrays.

It _is_ true that my current implementation of adjust makes stack assignment
a big-ticket performance hit, but there are ways to reduce that cost in
most cases if you'd like to implement that.  You wouldn't even need to
change the visible specification.

In summary: the issue of having flexible reusable components is _NOT_
just an academic issue, and checking for composability helps you get there.

If I were _really_ serious about making my generic stack general I'd add
some iterators; for demonstration purposes I'm not sure I'll bother.

--- David
    wheeler@ida.org