Friday, November 21, 2008

Friday, October 3, 2008

Visual Studio dialogs are modal—for OpenOffice

This is really irritating. I use Visual Studio 2008 and OpenOffice 2.2.0 Writer at the same time at work. When Visual Studio shows certain modal dialogs, such as a wizard for a new project, or dialogs of the SourceSafe plugin, OpenOffice freezes up completely. It won't even redraw itself, let alone respond to mouse clicks.

Update: I thought Visual Studio was unaffected by this quirk until I started OpenOffice.org Writer at the same time as a SourceSafe "differences" dialog was already open. A message box appeared saying "Unable to complete operation" and then Visual Studio crashed (disappeared instantly). Hmm.

Friday, September 26, 2008

Bitstream Vera Sans Mono Bold

My favorite font for programming. Use a black background for vibrant colors.

In this color scheme I use an off-white (not full intensity) rather than pure white, otherwise the white text seems brighter than everything else. Interestingly, this font is typically bundled with Linux, but IMO it looks significantly better in Windows.

Friday, September 12, 2008

Symbols in .NET

I'm a big fan of Ruby's "symbols". Symbols are sort of like strings or enums, but different. Their syntax is an identifier with a colon in front, e.g. :Foo. See here for details.

I love using symbols in place of enums, because if they are implemented properly, comparing two symbols is as fast as comparing two integers (enums). Enums have the problem of non-extensibility; library B can't define new values for an enum in library A. Meanwhile, anybody can define a new symbol at any time.

Via Loyc I would like to add symbol support to C# and boo, but Loyc is a long way off as long as I have nobody to help me. In the meantime, see here for my current implementation of Symbols in C#.

To simulate enums using Symbols in C#, I just define a static class full of Symbols. For example:
public static class Tokens {
static public readonly Symbol WS = Symbol.Get("WS"); // whitespace
static public readonly Symbol NEWLINE = Symbol.Get("NEWLINE");
static public readonly Symbol ID = Symbol.Get("ID"); // identifier
static public readonly Symbol PUNC = Symbol.Get("PUNC");
static public readonly Symbol EOS = Symbol.Get("EOS");
static public readonly Symbol ML_COMMENT = Symbol.Get("ML_COMMENT");
static public readonly Symbol SL_COMMENT = Symbol.Get("SL_COMMENT");
...
}
Enjoy!

Simulating covariant return types in C#

For several years, Microsoft engineers have refused to add support for covariant return types, a trivially simple feature that should have been in the CLR from the beginning.

Suppose you want to write a Clone() method that returns a copy of the current object. Naturally you want to write the following, but it is illegal:
class MyStuff : ICloneable {
public MyStuff Clone() { ... }
}

Since you are implementing an interface, you can use this workaround that uses explicit interface implementation:
class MyStuff : ICloneable {
public MyStuff Clone() { ... }
object ICloneable.Clone() { return Clone(); }
}

The above workaround is okay for implementing an interface, but what if you are writing a class hierarchy, and you want a Clone() method that is virtual but has the appropriate return type?
class BaseNode : ICloneable
{
object ICloneable.Clone() { return Clone(); }
public virtual BaseNode Clone() { ... }
}
class ComplexNode : BaseNode
{
override BaseNode BaseNode.Clone() { return Clone(); } // Error!
public ComplexNode Clone() { ... }
}

Oops, the workaround that you use for interfaces is illegal for class inheritance. There is still a solution, though:
class BaseNode : ICloneable
{
object ICloneable.Clone() { return Clone(); }
public BaseNode Clone() { BaseNode c; Clone(out c); return c; }
protected virtual void Clone(out BaseNode clone) { ... }
}
class ComplexNode : BaseNode
{
public new ComplexNode Clone() { ComplexNode c; Clone(out c); return c; }
protected override void Clone(out BaseNode clone) { clone = Clone(); }
protected virtual void Clone(out ComplexNode clone) { ... }
}

That's right. You need six Clone() methods. The last method is virtual in case you want to make a class derived from ComplexNode, e.g. VeryComplexNode:
class VeryComplexNode : ComplexNode
{
public new VeryComplexNode Clone() { VeryComplexNode c; Clone(out c); return c; }
protected override void Clone(out BaseNode clone) { clone = Clone(); }
protected override void Clone(out ComplexNode clone) { clone = Clone(); }
protected virtual void Clone(out VeryComplexNode clone) { ... }
}

Without covariant return types, you have to to define an additional virtual function for each additional derived class.

Sunday, June 1, 2008

How to get started with Subversion on Sourceforge

