Necessary and Sufficient

Definition
LSP was defined way back in 1988 by Dr. Barbara Liskov, who incidently won the 2009 Turing Award, perhaps the most prestigious award in computer science. Her original definition was:

“If for each object o₁ of type S there is an object o₂ of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o₁ is substituted for o₂ then S is a subtype of T.”

But Robert Martin offered a much more terse definition:

What this is saying is that a derived class should honor the contracts made by it's parent classes. In other words, if a method signature accepts a base class reference, then it should be able to accept an instance of any class derived from that base class without affecting the functioning of the method.

Motivation
Object-oriented programmers will be familiar with the concepts of abstraction and polymorphism. In statically-typed O-O languages, like C++, Java and C#, the key mechanism to achieve polymorphism is inheritance. LSP is a guiding principle that restricts how inheritance is used such that the OCP is not violated.

Technically speaking, the type of polymorphism this principle addresses is inclusion polymorphism. Inclusion polymorphism occurs in languages that allow subtypes and inheritance whereby an instance of a subtype can be manipulated by the same functions that operate on instances of the supertype (parent class type). This implies a reference (or pointer) of the parent class type can also refer to any child object, meaning that the type of the object being referred to must be determined at runtime. Since the type of object cannot be determined until runtime, and virtual methods are defined per type, it implies that a method call may be executed either in the parent or the child class and this dispatch decision cannot be made until runtime.

The Liskov Substitution Principle helps to guarantee inclusion polymorphism, which is a good thing because inclusion polymorphism improves reuse. All code that references the superclass can be reused referencing a subclass.

Why Follow It?
By adopting the LSP, the correctness of a method accepting base class references is guaranteed under certain substitutability conditions. Furthermore, since LSP is actually a special case of the Open-Closed Principle, every time you violate the LSP, you violate the OCP as a result - but not the other way round. It is this relationship between OCP and LSP that makes it easier to spot since developers tend to understand OCP much more readily that they do with LSP.

Say you develop a class hierarchy using inheritance, and you have a method in your base class that accepts a base class reference, and when you pass in a derived class reference you get unexpected results, it's a strong sign that the inheritance chain and the object model is incorrect. You need to remember that a class must fulfill an "is-a" relationship in order for it to be able to inherit from another class. This relationship is about behavior not data! In this sense, LSP is good at exposing faulty abstractions.

LSP is the reason that it is hard to design and create good deep hierarchies of sub classes and the reason to consider using composition over inheritance. (The strategy pattern is a prototypical example of the flexibility of composition over inheritance.)

The whole point of the Liskov Substitution Principle is really to make you think clearly about the expected behavior and expectations of a class before you derive new classes from it.

Obligatory Example
Common examples for violation of LSP are Rectangle::Square, Circle::Ellipse, etc. Rather than reproduce those here, take a look at the examples in Robert Martin's paper.

Design By Contract
The Liskov Substitution Principle is closely related to the design by contract methodology, which provides rules telling us the conditions under which it is acceptable to substitute a derived class for a base class:

• Preconditions cannot be strengthened in a subclass.
• Postconditions cannot be weakened in a subclass.

In other words, a sub-type can only have weaker pre-conditions and stronger post-conditions than its base class. Put differently...derived methods should expect no more and provide no less.

Violations
Signs of LSP violations include:

• A subclass that does not keep all the external observable behavior of it's parent class
• A subclass modifies, rather than extends, the external observable behavior of it's parent class.
• A subclass that throws exceptions in an effort to hide certain behavior defined in it's parent class
• A subclass that overrides a virtual method defined in it's parent class using an empty implementation in order to hide certain behavior defined in it's parent class

Method overriding in derived classes is probably the biggest cause of LSP violations. All method overrides should be done with great impunity as to avoid these violations.

In addition, the principle implies that no new exceptions should be thrown by methods of the subclass, except where those exceptions are themselves subtypes of exceptions thrown by the methods of the superclass. (think: co-variance and contra-variance).

A function using a class hierarchy violating the principle uses a reference to a base class, yet must have knowledge of the subclasses. Such a function violates the open/closed principle because it must be modified whenever a new derivative of the base class is created, and that really sucks because the compiler or your existing unit tests won't find these cases for you - you have to become a UN weapons inspector, remember what things exactly you need to look for, and go hunt them down manually!

Final Advice
In the words of Robert Martin, Agile Principles, Patterns and Practices in C# (P.149):

"A good engineer learns when compromise is more profitable than perfection. However, conformance to LSP should not be surrendered lightly. The guarantee that a subclass will always work where its base classes are used is a powerful way to manage complexity. Once it is forsaken, we must consider each subclass individually."

Other Parts in the Series
Design Guidelines Part.1: Single Responsibility
Design Guidelines Part.2: Open-Closed Principle
References
Robert Martin's Original Paper

Google Code Jam is an annual competition held by the search giant that allows programmers to try their hand at solving increasingly complex problems using the language of their choice. I managed to register for the competition in time but alas, due to various commitments, wasn't able to make it to the actual competition. Damn!!!

