onezero

I’ve struggled with how to allow immutable objects in object-oriented languages like C#, Java, and C++, either at the application level or with new language features. Here are a few thoughts.

It’s not so clear that immutable instances should be created in the constructor. For example, if an application has a complicated List<T> instance, how is this going to get created in a List<T> constructor? In general, if you want to build up a value and then declare it immutable, you have to make the constructor accept all possible state. One way, maybe the only way, to do that in a general way is to make a constructor or constructor-like method that accepts another instance of the same type and, from that instance, constructs an immutable instance. It may be that doing this in a thread-safe way requires something like calling Thread.MemoryBarrier() (System.Threading namespace) upon completion of construction. This will incur a significant performance penalty. If this call is made from automatically generated code, then many users will construct immutable objects without knowing about the penalty. Possibly the CLR could do it without the penalty.

Multi-type solutions seem very bad. They cause impedance mismatches – the same thing that happens in C++ when you try to call a non-const-ful method from a const-ful one. In C++ there are essentially two disjoint families or methods: those that have const arguments, and those that don’t. Practically, the two families do not work well with each other, and aesthetically, it’s irritating that there are two families in the first place. If you have one type for mutable instances and another for non-mutable, a smiilar problem arises. Multi-type solutions to immutability are non-polymorphic. For example, with String and StringBuilder, the only way to write a method that accepts an instance that could be either a String or a StringBuilder instance is to make a method that accepts an Object instance. Writing a method or collection of methods to deal with strings involves another two-family problem. You essentially have to decide whether you want to orient the methods towards String, or towards StringBuilder. This is not very pleasant. At least it’s better than having MutableString derive from ImmutableString, or vice versa.

After many design iterations, I’m now wondering if what’s needed is one bit for each object saying whether the instance is immutable. Possibly another bit or so could be used to say whether the instance is ‘read only’ in the sense returned by the List<T>.AsReadOnly method (System.Collections.Generic namespace). I have been using two such bits at the application level in my own library, and the system seems to be manageable.

If you want to allow semantics similar to copy-on-write, you might find the following enumeration helpful.

public enum AccessorIdentity : byte
{
    Us
  , Unknown
  , Nobody
}

Posted on May 7th, 2008 by Andrew
Under C# / Common Language Infrastructure, Programming | No Comments »

The base class library has a significant flaw with respect to System.Random: there is no abstract base class or interface for random number generators with the same interface as System.Random. (The System.Security.Cryptography namespace does have the RandomNumberGenerator base class, but that type’s interface differs from System.Random‘s.)

The situation is as though someone designed a type hierarchy for representing dogs as follows: instead of creating an abstract base class called Dog, they made an instantiable type called OrangeDog and forced everyone to derive from that. This hierarchy is problematic: it corresponds to the statement that all dogs are orange dogs, and it requires that all Dog instances unnecessarily store and possibly initialize data about OrangeDog instances.

If you want to create a new random number generator type that can be passed to existing methods that accept arguments of type Random, you are forced to derive from Random – the orange dog of the random number generator hierarchy. The new type must carry around data about Random instances, even though this data may have nothing to do with the type being defined and may never be used. Another bad consequence of having no base class for random number generators is that it causes people’s thinking about Random to become muddled. For example, people become tempted to create their own base classes or interfaces. Try a web search for C# RandomBase.

It may not be too late for standards parties such as Microsoft, Mono, and ECMA to add a base class or interface for System.Random, and modify System.Random to derive from it. A new base class could look like the following.

public abstract class RandomBase {
  public abstract int Next();
  public abstract int Next(Int32 maxValue);
  public abstract int Next
    (Int32 minValue, Int32 maxValue);
  public abstract void NextBytes(Byte[] buffer);
  public abstract double NextDouble();
}

The RandomBase type captures Random‘s public interface (without constructors).

Existing methods that accept a Random instance would continue to work without modification. They would be unable to accept random number generators that derive from RandomBase and not Random. This might be fine, particularly since RandomBase contains all the public Random methods that manipulate constructed Random instances. As long as code is not using reflection, serialization, or something outside the public interface of Random, that code would continue to work when a straight substitution of Random to RandomBase is applied. The vast majority of RandomBase instances would be System.Random instances – most code would not need modification. Code where it is essential to use different generators, as in simulations, libraries, and statistical tests of random number generators, could use RandomBase.

Incidentally, the argument name maxValue in Next(Int32 maxValue) is confusing and technically incorrect or misleading at best, because Next never returns a value of maxValue (unless maxValue is 0). A better name might be upperBound. I have been using the upperBound mnemonic for years to indicate that the upper end of an interval is not inclusive. While upperBound does not indicate whether the range is inclusive or exclusive, it is at least not wrong, and, if used consistently, does clarify semantics. If and when RandomBase is added to the base class library, that might be a good time to improve the maxValue argument’s name.

