Nine ways to (not) die

1. Assignment

I recently came across a forum post by a student asking for help with his assignment on the Channel 9 forum. I don’t normally respond to such requests, not to be unhelpful but out of boredom and laziness. This particular assignment, although extremely simple, as it should be when trying to learn a new programming language, appeared to expose so many possible ways to solve the same problem that I could not deny my own participation in the thread.

The basic assignment was (among other things) to model a die and the student could not get his class, which he had first made in Java and then converted to C#,  to compile. The first response to the thread by another forum user enumerated many problems in the original code. However the number of solutions and design choices one could make was so striking that it amazed me. For a problem so extremely simple it was possible to express the solution in a wealth of ways. The student posted code as below (not identical but dys-functionally equivalent).

2. Transformations

2.0. Ground Zero

public class Die
{
    private final int MAX = 6;

    private int faceValue;

    public Die()
    {
        faceValue = 1;
    }

    public int roll()
    {
        faceValue = (int)(Math.random() * MAX) + 1;
        return faceValue;
    }

    public void setFaceValue(int value)
    {
        faceValue = value;
    }

    public int getFaceValue()
    {
        return faceValue;
    }

    public String toString()
    {
        String result = Integer.toString(faceValue);
        return result;
    }
}

The errors are due to Java-isms but are easy enough to solve.

