Sunday, April 11, 2010

VB11 Wish List - Part 1

With the release of visual studio 2010 coming this week, it's high time to publish wish lists. The Visual Basic .Net of today has come a long way from the BASIC of yonder old days, and not all of it involves making the name longer. However, there's still so much that could be done, or could be done better. These are my wishes and my ideas, and hopefully they will affect Microsoft's decision process in some small way. Unfortunately, I have so many ideas there's no way they could all be implemented. Oh well, here we go!

#1) Public-Get/Private-Set and ReadOnly Auto Properties

One of the features introduced in VB10, and imported from C#, is auto properties. Unfortunately, VB10 auto properties are quite limited compared to their C# counterparts. It is impossible to specify an auto property with a private setter and a public getter (Oh well, at least it's only the most common case (sigh)). It's also not possible to create a ReadOnly auto property, which is odd considering auto properties otherwise act like variables (mostly).

I want the ability to define auto properties with different access levels on the getter and setter and ReadOnly (fixed at construction) auto properties. I suggest the following syntax:

'Public getter, private setter
Public Get Private Set Property Value As Integer
'Fixed after construction time
Public ReadOnly Property Value As Integer

#2) Flexible 'Implements'

You've probably had this happen to you before: you want to implement something from an interface, but your class doesn't quite match. You have a function but you need a property, you have a property but you need a ReadOnly property, you have a function but you need a subroutine or a function with a weaker return type, etc, etc. You work around the problem by implementing the interface member using a private function/sub/property which delegates to your existing stuff.

All of these not-really-a-mismatch cases should be allowed. The compiler should transparently implement the boilerplate code to match the interface member to the implementing construct.

#3) Infer Redundant Operators

Implementing a comparison operator without its partner currently causes a compile error. If you define '=' but not '<>', or '<' but not '>', or '<=' but not '>=', or vice versa, then you get a completely unnecessary compile error. I hate that compile error. The missing operator is trivial: invert the arguments for an ordering operator or invert the result for an equality operator. The compiler should be doing these trivial transformations for you. Defining an equality operator and an ordering operator should give you all of the comparison operators, no questions asked. At the very least, operators' partners should be inferred.

#4) Comparison Operator: <=>

Ruby has a very nice comparison operator: <=>. It returns the sign of comparing two values: -1 when the first argument is less, +1 when it is greater, and 0 when it is equal. I'd like to see it in VB/.Net.

Select Case value1 <=> value2
Case -1
Case 0
Case +1
End Select

#5) Iterator Blocks

I'm very surprised this didn't make it into VB10. I know the VB team had excellent ideas about it at least as far back as 2008. Iterator blocks? Awesome!

Function FromTo(ByVal low As Integer, ByVal high As Integer) As IEnumerable(Of Integer)
Return Iterator
If low <= high Then
Return low
Return Each FromTo(low + 1, high)
End If
End Iterator
End Function


#6) Linq Zip Operator

I often want to zip sequences together, but I have to break the linq flow and use explicit calls to Enumerable.Zip. There should be a linq operator for zipping:

Dim evenItems = From item In items
Zip index In Naturals
Where index Mod 2 = 0
Select item


#7) IDisposable Event Subscriptions

