The best advice I ever got

The super nice people over at InformIT[1. You may recall that they also recently asked me for my advice on good books for C# programmers. In the interests of full disclosure, I note that in my spare time I write and edit C# programming books for Addison-Wesley, which is owned by the same company that owns InformIT.] are running a series of short articles with the theme “the best advice I ever got”, which I think should prove to be an interesting series. They were kind enough to ask me to give an example of some good advice I got that helped my programming career, though as you’ll see it is not actually about programming at all.

Next time on FAIC: When is a cast not a cast?

Foolish consistency is foolish





Continue reading

Eric rambles on about C#, again



Implementation-defined behaviour

As I’ve mentioned several times on this blog before, C# has been carefully designed to eliminate some of the “undefined behaviour” and “implementation-defined behaviour” that you see in languages like C and C++. But I’m getting ahead of myself; I should probably start by making a few definitions.

Traditionally we say that a programming language idiom has undefined behaviour if use of that idiom can have any effect whatsoever; it can work the way you expect it to or it can erase your hard disk or crash your machine. Moreover, the compiler author is under no obligation to warn you about the undefined behaviour. (And in fact, there are some languages in which programs that use “undefined behaviour” idioms are permitted by the language specification to crash the compiler!)



All that said, for the rest of this article I’m not going to make a strong distinction between these two flavours of underspecified behaviour. The question I’m actually interested in addressing today is:


The first major factor is: are there two existing implementations of the language in the marketplace that disagree on the behaviour of a particular program? If FooCorp’s compiler compiles M(A(), B()) as “call A, call B, call M”, and BarCorp’s compiler compiles it as “call B, call A, call M”, and neither is the “obviously correct” behaviour then there is strong incentive to the language design committee to say “you’re both right”, and make it implementation defined behaviour. Particularly this is the case if FooCorp and BarCorp both have representatives on the committee.

The next major factor is: does the feature naturally present many different possibilities for implementation, some of which are clearly better than others? For example, in C# the compiler’s analysis of a “query comprehension” expression is specified as “do a syntactic transformation into an equivalent program that does not have query comprehensions, and then analyze that program normally”. There is very little freedom for an implementation to do otherwise. For example, you and I both know that

from c in customers 
from o in orders 
where c.Id == o.CustomerId 
select new {c, o}


from c in customers 
join o in orders 
  on c.Id equals o.CustomerId 
select new {c, o}


By contrast, the C# specification says that the foreach loop should be treated as the equivalent while loop inside a try block, but allows the implementation some flexibility. A C# compiler is permitted to say, for example “I know how to implement the loop semantics more efficiently over an array” and use the array’s indexing feature rather than converting the array to a sequence as the specification suggests it should. A C# implementation is permitted to skip calling GetEnumerator.



bool b = object.ReferenceEquals(f1, f2);

Suppose we were to require b to be true. How are you going to determine when two functions are “the same”? Doing an “intensionality” analysis — do the function bodies have the same content? — is hard, and doing an “extensionality” analysis — do the functions have the same results when given the same inputs? — is even harder. A language specification committee should seek to minimize the number of open research problems that an implementation team has to solve! In C# this is therefore left to be implementation-defined; a compiler can choose to make them reference equal or not at its discretion.




Those are just a few factors that come to mind; there are of course many, many other factors that language design committees debate before making a feature “implementation defined” or “undefined”.

Persistence, façades and Roslyn’s red-green trees


  • Immutable.
  • The form of a tree.
  • Cheap access to parent nodes from child nodes.
  • Persistent.

By persistence I mean the ability to reuse most of the existing nodes in the tree when an edit is made to the text buffer. Since the nodes are immutable, there’s no barrier to reusing them, as I’ve discussed many times on this blog. We need this for performance; we cannot be re-parsing huge wodges of text every time you hit a key. We need to re-lex and re-parse only the portions of the tree that were affected by the edit[1. Determining what those portions of the tree are is quite tricky; I might blog about that at a later date. An edit that, for example, adds async to a method can cause the parse of await(foo); in the method body to change from an invocation to a usage of the await contextual keyword.], because we are potentially re-doing this analysis between every keystroke.



But on the Roslyn team we routinely do impossible things. We actually do the impossible by keeping two parse trees. The “green” tree is immutable, persistent, has no parent references, is built “bottom-up”, and every node tracks its width but not its absolute position. When an edit happens we rebuild only the portions of the green tree that were affected by the edit, which is typically about O(log n) of the total parse nodes in the tree.

The “red” tree is an immutable façade that is built around the green tree; it is built “top-down” on demand and thrown away on every edit. It computes parent references by manufacturing them on demand as you descend through the tree from the top. It manufactures absolute positions by computing them from the widths, again, as you descend.

You, the consumer of the Roslyn API, only ever see the red tree; the green tree is an implementation detail. (And if you use the debugger to peer into the internal state of a parse node you’ll in fact see that there is a reference to another parse node in there of a different type; that’s the green tree node.)

Incidentally, these are called “red/green trees” because those were the whiteboard marker colours we used to draw the data structure in the design meeting. There’s no other meaning to the colours.

The benefit of this strategy is that we get all those great things: immutability, persistence, parent references, and so on. The cost is that this system is complex and can consume a lot of memory if the “red” façades get large. We are at present doing experiments to see if we can reduce some of the costs without losing the benefits.

Next time on FAIC: What precisely is “implementation-defined behaviour”?