Pages

Google+

Monday, January 18, 2010

Liskov's Behavioral Sub-Typing In Action... or How To Misuse Inheritance

 

Time To Eat My Own Dog Food


A few days ago, I posted an implementation of a Semaphore with AS3. Ever since then, something about the code just didn't sit right with me. I've wanted to research and write about the Liskov substitution principle (LSP) for a while now, and I decided that I would demonstrate it with my Semaphore classes and examples. When I first designed the classes, I thought I was doing a good job, now....not so much. In fact, I think I made errors in my application architecture and overall approach.


Before getting into my Semaphore fail,  a little bit about LSP. There are

LSP is a test for a designer to see if inheritance is being used properly.  It also closely resembles design by contract's concept that an overridden method's precondition must be the same or less than it's superclass. An algorithm's postcondition is less vital, as long as we're not breaking encapsulation of course. It was the design by contract's precondition concept that helped me diagnose my mistake.

I think of LSP like this:

Imagine you're transplanted into the future, and people get around by using vehicles called 'flying cars'. You want to use one, so you jump into one of these flying cars and all the familiar controls you expect for a car are in there. It's got a few more extra buttons, but you can tell that they are used just for flying. To test it out, you'd like to just simply move it a little further down the street ahead. You turn it on, put it in gear, push the gas pedal... and nothing happens. You ask your friend, who owns the car what's up, and he says: 'Oh you need to engage the levitation drive and take off the ground first, then you can drive forward.'

Is this 'flying car' really a flying 'car', or is it a different type of vehicle? According to LSP, this is not a type of 'car', it's a different type of vehicle. When a base type is used, it should be able to be swapped out with any of it's derived types. You should be able to use a 'flying car' just as you would a normal 'car', the difference being that if you choose to fly, you can (think about the Delorean from Back To The Future II).  A good example of this within AS3 is the display object hierarchy chain. Suppose you want to create an EventDispatcher object and use it only in that manner. If you were to type the object to MovieClip instead, but still only used it as an EventDispatcher, you would be fine.

Where I Went Wrong - Precondition Fail


I decided to have Standard_Semaphore extend Simple_Semaphore because I liked how the Simple_Semaphore was already keeping track of the current lock count and handeld when to execute the callback when all locks are released.


I overrided the two methods as seen below:
// Simple_Semaphore.as
public function aquire_lock() : Boolean
{
lock_count++;
locks_initiated = true;
return true;
}