Rather than sit on the sidelines waiting for next year to roll around I decided to take a stab at a number of these problems and found them interesting, challenging and a whole bunch of fun. I like the fact that Google lets you work through the problems even if you are officially excluded from the competition. What follows is my attempt at these mind benders starting with the practice problems...

The alien numbers problem asks that you translate from one arbitrary alien numeral system to another alien numeral system...

The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.

You can read complete details about the it here: Alien Numbers Problem

My Approach

Firstly you need to understand a few key facts:

1. a number system represented by X distinct characters is a base X number system
2. any "number", Z, in abitrary base X can be converted to a "number" in base Y using the polynomial form:

   z = c_n.Yⁿ + c_(n-1).Y^(n-1) + c_(n-2).Y^(n-2) + ... + c₂.Y² + c₁.Y¹ + c₀.Y⁰

   where c_i is a co-efficient digit taken from the target base system.

Fact (1) above means that we can easily ascertain the source and target base sizes from the input given to us as the problem description clearly indicates that "no digit will be repeated in any representation, and all digits in the alien number will be present in the source language". Those 2 conditions are the necessary and sufficient conditions to ascertain the base sizes. Furthermore, we know that the digits are always given to us in ascending order so we know everything we need to about the base systems. The problem is therefore reduced to a simple base conversion problem which is where Fact (2) comes into play.

Fact (2) tells us we need to think in multiples of Yⁿ when expressing numbers in the new base, Y. For example, if we want to convert the number 79 from base10 to, say base3 represented by the digits {0,1,2}, we need to identify the co-efficients, c_i ∈ {0,1,2}, that can be mutliplied against the powers of 3 (3⁰, 3¹, 3², 3³, ...) and added to give us 79. In fact 79 = 2 x 3³ + 2 x 3² + 2 x 3¹ + 1 x 3⁰ , so 79 would be written as 2221 in a base 3 number system using the characters "0","1" and "2". If that base system used the characters "o", "F" and "8" and that represented their ascending order then 79 would be written as 888F.

With respect to the polynomial expression given above you may be asking what the value of n will be. i.e. what the highest-order of Y is needed. This is needed to determine the value of the most significant bit and you can use the formula below to do so:

n=⌊log_Y(x)⌋

Essentually you take the floor of the base-Y logarithm of the input number, x.

My Code (in C#)


The Code Jam competition places an emphasis on getting the correct result within a time constraint for problems of a certain magnitude. As such you needn't bother with input validation - the input data is always going to be well formatted so the code below has no error handling or input validation around this.


You could also further optimise the code to make use of memoization and perhaps make the function better handle really, really large numbers by using a lowest-highest order bit approach rather than starting with the calculation of the most-significant bit and working down as I have done. But I'll leave that as an excerise for the reader.

using System;
using System.IO;

namespace GoogleCodeJam.AlienNumbers
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader(@"c\:input.txt");
            StreamWriter outfile = new System.IO.StreamWriter(@"c:\output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                string alienNoFromSrc = data[0];
                string srcLang = data[1];
                string tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                string alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, alienNoFromTgt));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }

        static string Convert(string number, string baseFrom, string baseTo)
        {
            double input=0;
            double srcBase = baseFrom.Trim().Length;
            double tgtBase = baseTo.Trim().Length;
            string result = "";

            // convert the input "number" to a numeric value first
            for (int i = 0; i< number.Length; i++)
            {
                input = input + (baseFrom.IndexOf(number[i]) * Math.Pow(srcBase, number.Length - 1 - i));
            }

            double index = Math.Floor(Math.Log(input, tgtBase)); // the leftmost index
            while (index >= 0)
            {
                int digit = (int)(Math.Floor(input / Math.Pow(tgtBase, index)));
                result = result + baseTo[digit].ToString();
                input = input - (digit * Math.Pow(tgtBase, index));
                index--;
            }
            return result;
        }
    }
}

And my Java code to do the same:

import java.io.*;

class Main implements Runnable {

    public static void main(String[] args) {
        new Thread(new Main()).start();
    }

    @Override
    public void run() {
        try
        {
            BufferedReader infile = new BufferedReader(new FileReader("/usr/local/data/workspace/AlienNumbers/A-large-practice.in"));
            BufferedWriter outfile = new BufferedWriter(new FileWriter("/usr/local/data/workspace/AlienNumbers/output.txt"));

            int testCases = Integer.parseInt(infile.readLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read the input data
                String[] data = (infile.readLine()).split(" ");
                String alienNoFromSrc = data[0];
                String srcLang = data[1];
                String tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                String alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

                // write out the results
                outfile.write(String.format("Case #%s: %s\n", caseNo, alienNoFromTgt));
            }
            infile.close();
            outfile.close(); // flush and close
        }
        catch(Exception e) {
            e.printStackTrace();
        }
    }

