Archgrove - Implicit Definition

It’s been a long time since I posted anything here, but as I only write when I have both time and something to say, it’s not that surprising. I’m moved to put fingers to keyboard today to discuss something I still get regular e-mails about - an old Decal plug-in, Magellan 2, for Asheron’s Call (for those who don’t recognise these terms, an older article series might be interesting).

The main function of Magellan 2 was as a dungeon mapping system - it would automatically generate real-time wireframe overviews of any dungeon as you walked around it. There’s nothing particularly amazing about it; indeed, retrospectively, a lot of how it worked was naive at best and bad at worst. However, a lot of people seemed to like it, and I still get about an email a fortnight asking for source code & technical information. So far, I’ve been sending out the code about once every 3 months, to give each person a chance to repair the code and publish something, alas to no avail. Hence, I figure it’s time to publish something more general and see what people can create.

Now, Magellan 2 did more than just map dungeons but the additional functionality (place search etc) is pretty trivial data management and nothing we’re interested in. We’ll be focusing on the map generation, but I’m not going to write this as a detailed set of technical specifications - more as a journey of creation suitable for all who are interested. Hopefully the information contained within, plus additional downloadable material will give people everything they need to recreate the work, if they want to.

Phase One : The problem

What we want: To create a client integrated real time usable map display of any dungeon a player wanders into, something that will help them both find their way around and allow them to explore the full depth of the dungeon (no more missed turns!).

What we we know: We have two data files, “cell.dat” and “portal.dat”, which form an archive of many thousands of smaller files. We also have some vague idea of how the AC client software deals with the problem - we know that when we enter a new dungeon, some data is downloaded and the “cell.dat” file gets larger. We also know, from our many years of dungeon crawling, that dungeons are very “modular” in design - they seem to be built out of standard components, reused many times within the dungeons.

What we can do: We can read the files contained in the cell.dat and portal.dat archive files. We can also, via Decal, draw onto the players screen, and find out their location and orientation in the world.

The challenge is set! Over the next few articles, we’ll see what we can create.

Zen made another small portal code change today, sadly breaking the usage checker (screen scraping is about as robust as a fine glass cricket bat). I’ve updated the code, but this is again a mandatory upgrade , so download now!.

A small update for the users of Zen Usage Checker. Version 1.1 is now uploaded, and supports the recent portal changes (as well as adding proxy support, and fixing a buglet with the pie chart rendering).

This is a mandatory upgrade (all previous versions have stopped working), so download now!.

OK, so we’ve all been busily tapping away at our keyboards trying to implement the rough design we came up with last time. Let’s have a look at one way of doing it (this is just one way; there are obviously many different methods).

    public class CallByFuture<T>
    {
        public delegate T CallResult();

        public static implicit operator T(CallByFuture<T> instance)
        {
            return instance.Result();
        }

        public static T operator ~(CallByFuture<T> instance)
        {
            return instance.Result();
        }

        private System.Threading.Thread workerThread;
        private T result;

        public CallByFuture(CallResult func)
        {
            workerThread = new System.Threading.Thread(delegate(object state) {
                ((CallByFuture<T>)state).result = func();
            });

            workerThread.Start(this);
        }

        public T Result()
        {
            workerThread.Join();

            return result;
        }
    }

The implementation has tried to stay as close to the design goals as possible; we have a generic class, parameterised by the return type of a delegate which the user will create (either implicitly through an existing function, or explicitly with an anonymous method). The construction spins up a thread which evaluates this delegate, and gives the result back to the enclosing CallByFuture class to be made public via a Result method which will block until the answer is available. For syntactic sugar, we allow the unary bitwise NOT operator as a shortcut to the Result method (so rather than a call to the result type T expressed by the CallByFuture being t.Result().Foo, we have simply (~t).Blah.

The use of operator~ as an “easy conversion” might seem rather strange – after all, the language supports explicit type conversion operators natively. It does not, however, support having both an implicit and explicit conversion operators for the same type; the people who actually read the code will have noticed the implicit conversion snuck in at the top of the class.

The implicit conversion is very useful – it allows you to use a CallByFuture in most cases you want a T without any additional syntax. However. I would personally probably flag its inclusion as “controversial ” in a code review mainly due to the excessive “magic” behind the conversion of complex types – an innocuous usage of a variable might entail a complex evaluation behind the scene (rather than the virtual no-op of just reference passing you were expecting) – it might even throw an exception. In our case, the worst that can happen is that it must wait until the result is evaluated (any exceptions will be thrown on the CallByFuture thread, and we’ll discuss them later). Total worst case, the evaluation locks because the CallByFuture delegate never completes.

Our implementation rules stated we wanted something we could “drop in” to existing programs, and the implicit conversion certainly aids in that so next time, we’ll look at mitigating the problems it raises as well as some usage examples to prove this really does work.

[Edit: Woops - forgot to actually include operator~]

Last time, we outlined an evaluation strategy known as “Call-by-future” and determined that it might (just might!) be useful in adding an easy to use concurrency feature to mainstream languages. Now we’re resolved to implement it, what features should we be aiming for in our implementation?

1. Easy to understand – the solution we come up with must be understandable by as many people as possible. This goes without saying for all code – we don’t want to create an un-maintainable monster that no one touches in their fear.
2. Type safety – We don’t want to throw away existing safeguards just to get a bit of convenience, as we’ll likely end up introducing bugs when using it.
3. Easy to begin using it in existing codebases – The point of this exercise was to come up with something people can use here and now, and just jump in with. If it requires a whole program redesign or an entirely new way of thinking, we’ve probably not done all that well.

So, how do we envisage this working? To comply with rule number 3 above, we want something that behaves as closely to normal parameter passing as it can – only we control the execution. Ideally, we’d be able to declare Foo using something like void Foo(callbyfuture int a) or similar, to indicate that the parameter would be evaluate using our call by future-by-future evaluation. Alas, we can’t add keywords to the complier – but – we can add types. How about void Foo(CallByFuture a)? We’re using the generics system to construct a CallByFuture type, indicating that the parameter evaluates to an int; this fulfils our 2nd requirement (type safety).

The other thing we need to do is find some method of “taking control” of parameter evaluation. That is, if I use the expression Foo(Bar()) in a C# program, the compiler will invoke it’s normal evaluation strategy and emit code that will first evaluate bar, then pass the result either by value or reference to Foo. We need to be able to step in and say “Whoa, don’t evaluate Bar() just yet – hold off!” so that we can evaluate it in the way we want without confusing the compiler.

Whilst we can’t control expression evaluation in general, we can control the evaluation of a group of expressions via a .net delegate (effectively a function pointer) – any list of expressions wrapped in a delegate, we can call “at will”. Now, manually creating a new delegate for every single parameter we wish to evaluate using call-by-future would be tedious in the extreme, and hence violate both rules 1 and 3 above. Luckily, in C# 2.0, a new feature was added – anonymous delegates. Using these, creating an “expression” whose evaluation we can control becomes as simple as delegate { return (expr); }. Not ideal, but fairly terse (and flexible – as we’ll soon see).

Having discussed how we see this all working, let’s head off and have the boring keyboard bashing session. Return soon for part 3, when we’ll have finished the implementation and be ready to take it for a road test!