5

I'm trying to deepen my understanding on this, the only thing I know for sure is that Iterator is an interface in Java.

I've been reading CS literature, for example here and here and looking for similar questions here.

All I've come up is just a bit confusing to me: I read, for example, that "abstract datatypes simply summarize names and types of operations (in Java, this means interfaces)" or "each ADT corresponds to a class (or Java interface) and the operations on the ADT are the class/interface's public methods". Some people even confuse ADTs with abstract classes.

So, may I state that an Iterator is an abstract data type?

6

A Tale of Abstractions

There's a lot of confusion about this on the Internet, but the term is quite technical, and according to the Cook paper (referenced in the answer liked to by Greg Burghardt), it essentially boils down to this.

OOP Objects (and the related static typing mechanisms, including classes, abstract classes and interface types) and ADTs represent two different approaches to data abstraction. Cook calls the OOP approach "procedural abstraction" - I'll come back to that later. The two have different strengths and weaknesses.

To understand this, think about the underlying concrete data structures (the representations), the operations on them, and the client code (that calls these operations). The OOP approach makes it easy to add new representations (new derived classes, or new implementations of an interface), as long as you don't change the set of operations. The term for this is the public interface. Don't confuse this with interface types (declared via the interface keyword); in this more broad meaning, the public interface is the set of public members (public methods, properties, fields, events). On the other hand, adding new operations is difficult - you have to hunt down all existing different derivatives and change their implementation details to make sure they all support the changed interface.

This is a "procedural abstraction" in the sense that the public interface defines a contract between clients and different implementations, a contract that abstracts away the actual functions (procedures) that are being called. The interface defines a more generalized notion of an operation - it defines what the operation means, what it does, but not exactly how it does it. When you call a method on an object through a variable of a more abstract type, you are expecting it to do perform this operation (as defined by this contract, and as explained in the documentation), but you don't know for sure which concrete function on which class will get called - the underlying language mechanism dispatches the call for you.

Now, with ADTs, it's a bit different. There's typically a finite, limited set of different representations (different underlying data structures). These are all then deemed to be different forms of the same abstract data type (ADT). It is abstract in the sense that you are arranging things so that you can use these different, concrete data structures to in a way that lets you pretend that it's all the same type. So far, that doesn't sound that much different from OOP. As before, client code never mentions the concrete representations (except when the constructors are called); all of it is written in terms of this ADT. However, the operations on the ADT aren't themselves abstract in the same way OOP operations are. Each ADT function internally provides an implementation for every possible representation. There's basically a switch statement in there, that switches on the concrete type, or if not, then there's some language feature that does roughly the same thing. So, in ADTs, clients can ignore the actual concrete type (concrete representation) because each function has a part that deals with any particular representation, and so is guaranteed to work.

This makes it easy to add new operations - you just add a new functions, and you write a bit of logic for each possible representation, or rely on existing functions and treat the data abstractly yourself. Adding new representations, however, is hard, because you then break the aforementioned guarantee; to maintain it, you have to find all functions on the ADT and implement support for the new case.

That means that even though concrete representations are hidden from client code, they are also a part of the ADT contract when it comes to extensions (to adding new operations).

As with any decoupling, in both cases there's an abstraction in between that represents a certain contract between the two components. They get to be decoupled precisely because they are both coupled to that contract, to the abstraction (which is a more generalized representation of the interaction between the two components). If the contract is broken, so is the decoupling.

You'll encounter ADTs more in functional languages, where the "switch" on the representation happens via pattern matching. But also, primitive types, like float can be considered ADTs as well (though internal to the language), at least in the context of certain operations, because there are different underlying representations - e.g. there are special bit patterns that represent -inf, +inf, NaN, etc., and when you use the normal arithmetic operations, you don't have to examine for these special cases, the operations can handle these by themselves.

It's not all about the type system though; you can use these ideas to design your own abstractions outside of the type system. One example is the Visitor pattern. While it's often described as a way to do multiple dispatch, it can also be seen as an implementation of an ADT: the different Element derivatives are the different representations, and different Visitors are different operations. Note the similarities: it is easy to add new visitors, but since each visitor handles every element, it is hard to add new elements. Another way to do it is to write operations that in terms of handles - instead of an object or a concrete data structure, an operation takes in a handle (e.g., an index of some sort), and then uses it internally to discover the concrete type and find some data structure somewhere. This is probably something you'd do under special circumstances, though - e.g., the motivation may be to increase performance by taking control over how data is stored to ensure cache friendliness.

Finally to answer your question; Iterator, as implemented in Java, is not an ADT in this sense; but in general it should be possible to implement iterators as ADTs.


