A dynamic definite assignment puzzle, part 2

Sorry for that unexpected interlude into customer service horrors; thanks for your patience and let’s get right back to coding horrors!

So as not to bury the lede: the C# compiler is correct to flag the program from the last episode as having a definite assignment problem. Thanks to everyone who participated in the discussion in the comments.

Particular mentions go out to Jeffrey L. Whitledge who sketched the solution mere moments after I posted the problem, C# architect Neal Gafter who posted a concise demonstration, and former C# compiler dev Chris Burrows who slyly pointed out on Twitter that he “solved the puzzle”. Indeed, he solved it nine years ago when he designed and implemented this logic in the compiler.

The reasoning the compiler has to go through here is rather arcane, so let’s dig into it.

First off, let’s remind ourselves of the fundamental rule of dynamic in C#. We identify all the places in the program where the compiler deduces that the type of a thing is dynamic. Imagine that you then replaced that type judgment with the actual runtime type of the thing. The behaviour of the program with dynamic should be the same as the behaviour of the imaginary program where the compiler knew the runtime type.

This means that the compiler has to assume that the control flow of a program containing dynamic could be any control flow possible for any runtime type, including types that are legal but extremely weird. So let’s make an extremely weird type or two and see what happens.

I’ve already discussed in this blog how operator overloading works for the && operator. Briefly, the rules in C# are:

  • if left is false then left && right does not evaluate right, and has the same value as left
  • otherwise, left && right evaluates both operands and has the same value as left & right

Obviously those rules work for bool; to overload &&, we therefore need a way to evaluate whether left is false or not, and a way to determine the value of left & right. The “operator true” and “operator false” operators tell you whether a given value is logically true or logically false, and both must be provided if you provide either. Let’s look at an example, but we’ll make it a crazy example!

class Crazy
{
  public static bool operator true(Crazy c)
  {
    Console.WriteLine(“operator true”);
    return true;  // Um…
  }
  public static bool operator false(Crazy c)
  {
    Console.WriteLine(“operator false”);
    return true; // Oh dear…
  }
  public static Crazy operator &(Crazy a, Crazy b)
  {
    Console.WriteLine(“operator &”);
    return a;
  }
}

This is obviously weird and wrong; this program says that all instances of Crazy are logically true, and also all of them are logically false (because “is this false?” returns true) and also if we & two of them together, we get the first unconditionally. But, whatever, this is a legal program. If we have

Crazy c = GetCrazy() && GetAnother();

The code generated will be the moral equivalent of:

Crazy c1 = GetCrazy();
Crazy
 c = Crazy.operator_false(c1) ?
  c1 :
  Crazy.operator_&(c1, GetAnother());

But of course at runtime for this particular program we will always say that c1 is false, and always just take the first operand without calling GetAnother().

Already we’ve got a very strange program, but maybe it is not entirely clear how this produces a code path that has a definite assignment error. To get that, we need a second super-weird class. This one overloads equality — C# requires you to overload equality and inequality in pairs as well — and instead of returning a Boolean, it returns, you guessed it, something crazy:

class Weird
{
  public static Crazy operator ==(Weird p1, Weird p2)
  {
    Console.WriteLine(“==”);
    return new Crazy();
  }
  public static Crazy operator !=(Weird p1, Weird p2)
  {
    Console.WriteLine(“!=”);
    return new Crazy();
  }
  public override bool Equals(object obj) => true;
  public override int GetHashCode() => 0;
}

Maybe now you see where this is going, but we’re not quite there yet. Suppose we have

Weird obj = new Weird();
string str;
if (obj != null && GetString(out str))

What’s going to happen? Weird overrides !=, so this will call Weird.operator_!=, which returns Crazy, and now we have Crazy && bool, which is not legal, so the program will not compile. But what if we make Crazy convertible from bool? Then it will work! So add this to Crazy:

  public static implicit operator Crazy(bool b)
  {
    Console.WriteLine(“implicit conversion from bool “ + b);
    return new Crazy();
  }

Now what does if (obj != null && GetString(out str)) … mean?  Let’s turn it into method calls. This thing all together is:

Crazy c1 = Weird.operator_!=(obj, null);
bool b1 = Crazy.operator_false(c1);
// it is true that it is false
Crazy c2 = b1 ? 
  c1 : // This is the branch we take
  Crazy.operator_implicit(GetString(out str));
if (c2) …

But wait a minute, is if(c2) legal? Yes it is, because Crazy implements operator true, which is then called by the if statement, and it returns true!

We have just demonstrated that it is possible to write the program fragment

if (obj != null && GetString(out str))
  Console.WriteLine(obj + str);

and have the consequence get executed even if GetString is never called, and therefore str would be read before it was written, and therefore this program must be illegal. And indeed, if you remove the definite assignment error and run it, you get the output

!=
operator false
operator true

In the case where obj is dynamic, the compiler must assume the worst possible case, no matter how unlikely. It must assume that the dynamic value is one of these weird objects that overloads equality to return something crazy, and that the crazy thing can force the compiler to skip evaluating the right side but still result in a true value.

