ADT's in the Standard Library

[Fred Spiessens]

Hi all,

I propose to extent (and if necessary change) the current ADT library 
in an ordered way and discuss this here.
We should discuss the whole organization of the ADT's, before the urge 
to PROVIDE SOMETHING leads to a less-than-optimal design of the 
standard ADT library.
That does NOT mean we have to decide every detail up front, but it is 
important that we establish guidelines and an agreed-upon style.
Some of the things I propose here are only mentioned because I think we 
should discuss them, not because they represent a strong opinion of 
mine.

We should stimulate the growth of the std. ADT lib into a complete and 
consistent whole of fast ADT's that support the different paradigms. 
These are some of the main goals and (style) guidelines I propose:

1. Provide closed (secure), record-style bundled abstractions (as does 
the current library)
  - It is practical
  - The fact that they are "bundled" (operations together with data) has 
the nice security property of helping to avoid unnecessary authority 
amplification (and thus avoiding confused deputy problems: more info 
about that is in our paper on OzE:
http://www.info.ucl.ac.be/people/fsp/oze.pdf )
  - It is more Oz-like than a similar standard class hierarchy would be.

2. Provide these data abstractions in several "styles":
- stateful (current style)
- functional (declarative: returning a new instance when updating)
- active object style (port & stream style, thread-safe)

3. Have some generic operations in all standard lib ADT's, e.g.:
- equality tests {X.eq Y ?B}
- hash function for efficiently storing the ADT in 
hashtable-implemented adt's
- reflection {X.type ?ADT} {X.isType ADT ?B}
- cloning
- conversion operations:
	- to/from the Base library (Records, Lists)
	- to/from other stdlib ADT's where relevant

4. Document the semantics of every ADT operation by providing the (real 
or equivalent) Oz code.

5. Many ADT's are collections. Where appropriate their interface should 
provide:
- generic testing
- generic visitation procedures
- order depending visitation
- deep and shallow cloning (with well defined semantics: Shallow does 
not clone the elements, Deep does)
- flattening
- weak versions
- depending on the implementation, they should allow for initialization 
with enough space for optimal performance. e.g {Array.new Size}

6. Some ADT's provide the same functionality based on a different 
implementation (e.g Queue and Stack), or extend the functionality (e.g 
Array vs Dictionary). Their interfaces should be designed to maximally 
support polymorphism and standardization.  I attached a proposal for a 
consistent set of collection ADT's, based on the elaborated Smalltalk 
class hierarchy, which I tried to adapt to Oz-specific requirements. 
This proposal is unfinished, and should be moulded by experienced 
Mozart developers.

If people are interested in discussing this part of future Mozart, I 
will synthesize a consensus document from your comments. This document 
can then be used as a reference by potential std-lib ADT developers as 
well as Mogul developers.

cheers,
Fred.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: mozadt.pdf
Type: application/pdf
Size: 52175 bytes
Desc: not available
Url : http://lists.gforge.info.ucl.ac.be/pipermail/mozart-users/attachments/20041218/18c19348/mozadt.pdf
-------------- next part --------------