Code Analysis: Abstract Data Type

Abstract data types are a pretty well known concept in computer science and software engineering.  The concept is pretty simple.  If you have something that is complicated, then you can make it easier to deal with by only exposing an API that allows you to safely interact with the complicated component.  Of course also known to computer science and software engineering are abstract data types that make your life miserable because of how bad they have been constructed.  So let’s talk about this.

You can use the problem analysis techniques from the first part of this blog series in order to analyze whether or not your abstract data type is easy or hard to deal with.  But for now we just want to generalize abstract data types into three different categories.

 

Strong Abstract Data Types

Consider the following:

private float _index
private int[] _array;

public void IndexMod( float x )
{
    _index = floor(x / 2);
}

public int Access()
{
    return _array[_index];
}

The API for this abstract data type will always allow you to call any legal function and will result in a valid path of execution.  This is very useful because it means that the complicated component you do not want to deal with can safely be ignored.  This allows you to break up and compartmentalize the problems you are trying to solve with your software solution.

 

Weak Abstract Data Types

Consider the following:

private float _index
private int[] _array;

public void IndexMod( float x )
{
    _index = x / 2;
}

public void IndexSecure()
{
    _index = floor( _index );
}

public int Access()
{
    return _array[_index];
}

The API for this abstract data type exposes functions that work, but sometimes using certain functions in certain orders will result in an invalid path of execution.  The program will crash or you will get an invalid result.  Sometimes this is just the world we live in.  Whatever you are trying to abstract is simply too complex or there isn’t enough time to properly analyze the component to build a strong abstract data type around it.  The important part is that there is some sequence of function calls that you can do in order to accomplish your goal with a valid path of execution.  You still have to think about and understand the problem inside of the abstract data type, but at least a lot of the tedious and/or heavy lifting is already complete.

 

Broken Abstract Data Types

Consider the following:

private float _index
private int[] _array;

public void IndexMod( float x )
{
    if ( _index - floor( _index ) == 0 )
    {
        _index = x / 2;
    }
}

public int Access()
{
    return _array[_index];
}

The API for this abstract data type exposes functions that work, but sometimes certain functions in certain orders will result in an invalid path of execution that you cannot recover from.  There is no combination or sequence of API function calls that you can perform to recover from your broken state.  The abstract data type instance must be thrown away because actions you want to take cannot be taken without resulting in a program crash or invalid results.  This is the most difficult type of abstract data type to work with because in addition to understanding the internal complicated component of the abstract data type you also need to augment it with additional logic and state in order to determine if your instance has entered into an invalid state.

 

Okay, now that we’ve looked at abstract data types we can move on to global state.