What are 'Abstract Data Types'?

Yesterday, while reading an old computer science textbook “Programming and Problem Solving with C++”, I saw a chapter on “Abstract Data Types” (ADTs) and was instantly curious. So I read the chapter, hoping to learn about this strange and mysterious things. I was surprised to find out that ADTs are not strange and mysterious at all. In fact, I have been writing them in my programming career.

An ADT is any entity that contains data and specified behavior (methods/functions). For example, let us define a simple Bank Account ADT. This is a “specification” (a detailed list of what we want our ADT to do):

1. We should store how much money is in the account.
2. We can withdraw money from this account.
3. We can deposit money from this account.
4. We know how much money is in the account.

And here’s an example of the Bank Account ADT, coded in Ruby…

class BankAccount attr_reader :current_funds

def initialize(amount)
  @current_funds = amount
end

def withdraw(amount)
  @current_funds -= amount
end

def deposit(amount)
  @current_funds += amount
end   end </code>

That’s it.

Now, you may not like how I wrote this ADT. Perhaps you prefer not using classes and may wish to use a more “functional” approach to programming. Or maybe you just want to write this ADT in a different language.

That’s perfectly fine. Code the way that you wish. As long as you follow the specification listed above, the ADT is still valid. Your version of BankAccount is just as valid as mine. The implementation of an ADT is seperate from the specification of an ADT. That’s why it is possible to refactor your code…so long as your code behaves the same way before and after the refactor.

Now, the mind-blowing part is that you can build ADTs…using ADTs. Suppose I want to create a Bank ADT that can store Bank Account ADTs, and I want to know how much money the Bank ADT has.

class Bank

def initialize(array_of_bank_accounts)
  @accounts = array_of_bank_accounts
end

def total_funds
  sum = 0
  @accounts.each do |account|
    sum += account.current_funds
  end
  sum
end

end </code>

“Programming and Problem Solving with C++” recommends the use of ADTs because it makes programs simpler and easier to understand, thereby making code easier to write. The book uses an example of a car to illustrate its point:

“With abstraction, we focus on the what, not the how. For example, our understanding of automobiles is largely based on abstraction. Most of us know what the engine does (it propels the car) but fewer of us know-or wnt to know-precisely how the engine works internally. Abstraction allows us to discuss, think about, and use automobiles without having to know everything about how they work.

And programming makes use of abstractions heavily, with some languages being entirely built on other languages. Ruby, for example, is built on C. Abstraction serves as a great way to manage complex code bases…and ADTs are the living paragons of abstraction.

But abstractions are ‘leaky’. What if there is some bug in my BankAccount ADT? That bug would harm my Bank ADT as well…and could even harm any ADTs that were built on top of my Bank ADT.

So while ADTs are useful, you cannot be totally dependent on them. You have to be willing to look at the internal code of an ADT you’re using and be able to debug it.

It is not enough to know how to program using abstractions. You must also know how to program the abstractions themselves.