RECITATION 7
By: Vasundhara Acharya
ABSTRACT DATA TYPES
• We know that a data type signifies the type and space taken by the
data used in programs. An Abstract Data Type is a special data type
that is defined by a set of values and a set of operations on that type.
• We call these data types as “abstract” because these are
independent of any implementation. We can use these data types and
perform different operations with them, but we do not know how
these operations are working internally.
• The implementation details of these data types are totally invisible to
the users. It does not specify how the data stores in the memory area
and what algorithms are useful for implementing the operations on
the data.
Types and Operations of Java Abstract Data
Type
• Types
• We can classify the Abstract data types either as built-
in or user-defined or as mutable or immutable.
• If an Abstract Data Type is mutable then we can change the
objects of its type and if it is immutable then we can’t change its
object.
• For example, the Date class is mutable because we can call its
setMonth() method and observe the change with the getMonth()
operation. But String is immutable because its operations do not
change the existing objects but create new String objects
• The operations of an abstract type are classified as follows:
• Creators create new objects of the type. A creator may take an
object as an argument, but not an object of the type being
constructed.
• Producers create new objects from old objects of the type. The
concat method of String, for example, is a producer: it takes two
strings and produces a new one representing their concatenation.
• Observers take objects of the abstract type and return objects of a
different type. The size method of List, for example, returns an int.
• Mutators change objects. The add method of List, for example,
mutates a list by adding an element to the end.
EXAMPLES
• int is a primitive integer type of Java. int is immutable, so it has
no mutators. Its operations are:
• creators: The numeric literals 0, 1, 2, 3,…
• producers: Arithmetic operators +, -, ×, ÷
• observers: Comparison operators ==, !=, <, >
• mutators: None (it’s immutable
• 2. The list is an interface of Java List. The list is mutable. Its
operations are:
• creators: ArrayList and LinkedList constructors,
Collections.singletonList
• producers: Collections.unmodifiableList
• observers: size, get
• mutators: add, remove, addAll, Collections.sort
• 3. A string is Java’s string type. The string is immutable. Its
operations are:
• creators: String constructors
• producers: concat, substring, toUpperCase
• observers: length, charAt
• mutators: none (it’s immutable)
EXERCISE FOR YOU
SOLUTION






















INTERESTING EXAMPLE OF REPRESENTATION
INVARIANT
• An invariant is a property of a program that is always true, for every
possible runtime state of the program. Immutability is one crucial
invariant that we’ve already encountered: once created, an
immutable object should always represent the same value, for its
entire lifetime
How do we guarantee that these Tweet
objects are immutable – that, once a tweet is
created, its author, message, and date can
never be changed?
THREAT1
SOLUTION
Is the REP still exposed?
SOLUTION
More DETAILED NOTES REFERENCE:
• Reading 13: Abstraction Functions & Rep Invariants (mit.edu)
ADT Methods
Representation Invariant
Recitation 6
Brandon Rozek
rozekb@rpi.edu
Rensselaer Polytechnic Institute, Troy, NY, USA
February 2022
Rozek Recitation 6
ADT Methods
Representation Invariant
Outline
Two things:
ADT Methods
Representation Invariants
Rozek Recitation 6
ADT Methods
Representation Invariant
Logistics
First exam is next week.
Let me know if you have any topics that you want me to go
over.
Rozek Recitation 6
ADT Methods
Representation Invariant
Running Example
I have an amateur radio license from the
FCC, callsign KN4VYS.
I am particularly interested in software
defined radio (SDR)
To make some of these concepts concrete,
let’s apply them to building an SDR!
Rozek Recitation 6
ADT Methods
Representation Invariant
Side Effects
A method is said to have a side effect if it modifies some state
outside its local context.
Examples include: modifying object fields, printing to the
screen, taking user input, network calls.
A program is not useful unless it has a side effect of some kind.
Rozek Recitation 6
ADT Methods
Representation Invariant
Reasoning through Side Effects
Since side effects exist outside the method you’re considering,
this makes them difficult to reason through.
The most common technique used to deal with side effects is
through immutability and exceptions.
Rozek Recitation 6
ADT Methods
Representation Invariant
Personal Thoughts
The functional programming community have made great
strides in dealing with side effects primarily through monadic
structures. (Feel free to ask me!)
Though a simple recommendation I have is to decouple
computation from side effects.
e.g A method radiate() should not also print to the screen
Rozek Recitation 6
ADT Methods
Representation Invariant
Reasoning through Abstract Data Types
In fact, methods that are small and follow the
single-responsibility principle are often easier to reason about
and prove!
At first, it’ll feel verbose and repetitive. Later on you’ll learn
techniques which are more concise.
Rozek Recitation 6
ADT Methods
Representation Invariant
Example: Radio Overview
A radio (more specifically a transciever) contains both a receiver
and a transmitter in one unit.
Rozek Recitation 6
ADT Methods
Representation Invariant
Example: Connecting to a Repeater
Amateur radio operators extend their reach by connecting to a
repeater. In the next slides, we’ll analyze channels.
Rozek Recitation 6
ADT Methods
Representation Invariant
ADT Methods
We group the access methods of an ADT into:
Creators: Creates a brand new object.
Observers: Returns information about this object.
Producers: Returns a new object of this type by performing
operations on the current object.
Mutators: Changes this objects fields.
Note: Immutable ADTs do not have mutators.
Rozek Recitation 6
ADT Methods
Representation Invariant
Creators
Another name for constructors
No preexisting state is changed, therefore modifies is none.
public Channel(double freq);
public Channel(double rxFreq, double txFreq);
Rozek Recitation 6
ADT Methods
Representation Invariant
Observers
Returns information about this which often is of a different
type (int, String, etc)
Should have no side effects.
public bool isSimplex() {
return this.rxFrequency == this.txFrequency;
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Producers
Returns an object of the same type, often with different fields.
This technique is very common in immutable objects.
Should have no side effects.
public Channel toDuplex(double txFrequency) {
return new Channel(this.rxFrequency, txFrequecy)
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Mutators
Changes internal state of this
Often does not return anything
public void changeRxFrequency(double frequency) {
this.rxFrequency = frequency;
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Immutability
In immutable objects, instead of changing state through
mutators, producers are used.
// Alternative to mutator
public Channel changeRxFrequency(double frequency) {
return Channel(frequency, this.txFrequency);
}
Java strings are immutable and follow this pattern.
Rozek Recitation 6
ADT Methods
Representation Invariant
Immutability
Big benefit to immutable objects is that they are thread safe
by default!
Slight performance detriment since memory gets copied.
For correctness, need to make sure memory is copied and not
referenced in new object.
Rozek Recitation 6
ADT Methods
Representation Invariant
Representation Invariant
Rozek Recitation 6
ADT Methods
Representation Invariant
Representation Invariant
Similar to how we use loop invariants to reason about loops,
we’ll use representation invariants to reason about objects.
Indicates whether data representation is well-formed.
Must hold before and after every method.
Example: this.frequency > 0
Rozek Recitation 6
ADT Methods
Representation Invariant
Abstraction Function
What does the data structure semantically mean?
Example from class: array[2, 3, -1] represents −x2 + 3x + 2
Rozek Recitation 6
ADT Methods
Representation Invariant
Representation Exposure
Representation exposure is unintentional external access to
the underlying representation of an object.
Allows access without going through object’s public methods
Representation exposure can break representation invariants!
Rozek Recitation 6
ADT Methods
Representation Invariant
Example
Java does not provide any guarantees with the private keyword.
public class Channel {
private double rxFrequency;
private double txFrequency;
public Channel(double freq) {
if (freq <= 0) {
throw new IllegalArgumentException();
}
this.rxFrequency = freq;
this.txFrequency = freq;
}
public static void main(String[] args) {
Channel c = new Channel(14.54);
c.rxFrequency = -5.0; // Bypassed our check :(
}
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Immutability Solution
With the final keyword, immutability is enforced.
public class Channel {
final private double rxFrequency;
final private double txFrequency;
public Channel(double freq) {
if (freq <= 0) {
throw new IllegalArgumentException();
}
this.rxFrequency = freq;
this.txFrequency = freq;
}
// Add producer method setFreq
public static void main(String[] args) {
Channel c = new Channel(14.54);
c.rxFrequency = -5.0; // Compiler error
}
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Beware of References
public class Channels {
private ArrayList cs;
public Channels(ArrayList cs_param) {
this.cs = cs_param;
}
public Channels add(Channel c) {
Channels new_channels = new Channels(this.cs);
new_channels.cs.add(c);
return new_channels;
}
public static void main(String[] args) {
Channel n2ty = new Channel(145.17);
Channels empty_channels = new Channels(new
ArrayList(););
Channels some_channels = empty_channels.add(n2ty);
System.out.println(empty_channels.cs.size());
}
} Rozek Recitation 6
ADT Methods
Representation Invariant
Recommendation: Copy
When dealing with mutable producers, always make sure you
perform a copy!
Do note the difference between a shallow and a deep copy...
Rozek Recitation 6
ADT Methods
Representation Invariant
Defensive Programming
If you’re dealing with mutable objects:
Assume your invariants will be violated!
Check the invariants on method entry, exit, etc.
Rozek Recitation 6
ADT Methods
Representation Invariant
Checking Invariants with Assertions
Assertions can be used to check invariant satisfaction.
java runs with assertions disabled by default (java -ea to
enable)
When assertions are not satisfied an AssertionError
exception is thrown.
Rozek Recitation 6
ADT Methods
Representation Invariant
Example
public Channel toDuplex(double txFreq) {
assert this.rxFrequency > 0;
assert txFreq > 0;
return new Channel(this.rxFrequency, txFreq);
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Defensive Programming - Preconditions
Recall that preconditions are what is assumed to be true
before the method call.
If its not true then all bets are off!
But as we saw with defensive programming constraints will
often get violated.
Rozek Recitation 6
ADT Methods
Representation Invariant
Preconditions and Exceptions
This class recommends to have weaker preconditions in order
to strengthen the specification.
Make use of exceptions when inputs are invalid!
There might be some cases where weaker preconditions are undesirable...
Rozek Recitation 6
ADT Methods
Representation Invariant
Client Code: Try/Catch/Finally
The exception pattern is quite common with I/O operations.
public void mute_transmit() {
Socket s;
try { s = new Socket(host, port); /* ... */ }
catch (ConnectionException e) { /* ... */ }
finally { s.close(); }
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Propagate Exceptions
In Java, checked exceptions must be either dealt or propogated by
the caller. To propogate, use the throws keyword in the method
declaration.
class Channels {
/* Declarations from before... */
public void loadConfigFromFile(String filename)
throws IOException {
FileReader file = new FileReader(filename);
BufferedReader fileInput = new
BufferedReader(file);
fileInput.readLine(); // Might throw IOException
fileInput.close();
}
}
Rozek Recitation 6
ADT Methods
Representation Invariant
Any Questions?
Rozek Recitation 6