public function release_lock() : void
{
lock_count--;
if(lock_count

Within my Standard_Semaphore's acquire_lock method I am only calling the super's method after a check for num_of_permits_available is made. If I were to swap Simple_Semaphore with Standard_Semaphore, acquire_lock would never return true, because the implementation of Simple_Semaphore does not deal with permits. This is exactly what is meant when dealing with subclass preconditions. There are more preconditions in my sub-class than there are in the super.

Semaphore Fail * 2 - Law Of Demeter & DIP


To fix this, I decided to make a complete break between Simple_Semaphore and Standard_Semaphore. I removed the inheritance from both the class: Standard_Semaphore extends Simple_Semaphore and the interface: Permit_Semaphore extends Semaphore. When I changed the class inheritance, everything was fine, but when changed the interface inheritance I broke something in my code. It was here, in my Sync_Animated_Object interface. The last argument in this method requires an object of type Semaphore:
public interface Sync_Animated_Object extends Display_Object, Disposable_Object
{
function start_animation(end_pos:Point, animation_length:Number,animation_sync:Semaphore) : Boolean;
}

My Ball class, which implements the Sync_Animated_Object interface, was expecting an object implementing the Semaphore interface. It relied on the Semaphore's two methods:
package semaphore
{
import functionality.Disposable;

public interface Semaphore extends Disposable
{
function set_lock() : void;

function release_lock() : void;
}
}

I did this because I wanted my Sync_Animated_Object, to expect to be given an already validated Semaphore to lock and unlock. This was how I was able to use my Ball object, which implements Sync_Animated_Object, to be used with all my demo classes. At first this seemed like a good idea, but as I thought about it, it wasn't. My Sync_Animated_Object, should not really know about how the Synchronization is being implemented. If I were to replace the Sync_Animated_Object's start_animation signature to omit the Semaphore and accept an animation_complete:Function instead, I'd have more flexibility.
public interface Animated_Object extends Display_Object, Disposable_Object
{
function start_animation(end_pos:Point, animation_length:Number,animation_complete_callback:Function : Boolean;
}

This goes along with the Dependency Inversion Principle as well because now my higher module Sync_Semaphore_Demo which uses a Sync_Animated_Object is not dependent on it to unlock the Semaphore. The Semaphore and it's lock counting are all done on the same level; I think this makes the code more flexible and easier to read as well. Another failure I had in my implementation was having an accessor to the Permit_Semaphore's permits:
public interface Permit_Semaphore extends Semaphore
{
function get num_of_permits_available() : uint;
// other methods....
}

I don't think data should be exposed in this manner ( Law of Demeter) - so I changed the method to:
public interface Permit_Semaphore extends Semaphore
{
function get permit_is_available() : Boolean;
// other methods....
}

That in turn will change this evaluation within my implementation:
// old
if(ball_animation_sync.num_of_permits_available != 0)
{
// lock semaphore
}
// new
if(ball_animation_sync.permit_is_available)
{
// lock semaphore
}

This looks cleaner and is easier to read. Plus, it allows me to play with the permit_is_available further down the line - if needs be.

Below is the revised Permit_Semaphore interface and the class that implements it, Standard_Semaphore. I have also included the old versions to compare to.
// old Permit_Semaphore.as
package semaphore
{
public interface Permit_Semaphore extends Semaphore
{
function get num_of_permits_available() : uint;

function set permit_available_callback(callback:Function):void;

function drain_all_permits() : void;

function reduce_permits(num_permits_to_remove:uint) : void;

function increment_permits(num_permits_to_add:uint) : void;
}
}

// new Permit_Semaphore.as
package semaphore
{
import functionality.Disposable;

public interface Permit_Semaphore extends Semaphore
{
function get permit_is_available() : Boolean;
}
}

// old Standard_Semaphore.as
package semaphore
{
public class Standard_Semaphore extends Simple_Semaphore implements Permit_Semaphore
{
private var max_permits : uint;
private var num_permits_given_out : uint;
private var notify_permit_available : Function;

public function Standard_Semaphore(unlocked_callback : Function, max_permits : uint, permit_available_callback:Function = null)
{
super(unlocked_callback);
this.max_permits = max_permits;
this.notify_permit_available = permit_available_callback;
}

override public function aquire_lock() : Boolean
{
if(this.num_of_permits_available != 0)
{
super.aquire_lock();
num_permits_given_out++;
return true;
}
else
{
return false;
}
}

override public function release_lock() : void
{
super.release_lock();
num_permits_given_out--;

if(notify_permit_available != null)
{
notify_permit_available();
}
}

override public function dispose_for_garbage_collection() : void
{
super.dispose_for_garbage_collection();
max_permits = NaN;
num_permits_given_out = NaN;
notify_permit_available = null;
}

public function get num_of_permits_available() : uint
{
return max_permits - num_permits_given_out;
}

public function set permit_available_callback(callback : Function) : void
{
this.notify_permit_available = callback;
}

public function drain_all_permits() : void
{
num_permits_given_out = max_permits;
}

public function reduce_permits(num_permits_to_remove : uint) : void
{
max_permits - num_permits_to_remove;
}

public function increment_permits(num_permits_to_add : uint) : void
{
max_permits += num_permits_to_add;
}
}
}
// new Standard_Semaphore.as
package semaphore
{

public class Standard_Semaphore implements Permit_Semaphore
{
private var max_permits : uint;
private var num_permits_given_out : uint;
private var all_locks_open_callback : Function;
private var locks_initiated : Boolean = false;

public function Standard_Semaphore(all_locks_open_callback : Function, max_permits : uint = 0)
{
this.max_permits = max_permits;
this.all_locks_open_callback = all_locks_open_callback;
}

public function get permit_is_available() : Boolean
{
return(max_permits - num_permits_given_out > 0);
}

public function set_lock() : void
{
if(permit_is_available)
{
num_permits_given_out++;
locks_initiated = true;
}
else
{
throw new Error("All Permits Given Out - Check For Permits with 'permit_available'");
}
}

public function release_lock() : void
{
if(locks_initiated)
{
num_permits_given_out--;

if(num_permits_given_out

Another benefit of not using inheritance here means that I have fewer objects to instantiate.

One thing also to note is, my interface Permit_Semaphore still extends Semaphore. This may be the 'wrong' way to think of interfaces, but to me an interface does not dictate implementation. To me it denotes intent. I want any Permit_Semaphore to be used in a similar manner as a Semaphore, but they have their own behavior that must be considered. This is how I think about my Disposable interface, which is my most used interface:
package  functionality
{
public interface Disposable
{
function dispose_for_garbage_collection() : void;
}
}

I have all kinds of objects implement this interface. They range from display objects to business logic. While they may be all wildly different, they all share a similar intent, that at some point I expect it to be disposed of during my application, perhaps even in one loop where each object is simply casted to the Disposable interface. This way I can logically corral my disposable objects into one method titled, 'dispose_unused_objects'.

Download Source Here


All These Fancy Terms Make Me Write Better Software Right?


Admittedly it's easy to go overboard with what is 'correct' and to impress others with fancy lingo. Blindly following anything is never good; however, they are guides and it's important to be pragmatic about it all. While I am aware of these concepts and consider their application when designing, I think I will continue to grow as long as I keep them at an arms length. I see programmers much, much better than myself do this and I think they are right.