Defining Data Behavior Without Implementation Details

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 4.1 Free with a free account

Defining Data Behavior Without Implementation Details

Data Structures and Algorithms · Chapter 4: Abstract Types, Exceptions, and Nested ClassesSection 4.1 · lesson 11 of 8710 min · free with a free account

← Choosing Between Contracts and Partial BlueprintsNext lesson: Turning Data Definitions into Working Java Code →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Specify data by its operations, conditions and invariants before coding.

  • Define an abstract data type by its operations, preconditions, postconditions and invariants
  • Explain how a specification acts as a contract between caller and implementer
  • Distinguish a specification from its many possible implementations
  • Decide how operations should return results and handle broken preconditions

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,467 words). Read along, or search it.

Opening Question

Building a Display Before the Counter

Ana is building a display that shows how many visitors are inside a shop. It needs a counter. Ben will build that counter, but he hasn't written a single line yet, and he hasn't even decided how to store the number. Can Ana start her part today, without waiting for Ben? And if she can, what would she need from him first?

Definition

What an Abstract Data Type Describes

Think of the volume button on a remote. Press it, and the sound gets louder. You don't know which circuit does the work. And the maker can redesign that circuit, without changing what the button means. Programmers do the same with data. Before deciding how to store information, they write down what the data must do. That written description is an abstract data type, or A D T. It describes data by what you can do with it, and what happens when you do. It says nothing about memory layout, or the steps inside. A vending machine is a good picture. Put in money, choose an item, and the item drops. Whether a motor, a spring or a robot arm delivers it is invisible, and it doesn't matter to you.

Specification Parts

Operations, Conditions and Invariants

A complete specification answers four questions. Operations: what can be asked of this data? For a counter, which remembers one whole number: increment, decrement, and get count. Preconditions: what must be true before an operation is called? Decrement needs the count to be above zero. Postconditions: what will be true after it finishes? After increment, the count is one more than before. And invariants: what is always true, before and after every operation? The count is never negative.

Contract

Who Promises What

Together, these parts work like a contract between a caller and an operation. The caller promises the precondition. Call decrement on a counter that's already zero, and you've broken your side of the deal. The implementer promises the postcondition and the invariant. If the precondition was met, the result must be exactly as described, and the always-true fact must still be true. If the precondition is broken, the contract makes no promise at all. That's why a good specification also says what happens in that case.

Worked Example

A Full Counter Specification

Here's a full specification for the counter, in words and a table. There's no code, and no mention of how the number is stored. Its purpose: remember a single whole number, the count, such as the number of people in a room. It starts at zero, and its invariant is that the count is never negative. Increment returns nothing, can always be called, and leaves the count one higher. Decrement needs a count above zero, and leaves it one lower. Get count returns the current count, and changes nothing. Reset sets the count to zero.

Invariant Protection

Why Decrement Needs a Precondition

Why does decrement have a precondition? Because of the invariant. If the count were zero and decrement ran anyway, the count would become minus one, and never negative would be broken. The precondition protects the invariant. Follow some calls. From zero, increment gives one, increment gives two, and decrement gives one. Get count reports one. Decrement gives zero. And one more decrement is refused, because its precondition fails. The count stays at zero, and every state kept the invariant.

Quick Check

Which Call Breaks the Contract

Quick check. A new counter starts at zero. The calls are: increment, decrement, decrement, increment. Which call breaks the caller's side of the contract? Pause, and decide. The second decrement. After increment and one decrement, the count is back to zero, so the precondition, count above zero, is false when the second decrement is called. The first decrement was fine: the count was one. And increment has no precondition at all, so it can never break the contract.

Implementation

Many Implementations of One Specification

A specification says what an ADT does. An implementation is one particular way of making it happen, and many implementations can satisfy the same specification. One counter keeps the count in a single whole number, and adds or subtracts one. Another keeps a list, with one tally mark for every increment, and removes a mark for every decrement. Wasteful, but after any valid sequence of calls, get count answers the same. Users depend on the specification. The implementations can be swapped behind it.

Benefits

Five Payoffs of Separation

Keeping them separate pays off five ways. Freedom to improve: replace the tally marks with a single number, and nobody using the counter is affected. Easier teamwork. Back to Ana and Ben: she can build the visitor display using only the counter's specification, while he builds the counter. That's what she needs from him first. Clearer thinking: you notice that decrement at zero needs a rule, before any storage is chosen. Easier testing: the specification says exactly what to check. And reuse: the same counter can count visitors, clicks, or items in a basket.

Second Example

Specifying a Bag of Items

