Fabulous Adventures In Coding

What is "binding" and what makes it late?

Eric Lippert — Mon, 06 Feb 2012 18:39:00 GMT

"Late binding" is one of those computer-sciency terms that, like "strong typing", means different things to different people. I thought I might describe what the term means to me.

First off, what is "binding"? We can't understand what it means to bind late if we don't know what it is to bind at all.

A compiler is by definition a device which takes in a text written in one language and outputs code that "means the same thing" in another language. The compiler I work on, for example, takes in C# and outputs CIL(*). All the principle tasks performed by a compiler falls into one of three broad buckets:

Syntactic analysis of the input text
Semantic analysis of the syntax
Generation of the output text -- we will be unconcerned with this step in this article

Syntactic analysis is analysis of the input text that does not consider anything about the meaning of that text; the syntactic analyzer is concerned with first determining the lexical structure of the program (that is, where all the boundaries are between comments, identifiers, operators, and so on) and then from that lexical structure determining the grammatical structure of the program: where are the boundaries between classes, methods, statements, expressions, and so on.

Semantic analysis then takes the results of the syntactic analysis and associates meanings with various syntactic elements. For example, when you say:

class X {}
class B {}
class D : B
{
public static void X() { }
public static void Y() { X(); }
}

syntactic analysis determines that there are three classes, that one of them contains two methods, the second method contains a statement which is a call expression. Semantic analysis determines that the X in X(); refers to the method D.X(), rather than, say, the type X declared above. That's an example of "binding" in its most widely-agreed-upon sense: binding is the association of a syntactic element that names a method with a logical element of the program.

"Binding" in the sense of "early" or "late" binding is almost always used to refer to the evaluation of a name used as a method call. That, however, is far too strict a definition of "binding" for me. I would also use "binding" to describe how the compiler's semantic analyzer determines that class D inherits from class B; the name "B" is bound to the class.

Moreover, I would use "binding" to describe other analyses as well. If you had an expression 1 * 2 + 1.0 in your program then I would say that the "+" operator is "bound" to the built-in operator that takes two doubles, adds them, and returns a third. People do not normally think of that analysis as associating the name "+" with a method, but nevertheless I consider it to be "binding".

Speaking even less carefully, I might also use "binding" to describe the association of types with expressions that do not directly name the type. In the example above if speaking casually I might say that the syntax 1 * 2 is "bound" to the type int, even though obviously it does not name that type. The syntactic expression is strongly associated with that semantic element, even though it does not name it.

So, speaking generally I would say that "binding" is any association of some fragment of syntax with some logical program element. (**)

What then is "late" vs "early" binding? People talk about these two kinds of bindings as though it was a binary choice, either early or late. As we'll see, actually there is more of a spectrum than you might imagine; some bindings are entirely early, some are partially early and partially late, and some are very late indeed. But before we get into that, earlier or later than what?

Basically by "early binding" we mean "the binding analysis is performed by the compiler and baked in to the generated program"; if the binding fails then the program does not run because the compiler did not get to the code generation phase. By "late binding" we mean "some aspect of the binding will be performed by the runtime" and therefore a binding failure will manifest as a runtime failure. Early and late binding might better be called "static binding" and "dynamic binding"; static binding is binding performed using "static" facts known to the compiler, and dynamic binding is performed using facts "dynamically" known to the runtime.

So which is better? Clearly neither is unambiguously better than the other; if one was clearly the winner then we wouldn't be having this discussion in the first place. The benefit of early binding is that you gain confidence that your program will not fail at runtime; the down side is that you lose the flexibility that comes with late binding. Early binding requires that all information required to make the right binding decision be known before the program runs; but that information might not be available until runtime.

I said that early and late binding falls on a spectrum. Let's take a look at some examples in C# of how we can "turn the dial" on early-to-late binding.

We begin with our example above of calling the static method X. This analysis is entirely, unambiguously early. There is no doubt at all that when Y is called, it is going to call the method D.X. No part of that analysis is deferred until runtime and the call will unambiguously succeed.

Next, consider:

class B
{
public void M(double x) {}
public void M(int x) {}
}
class C
{
public static void X(B b, int d) { b.M(d); }
}

Now we know less. We do a lot of early binding here; we know that b is of type B and that the call is to B.M(int). But unlike the previous example, we have no guarantee from the compiler that this invocation will succeed. b could be null. We are essentially deferring the analysis of whether or not the receiver of the call is valid to the runtime to determine. One normally does not think of that as a "binding" decision though, because we are not associating syntax with a program element. Let's make the call in C; a little more late bound by changing B:

class B
{
public virtual void M(double x) {}
public virtual void M(int x) {}
}

We are now doing some binding analysis at compile time; we know that the invocation will be on the virtual method declared by B.M(int). We know that the call will succeed in the sense that there will be such a method to call. However, we do not know which method will actually be called at runtime! There could be a derived type that overrides that method; some completely other code could be called that appears nowhere in this program. Virtual dispatch is a form of late binding; the decision about which method to associate with the syntax b.M(d) is partially made by the compiler and partially made by the runtime.

How about this?

class C
{
public static void X(B b, dynamic d) { b.M(d); }
}

Now the binding is almost entirely deferred until runtime. The compiler generates code that tells the Dynamic Language Runtime that static analysis has determined that the static type of b is B and that the method being invoked is called M, but the actual overload resolution to determine whether it is B.M(int) or B.M(double) (or neither, if d is, say, a string) is done by the runtime based on that information. (***)

class C
{
public static void X(dynamic b, dynamic d) { b.M(d); }
}

Now the only portion of the binding performed early is the fact that this is a method call on a method named M. This is almost as late-bound as it gets, but we can in fact go one step further:

class C
{
public static void X(object b, object[] d, string m, BindingFlags f)
{
b.GetType().GetMethod(m, f).Invoke(b, d);
}
}

Now everything is late-bound; we don't even know what name we are going to be associating with a method. All we can possibly know is that the author of X expects that the object passed as b has a single method named by the string in m that match the flags in f, and that it takes the arguments given in d. There is nothing whatsoever we can do to analyze this call site at compile time. (****)

(*) Of course the output is encoded into a machine-readable binary format, rather than the human-readable CIL format.

(**) You might then ask whether "binding" and "semantic analysis" are not synonyms; surely semantic analysis is nothing more than the association of syntactic elements with their meanings! Binding is much of the semantic analysis phase of the compiler, but there are many analyses that we must perform after a method body is entirely "bound". Definite assignment analysis, for example, cannot by any reasonable stretch be called "binding"; it is not associating syntactic fragments with specific program elements. Rather, it is associating lexical locations with facts about program elements, facts like "the local variable blah is not definitely assigned at the beginning of this block". Similarly, optimizing arithmetic expressions is a form of semantic analysis but is clearly not "binding".

(***) The compiler could still do lots of static analysis here. For example, suppose B were a sealed class with no methods named M. Even with a dynamic argument to the call we could know statically that the runtime binding of M will always fail, and tell you that at compile time. And in fact the compiler does some such analyses; precisely how it does so is a good topic for another day.

(****) In some sense this example gives a counterexample to my definition of binding; we are no longer even associating a syntactic element with a method; we're associating the contents of a string with a method.

What's the difference? Trenchcoat vs Duster

Eric Lippert — Fri, 03 Feb 2012 14:52:00 GMT

Today, yet another episode in my ongoing series "What's the difference?" This time, a non-computer-related topic.

I am often complimented on my choice of outerwear in the Seattle rainy season, and I hate to respond to a well-meant compliment with a correction. So I usually let all those "Nice trenchcoat!" comments slide and just say "Thanks!" But as a public service, let me lay it out for you so that you don't make the same mistake. Here we see David Tennant as the Tenth Doctor wearing a classic example of a trenchcoat: (Click for a larger version.)

The trenchcoat is a long waterproof coat, traditionally made of gabardine. The term originated in the trenches of the First World War, due to the popularity of this style of coat amongst officers in the British armed forces. The trench coat is not merely a functional warm raincoat but also stylish, with long wide lapels and decorative buttons. The trenchcoat is often belted and might be tailored in at the waist, particularly for women's trenchcoats.

A duster is also a long waterproof coat that is often referred to as a "trenchcoat" -- but as you'll see, it is quite different in its details. Here's the duster I wear, an Australian-made Driza-Bone:

Note the lack of decorative elements, the flap over the closure, the no-lapel collar (which clasps shut, completely enclosing the neck if necessary) and the built-in extra rain protection on the shoulders. (*) Dusters are typically made of oilcloth and are built for handling the practicalities of herding sheep in the rain, not for style (**).

Not shown in this view: the interior includes straps that let you attach the bottom of the coat to your legs, so that it does not blow around when you are on horseback. Also, the back is cut in such a way that you can cover both your legs and the rear portion of the saddle with the coat. I usually take the bus and not a horse to work, but still it's nice to know that options are available should I need them. These practical elements are usually not present in trenchcoats.

Right, glad we got that sorted out. Next time: What is binding, and why is it always either early or late? Can't it ever be on time?

(*) Duster manufacturers always hasten to point out that the shoulders are already waterproof; the extra layer keeps your shoulders warmer by shedding rain more effectively.

(**) There are, of course, some dusters built for style; if you watch the "Matrix" series of movies you'll see the heroes wear an assortment of extremely stylish dusters and trenchcoats both.

Anonymous Types Unify Within An Assembly, Part Two

Eric Lippert — Mon, 30 Jan 2012 16:20:00 GMT

Last time I noted that any two usages of "the same" anonymous type within an assembly actually unify to be the same type. By "the same" we mean that the two anonymous types have the same property names and types, and that they appear in the same order. new {X = 1, Y = 2 } and new { Y = 2, X = 1 } do not unify to a single type.

Why is that? You'd think that we could make these unify.

The trouble is that doing so causes more problems than it mitigates. An anonymous type gives you a convenient place to store a small immutable set of name/value pairs, but it gives you more than that. It also gives you an implementation of Equals, GetHashCode and, most germane to this discussion, ToString. (*)

Imagine, for instance, that you have written a bunch of LINQ queries in your code that extract data from a table using an anonymous type. As part of your unit testing, you dump the results of the query as a string out to a file and compare it against a known baseline. Maybe you have hundreds of such tests. And then one day, someone in a completely different part of the code happens to write a LINQ query that has "the same" anonymous type, but with the properties in a different order. We have to pick some order for the properties to be written out by "ToString", and there is no telling which one we'd pick if forced to choose. It seems very strange that using an anonymous type in one part of the program would cause tests to fail in a completely different part of the program.

Well then, you might say, you could solve this problem by canonicalizing the implementation of ToString. Always write out the properties in alphabetical order, say. But that is hardly an attractive solution. First off, whose alphabetical order? There are dozens of different alphabetical orders, depending on what location in the world you are in. Should we choose the alphabetical order of the developer? The current user? The "culture neutral" order? Assuming we could solve that problem satisfactorily, we'd still be disappointing most users. Developers have a reasonable expectation that ToString will give them the properties in the order they appear in the source code.

Another option would be to not implement ToString for you at all. That is to say, remove a useful and relatively commonly used feature (dumping data to a string for testing or debugging) in order to effectively implement a less useful, rarely used feature (unification of types).

(*) We give you Equals and GetHashCode so that you can use instances of anonymous types in LINQ queries as keys upon which to perform joins. LINQ to Objects implements joins using a hash table for performance reasons, and therefore we need correct implementations of Equals and GetHashCode.

Anonymous types unify within an assembly, Part One

Eric Lippert — Mon, 23 Jan 2012 15:55:00 GMT

Back in my last post of 2010 I said that I would do an example of anonymous types unifying within an assembly "in the new year". I meant 2011, but here we are "in the new year" again, so, no time like the present.

The C# specification guarantees you that when you use "the same" anonymous type in two places in one assembly (*) the types unify into one type. In order to be "the same", the two anonymous types have to have the exact same member names and the exact same member types, in the exact same order. (**)

It is easy to see how this works in a method body; you could simply say:

var anon1 = new { X = 1 };
var anon2 = new { X = 2 };
anon2 = anon1;
Console.WriteLine(anon2.X); // 1

And it is easy to see how you could verify this fact with reflection across method bodies within the same assembly:

