Always write a spec, Part Two
Upon submitting that specification for review, even before seeing my code, Chris found a bug and an omission.
The omission is that I neglected to say what happens when the ref variable is an index into a fixed-size array buffer. As it turns out, that case is also rewritten as a pointer dereference by the time we get to this point in the code, so missing that case turned out to not be a big deal.
The bug is that this line is wrong:
if x is ref/out instance.field then add var temp=instance to L and ref/out temp.field to A2.
because it does not meet the stated goal of the method, namely, to produce the same results after the transformation:
struct S { public int q; }
static void M(ref int r) { r = r + 1; }
static int Zero() { Console.WriteLine("hello!"); return 0; }
...
S[] arr = new[] { new S() };
M(ref arr[Zero()].q);
Console.WriteLine(arr[0].q); // 1
Here we have a variable expression of the form instance.field which has a side effect; it prints "Hello". So according to the spec, we rewrite that as
S temp = arr[Zero()];
M(ref temp.q);
Console.WriteLine(arr[0].q); // 0 !
Once more, mutable value types are revealed to be pure concentrated evil. We just mutated temp.q, which is a copy of arr[0].
The interesting thing here is that Chris found the bug by reading the spec and thinking about whether I'd missed any interesting cases. Bugs are always cheaper to fix the earlier you find them; a bug you fix as a result of reading the spec is a bug that you don't have to pay QA to find, it's a bug that your customers never see, it's a bug that never causes a backwards-compatibility breaking change, and so on.
I thought hard about this and realized that the painful case only happens when we have ref/out instance.field with a side effect and instance is a variable of value type. That's the missing case. Furthermore, we can solve this by recursing!
- if x is ref/out instance.field and instance is a variable of value type, then recurse. Compute T("ref instance"), as if we were invoking a method that takes a single parameter of this ref type. That will give us a resulting declaration list, which we merge onto the end of L, and a resulting argument list with one element on it, r. Add "ref r.field" to A2.
- if x is a ref/out instance.field but instance is not a variable of value type, then generate var temp=instance on L, ref temp.field on A2.
So if we have, say, M(ref arr[index].q), that ultimately is generated as var t1 = arr, var t2 = index, M(ref t1[t2].q), which is correct.
I fixed up my implementation, wrote some test cases to test the spec, and sent it off to testing for further analysis.
There's still a bug in this spec, which our tester David found during his analysis of my spec plus proposed implementation. Hint: the problem has nothing to do with ref/out semantics; it's a more fundamental error in reasoning.
Feel free to pause and reflect for a moment if you want a chance to figure it out for yourself.
...
The error is in the default case:
First, if x has no side effects, then simply keep x in the appropriate place in A2.
Whether x has side effects or not is completely irrelevant; what is relevant is whether the computation of x depends on the order of every other side effect!
For example, our spec would have that
int k = 0;
M( k, arr[k=1] );
is the same as
int k = 0;
var t1 = arr;
var t2 = (k = 1);
M(k, t1[t2]);
which is clearly not correct; the first argument is supposed to be zero, not one. The fact that the first argument has no side effects is irrelevant; it depends on the second argument's side effect taking effect after the first argument's value is computed.
We have to fix up the spec (and implementation) to say that if the argument corresponds to a value parameter, you always save away the value in a temporary, regardless of whether it has side effects or not. If it corresponds to, say, a ref parameter, and the argument is a ref to a local then we can still simply generate the ref to the local normally; regardless of whether the contents of the local change, the managed address of the local is always the same, and computing the address of a local causes no side effects.
I note that we could also make an exception in the case that the value is, say, a compile-time constant. Clearly the computation of its value does not have any dependency on the ordering of other side effects. But for the sake of not further complexifying my spec and implementation, I glossed over this detail. The optimizer will probably take care of it.
Commenter Pavel Minaev found several more corner cases that none of us found. The big one is that we should be clear about what happens with multidimensional arrays, and in fact, I had a bug in my implementation for multidimensional arrays, so thanks Pavel! He also found some obscure ones. One is that accessing a static field does have a side effect; if this is the first access to the class then that causes the static class constructor to run, which could have observable side effects. Another is that the exact semantics of when bad arguments cause exceptions is slightly changed by this transformation.
At this point I now believe that I have a correct specification of my function T (modulo Pavel's weird issues, which I'm still mulling over. But those are bizarre corner cases that might require some language spec work to sort out.) Since the implementation is a straightforward transformation of the specification into C++, I also believe I have a correct implementation. I've written test cases that verify every case in the spec, and handed it off to testing to look for practical cases I missed.
Anyone see any other problems with this spec? Anyone?
And anyone have any guesses as to why I needed this function implemented?
Comments
Anonymous
November 23, 2009
My guess is that you'd like to memoize some function called or generated by the compiler. I'm not familiar enough with the C# specification to venture a guess as to what you're planning to memoize. Given the general track that I've seen the language take, however, I'd say it's either something for LINQ or a new attribute that we can use to declare our code as memoizable.Anonymous
November 23, 2009
>>And anyone have any guesses as to why I needed this function implemented? Some kind of thread-safe-insurance?Anonymous
November 23, 2009
I'm assuming the purpose behind this is to provide a means of side-stepping the closing-on-the-loop-variable "gotcha" by capturing the values being supplied to the delegate (and, in so doing, the value of the loop variable).Anonymous
November 23, 2009
Could this be for some sort of method caching to optimize performance?Anonymous
November 23, 2009
I agree with Adam Robinson, this seems like a step toward addressing the closing over the loop variable issue. Specifically, you said, "we cannot make lambdas capture by value by default without a huge breaking change". However, if you can ensure that none of the captured values are associated with side-effects, then I think you can do that without a huge breaking change? Probably something for C# 5.0 or even (fingers-crossed) a 4.0 service pack.Anonymous
November 23, 2009
hemp: either he is implementing a new feature or he is improving performance. he cannot change the existing syntax and modifing the loop-closing scenario would be a modification of existing code.Anonymous
November 23, 2009
I can think of a few things it could be for, but the one that seems most likely to me is Code Contracts.Anonymous
November 23, 2009
@tobi, agreed; I wouldn't think that this (or anything else) could be a complete solution, as the very effect that some find unintuitively frustrating is (or could be) exactly what others are expecting. If this is aimed at that issue, then perhaps it's one of the alternate syntax scenarios that Eric mentioned in that post (though he seemed to distance himself from them, since you'd already have to know to do something different in order to know that you need them).Anonymous
November 23, 2009
"And anyone have any guesses as to why I needed this function implemented?" Since separating the list of arguments in two categories (with and without side effects) and storing the results of the evaluation of the arguments with side effects in local variables gives the benefit that the function can be called multiple times without causing those side effects more than once, my guess is that the functions is used in a "debugging" scenario, for debug evaluation (for a debug visualizer).Anonymous
November 23, 2009
Pop, even if that isn't what this is for, that would be a very neat feature.Anonymous
November 23, 2009
That was one of the other things I was thinking of, but that would also require you to ensure that the method itself does not have any side effects. Most of the other possibilities I thought of also had this restriction, and since ref/out parameters were a major consideration in the spec, it doesn't seem likely that whatever this is for would require the method to have no side effects.Anonymous
November 23, 2009
"Once more, mutable value types are revealed to be pure concentrated evil" You didn't really mean that, did you? :P Pure evil means absolutely no good can come out of mutable value types (Yes that's and absolute statement) and only bad things. What I've found is that value types complicate the code allot in multi threading scenarios (in place mutable state), but, I've found value types to be a invaluable tool dozens of times, when there was a performance requirement and resource requirement (memory) above all other requirements (and I mean 2 -3x more computational performance compared to classes, and less than half memory usage). I can understand why some people don't like value types, but I really and truly love them :) P.S. Even Immutable value types aren't thread safe, not just mutable value types, http://stackoverflow.com/questions/370859/why-isnan-is-a-static-method-on-the-double-class-instead-of-an-instance-property/370996#370996Anonymous
November 23, 2009
My guess would go for STM, some atomic {} optimization.Anonymous
November 23, 2009
Pop.Catalin said: "P.S. Even Immutable value types aren't thread safe, not just mutable value types". The immutable value type is still thread safe, the lambda expression is not. From the C#3 specification: "The body has access to the outer variables (§7.14.4) of the anonymous function. Access of an outer variable will reference the instance of the variable that is active at the time the lambda-expression or anonymous-method-expression is evaluated (§7.14.5)." i.e. The lambda captures the variable, not it's value.Anonymous
November 24, 2009
@Zak Jensen, I think you've misread the example. There are "two" calls to Console.WriteLine in a "single" instance method of a immutable value type. The instance method is called only "once", but the output is "two" different values, from within the same instance method that accesses a read only field of the instance. Basically the instance method reads a field of it's immutable value type instance twice and gets two different values. Besides, the example can be rewritten without lambdas, by promoting the local immutable value to a field (by using a lambda that captures the variable the compiler does the same thing basically).Anonymous
November 24, 2009
@Pop.Catalin Whoops, that detail escaped me. For some reason, I imagined that the Display() call was the lambda. I'll read closer next time :)Anonymous
November 24, 2009
"And anyone have any guesses as to why I needed this function implemented?" IntelliTraceAnonymous
November 27, 2009
Eric, your classification of possible ref/out arguments misses 'this' access in structures.Anonymous
November 28, 2009
The comment has been removedAnonymous
September 09, 2011
The comment has been removed