You should clean up your event handlers. Failure to do so can result in memory leaks (handlers can't be garbage collected while a long-lived event dispatcher has a reference to them). Just ask the Princeton team from the 2007 DARPA challenge, because they had exactly this type of memory leak. So, ideally, removing event handlers should be as painless as possible.

Unfortunately, removing event handlers isn't painless. First, every properly removed handler requires three lines (store delegate, add delegate, remove delegate). You must store the delegate you are going to add and remove, because otherwise you will try to remove an equivalent-but-different delegate and end up removing nothing. Second, every RemoveHandler line is an identical copy of an AddHandler line, except you replace the 'Add' prefix with 'Remove'. Finally, you add and remove events in different parts of the code, which makes it harder to keep the add/remove lines synced.

In order to overcome the far-away-sync pain, I started using the following pattern for event subscriptions: package the RemoveHandler call into a delegate, and package that inside an IDisposable. You end up with a 'subscription', which can be disposed to remove the event handler. Therefore, instead of using RemoveHandler, you dispose the subscription. This enormously simplifies removing groups of event handlers, because you can keep all the subscriptions in a list of IDisposable. For example:

Dim handler = AddressOf SomeMethod
AddHandler SomeObject.SomeEvent, handler
Me.subscriptions.Add(New DelegatedDisposable(Sub() RemoveHandler SomeObject.SomeEvent, handler))
... elsewhere, in the disposal code ...
For Each subscription In Me.Subscriptions
subscription.Dispose()
Next

Unfortunately, you still have to track the delegate (albeit in a hoisted local instead of a class member), and you still have to repeat yourself in the RemoveHandler call. All of this would be solved if 'AddHandler' returned an IDisposable which, when disposed, removed the added handler. There would be no more need to track the delegate or repeat the handler arguments. Instead of three lines of code per handler, you end up with just one:

Me.subscriptions.Add(AddHandler SomeObject.SomeEvent, AddressOf SomeMethod)

To Be Continued

Friday, March 12, 2010

Linq to Tasks

One of the more interesting properties of the Linq syntax is that, at heart, it has nothing to do with sequences or XML or SQL. Linq is a really syntax for performing operations with monads, and you can add your own types to it relatively easily. (For the uninitiated: a monad is essentially a wrapper class plus a way to transform functions to use wrapped values instead of normal values). Linq works with sequences because sequences are an extremely common Monad, and so the linq-to-list stuff is implemented as part of .Net. In this post, I'm going to show you an example of adding your own Linq-to-X functionality.

Tasks are a new feature in .Net 4.0. A task represents an asynchronous operation, such as a function running on another thread, and provides methods for working with the eventual result. You can use the ContinueWith methods to chain tasks together, feeding the eventual output of one task into the input of another task. For our purposes, the important thing is that tasks are a monad: they wrap a value, and you can modify functions to operate on tasks instead of normal values (using ContinueWith).

Since tasks are a type of monad, we can use them with Linq. All we have to do is define the necessary extension methods: Select and SelectMany. Select is the function used when you have a single 'From' line in your query, while SelectMany is used when there are multiple 'From' lines. Our task-version of Select will take a task and a function, and return a task for the function's eventual result after being given the task's eventual value. SelectMany is essentially the same thing, but with two tasks and two functions.

    Imports System.Threading.Tasks

Public Module LinqToTasks
<Extension()>
Public Function [Select](Of TArg, TResult)(ByVal task As Task(Of TArg),
ByVal func As Func(Of TArg, TResult)) As Task(Of TResult)
Return task.ContinueWith(Function(t) func(t.Result), TaskContinuationOptions.OnlyOnRanToCompletion)
End Function

<Extension()<
Public Function SelectMany(Of TArg, TMid, TReturn)(ByVal task As Task(Of TArg),
ByVal projection1 As Func(Of TArg, Task(Of TMid)),
ByVal projection2 As Func(Of TArg, TMid, TReturn)) As Task(Of TReturn)
Return task.Select(Function(value1) projection1(value1).
Select(Function(value2) projection2(value1, value2))).Unwrap
End Function
End Module

I know that doesn't seem like a lot of code, but that's all of it. We can now use the linq syntax on tasks. But keep in mind that we didn't implement many of the operators, like "where" (what would that even mean for a task?). Here are some examples of using the linq syntax on tasks:

Example #1: Returns a task that evaluates to 35 after five seconds:

        Public  Function TaskTest() As  Task(Of Int32)
Dim t = New TaskCompletionSource(Of Int32)
Call New System.Threading.Thread(Sub()
System.Threading.Thread.Sleep(5000)
t.SetResult(5)
End Sub).Start()
Return From value In t.Task
Let squared = value * value
Let doubled = value + value
Select squared + doubled
End Function

Example #2: Returns a task that evaluates to 20 after ten seconds:

Public Function TaskTest2() As Task(Of Int32)
Dim t = New TaskCompletionSource(Of Task(Of Int32))
Call New System.Threading.Thread(Sub()
System.Threading.Thread.Sleep(5000)
Dim t2 = New TaskCompletionSource(Of Int32)
t.SetResult(t2.Task)
System.Threading.Thread.Sleep(5000)
t2.SetResult(1)
End Sub).Start()
Return From taskValue In t.Task
From value In taskValue
Select value * 20
End Function

As you have seen, allowing linq syntax on a type is as easy as implementing extension methods for the operators. A good learning exercise is to implement the linq operators for the non-generic version of IEnumerable (hint: all the functions involve enumerating). There are tons of types you can linq-ify: collection types, nullables, Lazy<t>, delegates like Func<t>, etc, etc, etc and etc. Try not to overdo it.

Friday, March 5, 2010

Post-Mortem of a Job Application

I applied for a job recently, and was asked to write a small clone of Arkanoid (aka Breakout) using C++/DirectX. My C++ was rusty and the last DirectX stuff I did was five years ago and in VB6, but I figured I might as well try. At least it would refresh my C++ and force me to learn some DirectX. Unfortunately, I never managed to finish the game (on time). My lack of familiarity caused difficulties but, looking back, I can see that familiarity was not the issue. Learning sucked up some time, but the real time sink came about because of a design decision made only three hours into the project: I decided to write a Rational class instead of using floating point values.

Since this was a job application, I didn't want to do the bare minimum. I came up with the idea to record 'ghosts', so you could race against yourself. If I had the time, I could even feed the ghost data in live from another game for some relatively simple networked multiplayer. Thinking about how I would implement this, I remembered that floating points are not reliable in terms of consistency. Small optimizations made by the compiler, and differences across machines, can make the results of even simple additions come out slightly differently. That could be a problem, so I decided to write a Rational class and use it instead of floating points. That way I could guarantee consistency across machines.

At the beginning, I was reaping benefits. The rationals weren't as fast as floats, since constructing one involved computing a gcd, but the game wasn't even close to taxing the CPU. They even made the physics nice and exact, because all the 2d vector operations I used are closed over the rationals (No rounding errors. At all!). For example, this code computes the *exact* intersection point and normal of a moving point into a line segment:

//[example note: Vector2 is an x/y pair of Rationals. CollisionPoint is a location/normal pair which can be empty for no collision]

CollisionPoint CollisionPoint :: PointIntoLine(const Vector2 p, const Vector2 dp,

const Vector2 q1, const Vector2 q2) {

assert(dp != Vector2(0, 0));

assert(q1 != q2);

//Useful intermediate values

Vector2 p1 = p;

Vector2 p2 = p + dp;

Vector2 dq = q2 - q1;

Rational f1 = q1.Cross(q2);

Rational f2 = p1.Cross(p2);

//Intersection point (of lines extended to infinity)

Rational d = dp.Cross(dq);

if (d == 0) return CollisionPoint(); //no collision due to parallel lines

Rational cx = (f1*dp.X() - f2*dq.X())/d;

Rational cy = (f1*dp.Y() - f2*dq.Y())/d;

Vector2 intersectionPoint = Vector2(cx, cy);

//Confirm that the intersection point is within the segments

if (Median(p1.X(), cx, p2.X()) != cx ||

Median(p1.Y(), cy, p2.Y()) != cy ||

Median(q1.X(), cx, q2.X()) != cx ||

Median(q1.Y(), cy, q2.Y()) != cy) return CollisionPoint(); //missed

//return the point of impact and the normal of the line the at point of impact

return CollisionPoint(intersectionPoint, - dp.PerpOnto(q2 - q1));

}

The happy times continued until I hit an assert: "denominator < 0". I had decided that a rational's negative sign must always be on the numerator, and put an assert in the constructor to enforce this. Upon first seeing the error, I thought I had made some stupid error in one of the operator functions. Unfortunately, what had happened was far more insidious: integer overflow.

The thing to understand about rationals is that performing operations on them tends to make them 'share' their factors. If you add a/b and c/d, you get (ad + bc)/(bd), which almost always has a larger denominator and numerator even after removing the gcd. In the worst case each addition will square the numerator and denominator, and you only have to square five times to go from 2 to 2^32 and cause an overflow. Well guess what: a physics function involves way more than five additions, not to mention other operations.

I tried to smooth over the problem by rounding, but the problem kept happening. I rounded more aggressively, but it kept happening. Eventually I had rounding statements on practically every other line outside of the physics functions, but it still kept happening. Even my goat sacrifice to Apollo didn't work (maybe he doesn't like goats?). You could pick a physics function at random, give it touchy input, and cause an assertion. To make matters worse, all this tinkering and rounding kept introducing small bugs. Eventually I ran way over on time, and gave up.