    public static String Convert(String number, String baseFrom, String baseTo)
    {
        double input=0;
        double srcBase = baseFrom.trim().length();
        double tgtBase = baseTo.trim().length();
        String result = "";

        // convert the input "number" to a numeric value first
        for (int i = 0; i< number.length(); i++)
            input += baseFrom.indexOf(number.charAt(i)) * Math.pow(srcBase, number.length() - 1 - i);

        // Java doesn't let us specify the required base so we use the change-of-base theorem
        double index = Math.floor( Math.log(input) / Math.log(tgtBase)); // the leftmost index
        while (index >= 0)
        {
            int digit = (int)(Math.floor(input / Math.pow(tgtBase, index)));
            result += baseTo.charAt(digit);
            input -= digit * Math.pow(tgtBase, index);
            index--;
        }
        return result;
    }

}

C# provides the bitwise shift operators << and >>. These are extremely useful operators to do fast, parallel operations on bit maps and flag enumerations. But there are several subtleties that you should be aware of:

• This operator is defined for int/uint/long/ulong data types, however because of numeric promotion it can also be used on short/ushort/byte/sbyte. The 2 operands are in fact promoted separately and the result type is the promotion type of the first operand. The following code snippet demonstrates a common issues that leaves developers scratching their head. The cause is implicit number promotion from byte to int and a type mismatch on the assignment operation after shifting.  

              byte b = 3;
              byte c = b << 2; // this produces a "Cannot convert int to byte" compiler error 
              byte d = (byte)(b << 2);    // this is OK 

• The operator uses infix notation where the left hand operand is the number being shifted, and the right hand operand is the number of bits to shift. Be aware that the right hand side operand is masked so only the rightmost 5 bits are used for int/uint LHS values, and the rightmost 6 bits are used for longs/ulongs. This effectively means that the RHS operand is evaluated modulo 32 or 64 dependent on the type of the RHS. In the example below all RHS operands are treated as zero!
    

              Console.WriteLine(UInt32.MaxValue << 32);       // gives UInt32.MaxValue
              Console.WriteLine(UInt32.MaxValue << 64);       // gives UInt32.MaxValue
              Console.WriteLine(UInt32.MaxValue << 128);      // gives UInt32.MaxValue
              Console.WriteLine(UInt32.MaxValue << 0);        // gives UInt32.MaxValue

• Curiously, the RHS operand must be an int. It cannot be a uint/long/ulong despite the fact that the above mentioned 5/6 bit masking would make this trivial to implement.
• There is no circular shift operator (sometimes called bitwise rotation) in C#. You have to write it yourself. Here's what it would look like:
    

          public static uint CircularShiftLeft(uint value, int shiftCount)
          {
              shiftCount &= 31;
              return ( (value << shiftCount) | (value >> (32-shiftCount)));
          }
  
          public static uint CircularShiftRight(uint value, int shiftCount)
          {
              shiftCount &= 31;
              return ((value >> shiftCount) | (value << (32 - shiftCount)));
          }

• C# does not use a different operator to differentiate between logical shifting and arithmetic shifting for right shifts. Java and JavaScript use ">>" for arithmetic right shift and ">>>" for logical right shift. (No such differentiation is needed for left shifts since arithmetic left and logical left shifts produce identical results.) According to this article by Microsoft, the ">>>" operator is the only Java operator not supported by C#, because - according to Microsoft - there is no need for such an operator in a language which supports both signed and unsigned integers, which C# does. In C and C++, the unsigned modifier can be added to a integer variable declaration. It tells the compiler to treat the value of the variable as an unsigned value in arithmetic operations. In Java, there is no "unsigned" keyword and, with the exception of char, all integer primitive data types are signed. It is because of this that theJava language needs both the ">>" and ">>>" operators, as the developer has no other way of telling the compiler that s/he wants to work with logical or arithmetic shifts.
• Since C# doesn't use a different symbol to differentiate right shift behaviour, the internal implementation of right shifting (>>) is dependent on the data type of the LHS operand. If it is a signed number then arithmetic shifting is used. If it is unsigned then logical shifting is used. To see this, consider the following code. Since the LHS operand is a signed integer an arithmetic shift is done and therefore the sign bit is preserved and the result is a negative number. Had it been a logical shift the MSB would have been a zero which would indicate a positive number
   

              Console.WriteLine(Int32.MinValue);          // gives -2147483648
              Console.WriteLine(Int32.MinValue >> 1);     // gives -1073741824 

• Signed numbers are represented internally using two's complement form in C# so if you use a negative number for the RHS operand, it will have the lower 5 or 6 bits masked off (depending on whether the LHS operand is a 32 or 64 bit integer) from the two's complement representation of the number which produces some rather unexpected results.
   

              Console.WriteLine(Int32.MinValue >> -1);    // gives -1
              Console.WriteLine(Int32.MaxValue << 1);     // gives -2

• Lastly, left shift operations never cause overflows which is kinda nice!

All in all, the shift operators in C# are very useful to the resourceful programmer, and not to dissimilar to how shift operators work in other languages such as C++ and Java, but you just need to be aware of these subtleties.

http://msdn.microsoft.com/en-us/library/aa691377(VS.71).aspx

http://msdn.microsoft.com/en-us/library/xt18et0d.aspx