Please excuse this temporary and hurriedly put together web page on the subject of ASCL and, currently, list containers.
Last Updated: 03-Dec-2001 01:50
Nick Roberts
For more information, see The AdaPower Web Site.
This is an ongoing project to create a common utility library for the Ada programming language that provides the basic data structures which are not provided as standard by the language itself.
It is hoped that such a library would be used by default by Ada programmers, distributed by Ada compiler vendors, used as a basis for teaching in textbooks and education, and may even be adopted as part of the language standard at its next revision.
Recently, Ted Dennison initiated a lively discussion on the comp.lang.ada Usenet news group. He put forward a 'straw man' for a list structure:
Also under consideration are the following proposals or existing libraries (in varying states of completeness):
My own proposal is at the bottom of this page.
These are the criteria that (as far as I am aware) have been suggested for the list container. Old forms in [brackets].
| No | Requirement | Comments | Conclusion |
|---|---|---|---|
| 1 | The user must be able to get a list package with a single instantiation. | SL: [endorsed] JC: Consensus: Yes. Me: Yes. SW: Don't care. |
Accepted. |
| 2 | Lists must be safe (ie no dangling pointers, etc) against any list or iterator operation. | NJR: [endorsed] SL: No. There should be an Unchecked_Lists package that is fast, and perhaps another Checked version built on top of it. JC: Consensus: Undecided. Me: 99% safe is good enough. SW: I need to know what operations are safe and what operations aren't. |
Further discussion. |
| 3 | [lists must be efficient enough for hard real-time
use] Lists must be implemented efficiently, and have predictable execution time characteristics. They must not perform dynamic allocation other than for the actual insertion of data. They must not perform deallocation other than for the actual deletion of data. Iteration, single-step cursor movement, and access-at-cursor must be fast and have especially stable time characteristics. |
TED: [endorsed] MDC: [endorsed] SL: No. Hard real-time doesn't do dynamic allocation. NJR: No. I agree with SL. JC: Consensus: No. Me: No. SW: Yes, suitable for hard real-time. |
Rejected. |
| 4 | [lists must be safe in a multitasking environment]
Lists must be suitable for use in a multitasking environment (in particular, all procedures modifying distinct list objects must be re-entrant, and all functions must not cause any modifications). |
TED: [endorsed] MDC: [endorsed] SL: No [there should be two versions, one complying and one not complying with this requirement] NJR: Yes. This requirement is useful and unlikely to place any burden or difficulty on any implementation. JC: Consensus: No. Me: Basic list should be unprotected, and a protected version built on top of it should also be provided (this comes under the heading of "common enough" to supply, even though the client can do it himself). SW: I'm prepared to supervise access myself, I think. |
Further discussion. |
| 5 | Lists must not be a tagged type. | SL: I could go either way. Making it tagged allows deep copy on
a non-limited list, so I lean that way. MDC: I'd kind of favor tagged and inheriting from Controlled. TED: That's actually kind of required, I'm afraid. Any other option is going to run horribly afowl of the transparent storage management fans (and probably require removal of all the funtional calls). NJR: Automatic memory reclamation can be achieved with a non-tagged list type if that type (is a record type and) has a controlled component. Is there another reason for having a tagged type? JC: Consensus: No. Must be controlled. Me: Should not be visibly tagged, but must be controlled. SW: Don't care. |
Not visibly tagged, but controlled. |
| 6 | Lists must be safe for assignment (always do deep copy, or don't allow assignment). | SL: [endorsed] NJR: No. I prefer (explicit) shallow copy semantics, and assignment permitted (adjusted if need be). JC: Consensus: Yes. Me: Should be limited. SW: [endorsed] |
Further discussion. |
| 7 | [list elements must not be private] List elements must be limited private. |
SL: Yes. They force the user to provide a Copy routine,
allowing multi-layered deep copies. NJR: No. I prefer (explicit) shallow copy semantics, with data copy being done by the assignment inherent in a non-limited type. MDC: O.K. I can live with that. TED: Perhaps, but I'm pretty sure we already argued that one and decided against it. It would require some kind of "copy" routine be supplied as a generic, which would require even the 90% who don't want to deal with limited types to go create themselves a copy routine that performs vanilla assignment just to make the generic happy. Some suggested that we could create limited and non-limited versions, but the general agreement we arrived at was to just drop the whole thing and not deal with limited types. If it ends up being a huge problem, someone can always create a parallel Containers.Lists.Limited_Unbounded package later. MDC: O.K., I can live with that too! :-) NJR: ;-) JC: I guess I'm already on record as being a serious limited fan, but a standard with unlimited is better than no standard. JC: Consensus: No. Me: Yes. |
Further discussion. |
| 8 | Lists must support elements of any Ada type (private, limited, tagged, indefinite). | SL: Yes. But I could relax this one if it really is a hassle.
NJR: I prefer containers to stick to the conceptual model of a 'store', into and out of which things are copied. I would therefore prefer a generic formal data type is (non-limited) private, which would permit (but not require) tagged types, but exclude limited and indefinite types. JC: Consensus: No. Me: Needn't support indefinite types. SW: I'm pretty sure I want this, how expensive is it going to be? |
Further discussion. |
| 9 | The list facilities should mimic the Ada.String.* packages — on the basis that a string is a list of characters — as far as is reasonable (and no further). | NJR: [endorsed] | Too early. |
| 10 | The list facilities should provide easy interaction between lists, individual data values, and arrays of those values. | NJR: Since I support only one array type, perhaps my proposal doesn't fully comply with this requirement! | Too early. |
| 11 | The list facilities should provide full support for both the 'functional' and 'procedural' styles of use. | NJR: [endorsed] | Too early. |
| 12 | The list facilities should be compatible with execution environments that have unusual characteristics (e.g. JGNAT on top of JVM). | NJR: Only if reasonable. | Too early. |
| 13 | Support must be given for user-defined memory management. | NJR: No. Leave this to more sophisticated libraries (e.g. Booch). | Too early. |
Please feel free to add your endorsements, comments, your own requirements, or corrections. Either at the Usenet news group comp.lang.ada or via e-mail to me. The conclusions are my own interpretation, and may be challenged (at this stage).
A note about iteration: I make a distinction between cursors (which are bidirectional, possibly random, and list-specific) and iterators (which are uni-directional, strictly sequential, and container-wide). This distinction does not necessarily prejudice the final design (which may or may not entail such a distinction).
Here is my current proposal (version 5 revision 1).
The main changes from version 4 are: no abstract list type (one bounded concrete type, and one unbounded concrete type); separate cursor-based and absolute-indexed operations; specific exceptions; more complete documentation; exchange and various other operations added; renamed the 'Solitary' function to 'To_List' with a parameter named 'Singleton' (in line with Ada.Strings.*).
I hope to add later: iteration packages; reverse-in-place child packages; sort-in-place child packages; sample implementations of everything.
My previous proposal (for the curious):