class C
{
    public static object Anon1() { return new { X = 1 }; }
}
class D
{
    static void M()
    {
        // True:
        Console.WriteLine(C.Anon1().GetType() == (new { X = 2 }).GetType());
    }
}

But... so what? Using reflection in this way seems supremely uninteresting. What would be more interesting is to merge the two examples together:

class C
{
    public static object Anon1() { return new { X = 1 }; }
}
class D
{
    static T CastByExample<T>(T example, object obj)
    {
        return (T)obj;
    }
    static void M()
    {
        var anon1 = CastByExample(new { X = 0 }, C.Anon1());
        var anon2 = new { X = 2 };
        anon2 = anon1;
        Console.WriteLine(anon1.X); // 1
    }
}

As you can see, you can share instances of an anonymous type around an assembly if you want to. We do not expect that a lot of people will do so; typically if this is the sort of thing you like doing, you'd use either a tuple or a custom-built nominal type. Still, it is not expensive for us to make this guarantee, and it is kind of a nice property.

(*) Technically not exactly true. You could have an assembly made up of many different netmodules compiled at different times that do not know about each other; anonymous types defined in one netmodule will not necessarily unify with those in others.

(**) Next time I'll discuss why we have this latter requirement.

What is the defining characteristic of a local variable?

Eric Lippert — Mon, 16 Jan 2012 14:48:00 GMT

If you ask a dozen C# developers what a "local variable" is, you might get a dozen different answers. A common answer is of course that a local is "a storage location on the stack". But that is describing a local in terms of its implementation details; there is nothing in the C# language that requires that locals be stored on a data structure called "the stack", or that there be one stack per thread. (And of course, locals are often stored in registers, and registers are not the stack.)

A less implementation-detail-laden answer might be that a local variable is a variable whose storage location is "allocated from the temporary store". That is, a local variable is a variable whose lifetime is known to be short; the local's lifetime ends when control leaves the code associated with the local's declaration space.

That too, however, is a lie. The C# specification is surprisingly vague about the lifetime of an "ordinary" local variable, noting that its lifetime is only kinda-sorta that length. The jitter's optimizer is permitted broad latitude in its determination of local lifetime; a local can be cleaned up early or late. The specification also notes that the lifetimes of some local variables are necessarily extended beyond the point where control leaves the method body containing the local declaration. Locals declared in an iterator block, for instance, live on even after control has left the iterator block; they might die only when the iterator is itself collected. Locals that are closed-over outer variables of a lambda are the same way; they live at least as long as the delegate that closes over them. And in the upcoming version of C#, locals declared in async blocks will also have extended lifetimes; when the async method returns to its caller upon encountering an "await", the locals live on and are still there when the method resumes. (And since it might not resume on the same thread, in some bizarre situations, the locals had better not be stored on the stack!)

So if locals are not "variables on the stack" and locals are not "short lifetime variables" then what are locals?

The answer is of course staring you in the face. The defining characteristic of a local is that it can only be accessed by name in the block which declares it; it is local to a block. What makes a local truly unique is that it can only be a private implementation detail of a method body. The name of that local is never of any use to code lexically outside of the method body.

Every public change is a breaking change

Eric Lippert — Mon, 09 Jan 2012 17:08:00 GMT

Here's an inconvenient truth: just about every "public surface area" change you make to your code is a potential breaking change.

First off, I should clarify what I mean by a "breaking change" for the purposes of this article. If you provide a component to a third party, then a "breaking change" is a change such that the third party's code compiled correctly with the previous version, but the change causes a recompilation to fail. (A more strict definition would be that a breaking change is one where the code recompiles successfully but has a different meaning; for today let's just consider actual "build breaks".) A "potential" breaking change is a change which might cause a break, if the third party happens to have consumed your component in a particular way. By a "public surface area" change, I mean a change to the "public metadata" surface of a component, like adding a new method, rather than changing the behaviour of an existing method by editing its body. (Such a change would typically cause a difference in runtime behaviour, rather than a build break.)

Some public surface area breaking changes are obvious: making a public method into a private method, sealing an unsealed class, and so on. Third-party code that called the method, or extended the class, will break. But a lot of changes seem a lot safer; adding a new public method, for example, or making a read-only property into a read-write property. As it turns out, almost any change you make to the public surface area of a component is a potential breaking change. Let's look at some examples. Suppose you add a new overload:

// old component code:
public interface IFoo {...}
public interface IBar { ... }
public class Component
{
public void M(IFoo x) {...}
}

Suppose you then later add

public void M(IBar x) {...}

to Component. Suppose the consumer code is:

// consumer code:
class Consumer : IFoo, IBar
{
   ...
   component.M(this);
   ...
}

The consumer code compiles successfully against the original component, but recompiling it with the new component suddenly the build breaks with an overload resolution ambiguity error. Oops.

What about adding an entirely new method?

// old component code:
...
public class Component
{
public void MFoo(IFoo x) {...}
}

and now you add

public void MBar(IBar x) {...}

No problem now, right? The consumer could not possibly have been consuming MBar. Surely adding it could not be a build break on the consumer, right?

class Consumer
{
    class Blah
    {
        public void MBar(IBar x) {}
    }
    static void N(Action<Blah> a) {}
    static void N(Action<Component> a) {}
    static void D(IBar bar)
    {
        N(x=>{ x.MBar(bar); });
    }
}

Oh, the pain. In the original version, overload resolution has two overloads of N to choose from. The lambda is not convertible to Action<Component> because typing formal parameter x as Component causes the body of the lambda to have an error. That overload is therefore discarded. The remaining overload is the sole applicable candidate; its body binds without error with x typed as Blah.

In the new version of Component the body of the lambda does not have an error; therefore overload resolution has two candidates to choose from and neither is better than the other; this produces an ambiguity error.

This particular "flavour" of breaking change is an odd one in that it makes almost every possible change to the surface area of a type into a potential breaking change, while at the same time being such an obviously contrived and unlikely scenario that no "real world" developers are likely to run into it. When we are evaluating the impact of potential breaking changes on our customers, we now explicitly discount this flavour of breaking change as so unlikely as to be unimportant. Still, I think its important to make that decision with eyes open, rather than being unaware of the problem.

He's So Dreamy

Eric Lippert — Mon, 02 Jan 2012 17:23:00 GMT

Happy New Year all!

It has just been brought to my attention that this blog and the Programmer Ryan Gosling photo blog share at least one reader:

I admit it, I LOL'd.

In the interests of total accuracy I'd like to point out that the first entry on the blog contains a subtle error:

.NET actually supported generic covariance and contravariance on interface and delegate types from the beginning; generics were introduced in version 2, and they always allowed variance. You could write programs in MSIL and compile them with ILDASM and have generic variance, no problem. No "mainstream" language supported the feature until v4, and none of the interfaces or delegates in the class libraries were marked as variant, so effectively variance did not become a well-used feature until v4, but the capability was always there.

As a response to the unknown reader to submitted the first photo above, I give you the following:

Next time: some depressing news about breaking changes: they're everywhere!

Shadowcasting in C#, Part Six

Eric Lippert — Thu, 29 Dec 2011 15:05:00 GMT

OK, let's finish up this year and this series. We have an algorithm that can compute what cells in the zero octant are in view to a viewer at the origin when given a function that determines whether a given cell is opaque or transparent. It marks the visible points by calling an action with the visible cells. We would like that to work in any octant, and for the viewer at any point, not just the origin.

We can solve the "viewer at any point" problem by imposing a coordinate transformation on the "what is opaque?" function and the "cell is visible" action. Suppose the algorithm wishes to know whether the cell (3, 1) is opaque. And suppose the viewer is not at the origin, but rather at (5, 6). The algorithm is actually asking whether the cell at (3 + 5, 6 + 1) is opaque. Similarly, if that cell is determined to be visible then the transformed cell is the one that is visible from (5, 6). We can easily transform one delegate into another:

