0
$\begingroup$

I'm trying to understand whether integers are an abstract data type.

The Wikipedia article starts out by saying that integers are not an ADT:

In practice, many common data types are not ADTs, as the abstraction is not perfect, and users must be aware of issues like arithmetic overflow that are due to the representation. For example, integers are often stored as fixed-width values (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.

But then says integers are an ADT (see here):

For example, integers are an ADT, defined as the values ..., −2, −1, 0, 1, 2, ..., and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc., which behave according to familiar mathematics (with care for integer division), independently of how the integers are represented by the computer [...] but for most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.

Which paragraph is correct?

The literature defines an ADT as a class of abstract objects which is fully characterised by the operations that can be performed on them. I take this to mean that an ADT is a type that is representation independent.

While integers can be defined by the operations that you can perform on them (e.g. arithmetic, comparison), they are not representation independent as the first quote points out.

On the other hand, does full representation independence even exist in practice? If we go by the first quote, then even the list type would not qualify as an ADT, since users need to be aware of implementation-dependent space constraints.

$\endgroup$

4 Answers 4

1
$\begingroup$

The first paragraph is written in a way that is a bit confusing. It doesn't mean that integers are not an ADT. It means that fixed-width ints are not a faithful/valid/correct implementation of integers. Fixed-width ints are presumably the common datatype it is referring to.

$\endgroup$
1
  • $\begingroup$ See my answer. An abstract integer may exist in theory, and could be implemented as an arbitrary array of bytes, but the fixed-width integers that programmers typically deal in, do not even pretend to be an implementation of this "abstract integer". $\endgroup$
    – Steve
    Commented Aug 15, 2022 at 18:57
1
$\begingroup$

An abstract data type is defined by a domain (possible values taken by the type) and the operations that are defined on it. Usually, one lists the minimal set of operations sufficient to achieve a given task.

First example:

We define the ADT "parity". The underlying set is the naturals, and the following operations must be supported:

  • zero: returns the smallest natural;
  • inc(n): returns the successor of the natural;
  • even(n): tells if the naturalis even;
  • we don't require a way to get the "value" of the natural, it can be kept secret.

Second example:

We define the ADT "natural16". The underlying set is the integers in [0, 65535].

The operations to be supported are

  • get(n): returns the value as a binary number;

  • set(n): assigns the value as a binary number;

  • inc(n): returns the successor of n;

  • add(m, n): returns the sum of n and m, provided n+m ≤ 65535.

Third example:

We define the ADT "natural". The underlying set is the natural numbers.

The operations to be supported are

  • get(n): returns the value as a binary number;

  • set(n): assigns the value as a binary number;

  • inc(n): returns the successor of n;

  • add(m, n): returns the sum of n and m.


Even though computer implementations of these come naturally to mind, the implementation details are irrelevant and need not be disclosed. The third type cannot be "fully" implemented on a physical machine, but approximations by computers are quite sufficient for real applications.

$\endgroup$
0
$\begingroup$

On the other hand, does full representation independence even exist in practice?

*It depends on the domain you are working with.

In the case of integers as mentioned, being of fixed width makes them prone to conditions like overflow. This is because the notion of integer addition in mathematics(which operates on the set of integers) is associated with the implementation of integers. But actually what the implementation does work on is a fixed set of values and modular arithmetic(more precisely a Ring of size $2^w$ for w bit width). If you follow this model, then (modular)addition over integers does have a perfect abstraction(for argument's sake).

Shortly put, it depends on what ADT you are implementing, and on what platform, as all of it eventually needs to be realized on actual hardware.

but for most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.

Same as what I said at the beginning. Unless you come across a situation, where the implementation of integers doesn't satisfy your needs, its safe to assume the integers as truly abstract.

Which paragraph is correct?

Both of them are, in their own ways. The first one reflects the physical limits we have while implementing ADTs, and the second one stresses the fact that given a scenario, an imperfect abstraction would do just as good as a perfect one.

TLDR;

ADT's are as abstract as needed.

$\endgroup$
0
$\begingroup$

My first impression was that the source you've quoted is contradictory nonsense.

Having spent a bit of time reading up, I've come to the following conclusion.

The notion of an "abstract data type" makes sense only to the extent that we recognise certain data types can have different but equivalent implementations.

What might be abstract about an "integer" is that part of the type that doesn't seem to depend on whether a machine is big-endian or little-endian, two's complement or one's complement, and so on.

It's worth bearing in mind that Barbara Liskov, who apparently coined this term, was writing in 1974, when these sorts of storage details loomed large.

However, what exactly the full "abstract" definition of any given type is, may be something that is itself open to different interpretations. It's not always clear that programmers are dealing in rigorous abstractions, or merely in imprecise definitions and sloppy thinking.

I would be inclined to say that an "abstract" integer, free of all storage details like field size, is not something that is widely known to programmers. Probably because integers with variable-size storage (and thus, bounds limited only by the total available storage, which is a kind of limitation that applies only to the machine, not to a data type) don't commonly exist, and are probably extremely slow to process.

So we programmers might deal with the abstract Int32, and the abstract UInt8, but not the abstract integer that has no fixed bounds.

It's also not clear that "fixed-width integers", as a general concept encompassing a family of fixed-width integer types, meets the criteria of being an ADT in its own right, because each different fixed-width integer type do not differ merely by their implementation details, but by having a different fundamental specification of the range of values that can be represented by each fixed-width type.

I would also say the general usefulness of the distinction between "abstract" and "implemented" has probably reduced since 1974, as the use of compilers means that probably all types are conceived of by the programmer in a way that is abstract from the minutiae of their binary implementation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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