To get started with TortoiseSvn as the admin of a new project:

  1. On your SourceForge project page, choose "Subversion" from the "Admin" menu.
  2. Check the box beside "The following box should be checked to enable Subversion:" and click Update. (Note: you may also want to disable CVS from the Admin | CVS page).
  3. Prepare the folder that has your source code in it by removing binary files that are generated by your compiler (e.g. remove "bin", "Debug", "Release" folders), so you are only left with files you want to put in the repository.
  4. Install TortoiseSvn if you haven't already.
  5. Assuming your root folder is called "MyProject" and the "unix name" of your project on SourceForge is "myproject", right-click on the MyProject folder (on your hard drive) and choose TortoiseSVN | Import...
  6. As documented here, use https://myproject.svn.sourceforge.net/svnroot/myproject as the URL of the repository. Then click OK and your files will be uploaded.
  7. Unfortunately, the MyProject folder is still not associated with the repository; you are required to "check out" the files, which means downloading them, in order to complete the association between the files on your computer and the repository. To accomplish this, first rename the MyProject folder to MyProject2--or just delete it, as you probably don't need it anymore. Then make a new MyProject folder, right-click on it and choose "SVN Checkout...". Use the same repository URL as before: https://myproject.svn.sourceforge.net/svnroot/myproject. Click OK and the files are downloaded.
  8. Now when you recompile your project, the object files and stuff will come back (e.g. in "Debug", "Release" folders). You can ensure that TortoiseSVN won't upload a file/folder by right-clicking on the file/folder and choosing TortoiseSVN | Add to ignore list | filename.
  9. After making changes to your program, right click the MyProject folder and choose "SVN Commit..." to upload the changes. TortoiseSVN will update existing files in the repository automatically, but you need to check the check box beside new ("unversioned") files. Then click OK.
  10. When sharing a repository with other people, you must frequently right click the MyProject folder and choose "SVN Update" to download changes made by others.
  11. To learn more about Subversion and TortoiseSVN, read the truly excellent TortoiseSVN manual, by right-clicking on any file and choosing TortoiseSVN | Help.
  12. When inviting other developers to your project, point them to this other handy tutorial.

Sunday, May 18, 2008

VList data structure in C# (.NET Framework 2.0)

I've made an implementation of Phil Bagwell's VList data structure in C#, with a fairly comprehensive test suite. It comes in two flavors: VList(of T), where you normally add/remove items at the beginning of the list, and RVList(of T), to which you normally add/remove items at the end. It implements the complete IList(of T) interface plus quite a few additional members including AddRange, InsertRange, RemoveRange, Push, and Pop. Converting a VList to a RVList and vice versa is a trivial O(1) operation that appears to reverse the order of the elements. VList and RVList are value types (structs) that contain a reference to the underlying linked list of arrays (VListBlock(of T)). Small lists (0 to 2 items) are optimized with a specialized block class (VListBlockOfTwo(of T)).

License: Lesser GPL. Contact me at qwertie256, at, gmail.com if you would like the source code. Here's an example usage:

void Example()
{
VList<int> oneTwo = new VList<int>(1, 2);
VList<int> threeFour = new VList<int>(3, 4);
VList<int> list = oneTwo;
VList<int> list2 = threeFour;

ExpectList(list, 1, 2);
list.InsertRange(1, threeFour);
ExpectList(list, 1, 3, 4, 2);
list2.InsertRange(2, oneTwo);
ExpectList(list2, 3, 4, 1, 2);

// oneTwo and ThreeFour are unchanged:
ExpectList(oneTwo, 1, 2);
ExpectList(threeFour, 3, 4);
}
static void ExpectList<T>(IList<T> list, params T[] expected)
{
Assert.AreEqual(expected.Length, list.Count);
for (int i = 0; i < expected.Length; i++)
Assert.AreEqual(expected[i], list[i]);
}

I thought that I would use the RVList to implement Loyc's AST to help make it possible to take AST snapshots easily, but I now suspect it's not a good idea. I am still working on the problem.

Performance characteristics

Similarly to a persistent linked list,
  • Adding an item to the front of a VList or the end of an RVList is always O(1) in time, and often O(1) in space (though, unlike a linked list, it may be much more)
  • Removing an item from the front of a VList or the end of an RVList is O(1) in time, although space not necessarily reclaimed.
  • Adding or removing an item at the end of a VList or the front of an RVList is O(N) and requires making a copy of the entire list.
  • Inserting or removing a list of M items at the end of a VList or the front of an RVList is O(N + M).
  • Changing an item at an arbitrary position should be avoided, as it performs as poorly as inserting or removing an item at that position.
VLists, however, offer some operations that singly-linked lists cannot provide efficiently:
  • Access by index averages O(1) in ideal conditions
  • Getting the list length is typically O(log N), but O(1) in my version
  • If a sublist points somewhere within a larger list, its index within the larger list can be obtained in between O(1) and O(log N) time. Consequently, reverse enumeration is possible without creating a temporary stack or list.
Also, VLists can (in the best cases) store data almost as compactly as ordinary arrays.