What part of Iterator in Java doesn't meet the definition?

It's because of the kind of abstraction used here. It's the "procedural abstraction" (the OOP kind of abstraction): the Iterator interface represents a "thing you can iterate over" (a collection), that supports a certain set of abstract operations (most importantly, next and hasNext).

It's easy to add new representations (new implementations of Iterator) - you just implement the interface. Here, "new representation" refers to things like the state that the iterator keeps internally, and the exact details of how it goes about the iteration: you can vary the collection over which it iterates, the order in which it does so, how it keeps track of all of that, etc. And you don't have to make changes to client code, as long as it relies solely on the Iterator interface. Java's foreach loop ("enhanced for-loop") makes use of Iterator behind the scenes; it can work with custom collections if they implement the Iterable interface, which in turn provides the foreach loop with a way to obtain an Iterator.

More to the point, if Java came up with new collections and new iterators for them (new concrete representations of Iterator), that wouldn't affect other people's code - it's just a new option that people can make use of if they want to. If, on the other hand, they changed the foreach loop to require a new operation on the Iterable interface (the assumption here is that there's no reasonable default implementation), than that would be a breaking change - anyone who implemented Iterable & Iterator to provide support for the foreach loop would have to go back and change their code. Hopefully, this gives some context to "easy" vs "hard"; it's not merely about one being more inconvenient then the other for the programmer, but rather about the interaction between the client code and library code in the face of change, especially once the latter has been released "out there". New implementations are adding new behavior, sure, but it within the confines of the abstract operations (it's conceptually the same set of high-level operations), and client code is written in a way that expects this.

| improve this answer | |
  • 1
    Very detailed answer up to the part about answering the question. Maybe it's in there but could you explain what part of Iterator in Java doesn't meet the definition? – JimmyJames Jan 15 at 19:46
  • I'm struggling with something here: "This makes it easy to add new operations - you just add a new functions" then later we have: "But also, primitive types, like float can be considered ADTs as well", I can't 'add' operations to float. I can create things that work with float but I can do that with any type. Perhaps I'm missing something basic. – JimmyJames Jan 15 at 23:01
  • @JimmyJames: regarding floats - this is why I added "though internal to the language"; the programmer cannot add completely new operations (except if they can be written entirely in terms of existing ones), but the language designers can (in principle). In this case, it's an implementation detail of the language, but the concept can also be directly supported by the type system (letting programmers use it to express their own types), or it can be applied at design level (by relying on data, or by "repurposing" language features in some clever way). – Filip Milovanović Jan 16 at 1:22
  • @JimmyJames: "Maybe it's in there but could you explain what part of Iterator in Java doesn't meet the definition?" - I've edited the answer. – Filip Milovanović Jan 16 at 1:22
  • 1
    @JimmyJames I'm going to write my own answer. Maybe that will help. – Sebastian Redl Jan 17 at 9:52
1

So, may I state that an Iterator is an abstract data type?

An ADT is a collection of data and a set of operations that may be performed on that data. An iterator is composed of a set of data to iterate and a set of operations for performing that iteration. Importantly, those operations do not define how the operator is performed. So an iterator - in general terms - is an ADT.

But the answer to the question in your title, "Is it true that “A Java Iterator is an Abstract Data Type”?", is "no". The Java Iterator is an interface, ie it only defines the set of operations, not the collection. And in general, "Java iterators" are implementations of that interface, so they define how the behaviours are performed. They aren't abstract in that regard so aren't ADTs.

| improve this answer | |
0

If I remember right ADTs are abstract types. This means they are not expressed or implemented in any language. Java interface is already a specific representation of some possible abstract Iterator written or depicted on paper, on desk or as part of UML diagram for example.

But java.util.Iterator is definitely a very close representation of what possible Iterator should be. Many other languages have another representations of iterator. Cpp has std:: iterator for most common case. So iterator is what we talk about as a concept, what we can discuss. It's not what you use in day-to-day work in any particular language. Moreover it doesn't matter can you call smth in any certain construct as ADT or something else. It should just work as expected and that's all. Java iterators do what they should do. And nobody cares about naming and terms.

What else I can say about ADT is that it is outdated concept for modern computer science. ADTs cover just one aspect of program engineering - working with data. This is all about what is already implemented and reused via higher-level abstractions. Data abstractions are nowadays used mostly in just one layer of computer systems - DAO, data access objects. Other layers work mostly with other types of abstractions, eg actors, processes, strategies. So it's not productive to discuss naming of abstractions that already have thousands of implementations in existing code base for tens of years.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.