What is the moral of this story? There are several. The most practical moral is: do not compare any dynamic value to null! The correct way to write this code is

if ((object)obj != null && GetString(out str))

And now the problem goes away, because dynamic to object is always an identity conversion, and now the compiler can generate a null check normally, rather than going through all this rigamarole of having to see if the object overloads equality.

The moral for the programming language designer is: operator overloading is a horrible horrible feature that makes your life harder.

The moral for the compiler writer is: get good at coming up with weird and unlikely possible programs, because you’re going to have to do that a lot when you write test cases.

Thanks to Stack Overflow contributor “NH.” for the question which prompted this puzzle.

Advertisements

18 thoughts on “A dynamic definite assignment puzzle, part 2

  1. The problem seems to be that C# does not guarantee the logical absolutes. If you overload operators, then it’s up to the programmer to maintain them. In this case, the law of non-contradiction has been violated. So, dynamic cannot assume that the logical absolutes hold.

    It’s good to be aware of this. Could this have been avoided? Shouldn’t operator false automatically be “not operator true” and same for ==/!= or something? I vaguely recall there is a reason why == and != are not automatically logical inverses.

    • (er… Note that by ‘logical absolutes’ I mean the three laws of logic; not actually sure what the correct term is. Law of Identity, Law of Non-Contradiction, Law of Excluded Middle.)

      • The reason why you want to overload “true” and “false” operators in the first place is typically because you are implementing a logic in which the excluded middle does not apply! Consider a three-valued logic where we have “true”, “false” and “I don’t know”. Draw the truth table for && with this logic and you’ll see that we cannot conclude that “operator false” and “operator true” are always opposites, because “i dont know” is neither true nor false.

        • Wouldn’t this problem be solved if the overload for “false” was always checked before calling the overload for “true”? Breaking the Law of Excluded Middle is useful, but that does not mean it is okay to break the Law of Non-Contradiction.

          • The rule in C# is: operator false is used to determine if the right side of && is executed. operator true is used in ||, and when the expression in question is the condition of an if, while, for, and so on.

  2. > The moral for the programming language designer is: operator overloading is a horrible horrible feature that makes your life harder.

    It seems to me that the root of the weirdness is having two different implicit boolean conversions. The && construct uses operator_false, while the if condition presumably uses operator_true. Had there been only one implicit boolean conversion, the “impossible” behavior would have really been impossible.

    Put another way, when I see && in any language, if I know it’s short circuiting, I expect a && b to mean something like istrue(a) ? b : a. Surprisingly, C# has a separate isfalse operation that is not logically equivalent to the negation of istrue, and it is this operation that is used for &&. I am not aware of any other language that does this.

  3. I’ve still got a question. I came to an equivalent solution, but in the meantime, I’ve noticed some strangeness.
    If the first two lines of the program are:
    dynamic obj = GetObject();
    string str = “something”;
    and I remove implicit conversion from bool to Crazy (I called mine Trickster) together with & operator overload, then the program compiles and moreover runs successfully, which is, it doesn’t call GetString, enters the if and uses value “something” for str.
    Why doesn’t it fail?
    I understand that these removed methods are never called anyway, but why does the runtime understand that?

    • the error is the result of str not having been assigned a value yet. if you give it a value, everything should work ok. the issue is, how can && evaluate to true without having called GetString (which the compiler would know assigns a value to str because of the out parameter).

      • Nnope, I have a different thing in mind. After all this Crazy-Weird code is in place,
        with implicit conversion and & operator overload removed and declaration being
        Weird obj = GetObject();
        the compiler will complain at the if statement that “Operator ‘&&’ cannot be applied to operands of type ‘Crazy’ and ‘bool'”. So far so good.
        But with
        dynamic obj = GetObject();
        it turns out that the runtime doesn’t care, that there are no conversion and operator overload.

        • It looks strange, but just keep following the dynamic, and things start making sense again. If you replace
          Weird obj = GetObject();
          with
          dynamic obj = GetObject();
          then
          Crazy c1 = Weird.operator_!=(obj, null);
          bool b1 = Crazy.operator_false(c1);
          Crazy c2 = b1 ?
          c1 : // This is the branch we take
          Crazy.operator_implicit(GetString(out str));
          also gets a bunch of dynamics in it. If I use “dynamic” to also mean “whatever type has the best operator, given the runtime types of the supplied arguments”, that code becomes something like:
          dynamic c1 = dynamic.operator_!=(obj, null);
          bool b1 = dynamic.operator_false(c1);
          dynamic c2 = b1 ?
          c1 : // This is the branch we take
          (dynamic)GetString(out str);

          The important differences are the first and last line. With normal static types, the compiler errors if it can’t find a good implicit conversion between GetString’s returned bool and c1’s static Crazy type. But when obj’s compile-time type is dynamic instead, c1 follows it and also becomes dynamic. Then, on the last line, the compiler finds a perfectly good implicit conversion from bool to dynamic, and goes happily on its way.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s