Difference between revisions of "Data abstraction"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m (Example: fix)
 
(7 intermediate revisions by one user not shown)
Line 1: Line 1:
'''Data abstraction''' is an [[abstraction]] methodology in which functionality is separated from representation—we don't need to know how data is represented internally; we just need to know how to interact with it.
+
{{C-class}}
 +
'''Data abstraction''' is the invention of new data types. It separates functionality from representation—we don't need to know how data is represented internally; we just need to know how to interact with it.
  
 
Data abstraction is supported by defining an ''abstract data type'' (ADT), which is a collection of constructors and selectors. ''Constructors'' create an object, bundling together different pieces of information, while ''selectors'' extract individual pieces of information from the object.
 
Data abstraction is supported by defining an ''abstract data type'' (ADT), which is a collection of constructors and selectors. ''Constructors'' create an object, bundling together different pieces of information, while ''selectors'' extract individual pieces of information from the object.
Line 7: Line 8:
  
 
=== Examples ===
 
=== Examples ===
An ADT for [[Rlist|recursive lists]]:
+
An ADT for [[linked list]]s:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
empty_rlist = None
+
empty = lambda: 42
  
# constructor
+
def link(element, list=empty):
def make_rlist(first, rest=empty_rlist):
+
     return (element, list)
     return first, rest
+
  
# selector
+
def first(list):
def first(r):
+
     return list[0]
     return r[0]
+
  
# selector
+
def rest(list):
def rest(r):
+
     return list[1]
     return r[1]
+
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 72: Line 70:
 
# selector
 
# selector
 
def numer(rat):
 
def numer(rat):
     return rat[1]('numer')
+
     return rat[0]('numer')
  
 
# selector
 
# selector
Line 84: Line 82:
 
# mutator
 
# mutator
 
def set_denom(rat, value):
 
def set_denom(rat, value):
     rat[0]('denom', value)
+
     rat[1]('denom', value)
  
 
def print_rational(rat):
 
def print_rational(rat):
Line 94: Line 92:
  
 
=== Example ===
 
=== Example ===
An ADT for a [[rlist|recursive list]]:
+
An ADT for a linked list:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
class Rlist:
+
class LinkedList:
 
     class EmptyList:
 
     class EmptyList:
 
         pass
 
         pass
Line 114: Line 112:
 
     """Return the slope of the line that connects POINT1 and POINT2."""
 
     """Return the slope of the line that connects POINT1 and POINT2."""
 
     return (point1[1] - point2[1]) / (point1[0] - point2[0])
 
     return (point1[1] - point2[1]) / (point1[0] - point2[0])
</syntaxhighlight> We assume that the internal representation of a point is some type of sequence but this might not always be the case.
+
</syntaxhighlight> We assume that the internal representation of a point is a tuple. Instead, we should have used the selectors <code>x_coord</code> and <code>y_coord</code>.
  
Data abstraction violations destroy flexibility because if you want to change the representation of the ADT, you must change all the functions that use the ADT. If you maintain data abstraction, you need only change the constructors and selectors.
+
Data abstraction violations limit flexibility because if you want to change the representation of the ADT, you must change all the functions that use the ADT. If you maintain data abstraction, you need only change the constructors and selectors.
  
 
== Sources ==
 
== Sources ==
 
* http://inst.eecs.berkeley.edu/~cs61a/fa13/slides/10-Data_6pp.pdf
 
* http://inst.eecs.berkeley.edu/~cs61a/fa13/slides/10-Data_6pp.pdf

Latest revision as of 08:19, 10 July 2014

Data abstraction is the invention of new data types. It separates functionality from representation—we don't need to know how data is represented internally; we just need to know how to interact with it.

Data abstraction is supported by defining an abstract data type (ADT), which is a collection of constructors and selectors. Constructors create an object, bundling together different pieces of information, while selectors extract individual pieces of information from the object.

Functional ADTs

ADTs can be implemented by functions. Functional ADTs are usually immutable; that is, their fields cannot be modified.

Examples

An ADT for linked lists:

empty = lambda: 42
 
def link(element, list=empty):
    return (element, list)
 
def first(list):
    return list[0]
 
def rest(list):
    return list[1]

An ADT for points:

# constructor
def make_point(x, y):
    return x, y
 
# selector
def x_coord(point):
    return point[0]
 
# selector
def y_coord(point):
    return point[1]
and a function that uses it:
def slope(point1, point2):
    """Return the slope of the line that connects POINT1 and POINT2."""
    return (y_coord(point1) - y_coord(point2)) / (x_coord(point1) - x_coord(point2))

An ADT for rational numbers (in dispatch function style) that supports mutation:

# constructor
def rational(x, y):
    """
    >>> rat = rational(1, 3)
    >>> print_rational(rat)
    1 / 3
    >>> set_numer(rat, 2)
    >>> print_rational(rat)
    2 / 3
    """
    def put(field, value):
        nonlocal x, y
        if field == 'numer':
            x = value
        elif field == 'denom':
            y = value
 
    def get(field):
        if field == 'numer':
            return x
        elif field == 'denom':
            return y
    return put, get
 
# selector
def numer(rat):
    return rat[0]('numer')
 
# selector
def denom(rat):
    return rat[1]('denom')
 
# mutator
def set_numer(rat, value):
    rat[0]('numer', value)
 
# mutator
def set_denom(rat, value):
    rat[1]('denom', value)
 
def print_rational(rat):
    print("{0} / {1}".format(numer(rat), denom(rat)))

OOP ADTs

ADTs can also be implemented through object-oriented programming as Python objects. OOP ADTs are mutable and have built-in constructors (__init__) and selectors (dot notation).

Example

An ADT for a linked list:

class LinkedList:
    class EmptyList:
        pass
 
    empty = EmptyList()
 
    # constructor
    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

Data abstraction violation

A data abstraction violation occurs when you assume some representation of the ADT, bypassing the constructors and selectors. For example, we are committing a data abstraction violation when we write the following slope function using the point ADT above:

def slope(point1, point2):
    """Return the slope of the line that connects POINT1 and POINT2."""
    return (point1[1] - point2[1]) / (point1[0] - point2[0])
We assume that the internal representation of a point is a tuple. Instead, we should have used the selectors x_coord and y_coord.

Data abstraction violations limit flexibility because if you want to change the representation of the ADT, you must change all the functions that use the ADT. If you maintain data abstraction, you need only change the constructors and selectors.

Sources