If I had gone with the tried-and-true floating points, I would have finished with a potentially-maybe-slightly-out-of-sync ghost, instead of not finishing at all. The lesson I'm taking from all of this is that I shouldn't be experimenting with ideas when I'm on the clock, unless it's necessary. Sometimes they work, but when they don't the cost is too high. Perhaps, now that there's no time limit, I'll rewrite the rationals to use BigIntegers in order to guarantee there are no overflows. That could be an interesting side project.

Monday, January 4, 2010

Asymptotic Notation is Complex

Have you ever struggled with Big-O notation? I used to. If I saw "n = O(n^2)", I perceived "n equals O applied to n^2". It took time to train my mind to instead perceive "n is asymptotically less than n^2". It never caused any serious problems, it was just an incredibly annoyance. I used to think I was the problem, but now I realize the notation was the problem. In large part this realization comes from reading "The Design of Everyday Things", which talks about people blaming themselves for the failings of the common objects around them. It's time to face facts: Big-O notation sucks.

There are two main problems with Big-O notation: it looks like an equality (it's not), and the symbols are arbitrary (w.r.t. the rest of math). The first problem is by far the worse. Big-O notation is meant to express an ordering, not an equality. Using an equality to represent an ordering is a travesty of usability. It encourages you to make contradictory proofs like: 1 = O(1), 2 = O(1), therefore 1 = 2. You might as well switch a car's gas and brake pedals. The second problem is a learnability issue. If I know what Big-O means, and I see a Big-Omega, I can't infer what that means. I need to memorize all five symbols (o, O, θ, Ω, ω), and their meaning (Do you know what they all mean?). These problems have real consequences. There are many perpetually renewed questions on CS forums about the notation for asymptotic complexity, instead of about asymptotic complexity itself.

Since Big-O notation is so bad, let's design a replacement. We want to express an ordering, so we will use the standard ordering operators (<, <=, =, >=, >). We want it to look distinct, so we'll modify the operators in some way (eg. prefix them with an @ for asymptotic). That's it! The new notation is:

[F(x) = o(G(x))] === [F(x) @< G(x)]

[F(x) = O(G(x))] === [F(x) @<= G(x)]

[F(x) = θ (G(x))] === [F(x) @= G(x)]

[F(x) = Ω (G(x))] === [F(x) @>= G(x)]

[F(x) = ω (G(x))] === [F(x) @> G(x)]

Do you see how much clearer it makes the whole affair? It is now obvious that we are dealing with an ordering, obvious that [F(x) @<= G(x)] is the opposite of [F(x) @> G(x)], and obvious that [F(x) @= G(x)] is equivalent to [F(x) @<= G(x) and F(x) @>= G(x)]. All of the non-obvious parts have been isolated into the '@' symbol. In fact, I bet the notation just taught some people what little-omega (ω) means.

Here are some examples, using the above notation:

1 @<= 2

1 @= 10000

1 @< n

2*n @<= n

n^2 @<= n^10000

2^n @> n

3^n @> 2^n

Isn't that much nicer than Big-O notation? I hope that something similar to the above will replace Big-O in the future. I'm tired of telling people what Big-Omega means.

As a closing note, I want to point out how awkward the usual asymptotic complexity definitions are. Proving [Ǝc>0,e>0.∀x>e.F(x)<=c*G(x)] is usually a lot harder than proving lim(x to inf)(F(x)/G(x)) converges.