A second, richer example: the bag. A bag holds items in no particular order, and the same item may appear more than once, like a shopping bag with three apples and two lemons. It starts empty. Add puts in an item. Remove takes one copy out, and needs at least one copy to be there. Count of tells how many copies of an item the bag holds. Size gives the total, and is empty says yes or no. Three invariants tie them together. Count of is never negative. Size always equals the total of every count. And is empty is true exactly when size is zero.

Observation

A Bag Counts Many Items at Once

Notice that the bag is a counter for many items at once, each with its own count. And nothing says whether the items sit in a list, a table, or something else. That's left to the implementation.

Design Decision

A Small, Complete Set of Operations

Writing a specification is a design task, and three decisions shape it. First: which operations should it offer? Operations come in two families. Updates change the state: increment, reset, add, remove. Queries report on it without changing it: get count, size, is empty. Keep the set small: every extra operation is one more promise every implementation must keep. Keep it complete: users must reach every fact they need. And keep each one focused, with updates and queries apart, so that asking a question never changes the answer.

Design Decision

What Each Operation Returns

Second: what should each operation return? Queries return the answer in its simplest useful form: a whole number, a yes or no, or the item itself. Updates usually return nothing. Sometimes they return yes or no, to report whether the change happened, and then the specification must say exactly what each answer means. And name the return even when it's nothing, so no one has to guess.

Design Decision

Three Ways to Handle Failure

Third: what happens when an operation can't do its job, like removing an item that isn't in the bag? Silence leaves every implementer to guess differently, so the specification must choose. Choice one: refuse, and report an error. Calling remove without a copy breaks the precondition. That's good when a missing item usually means a bug in the calling code, but callers must check first. Choice two: return yes or no, yes if a copy was removed. Good when callers often don't know whether the item is there, though they can ignore the answer by mistake. Choice three: redefine the case as valid. If the item isn't there, remove does nothing. Good when the goal, the item gone, is already met, though real mistakes can slip by unnoticed.

Quick Check

Removing an Item Already Gone

Quick check. A family shares a shopping list. Two people often tap remove on the same item, and the second tap finds it already gone. The app simply redraws the list after each tap. Which way should the specification handle a missing item? Pause, and decide. Treat it as valid. The goal is an item that's off the list, and that's already true, so remove can simply do nothing. Refusing would turn an ordinary double tap into an error. And a yes or no answer would only be ignored, since the app never uses it.

Checklist

Steps for Writing a Specification

So, to write a specification: state the purpose in one sentence, and the starting state. List the invariants. List the operations, as updates and queries, each with its precondition, postcondition and return value. Say what happens when each precondition isn't met. Then read it all again, looking for any word that describes how instead of what, and remove it.

Key Takeaways

Specifications as Contracts

To summarize. An ADT describes data by its operations, preconditions, postconditions and invariants. The specification is a contract: the caller meets the precondition, and the operation delivers the postcondition and keeps the invariant. Specification and implementation stay separate, so implementations can change without disturbing users. And always state what happens when an operation can't do its job. Silence is the real mistake.

Think About It

Specifying a Stopwatch

Something to think about. Imagine a stopwatch, with start, stop, and get elapsed time. Write one invariant for it. Then decide what stop should do if the stopwatch was never started, and which of the three choices you picked, and why.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Defining Data Behavior Without Implementation Details

What is an abstract data type?
An abstract data type, or ADT, describes data by what you can do with it and what happens when you do, without saying how it is stored. A counter ADT, for example, offers increment, decrement and get count, and promises that the count is never negative. Whether the count sits in one whole number or a list of tally marks is left to the implementation.
What is the difference between a precondition, a postcondition and an invariant?
A precondition must be true before an operation is called, such as a counter's count being above zero before decrement. A postcondition is true after the operation finishes, such as the count being one higher after increment. An invariant is true before and after every operation, such as the count never being negative. Preconditions often exist to protect an invariant.
What is the difference between an ADT and its implementation?
The ADT is the specification of what the data does, while an implementation is one particular way of making it happen. Many implementations can satisfy one specification: a counter could keep a single whole number or a list with one tally mark per increment. Users depend only on the specification, so an implementation can be swapped or improved without affecting them.
How should an ADT specification handle an operation that cannot succeed?
The specification should state the behavior rather than stay silent. Three common choices are to refuse and report an error, which suits cases where failure usually signals a bug, to return yes or no to say whether the change happened, or to redefine the case as valid, so removing a missing item simply does nothing. Each choice has trade-offs, so match it to how callers behave.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →