Talk:Abstract data type

The article is plainly and fully wrong, and needs to rewritten from scratch. I'll work a little on this...

DONE

• added the summary section and two references.
• set the conceptual boundaries clear.

Hmm - not sure how to continue the article, because the topic quite large and needs quite some mathematics not really available in WP, yet.

Usually, the canon would require to make Signature, Specification, etc. and various semantics precise. An alternative would be, to leave things imprecise and and to write something for the intuition behind equational specifications.

A good starting point for that might be Equivalence class, which is weaker than equality congruence relation, but easier to understand first.

Because working with values is uncommon to most programmers, a section devoted to the topic that a value is value and not something modifyable as a machine or variable, could help understanding, too. One could give an example of an object memory that uses values and objects as attributes, to make the distinction more clear or to show how these two concepts fit together...

85.182.79.140 (talk)

--- —Preceding unsigned comment added by 85.182.78.247 (talk) 22:48, 26 July 2008 (UTC)

In computing, an abstract data type (ADT) consists of a "domain" (a set of data), a set of operations, and a set of "axioms" (rules that the operations must obey).

The first paragraph is wrong in several ways: (a) Classes, while one of the better ways to implement an ADT, aren't the only one, and the style described here is just one of several possible implementations even in an OO language; (b) there's no mention of axioms (it's implicit in "specification" if you will, but that's too easy to overlook).

Here's my attempt at cleaning this up:

In programming, ADTs are often used as a design and documentation vehicle: if some code carries as comment that amounts to "this implements a stack", it is immediately clear that the essential properties of the code are those of the "stack" ADT, and that everything else was considered accidental "implementation detail" by the programmer.

HTH. -- Joachim Durchholz [[1]]

---

How the heck would a balanced binary tree fit under this categorization? since it being balanced means that the internals ARE important. User:hfastedge

The answer is -- it doesn't. The fact that a binary tree is balanced is an implementation property. Although it may improve the practical performance of a binary tree greatly, it shouldn't have any effect on the functional properties. Balanced and unbalanced binary trees are identical from an ADT point of view -- Derek Ross

Actually a balanced binary tree *is* an ADT. It is a set of data (trees over some given data), operations (insert/remove/lookup by walking over tree nodes), and axioms (balancedness). However, it's usually not the ADT that users of a balanced binary tree are interested in. The ADT for these is a Map (insert/remove/lookup no matter how), plus some performance guarantees (performance guarantees are usually not considered part of an ADT, though I'd personally say that this would make the concept more useful). -- Joachim Durchholz [[2]]

---

This article as it currently stands does not spell out the clear separation between interface and implementation that is necessary in defining an abstract data type. See my alternative data abstraction article for an explanation of this.

Ldo 12:33, 12 Sep 2003 (UTC)

---

This page should include information on preconditions, postconditions, and invariants.

--

The original example seemed too complex. Hopefully, seeing the interface and implementation will help the reader to understand.

I hope to add an alternative implementation when I get some more time.

Bill Pringle | Talk]] 20:39, 10 Aug 2004 (UTC)

--- YES! An abstract data type is not a class or any other implementation. It is abstract -- not an implementation. And the abstract data type is not merely defined in terms of its programmatic interface, but as the commenter above noted: by the specification of the behavior: preconditions, postconditions, and invariants. —The preceding unsigned comment was added by 67.161.67.58 (talk • contribs) 19:08, 16 March 2007. ---

Complex number???

Is complex number really an ADT?????? Talam 00:56, 6 December 2005 (UTC)

Depending on how you look at it... If given enough explation why (being an instance of Number and AlgebraicallyClosedField), yes, but no, in the sense that it is a container like List and Tree. —R. Koot 16:15, 6 December 2005 (UTC)

It isn't that a complex number is an ADT, but rather you can create an ADT for a complex number. That is a list of ADT examples that can be found in text books. Personally, I think Complex Numbers make a lousy example, but the text book I use happens to use that example. wrp103 (Bill Pringle) - [[User talk:Wrp103|Talk]] 21:17, 7 December 2005 (UTC)

The way I've found that is the most successful way to explain what an ADT is, to give tangible examples. The ADT for an ordered set of information provides the same API for accessing the data, regardless of it being stored in an array, an unordered linked-list, an ordered linked-list, a binary tree, a 3-2 tree, etc. A List of the common interfaces for ADTs needs to also be added to the article.

Linked List and Binary Search Tree

An anonymous editor deleted linked list and binary search tree without any explanation in the edit summary. Thinking it was a new editor that was experimenting, I reverted their edit. They since contacted me on my talk page and gave the following explanation:

I tried to make an edit to correct your page about abstract data types. You list "linked list" and "binary search tree" as abstract data types, and I removed them from the list because I believe they should not be included. I was not attempting to vandalize the entry or "experiment" as you said in your message to me.

An abstract data type should not specify an implementation; therefore a linked list is certainly NOT an ADT. A list, also written in the page, IS an ADT. But not a linked list, no more than an array list.

For the same reason, a binary search tree is not an ADT. Binary search trees are, like linked lists, particular data structures and not implementation-independent. A binary search tree can be *USED* to implement an ADT such as a set or map.

(The editor used different IP addresses when they made the edit, and when they wrote to my talk page, so I don't have an easy way to contact them directly.)

I don't totally agree with the logic, but they made a good point, so I reverted my revert back to their version. They are correct that an ADT hides the implementation from the user, but that doesn't (IMHO) preclude an ADT from implementing a data structure.

Personally, I think that a linked list, for example, can be an ADT by providing methods to perform certain operations. The result is that the user doesn't need to know anything about how to make a linked list, but can still use them.

Anybody else have any strong feelings one way or the other? wrp103 (Bill Pringle) 00:48, 27 October 2006 (UTC)

---

Bill, I was the one who made the anonymous edit about linked lists and binary trees. I apologize for my unnecessary anonymity. My name is Marty Stepp and I'm a CS&E instructor at the University of Washington. I still believe that a linked list isn't an ADT, because the name itself implies the exact style of implementation, which is contrary to the idea of ADTs.

User:Martnstepp (Marty Stepp) 02:36, 14 November 2006 (PST)

I can see arguments on both side. There are many ways in which to implement a linked list (single / double, internal / external, pointers / array, etc.) Providing an object with a series of methods allows a user to incorporate a linked list within their program without knowing anything about the implementation. A new version of the class could be distributed with a totally new implementation that would not affect any users. That seems to meet the criteria of an ADT. I don't see that any different than, say Vector in Java: it is an abstract array. wrp103 (Bill Pringle) 14:15, 14 November 2006 (UTC)

Separation of interface and implementation

Regarding the last paragraph of the "Separation of interface and implementation" section, I appreciate the note regarding ADT representation using the class construct. However the final two sentences seem to introduce language contrasts that I am not aware of. C also provides mechanisms of enforcement and hierarchy. It might be more clear to add C to the list or to remove all language examples.

Also it is not clear what an "object oriented ADT" is. Perhaps an ADT represented as a class?

--Sector7agent 22:59, 8 January 2007 (UTC)

That is what I was thinking of when I wrote that. C is limited to declaring static functions that don't create entry points, but Java/C++ have private, public, and protected. Actually, I wrote that text some time ago, and have no problems if somebody wants to tweak (or rewrite) it. wrp103 (Bill Pringle) 16:00, 9 January 2007 (UTC)

The first paragraph, especially the last sentence; it's a classic! talk about explaining something in layman's terms. Arcturus 22:16, 8 February 2007 (UTC)