Saturday, December 7, 2013

Liskov Substitution Principle

This principle states:

References to the Base class must be completely substitutable by references of any of the Derived classes.

This principle was formulated by Barbara Liskov. In her own words :

"What is wanted here is something like the following substitution property: If for each object O1 of type S there is an object O2 of type T such that for all programs P deļ¬ned in terms of T, the behavior of P is unchanged when O1 is substituted for O2 then S is a subtype of T"

Once a design structure conforms to Open Closed Principle, the obvious question arises, as to what are the rules of Sub classing ? The open closed principle which states that A class is closed for modifications but open for extension. So are there any general rules to be taken care of while sub classing, violation of those would also mean violation of the open closed principle for the derived sub class ?

See Open closed Principle

SubTyping

In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphismin which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype. If S is a subtype of T, the subtyping relation is often written S <: T, to mean that any term of type S can be safely used in a context where a term of type T is expected. The precise semantics of subtyping crucially depends on the particulars of what "safely used in a context where" means in a given programming language

See wiki link to subtyping

What does a program achieve on its conformation to LSP

Violation of this principle also gives rise to violation of the Open closed principle.If there is a method that do not conform to Liskov's substitution principle ( LSP ) then that method contain references to the supertype but depend on the knowledge of the subtypes. This means that when a new subtype is added to the system, then this method must be modified to incorporate the knowledge of this newly created subtype. Modification of the Base class when a new subtype is added to the system is a clear violation of Open Closed Principle.This necessitates formulation or rules that must be taken care of while subtyping a given supertype.

Any attempt to subclass a given Base class must take care that the Derived classes do not beak any 'behaviour' of the Base class. Such an unintentational discrepancy of behaviour may occur when the Derived class does some value additions to the Base class.

Behaviour of Base class is defined by its Invariants, Preconditions and Postconditions. This behaviour must not break when a Derived class extends the Base class.

How to find if a given Object Structure Violates LSP


For class heirarchies to conform to LSP, below conditions must be satisfied
  1. The Invariants of the Super Types MUST NOT be violated or broken by the SubType. ( Illustrated by Example # 1 )
  2. PreConditions on an overridden method for the SubType must be a 'SUBSET' of the precondition on the same method for the SuperType. In other words, Preconditions must not be strengthened by the SubType. ( Illustrated by Example # 2 )
  3. PostConditions on an overridden method for the SubType must be a 'SUPERSET' of the preconditions on the same method for the SuperType. In other words,  PreConditions must not be weakened by the SubType.( Illustrated by Example # 3 )

Code Examples

Example # 1

This examples consist of a system of Rectangles and Squares. This example illustrates violation of LSP as the Invariants of the Super class are violated by the Subclass

Rectangle - This class has two member variables, width and height. Area is calculated as width * height.

Invariant imposed by Rectangle class
  • Both the width and the height can vary independently
Square - This class extends Rectangle. Since a Square has shares a lot of geometrical similarities with the Rectangle, it is quite tempting to assume that a Square ISA type of rectangle.

Invariant imposed by Square class
  • As for a square, width = height , always, so this class allows both width and height to change simultaneously. This violates LSP as it breaks the invariant condition of the Rectangle class

/**
* Here width and Height can vary independently
*/
public class Rectangle {

 protected int width;
 protected int height;

 public int getWidth() {
  return width;
 }

 public void setWidth(int width) {
  this.width = width;
 }

 public int getHeight() {
  return height;
 }

 public void setHeight(int height) {
  this.height = height;
 }
 
 public long getArea() {
  return getWidth() * getHeight();
 }

}

/** Here widh and height vary simultaneously. 
* Attempt to change the width also changes the height, and vice versa.
*/
class Square extends Rectangle {
 
 public void setWidth( int width ) {
  super.setWidth(width);
  super.setHeight(width);
 }
 
 public void setHeight( int height ) {
  super.setHeight(height);
  super.setWidth(height);
 }
}
class LspTest
{
 private static Rectangle getRectangle( String s )
 {
  if ( "rectangle".equals( s ))
   return new Rectangle();
  
  if ( "square".equals(s ))
   return new Square();
  return null;
 }

 public static void main (String args[])
 {
  Rectangle r = getRectangle( "rectangle" );
               r.setWidth(5);
  r.setHeight(10);
  long areaRectangle = r.getArea();
  
  System.out.println( areaRectangle ); // prints 50
  assert( areaRectangle == (long) 50 ); // PASSES !
  
  // Below case will fail
  // Indicates Violation of LSP
  Rectangle s = getRectangle( "square");
                s.setWidth(5);
  s.setHeight(10);
  long areaSquare = r.getArea();
  System.out.println( areaSquare ); // prints 100 !!
  assert( areaSquare == (long) 50 ); // FAILS !
  
 }
}

Example # 2

This examples represents a system of Pencil and Pens. Here Both Pencil and Pen are Concrete implementations of  the abstract class Writer. 
Both Pencil and Pen classes share a common abstraction of writing. Pencil extends this abstract class Writer and overrides its behaviour for writing.

Pen class also shares this abstract behaviour of writing, so Pen class Extends Pencil and overrides its write() method.

So far so OK.

Lets see the preconditions on the write() method for each of the Pencil and Pen classes.

Pencil - There are NO Preconditions on write() method for this class. Pencil class always writes to the console for every call to the write() method.
Also there are no Postconditions on method write() for Pencil class

Pen - This class has certain Preconditions on its write() method. 

Preccondition on write() method for the Pen class
Behaviour of Pen is such that a Pen shall write only when it's Ink Level is above a threshold. The Pen class is instantiated with a certain amount of Ink Fill. For the sake of programmatic simplicity, I have assigned the Ink threshold to half the value of the Initial Ink Fill. Everytime the Pen writes ( via call to write() method ),  the amount of Ink fill decreases by Unit One.

If the amount of Ink fill is less than the Threshold value, the Pen refuses to write() and throws a RuntimeException( " Cannot write. Do  a Refill " );

This Precondition strengthens the Precondition of the sueprclass Pencil and thus Violates LSP


/**
* Abstraction for write behaviour
*/
public abstract class Writer {

public abstract write();

}
/**
* Pencil class always writes to the console
*/
public class Pencil extends Writer {
 
 public void write( String toWrite ) {
  System.out.println( toWrite );
 }
}
/**
* Pen class extends Pencil and overrides the write() method with PreConditions
*/
class Pen extends Pencil {
 
 private int THRESHOLD_AMOUNT;
 
 private int fillAmount;
 
 public Pen( int fillAmount ) {
  super();
  this.fillAmount = fillAmount;
  THRESHOLD_AMOUNT = fillAmount / 2;
 }

/*
* VIOLATES Liskov's Substitution Principle !
*/
 public void write( String toWrite ) {
  if ( !isFilled() )
   throw new RuntimeException("Pen not Filled. Please Refill");
  
  write0(toWrite);
  decreaseFillAmount();   
 }
 
 public void reFill() {
  fillAmount = THRESHOLD_AMOUNT * 2;
 }
 
 private boolean isFilled() {
  return fillAmount > THRESHOLD_AMOUNT;
 }
 
 private void write0( String toWrite ) {
  System.out.println(toWrite);
 }
 
 private void decreaseFillAmount() {
  --fillAmount;
 } 
}
/**
* This class tests the LSP behaviour.
*/
public class TestLSP {
public static void main( String[] args ) {
  Pencil pencil = new Pencil();
  Pencil pen = new Pen( 4 );
  
/*
* Pencil writes to the console for all the 4 iterations of Loop
*/
  for ( int i = 0 ; i< 4; i++ ) {
   pencil.write("do write");
  }
  
/*
* Pen class writes only 2 times, after which its Ink amount falls below threshold and it throws a Exception
* This is a VIOLATION of LSP, because if the Pen class is substituted for Pencil then the program will
* behave erratically with Exceptions whenever the precondition fails
*/
  for ( int i = 0 ; i< 4; i++ ) {
   pen.write("do write"); // throws exception after 2 iterations
  }

  }
}

Example # 3

This example represents a system to track and monitor the attendance records of the office comers.( Attendees )

Attendee  - This class represents an Attendee. Any human being qualifies to be an Attendee
Attendance - Abstract class to define the abstract behaviour of Attendance when an Attendee visits the Office. This is abstracted by the method comesToOffice( Attendee officeComer )

OfficeAttendance - This  class extends Attendance class and overrides comesToOffice() behaviour.
This class imposes certain Postconditions on this behaviour.

Postconditions on comesToOffice() Method for OfficeAttendance class :
  • All Office attendees must be registered in the Attendance register. So every office comer must necessarily be marked as 'attended'.
OfficeWatcher - This class extends OfficeAttendance class and overrides comesToOffice() behaviour.  This class has an additional behaviour 'securityCheck()' for every attendee coming to office, which is perfectly fine as this is what an Office Watcher should do ! But, Apart from this additional behaviour of security check, this class also weakens the PostConditions of the OfficeAttendance superclass.

PostConditions on comesToOffice() Method for OfficeWatcher class :

  • Not all Office attendees are registered in the Attendance register. Only the Attendees who are Employees of the given office are marked as 'attended'. This PostConditions , thus, weakens the PostCondition on the comeToOffice() method of the superclass ( OfficeAttendace ). This class Violates LSP

public abstract class Attendance {
 
 public abstract void comesToOffice( Attendee officeComer );
}
public class Attendee {
 
 /*
  * Encapsulates behaviour for an Office Attendee. Any human being can be a Office Attendee
  */
}
public class OfficeAttendance extends Attendance {
 
 private Attendance register;
 
 public void comesToFiice( Attendee officeComer ) {
  
  sayHelloToOfficeComer( officeComer );
  
  markAttendance( officeComer );
 }
 
 protected void markAttendance( Attendee officeComer ) {
  
 /*
  * store the office coomer's name along with the time of entry ( current system time )
  */
  save( officeComer, System.currentTimeMillis() );
  
 }
 
 protected void sayHelloToOfficeComer( Attendee officeComer ) {
  officeComer.greet( " Hello. Welcome to my Office" );
 }
 
}
/**
* This class VIOLATES LSP as comesToOffice() method of this class 
* weakens the PostConditions of Base class ( OfficeAttendance )
*/
public class OfficeWatcher extends OfficeAttendance {
 
 /**
  * This method violates LSP as it does not satisfy the Post Conditions of the Base class
  */
 public void comesToOffice( Attendee officeComer ) {
  
  sayHelloToOfficeComer(officeComer);
  
  /*
   * Base class's Post Condition that every office attendee must definitely be marked in the attendance register
   * is not fulfilled here because of the conditional check. 
   * This violates LSP.
   */
  if ( officeComer.isThisOfficeEmployee( officeComer ) ) {
   markAttendance(officeComer);
  }
  
  doSecurityChecks( officeComer );
  
 }
 
 private doSecurityChecks( Attendee officeComer ) {
  /*
   * does some security checks
   */
 }
}

How to avoid Violation of LSP

Any attempt to subclass a given base class must take care that the derived class do not beak any behaviour of the Base class. Such an unintentational discrepancy of behaviour may occur when the Derived class does some value additions to the Base class.

How can we ensure that such a discrepancy does not occcur, which effectively means to find the objective ways exhibiting the occurrence of such a discepancy.

As already discussed, below conditions must always be satisfied to conform to LSP

Conditions to LSP conformation

  1. The Invariants of the Super Types MUST NOT be violated or broken by the SubType. ( Illustrated by Example # 1)
  2. PreConditions on an overridden method for the SubType must be a 'SUBSET' of the precondition on the same method for the SuperType. In other words, Preconditions must not be strengthened by the SubType. ( Illustrated by Example # 2 )
  3. PostConditions on an overridden method for the SubType must be a 'SUPERSET' of the postconditions on the same method for the SuperType. In other words, PostConditions must not be weakened by the SubType. ( Illustrated by Exampe # 3 )

Design by Contract

Design by contract is a software design approach that prescribes that a software design should follow a formal, precise and verifiable interface specifications for software components with preconditions, postconditions and invariants.

See wiki link to Design by Contract



S          O          L             I           D


No comments:

Post a Comment