Posted on April 30th, 2008 by Andrew
Under C# / Common Language Infrastructure, Programming | No Comments »

In version 3.5 of the NET framework, and possibly in earlier releases, there are variants of Array.Copy that accept 64-bit values for index and length. Unfortunately, Array.Clear has no such variant. This seems to leave only bad options for clearing an array using 64-bit indexes and lengths.

One option is to cast the arguments to Int32 values in each call, like this:

UInt[] a = something;
Int64 index = something;
Int64 length = something;
Array.Cear(a, ((Int32) index), ((Int32) length);

Another option is to make an ad-hoc method and call that instead of Array.Clear, e.g., make a method like the following, and call it instead of Array.Clear:

static void zero(
    UInt64[] a
  , Int64 index
  , Int64 length
)

{
  Array.Clear(
      a
    , checked((Int32) index)
    , checked((Int32) length)
  );
}

Another possibility is as follows.

static void zero(
    UInt64[] a
  , Int64 index
  , Int64 length
)
{
  for (Int64 c = 0; c < length; c++, index++) 
    { a[index] = 0; }
}

None of these options are good. The first two will not work when the index or length will not fit in 32 bits. The latter will work, but does not have whatever built-in speed benefits Array.Clear has, and, creates two ways of zeroing arrays – one with zero, another with Array.Clear. There are other problems with these solutions as well.

It would be better if the framework added a variant of Array.Clear that accepted 64-bit arguments for index and length. Even if, for some temporary period, this variant threw an exception when the value was not a legal 32 bit value, it would still be better in at least some applications to call this method than to resort to one of the above workarounds.

Posted on February 20th, 2008 by Andrew
Under C# / Common Language Infrastructure | No Comments »

What’s the best way in C# to test for a null reference? It turns out that there are a few different ways of doing this correctly, and that they have different speed and code size characteristics.

Consider overloading the == operator for some class Thing. A natural first attempt is as follows.

public static bool operator == (Thing u,Thing v)
{
  return  (u == null)
        ? (v == null)
        : u.Equals(v);
}

This won’t work – it will enter an infinite recursion loop.

This raises the question: is it even possible to perform a non-overloaded equality test for null? One idea is to try using the Object.ReferenceEquals method. This method returns true if u or v refer to the same instance or are both null, and returns false otherwise. Using Object.ReferenceEquals does in fact lead to a correct implementation:

public static bool operator == (Thing u,Thing v)
{
  return   Object.ReferenceEquals(u,null)
         ? Object.ReferenceEquals(v,null)
         : u.Equals(v);

Now let’s look at efficiency – this article’s main point. The above version of operator == that uses Object.ReferenceEquals generates 25 bytes of IL code. (All such statistics in this article are for .NET 2.0.) It also contains a method call for each of the two comparisons against null. It would be nice if the language translation sequence eliminated these calls. As of .NET version 2.0, the pre-JIT compiler doesn’t optimize away these calls. Maybe there is a logical reason why it can’t, or maybe the optimizer just happens not to do this optimization. It’s also conceivable that some version of the JIT compiler can recognize that one of its arguments is the constant null, and convert each call to Object.ReferenceEquals into a small number of assembly language instructions to test for null, without doing a method call.

In any case, there is another correct way that does not rely on any such optimizations happening:

public static bool operator == (Thing u,Thing v)
{
  return   (((Object) u) == null)
         ? (((Object) v) == null)
         : u.Equals(v);
}

The above code is less logically transparent than the version that uses Object.ReferenceEquals. But, this version translates to only 18 bytes of IL. Even if using Object.ReferenceEquals were to result in the same code outputted by the JIT compiler, there are methods where saving 7 bytes of IL code is the difference between having the method inlined and not. (The .NET 2.0 JIT compiler will not inline methods that are larger than 32 bytes.) Furthermore, we can rely on this version to not incur the overhead of method calls to Object.ReferenceEquals. So, when looking for best performance, it is probably better to use (((Object) u) == null) than Object.ReferenceEquals(u,null).

Incidentally, the .NET 2.0 documentation that is installed on my machine does not describe the behavior of the Object type’s == operator. This makes it a little harder than it might otherwise be to verify that one can use this operator to test for reference equality.

A well-behaved compiler will inline small methods such as the above Thing type’s == operator. In theory, after inlining, the compiler could determine that the operand can never be null, and eliminate the test altogether. Best of all, in my opinion, would be if null were not even in the programming language.

Posted on November 22nd, 2007 by Andrew
Under C# / Common Language Infrastructure | No Comments »

Did you ever notice the redundancy that’s forced by C#’s syntax for invoking and defining constructors?

using System.Collections.Generic;

class Thing
{
  Thing(int x, int y)
    { ... }

  public static void Main()
  {
     Thing a = new Thing(3,2);
     Dictionary<string,double> b
       = new Dictionary<string,double>();
  }
}

It might be nice if C# added a less redundant syntax.

using System.Collections.Generic;

class Thing2
{
  new(int x, int y)
    { ... }

  public static void Main()
  {
     Thing2 a = new(3,2);
     Dictionary<string,double> b = new();
  }
}

The short form is clearer and less cluttered. Adding it to C# would not require changes to the runtime. (In fact, the ILdAsm disassembler displays at least constructor references as .ctor. This short form does not include the type’s name.)

The long form would still be necessary when an invoked constructor’s including type differs from the type of the object being assigned, or when no type can be inferred from context:

class BaseClass { ... }
class Derived : BaseClass { ... }

class SideEffectConstructorClass
{
  public new()
    { System.Console.WriteLine("hello"); }

  public static void Main()
  {
    BaseClass p = new Derived();
    new SideEffectConstructorClass();
  }
}

Posted on February 25th, 2007 by Andrew
Under C# / Common Language Infrastructure | 3 Comments »

The essential ideas of using permalinks to avoid link rot have been around much longer than since the term permalink came into common use. The term permalink appears to have originated around the year 2000, and was widely used only after that. Tim Berners-Lee wrote an article about the essential ideas in 1998, and one suspects that he thought about this much earlier.

A long time has gone by since then. This is partly why it drives me crazy when popular software generates web pages that appear to be most naturally referred to with URIs that contain suffixes like .html, .php, and .cgi. I wish that people would stop making their software work this way.

Did you know, though, that sometimes you don’t have to suffer with including suffixes in your own links, even when you want to link to a page has one of these suffixes? With some web server configurations, you can omit the suffix in the URI, and the web server that resolves the target URI will figure it out. For example, Berners-Lee’s article resides at http://www.w3.org/Provider/Style/URI.html but when creating your own link to this page, you can omit the .html suffix, and use the following URI! http://www.w3.org/Provider/Style/URI For details, see Berners-Lee’s article.

Posted on February 25th, 2007 by Andrew
Under Accessibility | No Comments »

Sometimes one comes across the following guideline for C# structs:

All structs should be immutable.

The results of searching the web for justification for this are not very satisfying.

One argument sometimes advanced is that an immutable struct is usually simpler to understand than a mutable struct. This argument is true, but it also applies to classes, so it doesn’t explain why mutable classes should exist. Obviously we need mutable classes if the language is to be very useful as an object oriented language, so the simplicity argument for immutable structs has a major weakness.

A second argument is that making all structs immutable simplifies multithreaded applications, because it allows client code to be written without having to do the copying that is necessary with mutable structs:

void threadSafeMethod(mutableStruct s)
{
  mutableStruct t = s;
  (work with t)
}

This argument, too, is useful to know, and this argument, too, applies to classes and so is not a satisfying justification for why structs should be immutable.

A third argument for making structs immutable is that prominent value types are immutable, and many people will reason by analogy that structs should behave like the prominent exemplars of value types such as Int64 and Double. A struct that behaves differently would violate this expectation. This argument does not apply to classes and so may be somewhat more satisfying than the first two arguments.

A fourth argument for making structs immutable is to make it impossible to have a certain weird scenario where a boxed instance can be modified. This scenario violates reasonable client assumptions that values residing inside a box will not be modified. It is a satisfying argument because it does not apply to classes, since class instances cannot be boxed.

The weird scenario for modifying boxed values is described in Richter’s book, CLR via C#, Microsoft Press, 2006. Below is an adaptation.

using System;

interface IChangeable
  { void Change(int v); }

struct S : IChangeable
{
  int _v;

  public S(int v)
    { _v = v; }

  public void Change(int v)
    { _v = v; }

  public override string ToString()
    { return _v.ToString(); }
}

public class BoxingExample
{
  static void Main()
  {
    S s = new S(3);

    Object boxed = s;
    // One might expect the value in 'boxed'
    // to always be 3 after this point.

    ((IChangeable) boxed).Change(4);

    // But the next line prints "4"!!
    Console.WriteLine("boxed={0}", boxed);
  }
}

Posted on February 19th, 2007 by Andrew
Under C# / Common Language Infrastructure | 2 Comments »

When a method takes a boolean argument, it is sometimes better to restructure the method so that it takes an enumeration argument. In this article we show that the real benefit of this is not obvious and is often misunderstood.

Consider the following method and one of its clients:

void search(bool useCaseSensitiveSearch)
  { ... }

void client()
{
  ...
  search(true);
}

It’s usual to notice that rewriting to use an enumeration argument clarifies the caller’s intent:

enum SearchCaseStyle
  { CaseSensitive, CaseInsensitive }

void newSearch(SearchCaseStyle caseStyle)
  { ... }

void client()
{
  ...
  newSearch(SearchCaseStyle.CaseSensitive);
}

Sure enough, changing the argument from boolean to enumeration has clarified the intent of the caller – a positive outcome. But there are other ways to clarify the caller’s intent. One way is to follow the popular guideline of avoiding passing literals as parameters:

void client()
{
  bool caseSensitiveSearch = true;
  oldSearch(caseSensitiveStyle);
}

Another way to clarify the caller’s intent is to use comments.

We’ve seen that using an enumeration argument clarifies client intent, but that client intent can be clarified using other techniques, too. What, then, if anything, is the advantage of using an enumeration argument? It is as follows.

Rewriting a method to use an enumeration argument instead of a boolean argument increases the probability that a given caller’s intent matches the mechanism that the caller uses to communicate the intent.

This safety is something the other techniques for clarifying caller intent cannot provide. With a boolean argument, for example, even if the caller defines a constant to clarify intent, a mistake is still easy to make:

void client()
{
  bool isCaseInsensitiveSearch = true; // should be false
  oldSearch(isCaseInsensitiveSearch);
}

Here there is a mismatch between the way the caller defined the literal and the semantics of the called method. When a boolean argument is converted to an enumeration argument, such mismatches become much less likely. This is the real benefit of using an enumeration for an argument instead of a boolean value. The added safety is due to the creation of a new type; this allows the compiler to do static type checking on arguments passed in by callers.

The general principle is:

Creating a well thought out enumeration or other type for a particular method argument can make it more likely that a given value passed in by a client will match the client’s intent.

As a bonus, the client’s intent is documented almost automatically by virtue of reference to the type in client code, e.g., SearchCaseStyle.CaseSensitive.

Posted on February 19th, 2007 by Andrew
Under C# / Common Language Infrastructure | No Comments »

People sometimes wonder about the origin of my domain name onezero.org. Here’s how I chose it.

Some time around when I left grad school, I realized that it was good to have one’s own domain instead of relying on a school or company or something else to store it.

I spent the better part of a day trying to think up a domain name that I’d be happy with for years or decades. At some point during that day it occurred to me that since I spend so much time in the computing field, it might be good to have a domain name that has something to do with ones and zeroes. I also liked the fact that mathematically, 0 and 1 are essentially the two simplest objects possible. I found that the domain onezero.org was available, and that’s what I ended up with.

Only much later did I realize that 1 0 is the standard term for describing one minute chess games. In these games each side has one minute to make all their moves. That is, the entire game ends in 2 minutes or less. Upon hearing this, many people cannot get it into their heads that the entire game takes 2 minutes or less – they fix on some other idea, such as each move taking 2 minutes or less. Well. As one player put it, 1 0 isn’t your grandfather’s chess. Experts have been checkmated in real 1 0 games in less than 2 seconds. Sometimes an opponent’s queen can be won by simply attacking it and hoping that the opponent, in his hurrying, moves without noticing that his queen is attacked. It can be reasonable, or even best play, to attack your opponent’s queen with your own unguarded queen. There are many, many such tactics, especially near the end of the game when each side has 3 seconds or less. It’s common to be down a queen or two and still win. The 1 0 world is a world apart from slower chess. I have played a whole lot of 1 0, so onezero.org fits well with that too.

When I was a kid, people used to call me “ten” because I wore a football jersey that had the number 10, after Fran Tarkenton.

These other associations of 1 0 are just coincidences though. The main association of the name onezero.org is with the ones and zeros from computing and with the simplest possible mathematical objects.

Posted on February 19th, 2007 by Andrew
Under Personal | No Comments »

In C#, it is good practice to make the Equals method commute.  But even the Base Class Library fails to do this sometimes.  It’s possible to have a.Equals(b) != b.Equals(a) even with primitive types, e.g, when a is a Single (a float) and b is an Int32.

http://blogs.msdn.com/jmstall/archive/2005/03/23/401038.aspx

Posted on February 19th, 2007 by Andrew
Under C# / Common Language Infrastructure | No Comments »