private static Func<int, int, T> TranslateOrigin<T>(Func<int, int, T> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

private static Action<int, int> TranslateOrigin(Action<int, int> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

Similarly we can perform an octant transformation; if you want to map a point in octant one into a point in octant zero, just swap its (x,y) coordinates! Every octant has a simple transformation that reflects it into octant zero:

private static Func<int, int, T> TranslateOctant<T>(Func<int, int, T> f, int octant)
{
    switch (octant)
    {
        default: return f;
        case 1: return (x, y) => f(y, x);
        case 2: return (x, y) => f(-y, x);
        case 3: return (x, y) => f(-x, y);
        case 4: return (x, y) => f(-x, -y);
        case 5: return (x, y) => f(-y, -x);
        case 6: return (x, y) => f(y, -x);
        case 7: return (x, y) => f(x, -y);
    }
}

(And similarly for actions.)

Now that we have these simple transformation functions we can finally implement the code that calls our octant-zero-field-of-view algorithm:

public static void ComputeFieldOfViewWithShadowCasting(
    int x, int y, int radius,
    Func<int, int, bool> isOpaque,
    Action<int, int> setFoV)
{
    Func<int, int, bool> opaque = TranslateOrigin(isOpaque, x, y);
    Action<int, int> fov = TranslateOrigin(setFoV, x, y);

    for (int octant = 0; octant < 8; ++octant)
    {
        ComputeFieldOfViewInOctantZero(
            TranslateOctant(opaque, octant),
            TranslateOctant(fov, octant),
            radius);
    }
}

Pretty slick, eh?

One minor downside of this algorithm is that it computes the visibility of the points along the axes and major diagonals twice; however, the number of such cells grows worst case linearly with radius. The algorithm as a whole is worst case quadradic in the radius, so the extra linear cost is probably irrelevant.

I've posted the project that builds the Silverlight control from the first episode here, if you want to get a complete working example.

Happy New Year everyone and we'll see you in 2012 for more Fabulous Adventures in Coding!

Shadowcasting in C#, Part Five

Eric Lippert — Tue, 27 Dec 2011 18:05:00 GMT

I hope you all had a pleasant Christmas and Boxing Day; we chose to not travel to see family this year and had a delightful time visiting friends. We'll finish up 2011 here with a bit more on shadowcasting, and then pick up with more C# language design facts and opinions in January.

OK, so we've found the top and bottom cells in a particular column portion, bounded by a top and bottom vector. Now we have two tasks. First, all cells in that portion that are in the radius need to be marked as visible. Second, we must figure out what portions of the next column are visible through this portion, and enqueue that work.

The first bit is easily done. Thanks to the great comments to my earlier entry I've learned that of course it is better to consider the question "is the bottom left corner of the cell within the visible radius?" That makes for a nicer looking circle. I've made a helper method "IsInRadius" that does that. (Note that of course this introduces yet another kind of artifact; suppose that of the four corners of a cell, only the bottom right corner of a cell is below the top vector, but only the bottom left corner is within the radius. There might be no point in the cell that is both within the radius and not blocked. We'll ignore this detail; the radius is inherently approximate.)

The second bit is harder. What we'll do is keep track as we move from top to bottom of this portion whether we have seen any transitions from transparent to opaque or opaque to transparent. If we find a transition from transparent to opaque then we have found a boundary for the next column portion; we'll enqueue that new portion. If we find a transition from opaque to transparent then we'll enqueue new work for the new region when either we find an opaque cell or the bottom of the portion.

bool? wasLastCellOpaque = null;
for (int y = topY; y >= bottomY; --y)
{
    bool inRadius = IsInRadius(x, y, radius);
    if (inRadius)
    {
        // The current cell is in the field of view.
        setFieldOfView(x, y);
    }

A cell that was too far away to be seen is effectively an opaque cell; nothing "above" it is going to be visible in the next column, so we might as well treat it as an opaque cell and not scan the cells that are also too far away in the next column.

    bool currentIsOpaque = !inRadius || isOpaque(x, y);
    if (wasLastCellOpaque != null)
    {
        if (currentIsOpaque)
        {

We've found a boundary from transparent to opaque. Enqueue more work for later.

if (!wasLastCellOpaque.Value)
{

The new bottom vector touches the upper left corner of opaque cell that is below the transparent cell.

                queue.Enqueue(new ColumnPortion(
                    x + 1,
                    new DirectionVector(x * 2 - 1, y * 2 + 1),
                    topVector));
            }
        }
        else if (wasLastCellOpaque.Value)
        {

We've found a boundary from opaque to transparent. Adjust the top vector so that when we find the next boundary or do the bottom cell, we have the right top vector. The new top vector touches the lower right corner of the opaque cell that is above the transparent cell, which is the upper right corner of the current transparent cell.

I normally don't modify a formal parameter like this, but it seems reasonably unconfusing in this context.

            topVector = new DirectionVector(x * 2 + 1, y * 2 + 1);
        }
    }
    wasLastCellOpaque = currentIsOpaque;
}

And finally, we enqueue work for the lowest opaque-to-transparent transition, if there is one.

if (wasLastCellOpaque != null && !wasLastCellOpaque.Value)
queue.Enqueue(new ColumnPortion(x + 1, bottomVector, topVector));

And there you go; that's shadowcasting from the origin in the first octant. Next time we'll deal with the other seven octants, and deal with points other than the origin.

Shadowcasting in C#, Part Four

Eric Lippert — Thu, 22 Dec 2011 17:18:00 GMT

Last time we saw how many different ways there were to get the calculation of the top cell based on the top vector wrong. Today we'll take a briefer look at determining the bottom cell.

We know from our discussion of last time that the right way to determine what is the top-most visible cell in a column portion is to consider where the top vector leaves the column. By similar logic, the right way to determine where the bottom-most cell is in a column portion is to look at where the bottom vector enters the column. Clearly where the vector enters the current column is precisely the same place that it left the previous column, and we already know how to calculate that.

What sorts of things go wrong if you, say, round down instead of rounding to the cell where the vector enters the column? In my implementation of the other day I made a deliberate mistake: for the bottom direction vector I do the division and round down. This introduces some artifacts. For example, it means that you can see immediately behind nearby pillars but not behind far-away pillars:

Notice how the pillar to the left casts a full 90 degree shadow. However, the pillar to the right permits me to see the square immediately behind it, and then casts a shadow. This is not very realistic; if I can see immediately behind the pillar then why can I not also see beyond it?

Note that this also presents a gameplay problem. Suppose there was a monster "hiding" behind the pillar east of me there. I could see the monster, but it could not see me! If the targeting system for arrow attacks requires line-of-sight, and line-of-sight is determined by simply computing the whole field of view and checking whether the cell in question is in the field, then I can shoot the monster but it cannot shoot me. By similar logic, a monster that is two cells to the west of the pillar west of me can shoot me, but I cannot see it or shoot it.

Does this problem go away if we rewrite the rounding algorithm to be less permissive by rounding more appropriately? No! We still have a symmetry problem in a room full of pillars. Let's put both the "round down" and the "round to lowest column entry" algorithms next to each other for a comparison. Click on the control to play the game "in stereo":

Notice how in both implementations it is possible to get into a position where you can see behind a pillar, but the monster standing there cannot see you:

Monsters standing at the blue arrow cells are visible from the player's location, but the monsters cannot see the player. Monsters standing at the orange arrow locations can see the player, but the player cannot see them.

The problem here is that the algorithm computes the set of cells where any point in the target cell is visible from the center of the player's cell. In order for the algorithm to be symmetric we need to allow any point in the target cell to be visible from any point in the player's cell. That is the "permissive field of view" algorithm. It uses the same concepts that we've described here; it progressively scans a region (a quadrant, rather than an octant) and keeps a set of line segments (not vectors, since they need not go through the origin) that track what regions are in view as you get farther and farther away from the origin. It's a rather tricky algorithm to get right, and so I'm not going to present it here.

Next time: Now that we know how to compute the top and bottom cells, actually running the algorithm is pretty straightforward. We'll go through the details of the code.

Shadowcasting in C#, Part Three

Eric Lippert — Mon, 19 Dec 2011 16:06:00 GMT

Before we get started, thanks for all the great comments to the previous couple of posts. I'll be updating the algorithm to try to make even better-looking circles of light based on the comments. Like I said, there's a lot of subtleties to these algorithms and I am just learning about them myself.

To that end, in today's episode I am going to spend the entire prolix article analyzing a single division operation. You have been warned.

Before we begin though, some jargon. A cell which is invisible that by our physical interpretation ought to be visible, or a cell which is visible that ought to be invisible we will call an "artifact". An "artifact" is the product of our algorithm (or some detail of its implementation) not being a sufficiently accurate model of real-world physics. Today's article will be all about artifacts.

The actual workhorse that implements the field-of-view algorithm is this method that we mentioned last time:

private static void ComputeFoVForColumnPortion(
    int x,
    DirectionVector topVector,
    DirectionVector bottomVector,
    Func<int, int, bool> isOpaque,
    Action<int, int> setFieldOfView,
    int radius,
    Queue<ColumnPortion> queue)
{

This method has two main purposes. First, it assumes that all points in the portion of column x bounded by the top and bottom vectors are in the field of view, and marks them accordingly; some of them might be outside the radius, but the rest of them are by assumption visible from the origin. Second, it determines which portions of column x+1 are in the field of view and adds them to the work queue for later processing.

We described the algorithm as working from top to bottom of the portion of the column under consideration. Therefore the very first question we must answer is "which exactly is the top cell in the column portion, given the column number and the top direction vector?"

If the center point of a cell in column x happens to fall exactly on the top direction vector then it is pretty clear which is the top cell. Suppose for the sake of argument that's the case. The top cell is then computed by x * topVector.Y / topVector.X. This division is exact. Proving that is an easy bit of algebra and is left as an exercise.

So perhaps we should say that even if the division is inexact, we compute the top cell by:

int topY = x * topVector.Y / topVector.X;

(Note that we'll assume throughout that the numbers we are multiplying and dividing are small compared to the range of int, and therefore do not overflow.)

What happens if the division is inexact? We know that in C# an inexact integer division always rounds towards zero; it rounds down if necessary.

Rounding down is a bad idea because it doesn't model the physical world well and makes for extraordinarily bad-looking gameplay. Consider this extremely common scenario:

Scenario One

After processing column one we lower the slope of the top direction vector to one-third. Is point (2,1) in the field of view? It sure seems light it ought to be since its entire bottom surface is within the field of view. But if we do 2 * 1 / 3 we get zero, so no, the top cell that is visible in this column is (2, 0). We mark that as visible and continue on to column three without changing the slope. The top direction vector now intersects the center of cell (3, 1), so it and (3, 0) are visible. We lower the slope of the top vector to one-seventh, and now cell (4, 1) is not visible, again because we are rounding down. After processing all the columns shown here the state of affairs would be:

This matches neither the desired physics nor the desired gameplay; a straight corridor should not have weird "gap" artifacts. Notice also that the resulting top vector is a little bit too steep; we never considered the opaque cell in column four to be possibly shadowing anything beyond it; the rest of the world is only in the shadow of cell (3,1), not (4,1). Rounding down is clearly unacceptable.

Well. What to do, if rounding down doesn't work? Maybe we should round up!

That solves the problem for long corridors; now what happens is cell (2,1) is determined to be visible by rounding up, so the top slope is lowered to one-fifth. Then cell (3, 1) is determined to be visible, so the slope is lowered to one-seventh. Then cell (4,1) is determined to be visible, and the slope is lowered to one-ninth. That seems to be much better.

Moreover, we now also have the nice property that the corners of a room are visible. Consider this common situation:

Scenario Two

Cell (5,2) will be visible, which will render nicely, particularly if "box drawing" characters are used to represent interior corners as is the case in many roguelike games. This is a desirable artifact.

But surely now we have the opposite problem; if we round up then we are potentially making cells visible that ought to be in the shadow of some opaque cell. Let's take a look at an example of that.

Scenario Three

Cells (3,2) and (4,2) are unambiguously in the shadow of cell (2,1). But look carefully at column five. Even though the top vector does not pass through any part of (5,2) it does pass slightly above point (5,1) and therefore the division will round up such that (5,2) is considered visible! With this rounding algorithm you can "peek around a corner" a little bit. Visible point (5,2) is an artifact.

Even worse, consider what happens when the algorithm discovers that there is an opaque-to-transparent transition between (5,2) and (5,1). The top vector will be moved up!

That top vector is now steeper than it used to be. (Also note that if this had been the top vector when processing column four then the point (4,2) ought to have been visible.)

Obviously this situation can continue; rounding errors in later columns can continue to make the top vector steeper and steeper. (Exercise for the reader: is there a maximum slope that the top vector can attain via repeated applications of rounding error?)

We could easily put a check into the algorithm implementation to say that the top direction vector must never go from a shallower slope to a steeper slope. If we decided to use always-round-up rounding then we might do that. But it gets worse. Consider this scenario that I mentioned last time:

Scenario Four

Last time I made the simplifying assumption that cell (5,4) was out of range, and therefore not visible. But suppose the radius is larger; let's analyze this one in more detail. We'll round up to determine the highest visible cell in the column portion bounded by these vectors, so cell (5,4) is visible. We then find transitions from visible (5,4) to opaque (5,3) and opaque (5,2) to visible (5,1) (assuming that (5,1) is the bottom cell of the range; we'll discuss that assumption next time.) Therefore we have to divide this up into two sub-portions for column six. To compute the upper portion we keep the top vector the same and move the bottom vector up; to compute the lower portion we keep the bottom vector the same and move the top vector down. The result is this godawful mess:

The top direction vector of the upper column portion is now below the bottom vector. Yikes!

This error again allows the player to "look around corners" in a weird way, but it really is not so bad. What will happen here is that as long as the mis-ordered vectors identify the same cell as the top and bottom cell of the visible portion for a particular column, that single cell will be visible. As soon as the portion is large enough that the top and bottom cells are different, the loop that goes from top to bottom will immediately exit.

Again, we could prevent this situation by doing a check that verifies that the bottom vector is never moved to be above the top vector. However, perhaps we'd decide that this situation is sufficiently rare, and the artifact is sufficiently benign, that we'd just allow it.

Rounding up seems better than rounding down, but this still isn't great. Hmm. What if we rounded to the nearest lattice point?

Scenario One is unchanged. We still correctly compute visibility of the entire long straight wall.

Scenario Two is unchanged. We still make the desirable "corner artifact".

Scenario Three is improved. Cell (5,2) is not treated as visible, which is good because it is entirely in shadow. The top vector is not made more steep.

Scenario Four is unchanged. We can still end up in a situation where the top and bottom direction vectors are mis-ordered.

That's no change in three scenarios and a great improvement in one, so this is an unambiguous win, right?

Not quite. Consider this scenario:

Scenario Five

If we round to nearest then (4,3) is not visible, even though a full 30% of its lower surface has line of sight from the origin. Furthermore, by not treating this cell as visible, we fail to lower the slope of the top vector from 3/5 to 5/9, possibly allowing more cells to be visible in higher columns that ought to be shadowed by (4,3). Round-up would have treated (4,3) as the topmost cell in the region, so round-to-nearest is not an unambiguous win over round-up.

At this point it would be wise to take a step back and ask ourselves if continuing to tweak how the division rounds is the right thing to do. When you propose three different plausible calculations and they all turn out to be wrong in different ways, there might be an invalid assumption somewhere in the mix.

The invalid assumption is that y = SomeKindOfRoundingOf(x, top.Y, top.X) is correct in the first place. It is not. This calculation, no matter how you round it, is fundamentally calculating where the vector intersects the center of the column. Why is the center of the column at all relevant? It is the edges of the cell that cast shadows!

What we want to compute is "what is the highest cell in the given column that is anywhere intersected by the top direction vector?" The slope of the top direction vector is always positive; the line is always "sloping up", so the top cell can be identified by figuring out where the vector leaves the column. What we should be doing is working out the intercept of the vector with x + 0.5, not with x.

How are we going to do that? The first thing to observe is that (x + 0.5 ) * top.Y / top.X is the same thing as (2 * x + 1) * top.Y / (2 * top.X). Now everything is in integers. Let's work out the quotient and the remainder in integers:

int quotient = ((2 * x + 1) * top.Y) / (2 * top.X);
int remainder = ((2 * x + 1) * top.Y) % (2 * top.X);

Let's look at a bunch of possible different possibilities. Suppose the direction vector is (5, 3), so we go five "right" for every three "up". The interesting points are the points where the vector exits the column on the right hand side. The quotient is the black horizontal line below the interesting point. In this example the remainder is the number of tenths the interesting point is above the quotient line. (Tenths because the denominator is 5 x 2.) The numbers at the bottom of each column are the remainders:

(Note that the dividend will always be an odd number and the divisor will always be an even number, and therefore the remainder will always be an odd number. Proving those assertions is left as an exercise. Hint: what possible y values can the top direction vector take on if restricted only to integers?)

So, how should we round? Consider the columns labeled 1 and 3. In those the rounded-down quotient correctly identifies the cell that the direction vector intersects. The columns labeled 7 and 9, however, have a problem; the quotient is one below the correct result; we have rounded down incorrectly. What about the column labeled 5? If the remainder is exactly the "run" value of the top direction vector then the vector passes exactly through the boundary where two cells meet; which one should be visible? Since this is the "top" bounding vector, we should round down; no area of the upper cell is visible.

So, in summary: use the rounded-down quotient as the top cell in the column if the remainder is top.X or less; otherwise, round it up by adding one to the quotient.

Does that solve our problems?

Scenario One: Good. We correctly put the whole corridor wall into the field of view.

Scenario Two: Good. We "correctly" put the invisible corner cell into the field of view.

Scenario Three: Good. Cell (5,2) is not identified as being visible, and therefore the top vector's slope is not increased.

Scenario Four: Bad. We incorrectly identify cell (5,4) as being visible through cell (5,3), and thereby produce not only an artifact, but an "inverted" set of top and bottom vectors for the next column.

Scenario Five: Good. We make cell (4,3) visible and lower the slope of the top vector accordingly.

This algorithm is not perfect; we still make some artifacts. How might we solve the issue of scenario four?

A couple ways come to mind. One is that we could check to see if the direction vector enters the column at (5,3) and exits at (5,4). If it does then (5,4) is only the top cell if (5,3) is transparent.

Another way would be to allow cell (5,4) to be visible regardless -- this might have nice properties for showing corners, even if the cell is technically an artifact -- but to detect whether the new bottom vector is steeper than the old top vector and not allow the recursion.

In my actual implementation of last week I decided that solving the problem of scenario four is not worth it to me; I allow the artifacts and the inverted range. The results seem pretty decent.

As I warned you, it took me an extremely long article with nine complicated diagrams to figure out how to divide two numbers to determine the top cell. I said this was going to be excessively detailed!

Next time we'll do the same analysis for determining the bottom cell in the column portion. Hopefully things will go a bit quicker now that we have the basic idea of how rounding produces artifacts down pat.

Shadowcasting in C#, Part Two

Eric Lippert — Thu, 15 Dec 2011 16:43:00 GMT

I hope the basic idea of the shadow casting algorithm is now clear. Let's start to implement the thing. There are two main concerns to deal with. The easy one is "what should the interface to the computation look like?" The second is "how to implement it?" Let's deal with the easy one first; let's design the API.

What does the caller need to provide?

The coordinates of a central point
The radius of the field of view
Some way for the algorithm to know which cells are opaque

What does the implementation need to do for the caller?

Provide some way of telling the caller which cells are visible from the central point.

It's that last one that is a bit tricky. The implementation could return a list of point objects that are in view. Or it could create a two-dimensional array of bools and set the bools to true if the cell is in view or false if it is not. It could mutate a caller-provided collection. And so on. We don't know how the caller works or what it is going to do with that information. We don't even know if it is storing that information as bools or bit flags or a list of points. It is hard to know what the right thing to do is, so we'll punt on it. We'll make the caller decide by making the caller pass in an Action that does the right thing for it!

public static class ShadowCaster
{
    // Takes a circle in the form of a center point and radius, and a function that
    // can tell whether a given cell is opaque. Calls the setFoV action on
    // every cell that is both within the radius and visible from the center.
    public static void ComputeFieldOfViewWithShadowCasting(
        int x, int y, int radius,
        Func<int, int, bool> isOpaque,
        Action<int, int> setFoV)
    {
        // The miracle happens here
    }

OK, so that's the point of entry for the caller. What about the implementation?

I wanted my implementation to have the following characteristics:

First and foremost, the implementation should be clear and correct. It should be performant enough for small demos, but not necessarily wringing every last drop of performance out of the processor. If the code is clear and correct but not fast enough, targeted performance analysis can find the hot spot later. For debuggability, I'd like it if the code operates more or less in the same order as in the description of the algorithm I laid out. Also, the code should be DRY -- Don't Repeat Yourself. (*)

I want the implementation to not be overly concerned with vexing book-keeping details. We laid out the algorithm as one which assumed that the viewpoint was the origin and the field of view was calculated only in the zero octant; our implementation should do the same, rather than trying to keep track of details like where the viewpoint really is.

This algorithm is often implemented recursively but I wanted to avoid that, for two reasons. First, because the typical recursive implementation recurses at least once per column; one can imagine a scenario in which a long narrow tunnel hundreds of cells long blows the stack. Second, because the typical recursive implementation explores the octant in a "column depth first" manner. That is, when it must divide the visible region into multiple "portions" each with its own top and bottom direction vector, it explores each portion through to the final column; the priority is to explore each portion entirely before starting on the next. But we characterized the algorithm as a straightforward left-to-right, top-to-bottom progression of cells that explores each column entirely before starting on the next. As I said before, for both clarity and debuggability it would be nice if the implementation matched the description.

The basic idea of my implementation goes like this:

For each column, take as an input a set of cells in a column known to be either definitely in the field of view, or possibly just barely out-of-radius.
From that set, compute which cells in the next column are either definitely in the field of view or possibly just out-of-radius.
Repeat until you get to the column that is entirely outside of the field-of-view radius; you can stop there.

That's a good high-level overview, but let's make the action a bit more crisp:

Break each column (identified by the x-axis coordinate that defines the center of the column) down into one or more contiguous "portions" each bounded by a top and bottom direction vector.
For each portion in the current column, determine the set of portions in the subsequent column that are visible.
Add each of those subsequent portions to a work queue.
Keep on processing portions from the work queue until there are no more.

OK, that's enough of a description to actually write some code to implement these abstractions. We can do that with two little immutable structs.

Recall that we decided to represent direction vectors as a point on the line of the vector, and that we do not care about the magnitude, only the direction. As we'll see, the only direction vectors we need fall on lattice points, so we can use ints as the coordinates.

private struct DirectionVector
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public DirectionVector(int x, int y)
        : this()
    {
        this.X = x;
        this.Y = y;
    }
}

The portion of the column we are dealing with is characterized by three facts: what is the x-coordinate of the column's center, what is the direction vector bounding the top of the portion, and what is the direction vector bounding the bottom of the portion?

private struct ColumnPortion
{
    public int X { get; private set; }
    public DirectionVector BottomVector { get; private set; }
    public DirectionVector TopVector { get; private set; }
    public ColumnPortion(int x, DirectionVector bottom, DirectionVector top)
        : this()
    {
        this.X = x;
        this.BottomVector = bottom;
        this.TopVector = top;
    }
}

Now that we have these data structures we can make the main loop of the engine. Note that we are now assuming that the center point is the origin and that we are only interested in octant zero. Somehow the entry point is going to have to figure out how to deal with that requirement, but that's a problem that we'll solve later.

private static void ComputeFieldOfViewInOctantZero(
    Func<int, int, bool> isOpaque,
    Action<int, int> setFieldOfView,
    int radius)
{
    var queue = new Queue<ColumnPortion>();
    queue.Enqueue(new ColumnPortion(0, new DirectionVector(1, 0), new DirectionVector(1, 1)));
    while (queue.Count != 0)
    {
        var current = queue.Dequeue();
        if (current.X >= radius)
            continue;
        ComputeFoVForColumnPortion(
            current.X,
            current.TopVector,
            current.BottomVector,
            isOpaque,
            setFieldOfView,
            radius,
            queue);
    }
}

The action of the main loop is straightforward. We make a work queue. We know that all of column 0 is in the field of view and that its top and bottom vectors are the lines emanating from the origin that bound the entire octant. We put that on the work queue. We then sit in a loop taking work off the queue and processing each portion of the column. Doing so may put arbitrarily more work on the queue for the next column. Since the work queue is a queue, we guarantee that we complete one column before we start working on the next; this makes the action of the algorithm similar to that of the description of the algorithm.

The attentive reader will have noticed that we've already made a very interesting choice that actually fails to correctly implement the stated algorithm. If the column portion on the queue is outside of the radius of the field of view then we discard it without processing it. This guarantees that the algorithm will terminate, and also makes sure that we don't do unnecessary work computing a column that is entirely outside of the field of view. That in of itself is fine; the interesting choice is that the comparison is

if (current.X >= radius)

and not

if (current.X > radius)

If we are asked for a field of view of radius six we do not actually make any cells in column six visible even though exactly one of them might be visible -- namely, the cell at (6, 0). Every other cell in that column is more than six units away from the origin. Why make this choice?

Aesthetics. Suppose there are no obstacles, and we compute the field of view of radius six for all eight octants. The resulting field of view will look like this:

       O
    OOOOOOO
   OOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOO@OOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
   OOOOOOOOO
    OOOOOOO
       O

Which looks bizarre. The curvature of a circle by definition should appear to be the same everywhere; this makes the circle look extremely pointy at four places. The boundary of a circle should be convex everywhere; if you imagine joining the center points of all the O's along the boundary they make for a convex hull except at eight points where the circle suddenly becomes concave. This is terribly ugly; to eliminate this ugliness we round off to an octagon by omitting the extreme column:

    OOOOOOO
   OOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOO@OOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
   OOOOOOOOO
    OOOOOOO

Much nicer. And the "error" is small, both in that it is only four points that are removed, and small in the sense that these are the four points that are the farthest-away points visible from the center; if you're going to eliminate points, those are the most sensible ones to take away.

Today we saw that a small rounding decision can have a big impact on the aesthetics of the algorithm; next time we'll dig into the first statement of ComputeFoVForColumnPortion and discover that subtle decisions about managing rounding errors can make a big difference in determining how the output looks to the player.

(*) Many implementations of this algorithm you find on the internet needlessly repeat all of the code eight times, once for each octant.

Shadowcasting in C#, Part One

Eric Lippert — Mon, 12 Dec 2011 15:13:00 GMT

I've always loved the "roguelike" games; perhaps you've played some of them. Those are the games where you get a top-down view of a tile-based world, and have as much real time as you like to make a choice of action. The canonical plot is to enter a dungeon, get to the bottom, retrieve the Amulet of Yendor, and make it back out of the dungeon with it. As you might expect, the original game with these characteristics was called "Rogue", and it has spawned many far more complex imitators. I'm particularly fond of Nethack, which I have completed twice in many, many hundreds of attempts. Hard game, Nethack.

The original Rogue had a very simplistic approach to lighting the dungeon: when you entered a lit room, you could see everything in the room regardless of whether it was behind an obstacle or not. More modern roguelike games have had increasingly more sophisticated algorithms for determining lighting that take obstacles, light intensity, and so on, into account. I was curious to see what different techniques existed for simulating realistic lighting in roguelike games, and I quickly found the collection of articles on RogueBasin on "Field of View".

Though I really appreciate the effort that went into writing these articles and the implementations -- in particular, the articles by Gordon Lipford, Björn Bergström and Henri Hakl -- I must say that I found a number of them difficult to follow. There are a lot of subtleties to these algorithms, and some of these articles use common important words from geometry (like "slope", "line" and "angle") in unusual and inconsistent ways. When I looked at various implementations of various algorithms that people had - again, very helpfully - published, I found a lot of good stuff but also some questionable programming practices and uncommented subtle choices.

I thought what I might do then, both for my own education and as a public service, is to describe one of the algorithms in excessive detail, implement it, and describe the various factors I considered when choosing implementation techniques.

First off, before we get into the details, here's a little Silverlight application that demonstrates what I mean. Click on the control below and then use the cursor arrow keys to move you (the "at" sign") around. Notice that you can only see so far -- about nine or ten squares in any direction -- and that obstacles cast shadows. In particular, notice how shadows behave in the region that contains a lot of tightly-spaced "pillars". Do the shadows behave realistically? While pondering that question, see if you can find the treasure and escape with it!

My first ever published roguelike game is apparently pretty easy.

Ray Casting

The algorithm most people first think of when considering how to do realistic lighting is "ray casting". That is, you imagine a circle around the player that is the limit of their light source. For each cell along the edge of the circle, imagine a ray of light emanating from the player towards the center of that cell. Work out what the first object, if any, the ray encounters along its way. All the cells that the ray passes through until the first obstacle are "visible"; the ray casting terminates at that first obstacle.

This algorithm can work, but it has a number of drawbacks. The major drawback is that if the circle is large then the number of rays that must be cast is large. Lots of rays means that the region close to the player is "visited" over and over again, which seems like it's bad for performance. It would be nice if every cell was processed only once, or, almost as good, that every cell is processed only a small number of times.

Shadow Casting

The algorithm I've actually implemented here is called "shadow casting"; the basic idea of the algorithm is that rather than tracking the individual rays of light, instead we assume that everything in the circle is lit and then figure out which cells are necessarily in shadow. I'm going to start by describing the algorithm geometrically, and then we'll see how the code implementation matches or deviates from the geometrical description.

So let's precisely define some terms here. The world consists of a two-dimensional Euclidean plane of points. Points are represented by pairs of real numbers of the form (x,y). We use the standard geometrical convention that x increases as we move "east" and y increases as we move "north". (*) The point (0,0) is called the "origin".

The world contains objects that inhabit this plane. Every object is centered on a "lattice point" (x,y) where x and y are both integers, and entirely fills the square bounded by (x-0.5, y - 0.5) in the bottom left corner and (x+0.5, y+0.5) in the top right corner. That region is called the "cell" associated with the lattice point.

The "field of vision" (FoV) problem is to determine which cells are "in line of sight" from a particular point (or, in some algorithms, from any point in a given cell) when given a collection of objects that can block sight and a maximum distance.

Without loss of generality, we're going to solve the FoV problem assuming that the "particular point" in question is the origin. As we'll see later, we can do a simple coordinate transformation to solve the problem at other points.

Direction Vectors

The primary tool we're going to use to solve this problem is the "direction vector". A "vector" is like a line segment that emanates from the origin. A vector has both a magnitude and a direction, but for our purposes we will only be concerned with the direction. The direction of a (non-zero-length) vector can be described in a number of ways:

Name a point other than the origin which the vector, when extended in a straight line from the origin, would pass through; that determines the direction of the vector.
Name a point (x,y) as above; divide the y coordinate of that point by the x coordinate to obtain the "slope". (**)
Draw a unit circle centered on the origin. Extend the vector, if necessary, to pass through the circle. Now measure the distance moving counter-clockwise from the point where the circle touches the x axis to the point where the circle touches the vector. That arc length is the angle of the vector measured in radians. Multiply by 180 / pi to get the angle in degrees.

We could use any of these methods. The disadvantage of the "slope" and "angle" methods is that in our application, slopes and angles will often be fractions that cannot be represented exactly in floating point arithmetic; it would be nice to be able to do all the arithmetic exactly. (Another disadvantage is that slopes increase to infinity as the vector angle approaches 90°, though as we'll see, we'll actually never be working with vectors whose slopes are larger than one or smaller than zero.) In our application it turns out that all the vectors we deal with will pass through a lattice point. We'll therefore use the "name a point" mechanism for characterizing a direction vector.

Here we have a picture illustrating the situation so far. The transparent grey box represents the cell centered on the origin. The filled-in grey box represents an object filling cell (2, 1). The red line represents a direction vector emanating from the origin and passing through (5, 1). (Click on any graph for a larger image.)

The Basic Idea of the Algorithm

The basic idea of the algorithm goes like this:

We've already said that without loss of generality, we're going to solve the FoV problem assuming that the cell is the origin. Furthermore, we're going to solve the problem only on octant zero of the plane. If you imagine direction vectors at 0°, 45°, 90°, 135°, 180°, 225°, 270° and 315° degrees, you see that those eight vectors divide the plane into eight "octants": (***)

If we can solve the problem in octant zero then we can solve the problem in every other octant by simply reflecting the desired octant into octant zero. For example, to compute FoV in octant seven we could "reflect" all the points in octant seven through the x axis, and hey, now we're in octant zero again.

So, how are we going to solve the problem in octant zero? We will divide the cells whose centers fall into, or on the edges of this octant into columns: (****) Here we see columns zero through six; three of the columns are occupied by opaque cells. The question is, of these cells which are within six units of the origin such that an observer at the origin would have the ability to see the cell?

We're going to go column by column, left to right. Within each column we are going to scan from top to bottom. We start with a pair of vectors. The pair of vectors represents a region of the world that is not in shadow.

We start off with the vectors (1,0) and (1,1) because the whole of column zero is in the field of view. Remember, we are interested in the vectors only for their direction, not their magnitude, so I'm going to extend the vectors along their directions indefinitely. When processing column zero, this is the situation:

The "upper" vector is in blue and the "lower" vector is in green. The cells that fall between these vectors are the ones thus far believed to be in the field of view of the origin for this octant. We make a note that cell (0,0) in column zero is visible from column zero.

We then scan column one from top to bottom. We do not find anything that would block the view, so the vector state is unchanged after scanning column one, and every cell in column one is visible from the origin. Same for column two. However, when we come to column three we immediately find at the top of column three an opaque cell, but below it there is a transparent cell. We therefore lower the upper vector to account for the fact that the cell at (3,3) is possibly blocking the view of something in a later column.

We do not find anything else opaque in column three, so after processing column three the state of the algorithm now looks like this: (known-to-be-visible cells are marked with a sunburst.)

All of column three was in view, including the opaque cell. But now the upper vector has been lowered. When we start scanning column four, we start from the top, but the top cell in column four is now outside of the region enclosed by the vectors. It is not visible. We start scanning column four from cell (4, 3) downward. We discover that there is an opaque cell at the bottom of column four, so this time we raise the lower vector. At the end of processing column four the state of the algorithm is:

Notice something interesting: the viewable angle is getting smaller and smaller, so even though the columns are getting taller, the actual number of cells we're scanning per column is not growing. This means that it is likely that this algorithm has better performance the more obstacles there are! That's a nice property to have.

Now we come to the first really interesting part of the algorithm. Is cell (5,4) visible? From a strict physics perspective, clearly no portion of cell (5, 4) is visible from an observer exactly at the origin. Any possible line-of-sight vector from the origin either goes through the opaque cell at (3,3) or the opaque cell at (5,3). However, we are scanning each column from the top down; we haven't processed cell (5, 3) yet. Another interesting question is: suppose cell (5,3) were transparent; then would cell (5,4) be visible? Its lower right corner would have line of site to the origin, but its center would not. Does that matter? Fortunately, we are saved from having to answer this question because the cell (5, 4) is out of range; we can only see for six units and (5,4) is farther away than that from the origin. However, in general we will need to consider this matter more carefully.

By similar logic, we need to decide whether cell (5,0) is visible or not. Clearly from a "physics" perspective again it is not; it is entirely blocked by cell (4, 0). There might however be implementation or gameplay reasons why we'd want to fudge things a little and allow (5,0) to be visible. We'll come back to these points and consider them in detail when we dive into the exact implementation. For now, let's suppose for the sake of presenting the idea of the algorithm than somehow a miracle happens and we consider cell (5, 3) to be the uppermost visible cell of column five and (5,1) to be the lowermost visible cells of column five. As we did when processing column three, we discover that there is a visible opaque cell above a visible transparent cell, and so we lower the upper vector:

And now there are no cells left that are both less than six units from the origin and have line-of-sight; we're done. The field of view has been determined.

Let's take a briefer look at another scenario. Suppose we have already processed a bunch of columns:

Everything in column four is visible. But what are the vectors to compute the visible cells of columns five and six? We need two sets of vectors now!

When computing the FoV of columns five and six we'll consider both pairs of vectors as possibly containing viewable area. Naturally, if there were larger columns with many small gaps in them then we could end up generating even more vector pairs.

That's the basic idea of the algorithm; next time we'll try to actually implement it in C# and see what difficulties we run into.

(*) The fact that many computer display systems do not follow this convention is one of the things that makes it unnecessarily difficult to reason about code that implements these lighting systems. Some implementations assume that when given a rectangle with corners (0,0) and (1,1) the origin is the top left corner, not the bottom left corner as would be conventional geometrically. I think the best thing to do is to follow the geometrical convention, and do a transformation to the display coordinate system in code specifically tasked with making that transformation.

(**) Some implementations of this algorithm that you find on the internet define the "slope" as the negative of the "run" divided by the negative of the "rise". Slope is more conventionally defined as the "rise" divided by the "run", as I do here.

(***) Some implementations of this algorithm that you find on the internet define octant zero as what I here define as octant two. I think it is more consistent with general practice to number the octants counter-clockwise starting from the x-axis, just as angles are conventionally measured counter-clockwise from the x axis.

(****) Some implementations call these collections of cells "lines", which is a bit confusing; they are not geometric lines, they are columns of cells.

Roguelike people

Eric Lippert — Fri, 09 Dec 2011 17:35:10 GMT

No technology today. Rather, some advice.

I don't know if there's some sort of grifter convention going on, but I have seen four different short-con artists operating in Wallingford, the neighbourhood of Seattle where I live, in the last three days. Though that might be a slight mischaracterization. One of them was selling from a bag Christmas ornaments that they'd clearly just now shoplifted from Walgreens, which is not much of a "con". One of them might have plausibly actually been panhandling. But the other two were clearly running short cons, and even two is a lot for Wallingford in two days.

For those of you readers not intimately familiar with the short con, let me break it down for you. There are two basic kinds of confidence scams, "short" and "long". The short-con artist -- the "grifter" -- aims to tell the target -- the "mark" -- a story that convinces the mark to part with a small amount of money immediately, and then the grifter disappears forever from the mark's life. (*) They don't care if the mark realizes five minutes later that they've been taken by a short con; the grifter has got their five dollars and has moved on to the next mark. The long-con artist aims to gain the confidence of the mark for a long period of time, take them for a large amount of money, and maintain the mark's confidence even after the scam is over. "The Sting" is a great movie for seeing both the short con and the long con in action; the movie opens with a "Pigeon Drop" short con and ends with a "Big Store" long con.

The short cons that I've see around Wallingford over the last ten years are extraordinarily weak; they're barely a step up from panhandling. The guy who stopped me on the street last night was a perfect example: "hey buddy, can you help me out, I've lost my ferry ticket, well, it's not lost, it's at home on the coffee table but I can't get there in time and my roommate isn't picking up the phone, and I need to be at the ferry terminal to get to my brother's place, he's broken his leg, but here I am in Wallingford because I was having coffee with my friend Cindy at that bakery behind you and we ended up talking longer than I expected, but she's on the bus to Northgate now so she can't help me, but if you can loan me the money for the ticket I'll be back here tomorrow, hey, you can call me on my cell phone and we can arrange to meet, let me tell you my cell phone number and you can call me right now to verify that it's real" and that's when I stopped him, because I kid you not, all that came out of him without him letting me get a word in.

The sob-story short cons are all the same: I've lost my ferry ticket (but strangely enough we're nowhere near the ferry terminal), my car is out of gas and I need to get to my sick mother (but strangely enough the car is nowhere nearby), I'm almost out of my medication (here's the pill bottle, see?) but I've lost my wallet and I can't pay the pharmacy fee, can you help a brother out?

So, a word of advice to you guys:

People who mean you well do not stop you on the street. They ignore you, the same way you ignore strangers on the street whom you do not intend to defraud.
If the story sounds rehearsed, that's because it is.
You are under no obligation to give money to any stranger on the street who spins you a line.
Call the police non-emergency line; large cities may have a "bunco squad" that is interested to know where short-con artists are operating.

And a word of advice to any con artists out there who might be reading my blog about programming language design:

Too many details! Always you guys with your too many details! Look at all the irrelevant details the con artist gave me yesterday. Real people in trouble don't do that. Con artists always think that details add veracity but they do not; they make it sound like you're trying to convince me of a lie.
Giving the whole spiel at once, and having your props already in hand -- the cell phone, the gas can, the pill bottle -- make you seem like you are performing a monologue on stage. It is not realistic. Try a more naturalistic approach.
Consider giving up the con and go to honest panhandling. It's safer. Non-aggressive panhandlers I ignore; grifters I report to the police so that they can be arrested.

Next time: We'll finish up 2011 with rogues of a different sort!

(*) They hope; I in fact have been the target of the same con artist with the same "pill bottle" story twice, once in Wallingford and once in the parking lot of a vegetarian Chinese food restaurant by Seattle Center. He was even wearing the same t-shirt both times -- dark blue with "PUNK ROCK!" written on it in big white letters; an odd choice of costume, I thought. It certainly was a great identifying detail when I reported him to the police. I guess you can't remember everyone you meet when you're in that line of work. The off-my-meds punk rock enthusiast's story was utterly unconvincing the first time; the second time, it was just sad. I kinda hope to meet the guy a third time; I'd be interested to find out if this story actually works.

So many interfaces, part two

Eric Lippert — Thu, 08 Dec 2011 15:51:00 GMT

In my earlier article from April 2011 on interface implementation I noted that C# supports a seldom-used feature called "interface re-implementation". This feature is useful when you need it but unfortunately is one of those features that can bite you if you use it incorrectly or accidentally.

Every interface method of every interface you implement in a class or struct has to be "mapped" to a method in the type (either a method directly implemented by the type or a method that the type obtained via inheritance, doesn't matter) that implements the interface method. That's pretty straightforward. The idea of interface re-implementation is basically that if you re-state on a derived class that you implement an interface that was already implemented by a base class, then when analyzing the derived class, we abandon all the information we had previously computed about the "mappings" in the base class.

This is useful particularly in the case where a base class does an explicit implementation of an interface and you would like to replace its implementation with your own:

interface I
{
void M();
}
class Echo : I
{
void I.M() { ... }
}
class Foxtrot : Echo, I
{
void I.M() { ... }
}

Echo does not have a public, protected, or internal virtual method M that Foxtrot can override; if Foxtrot wants to replace Echo's behaviour then its only chance to do so is via interface re-implementation.

Like I said, that can be useful but you should be aware that this is a sharp tool that can cut you in some situations. Here's a situation we found ourselves in recently on the Roslyn team where we managed to cut ourselves with our own tool!

We have two very similar interfaces, IInternal and IPublic. We intend that our component be used by the public -- you guys -- via the IPublic interface. As an internal implementation detail, we also have an internal interface IInternal that we use to communicate with a particular subsystem that has been provided for us by another team within Microsoft. The methods of IInternal are a superset of the methods of IPublic:

internal interface IInternal
{
void M();
void N();
}

public interface IPublic
{
void M();
}

public abstract class Bravo : IInternal (*)
{
// These are our internal workings that we use to communicate
// with our private implementation details;
// they are explicitly implemented methods of an internal interface,
// so they cannot be called by the public.
void IInternal.M() { ... }
void IInternal.N() { ... }
}

public abstract class Charlie: Bravo, IPublic
{
// class Charlie, on the other hand, wants to expose M both
// as a method of Charlie and as an implicit implementation
// of IPublic.M:
public void M() { ... }
}

public sealed class Delta : Charlie, IInternal
{
// Delta is a derived class of Bravo via Charlie; it needs to
// change how IInternal.N behaves, so it re-implements the
// interface and provides a new, overriding implementation:
void IInternal.N() { ... }
}

This is wrong. There are three methods that Delta must provide: IInternal.M, IInternal.N and IPublic.M. IPublic.M is implemented in Delta by Charlie, as usual. But we are doing an interface re-implementation of IInternal, so we start fresh. What is the implementation of IInternal.N? Obviously the explicitly implemented method in Delta. But what is the implementation of IInternal.M? It's the public method in Charlie, not the invisible-to-everyone explicit method in Bravo. When an instance of Delta is passed off to the internal subsystem it will now call the public method Charlie.M instead of the correct code: the explicit implementation in Bravo.

There is no way for Delta to get to Bravo's implementation of IInternal.M; that is a private implementation detail of Bravo. The interface re-implementation pattern is simply a bad technique to use here; the scenario is too complicated for it to work without you cutting yourself accidentally. A better pattern is to have only one implementation of the internal interface that then defers to an internal-only method:

public abstract class Bravo : IInternal
{
void IInternal.M() { this.InternalM(); }
internal virtual void InternalM() { ... }
void IInternal.N() { this.InternalN(); }
internal virtual void InternalN() { ... }
}

public abstract class Charlie: Bravo, IPublic
{
public void M() { ... }
}

public sealed class Delta: Charlie
{
internal override void InternalN() { ... }
}

And now Delta can even call base.InternalN if it needs to call Bravo.InternalN.

Once more we see that designing for inheritance is trickier than you might think.

(*) People are sometimes surprised that this works. The accessibility domain of a derived class must be a subset of the accessibility domain of its base class; that is, you cannot derive a public class from an internal base class. The same is not true of interfaces; interfaces can be as private as you like. In fact, a public class can implement a private interface nested inside itself!

What's the difference? Remainder vs Modulus

Eric Lippert — Mon, 05 Dec 2011 15:05:00 GMT

Today, another episode of my ongoing series "What's the difference?" Today, what's the difference between a remainder and a modulus, and which, if either, does the % operator represent in C#?

A powerful idea that you see come up in mathematics and computer programming over and over again is the idea of an equivalence relation.

First off, let's define (again) what a "relation" is; a relation is a function that takes two things, say, integers, and returns a Boolean that says whether the two integers are "related" or not. For example, "is greater than" is a relation. It takes two integers, say 4 and 2, and returns a Boolean that indicates whether 4 "is greater than" 2 or not; in this case, yes, it is.

An "equivalence relation" is a relation which is reflexive, symmetric, and transitive. That is, if ∾ is an equivalence relation, then:

Reflexive: X∾X is true for any X
Symmetric: X∾Y = Y∾X for any X and Y
Transitive: if X∾Y and Y∾Z are both true then X∾Z is also true.

Clearly "is greater than" is not an equivalence relation; though it is transitive, it is neither symmetric nor reflexive. "Have the same sign" on the other hand, is an equivalence relation; all negative numbers are equivalent to each other, all positive numbers are equivalent to each other, and zero is equivalent to itself.

An equivalence relation partitions the set of integers into (possibly infinitely many) equivalence classes. For example, let's consider the equivalence relation A∾B if and only if A-B is evenly divisible by 4. So 0∾4 is true and -86∾2 is true, and so on. We can make four "equivalence classes" where every integer is in exactly one class, and every integer in each class is related to every other integer in that class. The classes are {0, 4, -4, 8, -8, 12, -12, ... }, {1, -3, 5, -7, 9, -11, ... }, {2, -2, 6, -6, 10, -10} and {3, -1, 7, -5, 11, -9, ... }.

These classes are classes of "equivalent" integers, where "equivalence" means "is equally good in terms of determining whether the relation holds". Equivalence classes are often identified by a "canonical" member; in the case of the equivalence classes of "integers that are congruent modulo four", the canonical members are usually taken to be 0, 1, 2 and 3.

One can of course generalize this; given any positive integer n you can create the equivalence relation "A∾B if and only if A-B is evenly divisible by n". This defines n equivalence classes, which are usually identified by the canonical elements 0, 1, ..., n-1. The relation is usually written (somewhat clumsily, in my opinion) as A ≡ B mod n and is read as "A is congruent to B modulo n".

It is very tempting to think of the A % M operator in C# as meaning "partition the integers into M equivalence classes and give me the canonical element associated with the class that contains A" operator. That is, if you say 123 % 4, the answer you get is 3 because 123 ≡ 3 mod 4, and 3 is the "canonical" element associated with the equivalence class that contains 123.

However, that is not at all what the % operator actually does in C#. The % operator is not the canonical modulus operator, it is the remainder operator. The A % B operator actually answer the question "If I divided A by B using integer arithmetic, what would the remainder be?"

In order to work out what the remainder is, we need to first clearly define our terms. The divisor, dividend, remainder and quotient must obey the following identity:

dividend = quotient * divisor + remainder

Now, that is not enough to uniquely determine an answer to the question of what, say, 123 / 4 is. 123 = 30 * 4 + 3 is the desired solution, but 123 = 6000 * 4 - 23877 is also a possible solution. We need to put restrictions on the quotient and remainder.

Naively we might say that the lesser quotient is the better quotient. But of course that does not help either, because 123 = 1 * 4 + 119 is also perfectly good, and 1 is less than 30, but 1 is not a better quotient. We need some better rules; the rules we've come up with to determine the quotient and remainder (assuming that the divisor and dividend are valid, that is, we're not dividing by zero and so on) are:

* If there is any quotient that makes the remainder zero then that's the quotient and the remainder is zero, and we're done.
* Otherwise, do the division in all non-negative integers. Take the largest quotient that keeps the remainder positive.
* If the divisor and dividend have opposite signs then make the quotient negative.
* The remainder can now be worked out so as to obey the identity.

The net result here is that integer division rounds towards zero. That should make sense; we want 123/4 to be 30 with a remainder of 3, not 31 with a remainder of -1. Similarly, we want -123/4 to be -30, not -31! It would be bizarre to say that 4 goes into 123 30 times but goes into -123 -31 times! One expects that changing the sign of a term changes the sign of the result; it does not change the magnitude of the result.

If -123/4 is -30, then what is the remainder? It must obey the identity, so the remainder is -3. That is not the canonical item associated with the equivalence class that contains -123; that canonical item is 1.

It's important to remember this fact when doing things like balancing a hash table:

int bucketIndex = item.GetHashCode() % bucketCount;

or determining if a number is odd:

var oddNumbers = someSequence.Where(x => x % 2 == 1);

The first is wrong because the array index can be negative if the hash code is negative; the second does not classify -123 as an odd number. The % operator does not give the canonical modulus, it gives the remainder.

Why have a stack?

Eric Lippert — Mon, 28 Nov 2011 18:39:03 GMT

Last time I discussed why it is that we have all the .NET compilers target an "intermediate language", or "IL", and then have jitters that translate IL to machine code: because doing so ultimately reduces the costs of building a multi-language, multi-hardware platform. Today I want to talk a bit about why IL is the way it is; specifically, why is it a "stack machine"?

To begin with, what is a "stack machine"? Let's consider how you might design a machine language that could describe the operation of adding together two integers to make a third. You could do it like this:

add [address of first addend], [address of second addend], [address of sum]

When the machine encounters this instruction it looks up the values of the addends stored in the two addresses, somehow adds them together -- how it does so is its business -- and stores the result in the third address.

You might instead say that there is a special region of memory called the "accumulator" which knows how to add a given value to itself:

clear_accumulator
increase_accumulator [address of first addend]
increase_accumulator [address of second addend]
save_accumulator [address of sum]

Or, you could say that there is a special region of memory called the "stack" which can grow and shrink; you get access to the items on the top:

push_value_at [address of first addend]
push_value_at [address of second addend]
add
pop_value_into [address of sum]

The "add" instruction takes the two values off the top of the stack, somehow adds them, and then puts the result back on the stack; the net result is that the stack shrinks by one.

A virtual machine where most of the instructions are of this third form is called a "stack machine", for obvious reasons.

IL specifies a stack machine, just like many other virtual machines. But most hardware instruction sets actually more closely resemble the second form: registers are just fancy accumulators. Why then are so many virtual machines specifying stack machines?

There are several reasons, but again, it primarily comes down to lowering costs. Stack machines are very easy to understand, they are very easy to write a compiler front-end for, they are easy to build interpreters for, they are easy to build jitters for, and they provide a concise abstraction for the common case. The common case is that the result of any particular operation is only going to be of interest for a brief period.

Imagine, for example, if we chose the first strategy for IL, and then had to compile an expression like x = A() + B() + C(); What would we have to do in the first case? Something like this:

create_temporary_storage // for result of A()
call A(), [address of temporary storage]
create_temporary_storage // for result of B()
call B(), [address of temporary storage]
create_temporary_storage // for result of first addition
add [address of first temporary storage], [address of second temporary storage], [address of third temporary storage]
...

You see how this goes? The IL is getting huge, and all so that we can keep track of precisely which memory locations are used to store values that we are about to never care about again. A stack abstraction lets the stack implementation deal with the temporary storages; in a stack machine, the same code looks something like:

push [address of x]
call A() // implicitly creates a temporary storage by pushing the result on the stack
call B()
add
call C()
add
store // store result on top of stack in address just below it.

The code is much smaller and much easier to understand. A stack machine is a very simple way to describe a complex computation; by being able to write code for such a simple machine, it lowers the cost of making a compiler. And not only is it easier to write compilers and jitters that target simple stack machines, it is easier to write other code analysis tools as well. The IL verifier, for example, can quickly determine when there is a code path through a method that, say, misaligns the stack, or passes the wrong types of arguments to a method.

Why IL?

Eric Lippert — Fri, 18 Nov 2011 17:22:17 GMT

One of the earliest and most frequently-asked questions we got when we announced the Roslyn project was "is this like LLVM for .NET?"

No, Roslyn is not anything like LLVM for .NET. LLVM stands for Low-Level Virtual Machine; as I understand it (admittedly never having used it), compiler "front ends" take in code written in some language -- say C++ -- and spit out equivalent code written in the LLVM language. Another compiler then takes the code written in the LLVM language and writes that into optimized machine code.

We already have such a system for .NET; in fact, .NET is entirely built upon it and always has been, so Roslyn isn't it. The C#, VB and other compilers take in programs written in those languages and spit out code written in the Common Intermediate Language (CIL, or also commonly MSIL or just IL). Then another compiler -- either the jitter, which runs "just in time" at runtime, or the NGEN tool which runs before runtime -- translates the IL into optimized machine code that can actually run on the target platform.

I'm occasionally asked why we use this strategy; why not just have the C# compiler write out optimized machine code directly, and skip the middleman? Why have two compilers to go from C# to machine code when you could have one?

There are a number of reasons, but they pretty much all boil down to one good reason: the two-compilers-with-an-intermediate-language system is much less expensive in our scenario.

That might seem counterintuitive; after all, now we have two languages to specify, two languages to analyze, and so on. To understand why this is such a big win you have to look at the larger picture.

Suppose you have n languages: C#, VB, F#, JScript .NET, and so on. Suppose you have m different runtime environments: Windows machines running on x86 or x64, XBOX 360, phones, Silverlight running on the Mac... and suppose you go with the one-compiler strategy for each. How many compiler back-end code generators do you end up writing? For each language you need a code generator for each target environment, so you end up writing n x m code generators.

Suppose instead you have every language generate code into IL, and then you have one jitter per target environment. How many code generators do you end up writing? One per language to go to IL, and one per environment to go from IL to the target machine code. That's only n + m, which is far less than n x m for reasonably-sized values of n and m.

Moreover, there are other economies in play as well. IL is deliberately designed so that it is very easy for compiler writers to generate correct IL. I'm an expert on the semantic analysis of the C# language, not on efficient code generation for cellular phone chipsets. If I had to write a new backend code generator for every platform the .NET framework runs on, I'd be spending all my time doing a bad job of writing code generators instead of doing a good job writing semantic analyzers.

The cost savings go the other way too; if you want to support a new chipset then you just write yourself a jitter for that chipset and all the languages that compile to IL suddenly start working; you only had to write *one* jitter to get n languages on your new platform.

This cost-saving strategy of putting an intermediate language in the middle is not at all new; it goes back to at least the late 1960's. My favourite example of this strategy is the Infocom Z-Machine; the Infocom developers wrote their games in a language (Zork Implementation Language) that compiled to an intermediate Z-Code language, and then wrote Z-Machine interpreters for a variety of different platforms; as a result they could write n games and have them run on m different platforms at a cost of n + m, not n x m. (This approach also had the enormous benefit that they could implement virtual memory management on hardware that did not support virtual memory natively; if the game was too big to fit into memory, the interpreter could simply discard code that wasn't being used at the moment and page it back in again later as needed.)

Next time I'll talk a bit about why IL is specified the way it is.

A C# Reading List

Eric Lippert — Thu, 10 Nov 2011 19:47:00 GMT

Just a couple of quick links today.

First: One of the questions I get most frequently is "can you recommend some good books about learning to program better in C#?" The question is usually asked by a developer; the other day I was surprised to get that question from one of the editors of InformIT. She was kind enough to post the list on the InformIT web site, so check it out.

Second: Bill Wagner posts his own follow-up article on my recent MSDN magazine article about async/await. Check it out.

Breaking changes and named arguments

Eric Lippert — Mon, 07 Nov 2011 19:00:15 GMT

Before I get into the subject of today's post, thanks so much to all of you who have given us great feedback on the Roslyn CTP. Please keep it coming. I'm definitely going to do some articles on Roslyn in the future; the past few weeks I have been too busy actually implementing it to write much about it.

We introduced "named and optional arguments" to C# 4.0; that's the feature whereby you can omit some optional arguments from a method call, and specify some of them by name. This makes the code more self-documenting; it also makes it much easier to deal with methods in legacy object models that have lots and lots of parameters but only a few are relevant. The most common commentary I've seen about the "named" side of that feature is people noting that this introduces a new kind of breaking change. The commentary usually goes something like:

Suppose you are making a library for consumption by others. Of course if you change details of the public surface area of the library, you can break consumers of the library. For example, if you add a new method to a class then you might make an existing program that compiled just fine now turn into an error-producing program because a call to the old method is now ambiguous with a call to the new method. In the past, changing only the name of a formal parameter was not a "breaking change", because consumers always passed arguments positionally. Recompilation would not produce different results. In a world with named arguments though, it is now the case that changing the name of a formal parameter can cause working code to break.

Though that commentary is certainly well-intentioned and informative, it is not quite accurate. The implication is that this breaking change is something new, when in fact it has always been the case that a library provider could break consumers by changing only the name of a formal parameter. Visual Basic has always supported calling methods with named parameters. In the past, changing the name of a formal parameter was a breaking change for any consumers using Visual Basic, and that's potentially a lot of people. Now it becomes a potential breaking change for even more users. Adding a new feature to C# doesn't change the fact that the risk was always there!

Library providers should already have been cautious about changing the names of formal parameters, and they should continue to be cautious now.

The Roslyn Preview Is Now Available

Eric Lippert — Wed, 19 Oct 2011 21:00:00 GMT

I am super excited to announce that the Roslyn project code is now sufficiently coherent that we can start showing it to customers!

But I am getting ahead of myself somewhat. What is this "Roslyn" project?

Here's the deal. We've got these great premiere languages for .NET development, C# and Visual Basic. Obviously the compilers need to do considerable lexical, syntactic and semantic analysis of the code in order to first off, produce IL out the back end of the compiler, and second, produce all of that on-the-fly analysis needed for syntax colourization, IntelliSense, automatic refactorings, and so on. We do all this work to produce an analysis of the code, but we do not let you, the customer, take advantage of that analysis engine directly. Rather, you just get to see how the compiler and IDE teams make use of that analysis engine.

This is unfortunate. When I look around just Microsoft I see a dozen little C# and VB language lexers, parsers and semantic analyzers that different teams have written to meet their own needs. There have got to be many more out there in the wild. This is a problem we can solve once for you, and then let you make use of the analysis engine for your own purposes.

Furthermore, it became clear as we were designing the next versions of C# and VB that the existing compiler infrastructure built in unmanaged C++ was not going to meet our needs without a major overhaul at some point. We want a compiler infrastructure that supports both new interesting language features, and more dynamic ways to interact with your code as you're developing it.

To achieve all those goals we decided to join the C# and VB teams together, and then split the resulting team apart into two subteams: one concentrating on upcoming C# and VB features like async/await, and one concentrating on the long-term future of the compiler and tools infrastructure. The latter team is codenamed "Roslyn", and that's the team I've been working on for some time now.

We are now at the point where the Roslyn codebase is sufficiently fully-featured and coherent that it makes sense to start getting feedback from customers. You can download the Roslyn Community Technology Preview as of right now; it installs as an extension to Visual Studio 2010 SP1. We would love to get as much constructive feedback from you as possible; rather than leaving comments here, please leave comments on the Roslyn Forum. That way we'll be sure that our crack team of program managers sees the feedback and can aggregate it all appropriately. We're making a huge investment here and want to know that we're heading in the right direction to make something insanely great for you guys.

What we're looking for feedback on primarily is the set of code analysis APIs we're exposing to you guys. The APIs themselves as a set of classes with methods and so on, are now reasonably complete; we do not anticipate making major changes to the infrastructure for Symbols, SyntaxNodes and so on unless we hear loud feedback that we have gone with the wrong model. Does this set of APIs meet your needs? What parts do you like, and what would you like to be different?

I want to make sure that we're setting expectations appropriately here. This is a very early pre-beta-quality release of some extremely complicated software. Keep that in mind as you are using it. The lexical and syntactic analysis engines that underlie those APIs are pretty much complete. The semantic analysis engine that sits behind the semantic analysis APIs is right now nowhere near done; on the C# side we are still missing semantic analysis of major feature areas like query comprehensions, attributes, iterator blocks, optional arguments, dynamic, async/await and unsafe as well as a bunch of control flows; VB is in a similar state. Extension methods, method type inference, lambdas, and generics are working, so LINQ queries in the "method call" syntactic form should work.

Also, the performance of the entire analysis engine is not as high as we would like; we have done some performance tuning but there is more to come.

In short, you're getting the earliest possible build we could reasonably show to people to get good feedback; we are still a long way from being done. We are absolutely not announcing any dates or "ship vehicles" for a final release; even if I knew - which I don't - I couldn't tell you, so don't ask.

We are also as a part of this release shipping a preview of a new "interactive scripting" environment for C# that will allow you to play around with code in a more experimental and free-form way, like you can do in F# and other "Read-Eval-Print Loop" languages. Give it a spin and let us know what you think! (Sorry, no VB version of this feature is available with the CTP.)

Over the next few months I'll do some more posts describing the interesting technology we've built behind-the-scenes to make the C# and VB Roslyn code analysis engines work. For now, you can get more information on Roslyn at the following places:

Some helpful blog posts:

Fun stuff:

Wikipedia on Roslyn
We called it "Roslyn" because my office has a Northern Exposure. Ha ha ha!

Insanely great

Eric Lippert — Thu, 06 Oct 2011 15:42:33 GMT

I've never owned an Apple product; I haven't written Mac software professionally since working on the Mac version of Visual Basic briefly in 1994. Nevertheless, Steve Jobs inspired me every day. Wanting to make "insanely great" technology is one thing. Having someone prove, over and over again, that the insanely great is actually within our grasp is another thing entirely. Thank you, Steve.

Async articles

Eric Lippert — Mon, 03 Oct 2011 20:30:00 GMT

I am pleased to announce that MSDN Magazine is doing a special issue this month on the new "async-await" feature that we are working on for the next versions of C# and Visual Basic. If this subject interests you, see my introductory article for beginners, Mads Torgersen's article on how it works behind the scenes and Stephen Toub's expert-level article on async performance. And of course, for a much longer introduction to the topic, see my long series from earlier this year. If you want to try it out yourself, download the CTP build from the async CTP main page.

Please do keep the great feedback coming! If you have comments, questions or constructive feedback on any aspect of the new feature, please post it to the async forum. Thanks!

Keep it secret, keep it safe

Eric Lippert — Tue, 27 Sep 2011 16:30:08 GMT

A lot of people really love the idea of cryptography. To computer geeks like us there is nothing cooler than the idea that computing relatively simple arithmetic on a message can enable you to communicate secretly with anyone in the world, even if there are eavesdroppers. Unfortunately, this means that there are a lot of computer people out there who are enamoured with the idea of creating their own cryptosystems, or their own implementations of the cryptosystems invented by others. It also means there are a lot of software product managers who are convinced that security equals cryptography, and that their products will magically become "secure" if only there is more crypto in them. I've gotten a fair number of questions over the years about how to add crypto to applications -- a subject that I am actually not an expert on -- and most of the time the answer is "don't". Many times the question comes from a developer who, though an expert developer of applications in their line of business doesn't "get" the basic idea of cryptography. As a public service, let me lay it out for you. The fundamental idea of modern cryptography is this:

The strength of the security of a large quantity of data -- known as the "plaintext" -- against discovery or modification by a motivated attacker depends upon the security of a small quantity of data -- known as the "key". (*)

That is, modern crypto is essentially a form of mechanical advantage. With a gearing system or a lever you can turn a small motion into a large motion. With a strong cryptosystem you can turn the security of a 1 KB key file into the security of a 10 MB data file. Cryptosystems do not manufacture new security, any more than a lever manufactures new motion. Cryptosystems turn the security of one thing (the key) into the security of another much larger thing (the plaintext).

It is the failure to understand that fundamental idea that underlies most of the questions I get from non-crypto experts about implementing crypto in their applications. Non-crypto experts get enamoured with the math of the cryptosystem but that is not the part that provides the security. The part that provides the security is the security of the key. The cryptosystem itself (or its implementation) might be weak or strong, but even the strongest modern cryptosystem depends fundamentally on the correct management of the keys for its security.

Before the 1970's, all modern cryptosystems were "shared key" systems. That is, if Alice wanted to send a message to Bob over an insecure channel that had attackers attempting to either read or modify the message, then first Alice and Bob would somehow communicate a secret shared key over a secure channel. Once Alice and Bob both had the shared key, Alice could encrypt the message with the shared key, send it over the insecure channel, and Bob could decrypt it with the shared key. Bob would then have the plaintext message, but the eavesdropper would only have the encrypted message. (There are also techniques in shared-key systems whereby Bob could verify that no one tampered with the encrypted message while it was in the insecure channel.)

Clearly the security of this system depends entirely on there being a secure channel over which Alice and Bob can negotiate what their small shared key is. If they try to exchange the secret key over an insecure channel then an eavesdropper can determine what the secret key is, and it's no longer a secret. (As we'll see later, a more aggressive "man in the middle" can cause even more havoc.)

You might immediately wonder why Alice and Bob need to use crypto at all if a basic assumption is that they have a secure method for key exchange. Why not just use the required-to-be-secure channel for sending the unencrypted text? The point is that the secure channel might be extremely expensive, or it might be available only at certain times. For example, the "secure channel" might be that Alice and Bob meet for coffee in Seattle in their hidden underground bunker, decide on a secret key, and then Alice moves to Switzerland and Bob moves to the Cayman Islands, and they can no longer cheaply meet for coffee. But they can still communicate securely after their key exchange, even if they are no longer in the same room together.

The security of the system also depends upon them both Alice and Bob being able to keep that key a secret. If Alice or Bob reveals the key to a third party -- say Eve, the eavesdropper -- then Eve can discover the plaintext of every message sent over the insecure channel. Worse, if the key is discovered by Mallory -- the "man in the middle" modifying the message -- then she can not only discover the plaintext but can modify the plaintext, encrypt the modified message with the secret key, and send the fake message to Alice or Bob, purporting to be the other.

What about public key cryptosystems? Don't they solve this problem? Turns out, no. Now you have four key management problems. Let me explain:

The idea of a public key cryptosystem is that there are two keys. One, the private key, is kept secret. The other, the public key, is -- you guessed it -- public. A message encrypted with the public key cannot be decrypted with the public key, but it can be decrypted with the private key, and vice versa. Alice and Bob both have a key pair; they do not know each other's private keys, but they do know each other's public keys. To send a message to Bob, Alice encrypts it with her private key(**), and then encrypts that with Bob's public key. She sends the twice-encrypted message over the insecure channel to Bob. Bob decrypts it with his private key, and then decrypts the result with Alice's public key. Now he knows that only he could read the message, because only he has his private key. And he knows that it was not tampered with, because only Alice's public key could decrypt the message. Therefore the message was neither read by Eve nor tampered with by Mallory.

Like I said, we now have four key management problems whereas before we had one. Before, Alice and Bob had to securely exchange their private key and then keep it secret. Now Alice and Bob both have to keep their private keys secret. If Bob's private key is compromised then Eve can read any message sent by Alice to Bob. And if Alice's private key is compromised then Mallory can send a fake message to Bob purporting to come from Alice.

That's two; what are the other two key management problems? I completely glossed over the most important part of the system! The detail that the security of the entire system rests on is that bit above where I said "but they do know each other's public keys". Somehow they had to securely exchange public keys. Why's that?

Suppose Alice and Bob are sending each other their public keys. How do they do that? If they do it over an insecure channel, it does not matter if Eve can read the public keys. They are public, after all. But it matters very much if Mallory can modify the keys in transit! If Alice sends her public key to Bob over an insecure channel then Mallory can intercept the message and replace Alice's public key with Mallory's public key. Mallory now knows Alice's public key, and Bob believes that Mallory is Alice! When Alice sends a message to Bob, Mallory can intercept it and replace it with a different message encrypted with Mallory's private key and Bob's public key. Bob decrypts the message with his private key and Mallory's public key, believing it to be Alice's public key, and Mallory has tricked Bob into thinking that she is Alice.

Similarly, when Bob sends his public key to Alice, Mallory can intercept it and replace it with Mallory's public key. When Alice sends a message to Bob she encrypts it with her private key and Mallory's public key, thinking that it is Bob's public key. Mallory can intercept it, decode it with her private key, read the message, and re-send it along to Bob, encrypted with Bob's real public key.

Somehow there has to be a secure channel by which public keys are exchanged. Remember, the entire point of crypto is to turn the security of a small amount of data into the security of a large amount of data. If the keys aren't secure -- either because the private keys are compromised or the public keys are not correctly associated with their real owners -- then the communication is not secure at all.

This is not of theoretical concern; we have to solve this problem in real life. When you go to a web site that is going to take your credit card number, you want some assurances that first, no eavesdropper is going to be able to see that credit card number when it goes over the wire, and second, that when you send your credit card to a web site, you really are communicating with the real web site, not a fake hacker web site that looks just like it. You might not know the public key of the web site! Without a secure mechanism to obtain that public key, you might be obtaining the man-in-the-middle's public key.

This problem is in practice solved by both the client (you) and the server (the web site) agreeing to trust a third party called the Certifying Authority, or CA. When the web site sends you the certificate containing their name and public key, the certificate is encrypted with the CA's private key. By decrypting it with the CA's public key, you can verify that the CA vouches for that web site actually being associated with that public key. Of course, if you do not trust the certifying authority, or the web site does not obtain certification from that certifying authority, then the key negotiation fails and the browser gives you some error message about the certificate not being verified.

But hold on a minute. Now we have yet another key management problem. The CA has to keep their private key a secret, and the CA has to somehow tell you what their public key is without being attacked by a man in the middle purporting to be the CA! We seem to have not solved the problem at all, but rather just pushed it off another level. How do we finally solve this problem once and for all? Can we use even more crypto?

Nope. This is the point where the crypto stops. (***) It has to stop somewhere; again, the point of crypto is to turn the security of a small thing into the security of a large thing; that security has to come from somewhere originally, just as the energetic motion of a lever has to come from somewhere outside the lever mechanism. The secure transmission of the CA's public key is the piece that has to be accomplished without using any crypto. How you accomplish that is up to you; typically the operating system comes pre-installed with a list of known public keys of certifying authorities that have been verified independently by the operating system vendor. New CA "root" certificates can also be installed by your machine or network administrator. The CA roots are the organizations you trust to make security-impacting decisions on your behalf.

I seem to have strayed somewhat from my original point, but I hope I've made myself clear: the hard part of a secure design that uses crypto is not the math. When adding crypto to an application, the fundamental question you should be asking yourself is not "what math am I going to do on the plaintext to encrypt it?" The fundamental question is "how are my users going to generate keys, securely exchange secret keys or public keys, and keep the secret keys private?" The security of the entire system rests upon being able to leverage the secure generation and distribution of the keys into the security of the message, so solve the key management problem first.

------------------------

(*) A cryptosystem is strong or weak to the extent that it delivers on this fundamental goal. If the security of the message can be compromised without the user compromising the key then the cryptosystem is weak. The goal of modern crypto is to create cryptosystems that deliver on this promise.

(**) In a realistic scenario she encrypts a hash and appends that to the message, because that is higher performance. But let's gloss over that detail.

(***) Just to complete the sketch: the way HTTPS actually works is that a shared "session" key is securely exchanged between the client and the server. The shared key is then used to encrypt and decrypt all the messages sent between the client and the server. As we already discussed, to exchange that shared key we need a secure channel. To obtain a secure channel, the client and the server agree upon a mutually trusted CA. The server convinces the client that the agreed-upon CA vouches for the server's public key, and so the client now has the real public key of the server. The client can then suggest a shared session key to use for the rest of the communication, and send it to the server encrypted with the server's public key. So: the secure transmission of the shared session key relies upon (1) the secrecy of the server's private key, (2) the secrecy of the CA's private key, and (3) that the client and the server both have an accurate copy of the CA's public key, obtained through some non-crypto-based secure channel. The cryptosystem leverages the secrecy of two private keys and the successful transmitting of one public key into the security of the messages transmitted in the session. If any of those keys are compromised then the whole system falls apart. (To deal with that problem, CA's also provide the service of publishing a "revocation list" of servers that have lost control of their private keys, so that you know to not trust those guys.)

Inheritance and Representation

Eric Lippert — Mon, 19 Sep 2011 17:18:00 GMT

(Note: Not to be confused with Representation and Identity)

Here's a question I got this morning:

class Alpha<X>
where X : class
{}
class Bravo<T, U>
where T : class
where U : T
{
Alpha<U> alpha;
}

This gives a compilation error stating that U cannot be used as a type argument for Alpha's type parameter X because U is not known to be a reference type. But surely U is known to be a reference type because U is constrained to be T, and T is constrained to be a reference type. Is the compiler wrong?

Of course not. Bravo<object, int> is perfectly legal and gives a type argument for U which is not a reference type. All the constraint on U says is that U must inherit from T (*). int inherits from object, so it meets the constraint. All struct types inherit from at least two reference types, and some of them inherit from many more. (Enum types inherit from System.Enum, many struct types implement interface types, and so on.)

The right thing for the developer to do here is of course to add the reference type constraint to U as well.

That easily-solved problem got me thinking a bit more deeply about the issue. I think a lot of people don't have a really solid understanding of what "inheritance" means in C#. It is really quite simple: a derived type which inherits from a base type implicitly has all inheritable members of the base type. That's it! If a base type has a member M, then a derived type has a member M as well. (**)

People sometimes ask me if private members are inherited; surely not! What would that even mean? But yes, private members are inherited, though most of the time it makes no difference because the private member cannot be accessed outside of its accessibility domain. However, if the derived class is inside the accessibility domain then it becomes clear that yes, private members are inherited:

class B
{
private int x;
private class D : B
{

D inherits x from B, and since D is inside the accessibility domain of x, it can use x no problem.

I am occasionally asked "but how can a value type, like int, which is 32 bits of memory, no more, no less, possibly inherit from object? An object laid out in memory is way bigger than 32 bits; it's got a sync block and a virtual function table and all kinds of stuff in there." Apparently lots of people think that inheritance has something to do with how a value is laid out in memory. But how a value is laid out in memory is an implementation detail, not a contractual obligation of the inheritance relationship! When we say that int inherits from object, what we mean is that if object has a member -- say, ToString -- then int has that member as well. When you call ToString on something of compile-time type object, the compiler generates code which goes and looks up that method in the object's virtual function table at runtime. When you call ToString on something of compile-time type int, the compiler knows that int is a sealed value type that overrides ToString, and generates code which calls that function directly. And when you box an int, then at runtime we do lay out an int the same way that any reference-typed object is laid out in memory.

But there is no requirement that int and object be always laid out the same in memory just because one inherits from the other; all that is required is that there be some way for the compiler to generate code that honours the inheritance relationship.

------------

(*) or be identical to T, or possibly to inherit from a type related to T by some variant conversion.

(**) Of course that's not quite it; there are some odd corner cases. For example, a class which "inherits" from an interface must have an implementation of every member of that interface, but it could do an explicit interface implementation rather than exposing the interface's members as its own members. This is yet another reason why I'm not thrilled that we chose the word "inherits" over "implements" to describe interface implementations. Also, certain members like destructors and constructors are not inheritable.