Representation of Abstract datatype using Rational numbers

Representation of Abstract datatype using Rational numbers

The basic idea of data abstraction is to structure programs so that they operate on abstract data. That is, our programs should use data in such a way, as to make as few assumptions about the data as possible. At the same time, a concrete data representation is defined as an independent part of the program.

Note

In concrete data representation, a definition for each function is known

Any program consist of two parts. The two parts of a program are, the part that operates on abstract data and the part that defines a concrete representation, is connected by a small set of functions that implement abstract data in terms of the concrete representation. To illustrate this technique, let us consider an example to design a set of functions for manipulating rational numbers.

Example

A rational number is a ratio of integers, and rational numbers constitute an important sub-class of real numbers. A rational number such as 8/3 or 19/23 is typically written as:

<numerator>/<denominator>

where both the <numerator> and <denominator> are placeholders for integer values. Both parts are needed to exactly characterize the value of the rational number. Actually dividing integers produces a float approximation, losing the exact precision of integers.

8/3 =2.6666666666666665

However, you can create an exact representation for rational numbers by combining together the numerator and denominator.

As we know from using functional abstractions, we can start programming productively before you have an implementation of some parts of our program. Let us begin by assuming that you already have a way of constructing a rational number from a numerator and a denominator. You also assume that, given a rational number, you have a way of selecting its numerator and its denominator component. Let us further assume that the constructor and selectors are also available.

We are using here a powerful strategy for designing programs: 'wishful thinking'. We haven't yet said how a rational number is represented, or how the constructor and selectors should be implemented.

Note

Wishful Thinking is the formation of beliefs and making decisions according to what might be pleasing to imagine instead of by appealing to reality.

Example: An ADT for rational numbers

- constructor

- constructs a rational number with numerator n, denominator d

rational(n, d)

- selector

numer(x) → returns the numerator of rational number x

denom(y) → returns the denominator of rational number y

Now you have the operations on rational numbers defined in terms of the selector functions numer and denom, and the constructor function rational, but you haven't yet defined these functions. What you need is some way to glue together a numerator and a denominator into a compound value.

The pseudo code for the representation of the rational number using the above constructor and selector is

x,y:=8,3

rational(n,d)

numer(x)/numer(y)

- - output : 2.6666666666666665