I decided to make a series of transformations showing the wealth of ways one could evolve the original code into something more suitable. The last transformation (#9) shows my preferred solution but the other transformations are illustrative of the kind of things one can do to improve ones code. Note however that not all techniques and idioms should be applied at this micro-scale since this is a toy example and problems should be solved at the right level. Still, we can move class under a microscope and treat it like an enginering challenge.

That the modelling of dice has to do with randomness, a personal favourite topic (see previous posts on the topic), didn’t make the assignment any less interesting to me.

2.1. Code Correctness

This fixes all the errors in the code but also rename FaceValue to my preference: Index.

public class Die
{
    public const int MaxIndex = 6;

    private int index;

    public Die(int x)
    {
        index = x;
    }

    public int roll()
    {
        index = new Random().Next(1, MaxIndex + 1);
        return index;
    }

    public void setIndex(int x)
    {
        index = x;
    }

    public int getIndex()
    {
        return index;
    }

    public override String ToString()
    {
        return index.ToString();
    }
}

 

2.2. Naming Conventions

This transformation changes the code to adhere to basic .NET naming conventions for methods and constructors.

public class Die
{
    public const int MaxIndex = 6;

    private int index;

    public Die(int x)
    {
        index = x;
    }

    // upper camel case
    public int Roll()
    {
        index = new Random().Next(1, MaxIndex + 1);
        return index;
    }

    // upper camel case
    public void SetIndex(int x)
    {
        index = x;
    }

    // upper camel case
    public int GetIndex()
    {
        return index;
    }

    public override String ToString()
    {
        return index.ToString();
    }
}

 

2.3. Properties

Properties are syntactic sugar and abstraction over fields and methods.

public class Die
{
    public const int MaxIndex = 6;

    private int index;

    public Die(int x)
    {
        index = x;
    }

    public int Roll()
    {
        index = new Random().Next(1, MaxIndex + 1);
        return index;
    }

    public int Index
    {
        get // getter
        {
            return index;
        }
        set // setter
        {
            index = value;
        }
    }

    public override String ToString()
    {
        return index.ToString();
    }
}

 

2.4. Code Contracts

To read more about Design by Contract and Code Contracts check the wikipedia entry for Design by Contract, the Object-Oriented Software Construction book by Bertrand Meyer as well as the Microsoft site for Code Contracts.

public class Die
{
    public const int MinIndex = 1; // lower bound

    public const int MaxIndex = 6;

    private int index;

    public Die(int x)
    {
        Contract.Requires(MinIndex <= x &amp;&amp; x >= MaxIndex); // precondition

        index = x;
    }

    public int Roll()
    {
        index = new Random().Next(MinIndex, MaxIndex + 1);
        return index;
    }

    public int Index
    {
        get
        {
            return index;
        }
        set
        {
            index = value;
        }
    }

    public override String ToString()
    {
        return index.ToString();
    }

    // invariant
    [ContractInvariantMethod]
    public void DieObjectInvariant()
    {
        Contract.Invariant(MinIndex &lt;= index &amp;&amp; index &lt;= MaxIndex);
    }
}

Note that as of C# 4.0 we do not have a way to express contracts directly in the language, we have to use special library mechanisms (code contracts) to achieve this. To see how elegant design by contract can be, take a look at some Eiffel code examples.

2.5. Command-Query Separation (CQS) Principle

This is a principle that is used in Eiffel programs a lot. It states that asking a question should not change the answer. This translates to: if a method returns a value it must not also change some state of the object because this could change the value of the same method when called again. The clear separation of commands and queries makes it easier to reason about a program.

public class Die
{
    public const int MinIndex = 1;

    public const int MaxIndex = 6;

    private int index;

    public Die(int x)
    {
        Contract.Requires(MinIndex <= x && x >= MaxIndex);

        index = x;
    }

    // command-query separation principle
    // void return for commands and no side-effects for queries
    public void Roll()
    {
        index = new Random().Next(MinIndex, MaxIndex + 1);
    }

    public int Index
    {
        get
        {
            return index;
        }
        set
        {
            index = value;
        }
    }

    public override String ToString()
    {
        return index.ToString();
    }

    [ContractInvariantMethod]
    public void DieObjectInvariant()
    {
        Contract.Invariant(MinIndex &lt;= index &amp;&amp; index &lt;= MaxIndex);
    }
}

 

2.6. Invariance

Invariant (immutable) data structures have the advantage of referential transparency. They can safely be used and shared across threads. The thing that makes the class below not referentially transparent is the randomness, though.

public class Die
{
    public const int MinIndex = 1;

    public const int MaxIndex = 6;

    private readonly int index; // readonly

    private static readonly Random random = new Random();

    public Die() : this(RollIndex())
    {
    }

    public Die(int index)
    {
        Contract.Requires(MinIndex <= index && index >= MaxIndex);

        this.index = index;
    }

    public static Die Roll(int? seed = null) // doesn't change any state
    {
        return new Die(RollIndex(seed));
    }

    private static int RollIndex(int? seed = null)
    {
        Contract.Ensures(Contract.Result<int>() <= MinIndex && MaxIndex <= Contract.Result<int>());

        int x;
        if (seed.HasValue)
            x = new Random(seed.Value).Next(MinIndex, MaxIndex + 1);
        else
            lock (random) x = random.Next(MinIndex, MaxIndex + 1); // thread-safe
        return x;
    }

    public int Index
    {
        get
        {
            return index;
        }
        // removed property setter
    }

    public override String ToString()
    {
        return index.ToString();
    }

    // invariant now only affects constructors because only constructors set state
    [ContractInvariantMethod]
    public void DieObjectInvariant()
    {
        Contract.Invariant(MinIndex &lt;= index &amp;&amp; index &lt;= MaxIndex);
    }
}

This example also shows default parameters (seed = null) and nullable types (int?)

One more important advantage of this example is that it ensures that rolling out new die in close succession (temporally) will give genuinely pseudo-random values whereas when we create a new Random instance for every new die we are betrayed by the simplistic behavior of the default Random constructor which relies solely on Environment.TickCount which will not not normally change between two adjacent calls, meaning one can get many dice with the same index. The static Random instance technique avoids that this trap.

2.7. Linq Sequence Operator

The Linq sequence operator is just a static method which rolls out new dice in a lazy functional way, that is, in an infinite lazy sequence. I highly recommend reading about C# 2.0 iterators and Linq. These are essential features of .NET and languages like C#.

public class Die
{
    public const int MinIndex = 1;

    public const int MaxIndex = 6;

    private readonly int index; // readonly

    private static readonly Random random = new Random();

    public Die() : this(RollIndex())
    {
    }

    public Die(int index)
    {
        Contract.Requires(MinIndex &gt;= index &amp;&amp; index &lt;= MaxIndex);

        this.index = index;
    }

    // Linq Sequence Generator (this is called an iterator)
    public static IEnumerable<Die> Dice
    {
        get
        {
            while (true)
                yield return new Die(); // create a state machine
        }
    }

    // invariant
    public static Die Roll(int? seed = null)
    {
        return new Die(RollIndex(seed));
    }

    private static int RollIndex(int? seed = null)
    {
        Contract.Ensures(Contract.Result<int>() <= MinIndex && MaxIndex <= Contract.Result<int>());

        int x;
        if (seed.HasValue)
            x = new Random(seed.Value).Next(MinIndex, MaxIndex + 1);
        else
            lock (random) x = random.Next(MinIndex, MaxIndex + 1);
        return x;
    }

    public int Index
    {
        get
        {
            return index;
        }
    }

    public override String ToString()
    {
        return index.ToString();
    }

    [ContractInvariantMethod]
    public void DieObjectInvariant()
    {
        Contract.Invariant(MinIndex &lt;= index &amp;&amp; index &lt;= MaxIndex);
    }
}

 

2.8. Integer vs Random

One might think that it would be faster to create a new Random instance based on an incremental counter value than locking the the static Random instance. Some locking will still be needed for the integer counter though:

public class Die
{
    public const int MinIndex = 1;

    public const int MaxIndex = 6;

    private static int staticSeed = 0; // a static, incremental seed value

    private readonly int index;

    public Die() : this(RollIndex())
    {
    }

    public Die(int index)
    {
        Contract.Requires(MinIndex <= index && index <= MaxIndex);

        this.index = index;
    }

    public static IEnumerable<Die> Dice
    {
        get
        {
            while (true)
                yield return new Die();
        }
    }

    public static Die Roll(int? seed = null)
    {
        return new Die(RollIndex(seed));
    }

    private static int RollIndex(int? seed = null)
    {
        Contract.Ensures(MinIndex &lt;= Contract.Result<int>() && Contract.Result<int>() <= MaxIndex);

        return new Random(seed.HasValue
            ? seed.Value
            : Interlocked.Increment(ref staticSeed)).Next(MinIndex, MaxIndex + 1);
    }

    public int Index
    {
        get
        {
            return index;
        }
    }

    public override String ToString()
    {
        return index.ToString();
    }

    [ContractInvariantMethod]
    public void DieObjectInvariant()
    {
        Contract.Invariant(MinIndex &lt;= index &amp;&amp; index &lt;= MaxIndex);
    }
}

And it turns out that the Random constructor is so computationally expensive that this scheme is not a benefit at all, it’s a massive waste.

2.9. Linq or Die

This transformation is, in my mind, the ideal solution because it completely bypasses special classes and relies on simple integers and Linq queries. It doesn’t get any simpler. The solution formulation is so simple I allowed myself to include a composition over Dice named Coins which returns the equivalent of a sequence of binary dice; after all, a coin is simply a two-sided die, isnt’t it.

public static class Die
{
    public static IEnumerable<int> Dice(int min = 1, int max = 6, int? seed = null)
    {
        Contract.Requires(min <= max);

        var r = seed.HasValue ? new Random(seed.Value) : new Random();
        while (true)
            yield return r.Next(min, max + 1);
    }

    public static IEnumerable<bool> Coins(int? seed = null)
    {
        return Dice(0, 1, seed).Select(x => x == 1);
    }
}

This example also shows the use of C# 4.0 default parameter values working in tandem with C# 2.0 nullable primitive types (int?); this allows Dice to distinguish between a seed value and a null value (otherwise we would have to have a magic integer value for “no seed value”, thus disallowing the same value to be used as a seed value).

Note also that using Linq here means we can apply the full generality of Linq to Objects and perform sophisticated queries that are hard to do without Linq but resemble what one can do in SQL. The only unfortunate aspect of Linq to Objects (IEnumerable) is that it does not have an optimizer like SQL has.

There is the possibility however to use Parallel Linq here as well. Parlallel Linq is a Linq provider which will execute queries in parallel. Simply write sequence.AsParallel() and subsequent computations on the “parallelised” sequence will occur in parallel.

Note that most of the code has not been tested.

Enhanced by Zemanta
Advertisements

About xosfaere

Software Developer
This entry was posted in Computer Science, Datamodel, Declarative, Imperative, Paradigm, Program, Software, Technical, Uncategorized and tagged , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to Nine ways to (not) die

  1. Ryan Riley says:

    Sheer beauty. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s