Google definition of the term here: [http://www.google.com/search?hl=en&lr=&ie=UTF-8&oi=defmore&q=define:abstract+data+type].  This page could be entitled "''An argument for OO as composition of Abstract Data Types''"

[CMCc] I'm going with this definition "''A data type together with all the operations on data objects of that type that make use of information about the representation of the data type''"

[Array] is an abstract data type, since you can access its contents with [[array get]] or using (), but you can't tinker with the hash collision tables which underly the array representation.

Array presents a good example of some of the benefits of encapsulation:

    * you can't change the internal representation of an array in such a way as to break it.
    * it has a clearly defined interface, represented by the subcommands of array
    * someone can change the implementation of array, without changing its behavior

Each of the other builtin data structures, and many of those in [tcllib] have these benefits too.

However, array and (say) ::struct::tree suffer from an inability to be composed together with other data types into more complex abstract data types.

For example, one can't derive a SortedArray, which always returns its [[array get]] in a predefined order.  Native array doesn't do this because it's unnecessary for most uses and it would be expensive but there are cases where one might like this: for example if one was using an array to store a time sequence of events.

The ability to derive SortedArray (e.g.) from builtin Array in a coherent and consistent manner, while preserving something of the encapsulation of Array, would be a benefit of OO.

How many ways are there to wrap Array in something which adds/changes its functionality?  An infinite number.  There should also be a single, efficient, simple, predictable, well known way.  That, I think, is what the adherents of [OOTcl] are suggesting.  I agree with them.
----
[RS] has never felt a need for "SortedArray" - it's easy enough to iterate like this:
 foreach name [lsort [array names arr]] {...}
Types/subtypes/classes/derived classes are popular in other languages, but doing without them, I just feel freer in Tcl... :)

----

[Lars H]: As remarked in the lengthy discussion on the [Things holding Tcl back] 
page, it is possible to encode data structures on top of simpler data structures, 
and these on top of still simpler data structures, in rather many levels. Tcl 
has a marvellous way of encoding [list]s as strings, but stops there, as
[everything is a string]. Most computational models (e.g. [Turing machine]s) 
stop there as well, although some (e.g. recursively defined functions) 
continue by encoding strings as Gödel numbers. That something ''can'' be 
encoded using simpler structures is not of much interest here.

Given a range of implementations of a data structure, the right question is 
probably rather what the computational complexities of standard operations 
are for these implementations. If one can find an example of a data structure 
where Tcl implementations have significantly worse complexity than other 
languages, then that is a sign that the language could do with improvements. 
Some historical examples:

'''Lists.'''
In Tcl 7, there were no [Tcl_Obj]s, and thus in particular, lists had no 
"internal representation". Any operation on a list required that the string 
was reparsed, so that for example [llength] and [lindex] (on average) was 
linear time operations. In particular, the complexity would depend on how 
large (as strings) the elements of the list were, which was a significant 
drawback in comparison with e.g. [Lisp].

In Tcl 8, both [llength] and [lindex] are constant time operations on 
values that have a list internal representation (and in these circumstances 
it is reasonable to assume that list values are only being operated on 
using list operations). Now it is rather Lisp (using a linked list 
implementations) that is at a disadvantage, because computing the length 
of a linked list requires that the list is traversed. (OTOH, insertion is 
linear in list length in Tcl, but can be faster in Lisp.)

'''Dictionaries.'''
In Tcl 8.4, getting and setting individual elements of a dictionary (stored 
as a "key value key value ..." list) is linear in the size of that 
dictionary, but in Tcl 8.5 the new dictionary values with a hash internal 
representation will be faster (anyone know how much faster? Logarithmic?).

In these two cases, there was a clear gain with getting these things into 
Tcl, but for many of the things proposed, there is no gain! Lists are all 
that one needs.


'''Fancier data structures aren't always better'''

In the [reference] page (or thereabout) I asked whether there was 
''any case at all'' of a data structure that could be implemented more 
efficiently (better complexity) using references (e.g. Lisp cons cells or 
C pointers to structs) than in current Tcl. The simplest example anyone 
gave was that of a dual-sorted queue: If the queue is a list then you need 
to search through it to find the smallest element in at least one of the 
sorting orders, so dequeueing is a linear time operation. If the queue is 
instead implemented as a linked list, where there is one "next1" reference 
for sorting order 1 and one "next2" reference for sorting order 2, then it 
is possible to find and dequeue the first element according to either sorting 
order in constant time. You do need to make both linked list structures 
dual-linked, so there is a total of four pointers per queue element, but 
it is still constant time.

There is a "but" though: that is just the complexity of dequeueing. Any kind 
of system that makes use of such a queue would have to enqueue as many 
elements as it dequeues, and inserting a new element on the proper position 
into a linked list is still a linear time operation. So in the end there 
was no gain, and total complexity is the same regardless of whether one 
uses reference-based linked lists or just plain Tcl lists.

Then again, it is possible to speed up insertion in the linked list case 
by adding a self-balancing tree structure to the thing, in which the original 
linked list is just the "thread" (I think it is called); this gets insertion 
down to logarithmic time, at the price of increasing the total number of 
references by another factor two (possibly more). The result is a rather 
huge data structure, but it is faster than simple-minded searching through 
a list. On the other hand, it still isn't superior to Tcl, because nothing 
stops us from treating a Tcl list as one in the old days sometimes treated 
an Pascal array as a "heap" from which we can allocate and deallocate 
our own dynamic memory ("pointers" then being indices into this list). 
Anything that can be done with references (without automagic garbage
collection) can be simulated in Tcl using lists, without loss of asymptotic 
performance.

[CMCc] '''Who said the sole metric of "better" is "more efficient"?'''

Lars gives a few examples of completely encapsulated objects which benefited from a reimplementation without a change in interface.  The ability to do that, to distinguish between implementation and interface is why something which permits encapsulation is "better" than something which does not.

If it were not for the fact that the internal representation (and implementation) was distinct from its interface, it may well have been practically impossible to produce the more efficient implementation without disrupting users of the construct.

For such a distinction to be significant, it has to be distinct and recognisable by most people.  That's one of the things OO does - signals what's available for use and what's implementational, and subject to change.

[RS] has never felt a need for the example I gave, SortedArray.  One presumes he's never had more than a few instances of SortedArray and discovered that he had to change the sort order ... in OO one changes it once, in the solution proposed, it needs changing everywhere it appears.

Secondly, as there are an infinite number of ways to wrap functionality and compose simpler objects programmatically, and the only metric of quality being admitted here is performance, it would seem very difficult for a maintainer to recognise it when it's being done.


[Lars H]: Your claim that my examples concern "completely encapsulated objects"
is incorrect. Lists were not completely encapsulated in Tcl 7 (they could at any 
time be introspected using e.g. [[string index]]) and they are not completely 
encapsulated in Tcl 8 either (you can still peek at characters using 
[[string index]]). It is ''inefficient'' to operate on them using non-list 
commands, but it is perfectly possible.

Come to think of it, this may be what object-oriented programmers have hard 
to understand about [everything is a string] (or at least ''one'' thing that 
makes them confused): A good data structure need ''not'' necessary hide 
the data behind some opaque API -- it is sufficient that the public 
representation (the string) of the data can be lazily generated. Thinking 
of data structures as objects instead promotes the view that as little as 
possible should be made public.


[[ [Category Data Structure] ]]