Smart Software

The Awkwardness of Functional Programming

Both Reddit’s main page and programming subreddit includes a popular post “Admitting that functional programming can be awkward.” Each of these subreddits have elicited numerous interesting responses.

In it, James Hague recounts how a semi-successful Mac game he wrote called Bumbler is trivial to write in C, but that a purely functional approach appeared to be barely doable and may well be the wrong paradigm for these types of problems:

What's interesting is that it would be trivial to write this in C. Some incrementing, some conditions, direct calls to sound playing routines and insect spawning functions, reading and writing from a pool of global counters and state variables. For a purely functional approach, I'm sure the data flow could be puzzled out...assuming that everything was all perfectly planned and all the behaviors were defined ahead of time. It's much more difficult to take a pure movement function and say "okay, what I'd like is for this object to gravitationally influence other objects once it has bounced off of the screen edges three times." Doable, yes. As directly implementable as the C equivalent? No way.

That's one option: to admit that functional programming is the wrong paradigm for some types of problems. Fair enough. I'd put money on that. But it also may be that almost no one has been thinking about problems like this, that functional programming attracts purists and enamored students. In the game example above, some of the issues are solvable, they just need different approaches. Other issues I don't know how to solve, or at least I don't have solutions that are as straightforward as writing sequential C. And there you go...I'm admitting that functional programming is awkward in some cases. It's also extremely useful in others.

It’s not always obvious, perhaps because people often continue to think imperatively when finding an functional approach. Rather than thinking that functional programming is not very compatible with game development, there might be a radically different way of thinking about a problem. I have encountered one computer engineering thesis called “Functional Programming and 3D Games” which specifically deals with the topic.

I have been in a similar situation a few times, but I have always been able to come up with an elegant, often unexpected, solution after thinking about the problem from a high level.

In a functional pearl paper on the Zipper data structure, Gerard Huet writes about the apparent unsuitability of functional approach to many data structures, but then he proposed a new functional data structure called the Zipper to rectify these problems:

The main drawback to the purely applicative paradigm of programming is that many efficient algorithms use destructive operations in data structures such as bit vectors or character arrays or other mutable hierarchical classification structures, which are not immediately modeled as purely applicative data structures. A well known solution to this problem is called functional arrays (Paulson, 1991). For trees, this amounts to modifying an occurrence in a tree non-destructively by copying its path from the root of the tree. This is considered tolerable when the data structure is just an object local to some algorithm, the cost being logarithmic compared to the naive solution which copies all the tree. But when the data structure represents some global context, such as the buffer of a text editor, or the database of axioms and lemmas in a proof system, this technique is prohibitive. In this note, we explain a simple solution where tree editing is completely local, the handle on the data not being the original root of the tree, but rather the current position in the tree.

One of his examples of a tricky data structure—the database of axioms and lemmas in a proof system—hit close to home. I was trying to move my proof system to a more functional approach, which would offer me numerous benefits including immutability, automatic support for backtracking and shared copies as well as easy inclusion inside any other data structure. I did come up with a solution by utilizing a binary tree implementation with filters at each node, aggregated from each of the child nodes. These filters allow me to perform an arbitrary search in an efficient divide-and-conquer manner, whereby a subtree in which no child contains a desired property is left unexplored. It was faster and more light-weight than my previous imperative attempts, and also simpler, because I no longer needed to maintain and synchronize a separate data structure for indexing.

Immutable Data Structures in C#

In the post on Path Finding using A*, Eric Lippert, programmer in the Visual C# team, writes that immutable data structures are the way of the future in C#. As immutable data structures have been a frequent posting topic of mine, I am really happy about this direction towards immutable data and functional programming that C# is taking. My only quibble is that the last two words, "in C#," are not really necessary.

The frequent complaint of functional programming is that it is slower than procedural programming. However, I discovered something else: As you know, the immutable data structures for maps may be slower for some operations than their imperative cousins, but the running times for all the operations are typically acceptable and well-balanced. (Even then, I did bring up in a recent post a version of persistent hash-tables and array used by COQ that offers nearly identical performance). Plus, these data structures are very flexible--able to be used freely anywhere with no constraints.

Most of my data structures in NStatic and elsewhere are immutable. In my data structures, the equality and the copy operation are constant-time, even for large object trees. The immutability and balanced performance allows many otherwise exponential algorithms to be done efficiently. A good example is the use of dynamic programming in which function values are "memoized" (sic); this technique is absolutely essential for natural language parsing.

Wes Dyer, another developer in the C# team, wrote early this year that "imperative programming is sometimes reminiscent of a Rube Goldberg machine. Both require meticulous thought to ensure that a process works correctly despite a myriad of state transitions and interdependencies. It is amazing these complicated programs work at all." Hmm... could he be referring to any popular application software that we know of?

That Microsoft and the rest of the world programs imperatively and suffers the consequence of their decisions is the main reason that I can even consider developing the software that may indirectly compete with their own.

Type Names

I picked up a lot of interesting knowledge about C# in the course of developing and testing a parser for the language. I'll try to post a few tidbits as they come to mind again.

One nice tidbit is how to create new short type names without having to specify the full name of every non-primitive type, especially inside of generic type names.

Normally, using "using" to create a new type name, even in the presence of the appropriate namespace import, one has to fully qualify every type name that is not a keyword.

using System.Collections.Generic;
using T = System.Collections.Generic.List<string>

However, if the "using" is inside a namespace, then it will utilize any imports located in an outer namespace.

using System.Collections.Generic;

namespace MyCompany
{
    using T = List<string>;
}

Source Code

Scott Hanselman's post on Weekly Source Code 2 reminded me of my desire to post some of my source code. I'll probably do just that, but, with me and my short-term memory loss, I often forget to follow up until after a few years go by.

A couple of my classes come to mind:

• Rational number class. This is an implementation of a general-purpose 16-byte data type that can precisely represent rational numbers (up to a certain precision), long (both signed and unsigned), and doubles. The code is written in IL to take advantage of extended-precision floating point. More info...
• Fast, persistent hash-tables and array. This is one of my two sets of persistent collection classes. Similar to persistent arrays used by the COQ theorem prover for fast, functional union-find data structures, these data types are as fast as their imperative cousins and are ideal for backtracking. Unfortunately, my implementation is not thread-safe. My second set of persistent data structures is fully "functional" and thread-safe, but is more connected to my code-base.

If I haven't posted any source code by the end of September, give me a ring.

---

I have been meaning to post some regular expression matching implementations from my post in December: one using closures and another less efficient implementation using iterators. Both are functional, but imperative implementations can be compact too. I won't get around to doing it until after I ship NStatic, though.

Several years ago, I wrote a fast pattern-matcher and a slower unification engine (bidirectional pattern-matching) for expressions. Both algorithms provided a superset of regular-expression capabilities including wildcards and disjunctions.  (For unification, one regular expression pattern might be matched against another pattern.) They also handled other phenomena such as associativity and commutativity. By going completely functional, I was able to merge both algorithms into one, fast algorithm and dramatically reduce the total number of lines down to about 500.

I had written a regular expression engine for a college class based on NDFAs, the code for which was substantial. I also know that Microsoft's Rotor implementation includes a large number of files, so I was surprised by the compactness and directness of my functional pattern matcher implementation.

Since then, I have been (re-)writing most of my code in the functional style with the same consistent results. Programming in a functional manner entails heavy use of closures (anonymous methods), which is only really practical in C# 2.0+, and greatly eliminates the need for temporary or accidental classes.

Orcas Beta 2

Orcas Beta 2 is here, and it includes a go-live license. I plan a switch over (plus a clean reinstall of Vista) by the end of this month. I do prefer to use the latest tools to keep on top of technology, and, despite the installation being a distraction from my current work, I do feel rejuvenated by a sense of progress and change of scenery.

I have been developing in Orcas Beta 1 for about a month now, but haven't been using any of the new compiler features and libraries. Both Refactor Pro and Resharper have latest versions that will run on Orcas, though I don't think Resharper 3.0 supports the new language syntax yet. With the go-live license, it might even be possible to use the LINQ APIs even though the product has RTMed, but I'll wait.

It is hard for me to recall a specific benefit of using Orcas, but it is very stable and doesn't require Administrator privileges to run. Most of the benefits from using the IDE come are related to .NET 3.0/3.5 (which include WPF and LINQ).

I am not planning on using WPF in the near term, but it is something I am currently looking into the future. And if I were, it would initially be from inside a WinForms application using its interoperability features. I also don't see a compelling reason now to use it. I have seen a couple reports that WPF is not ready for prime time use, Rod Paddock, Eric Sink and Lhotka. I have seen ribbon and other components from ActiproSoftware, DevComponents and Infragistics, but the component libraries are still minimalistic and not fully developed. The runtime, required for Windows XP, also adds 2.8 Mbs to my setup package, and forecloses my ability to run in Windows 2000 (though, I must admit, I can't guarantee NStatic even runs in 2000 in its present state).

Jumping to Orcas and WPF

After releasing the first version of my product, I would most likely jump directly to using Orcas and WPF targeting 3.0, at which point I will begin blogging about my experiences and the new feature set. I firmly believe in moving to the latest released languages and technologies as soon as possible. I don’t want to invest in moribund technologies, and I do want the most productive tools as I have limited resources.

I wonder how practical it is for me to move to the Orcas beta right now. There will be probably be a number of problems that I encounter, but will it be more than made up by the expanded feature set of Visual Studio or will there be show-stoppers? Is compiler and IDE performance going to take a hit as it did in Whidbey? Both productivity tools, Resharper 3.0 and Refactor Pro/CodeRush, already support Orcas.

For now, I will play it safe and jump into Orcas after I released NStatic. Every change seems to drag my release ever farther away.

As for WPF, I halted my user interface development work in anticipation for WPF, since it would obsolete some of my existing work and also includes support for animations, 3D, and a declarative programming model. My 3D effects library that I spent some time developing, including perspective warping for images, will probably go to waste.

My plan is to switch over to WPF as the primary programming model and utilize its WinForms compatibility controls. I will purchase the WPF editions of the existing control library as there are already many WPF-based user interface components available now. I purchased Chris Sells and Chris Anderson’s books on WPF; I will probably also buy Adam Nathan’s based on Jeff Atwood’s recommendation. The WPF programming model is just so clean and beautiful, a sharp contrast from MFC.

Anonymous Recursion

I was planning on writing about anonymous recursion relating to work in NStatic, but Wes Dyer beat me to the punch with his post Anonymous Recursion in C#. In addition to my name, Wes Dyer shares my desire to push a more functional style of programming in C# (and he's also a member of the C# team, so we may win).

 

Loops and recursive functions in NStatic are converted to recursive lambda expressions, and then through various techniques like unrolling, recurrence solving, inductive proofs, are simplified to a closed form. The expressions above are intentionally unsimplified for illustrative purposes. 

Each of the lambda expressions displayed above are recursive. Nonrecursive lambda expressions are applied over their arguments, so they aren't normally seen unless standalone without any arguments.

I am not currently sure how I will eventually display lambda expressions in C#; the current display is attractive to my eyes, personally, but may turn off users unfamiliar with lambda calculus. I probably will ultimately go with a more C#-like syntax. My previous attempt was quite unreadable or quite verbose because the lambda operator => looks like the inequality operator and the use of parenthesis was quite excessive. Another possibility is to use C# 2.0 syntax with delegate and return keywords.

For those with sharp eyes, I introduced a fix operator to concisely display recursive lambda expressions. The fix function takes as its argument any lambda expression that includes a first parameter, representing the name of the function itself. That parameter can be used inside the lambda expression to recursively call itself.

In a language that does not explicitly have recursion operators, lambda expressions can be used to introduce recursion. It's not very pretty, but one such operator to do this is called the Y fixed-point combinator.

    public delegate Func<X,T> YFunc<X,T>(YFunc<X,T> f);
    public static Func<X, T> YCombinator<X, T>(Func<Func<X,T>, Func<X,T>> f)
    {
        YFunc<X,T> lambda = delegate(YFunc<X,T> y)
        {
            // return f(y(y)); -- only works with call by name
            return f(delegate(X x) { return y(y)(x); });
        };
        return lambda(lambda);
    }

The combinator does not allowed to use recursion, only function application, in its definition, since it's purpose is to introduce a form of recursion in the first place.

The Y combinator is possible in a typed language like C# because C# allows us to recursively define types--that is, YFunc was defined in terms of itself. A slight modification, an additional lambda expression, was also needed to allow f(y(y)) to be called by name.

A more efficient function for anonymous recursion takes advantage of assignment in the C# to avoid the creation of more than one closure is the following function.

    public static Func<X, T> Fix<X, T>(Func<Func<X,T>, Func<X,T>> func)
    {
        Func<X,T> fixfunc = null;
        fixfunc = func(delegate(X x) { return fixfunc(x); });
        return fixfunc;
    }

An example of its use in C# is the following:

    Func<int,int> func = Fix<int,int>(
        delegate(Func<int,int> f)
        {
            return delegate(int n)
            {
                return n<=1 ? 1 : n + f(n-1);
            };
        });
    
    Console.WriteLine(func(6));

Continuation Passing Style & Anonymous Methods

I thought that I would briefly explain the concept of continuation-passing style from my previous post. CPS is a way of simulating continuations in a language that doesn’t support the feature. Basically, we making a function call, one passes to the call an additional argument, which is another function that represents the continuation of the calling function.

Anonymous methods (closures) in C# 2.0 enables CPS with a very convenient syntax. Closures are frames constructed on the heap—allowing us to bypass limitations on function calls imposed by the CLR stack-based implementation.

public void Method()
{
     // Code before call
     T result = Call(a, b, c)
     // Code after call
}

becomes

public void Method()
{
     // Code before call
     Call(a, b, c,
     delegate(T result)
     {
           // Code after call
     });
}

The callee function returns a value by calling the continuation function passed in with the return value.

public void Call(int a, int b, int c, Action<T> func)
{
      // ...
      if (...)
      {
          func(result);
          return;
      }
      // ...
}

If a method itself returns a result, then we might return the result of the call like so among many possible ways.

public T Method()
{
     // Code before call
     return Call(a, b, c,
     delegate(T result)
     {
           T result2;
           // Code after call
           return result2;
     });
}

Unlike a stack-based implementation, the continuation can be called multiple times with different return values or not at all. This technique can be used for backtracking, multithreading, and many other uses. Richter previously used this for a Fire-and-Forget approach to locking. I found this technique useful with dialog boxes to eliminate modality.

 

Larry O'Brien

I have not been blogging frequently because I am attempting to deliver a product, but I decide to respond to one of Larry O’Brien’s two posts critiquing my own blog posts. In the other post, he puts my name on the title and links me to a strawman argument that I didn’t actually make: “Wesner Moise Claims IDEs Disprove ‘No Silver Bullets’: I Say ‘Are You Kidding?’”

In Bad Comparison: 14 Line Python RegEx evaluator versus Microsoft’s 14K lines, Larry writes.

Wesner Moise points to "generalized regular expression matching" as a moderately hard problem that might serve as the basis for comparing programming languages and approaches. He says "Microsoft's implementation of regular expression matching over strings is spread across 24 files and 14,455 lines of code including comments and whitespace." (I'm not sure how he'd know that -- I assume he's talking about Rotor source code.)

He wonders if a functional approach could be more efficient and points to a 14-line Python program.

No, no, no: they are two incredibly different capabilities.

The Python program implements something like the original definition of a regular expression --restricted to that which can be expressed in a single line of Extended Backus-Naur Form without recursion. "Regular expression support" for today's languages means something very, very different, starting with compatibility with Perl5 and going from there. Backslashes, named groups, etc. are complex features that require, in any language, something in excess of 14 lines.

Larry seems to miss the fact that the Python implementation could easily incorporate all of the features he described easily. The implementation is based on functions not finite state machines, so we aren’t limited by the expressiveness of regular languages. The Microsoft implementation does include compilation and parsing, so it’s not directly comparable, but if one wanted to create a reasonably performing regular expression engine for list structures besides strings with the same sets of capabilities, it could involve dramatically less code implemented in a functional style. I’ll eventually post source code for such an implementation, but right now I can’t justify the time when I still need to deliver a product and generate income.

Implementing a regular expression engine is not really a hard problem. My first implementation was difficult when I tried in college to extend the DFAs and NDFAs to accommodate features introduced in Perl, while at the same retaining the minimal processing that FAs offer. When I look at Spencer’s open source UNIX implementation of regular expressions, I noticed that he eschewed all the academic models for what I considered at the time “a quick and dirty” implementation, which while must faster in practice had theoretically inferior performance. 

Larry continues about functional programming and silver bullets:

Having said that, regular expressions are a good fit for functional approaches. But, just to point out the lack of silver bullets, attempting to parse a left-recursive grammar (a grammar with a production of the form A->AB) will hang a simplistic recursive-descent parser.  

Larry, whose job is to be an expert on programming languages, seems to lack any imagination. Larry takes a false premise about recursive-descent parsing and makes a false inference about the lack of silver bullets. He’s making a statement about a programming style that, being Turing-equivalent, is maximally expressive. It is possible to implement a highly readable, simple, table-free, recursive-descent parser for left-recursive grammars using continuation-passing style that performs as well as traditional table-driven approaches. I myself use continuation-passing style for implementing backtracking algorithms. One good paper on this is Derivation of a Typed Functional LR Parser. There are other approaches I have seen such as using data representations of functions in parser combinators.

Larry’s heavily wedded to the idea that there is no silver bullet. It has a Godelian ring that makes him look wise. I don’t buy into Brooks’ argument that there is no silver bullet to put down the software beast. It rests on assumptions such as that existing program languages have become high-level enough. He wrote this back in 1986, when the dominant languages of the time, assembly, C, Basic, Fortran pre-90, were quite primitive compared to now. Program languages can still become far more conceptual and declarative. I personally see the incorporation of functional techniques and symbolic manipulation as necessary steps towards that goals. My own belief in silver bullets, probably reflects my own push for fundamental advances in software that are happening too slowly in the big companies.

Lastly, Larry O’Brien claims in one post that he is nice during the day, but becomes a werewolf when he writes his blog post.

I think I'm quite nice. You might not know that if you just know me from my blog and articles. I try to always be fair when I write, but that's not the same as being nice, which I think I am in person.

Hopefully, someone like Charles Simonyi comes along and shoots a silver bullet through the beast, whose collapsing hairy body morphs back to the naked, pale-skinned body of a Hawaiian geek.

No Meeting Monday

I didn’t receive any confirmation for the .NETDA meeting on Monday night as I originally arranged for over a month ago, so I cancelled. It appears that I contacted the wrong people, the organization president and the events coordinator, when I should have contacted the meeting leader. It’s possible that my content did not fit well with the Web Developer meeting. I plan on scheduling a talk on January as well as one during the MVP summit.

This also gives me time to fix up my support for IL interpretation of API calls, which I am currently adding. This gives me automatic parameter validation and automatic extraction of algebraic properties of API calls.

Special thanks to the following companies for free components

• Mark Miller for DevExpress
• SmartAssembly code obfuscation tools
• Jamie Cansdale for TestDriven.NET
• Sky Software
• NDepend

I made a blanket statement in my last post about large component companies based on experience with one vendors, which is probably not entirely true. For example, what I have seen from DevExpress is very impressive.

Almost as if he was responding to my last post, Mark Miller, the chief architect at DevExpress, announced yesterday that the DXperience Enterprise, containing all DevExpress software, is being made freely available to all MVPs.

Active Loops

There aren’t many times where I can compare bits and pieces of code that I have written to those of other experts. One such time involves active loops (aka, parallel apply).

Shortly after posting on Concurrency last December, I began implementing my own version of active loops mentioned in the posts. A newly proposed extension for a future version of Visual C++,  an active loop is a loop in which some iterations may run in parallel, typically over a collection. Visual C++ already has a limited support in the form of OpenMP.

Since that post, I noticed many entries posted on blogs and articles:

• Larry O’Brien – ParallelApply: Distribute Calculations Over Multicore / Processors
• Eric Sink — C# implementation of Map with multicore support
• Joe Duffy, Microsoft Concurrency expert — MSDN Article “Using Concurrency for Scalability” with a sample source code for a “Simplistic Parallel Implementation”

I recall Jeffrey Richter producing an implementation in one of his MSDN articles or in his PowerThreading library, but I cannot seem to locate the code snippet.

My own code is similar to Larry’s except that I used BeginInvoke instead of DynamicInvoke (reflecting my preference for early binding) and the use of the AutoResetEvent. BeginInvoke requires a call to EndInvoke. I’ll post my code snippet shortly after I sufficiently tested it.

I picked up from Joe Duffy the use of Environment.ProcessorCount to optimize the number of threads to queue from. Since he’s using the thread pool, it may be worthwhile to also look at ThreadPool.GetAvailableThreads().

Although my product is multithreaded, the parallelism is limited. My code analysis run in one thread, while the user interface runs in another. I am planning to introduce additional parallelism into my tool to take advantage of the new multicore systems available today; because I rely heavily on immutable data structures, the transition should be painless.  I just purchased a Core 2 Duo E6600 Dell System with 4MB cache to replace my aging Pentium 4 desktop of three years and to experience and test with true parallelism.

My preference for multithreaded programming is to rely on immutable state, actor objects, and message passing. I try to avoid share state and low-level threading constructs; when I can’t, I rely on the CLR basics such as locks, interlocked calls, and don’t try to invent my own. 

I have also been looking at BackgroundWorker, trying to uncover any differences between it and Control.Invoke.  Unlike the Control.Invoke mechanism of .NET V1.1, the BackgroundWorker class is a new component available outside Windows applications; it uses a new abstraction called a SynchronizationContext. One difference appears to be that a call to ReportProgressChanged in BackgroundWorker usually waits, but not always, until the event finishes before proceed. Profiling of my app indicated a substantial amount of time spent in this call.

A reader wrote me around February mentioning that the MSDN article for BackgroundWorker contained a mistake. The author indicated that the BackgroundWorker will perform certain operations like ProgressChanged and RunWorkerCompleted on original calling thread. That’s probably only true for WinForms apps, which has a message pump, although one message board topic suggests that in some cases RunWorkerCompleted will be invoked in a third thread, if the SynchronizationContext is not properly initialized by WinForms. In console apps with no message pump, injecting a function call into a busy thread would be a bugfest and a security hole, which is why Thread.Suspend and Thread.Resume have been deprecated in Whidbey.

 

Symbolic Links Redux

There's been some confusion as to whether symbolic links are based on reparse points from my last post on symbolic links in Vista. Symbolic links are reparse points, too, not just junctions. Reparse points are an extension mechanism in NTFS for both files and directories, not just directories. They are also used by Windows for volume mount points and files archived by Remote Storage Server. Third-party applications can create their own reparse points to extend the file system, which is how the acquired Windows Services for Unix originally implemented symbolic links.

There's a definitive answer to this by using the "fsutil reparsepoint" command in Windows XP. This is a directory containing two symbolic links and a junction points:

c:\test>dir
Volume in drive C has no label.
Volume Serial Number is 1C59-71F8

Directory of c:\test

10/09/2006 07:32 AM <DIR> .
10/09/2006 07:32 AM <DIR> ..
10/03/2006 06:00 PM <DIR> dest
10/03/2006 05:52 PM <JUNCTION> junction [c:\test\dest]
10/09/2006 07:22 AM <SYMLINK> symlink.txt [test.txt]
10/03/2006 05:51 PM <SYMLINKD> symlinkd [dest]
10/03/2006 05:52 PM 0 test.txt
2 File(s) 0 bytes
5 Dir(s) 5,580,132,352 bytes free

This is the contents of a reparse point for a symbolic link to a directory.

c:\test>fsutil reparsepoint query symlinkd
Reparse Tag Value : 0xa000000c
Tag value: Microsoft
Tag value: Name Surrogate
Tag value: Symbolic Link

Reparse Data Length: 0x0000001c
Reparse Data:
0000: 08 00 08 00 00 00 08 00 01 00 00 00 64 00 65 00 ............d.e.
0010: 73 00 74 00 64 00 65 00 73 00 74 00 s.t.d.e.s.t.

This is the content for a junction.

c:\test>fsutil reparsepoint query junction
Reparse Tag Value : 0xa0000003
Tag value: Microsoft
Tag value: Name Surrogate
Tag value: Mount Point
Substitue Name offset: 0
Substitue Name length: 32
Print Name offset: 34
Print Name Length: 24
Substitute Name: \??\c:\test\dest
Print Name: c:\test\dest

Reparse Data Length: 0x00000044
Reparse Data:
0000: 00 00 20 00 22 00 18 00 5c 00 3f 00 3f 00 5c 00 .. ."...\.?.?.\.
0010: 63 00 3a 00 5c 00 74 00 65 00 73 00 74 00 5c 00 c.:.\.t.e.s.t.\.
0020: 64 00 65 00 73 00 74 00 00 00 63 00 3a 00 5c 00 d.e.s.t...c.:.\.
0030: 74 00 65 00 73 00 74 00 5c 00 64 00 65 00 73 00 t.e.s.t.\.d.e.s.
0040: 74 00 00 00 t...

This is the content for a file symbol link.

c:\test>fsutil reparsepoint query symlink.txt
Reparse Tag Value : 0xa000000c
Tag value: Microsoft
Tag value: Name Surrogate
Tag value: Symbolic Link

Reparse Data Length: 0x0000002c
Reparse Data:
0000: 10 00 10 00 00 00 10 00 01 00 00 00 74 00 65 00 ............t.e.
0010: 73 00 74 00 2e 00 74 00 78 00 74 00 74 00 65 00 s.t...t.x.t.t.e.
0020: 73 00 74 00 2e 00 74 00 78 00 74 00 s.t...t.x.t.

I have also noticed the misuse of the words "hard link" on other blog posts. This is from the Microsoft site.

A hard link is a directory entry for a file. Every file can be considered to have at least one hard link. On NTFS volumes, each file can have multiple hard links, and thus a single file can appear in many directories (or even in the same directory with different names). Because all of the links reference the same file, programs can open any of the links and modify the file. A file is deleted from the file system only after all links to it have been deleted. After you create a hard link, programs can use it like any other file name.

A hard link is identical to the same concept in UNIX and refers only to files. It's not technically impossible to have hard directory links; NTFS just wasn't designed that way. A hard link is a peer of the original file; the original file could also be seen as a hard link to the new file.

One last point, I used linkd.exe from the Windows Resource Kit; junction.exe appears to have limitations constructing junctions on other drives.

Symbolic Links in Vista

I have been reading Hanselman's post on symbolic links in Vista and trying to get a handle on what exactly is the difference between junctions and the new UNIX-style symbolic links in Windows Vista.

Windows Vista now supports four different types of links: shortcuts, hard links, junctions and symbolic links.

Desktop Shortcuts are COM-based objects understood and maintained by the shell. Shortcut data resides in special .lnk files that store metadata such as icons and can point to files, command strings, directories and other shell objects. While these are the most common and most user-friendly links used, they are not recognized by the underlying operating system, making them almost worthless to developers.

The other types of links are handled properly in API calls, but are only available in NTFS.

Hard Links are very tight file links that seem to track the location of target within a single volume. In reality, hard links are based on the same concept in UNIX and represent an N:1 association between a file name and a data object. Each data object contains a reference count of how many file names refer to it. When all files referring to the data object are deleted, then and only then is the data object removed. Every file is thus a hard link to its data, and there is no notion of a source or target file. Hard links can only reside in a single volume.

Symbolic links and Junctions ("soft links") both use reparse points and store the string path of the target file system object. Symbolic links for both directories and files were returned when I typed "dir /aL" to list just reparse points, and there was other evidence in the MSDN pages. Unlike hard links, the target object does not actually have to be in the same volume or actually exist for either type of link.

Junctions and symbolic links for directories are similar enough that junctions were often referred to as symbolic links in past versions of Windows. There are a few differences, though:

• Symbolic links also work on files in addition to directories.
• Symbolic links store relative paths, while junctions uses absolute paths. This difference is noticeable when moving links around the file system. Symbolics links are much better for referring to nested directories.

Microsoft says symbolic links are designed to preserved UNIX idiosyncrasies. They may have been swiped from Windows Services for UNIX.

A symbolic link is a file-system object that points to another file system object... Symbolic links are transparent to users; the links appear as normal files or directories, and can be acted upon by the user or application in exactly the same manner. Symbolic links are designed to aid in migration and application compatibility with UNIX operating systems. Microsoft has implemented its symbolic links to function just like UNIX links.

In comparison, Microsoft mentions this about junctions:

A junction (also called a soft link) differs from a hard link in that the storage objects it references are separate directories, and a junction can link directories located on different local volumes on the same computer. Otherwise, junctions operate identically to hard links. Soft links are implemented through reparse points.

Hanselman's claim that junctions don't work across volumes may have been in reference to Russinovich's warning that junctions do not work on remote shares, which is true, and his use of Russinovich's tool junction.exe, which may have an articial limitation against local volumes. I do know that junctions have always and still do work on separate volumes as this is how my development environment is set up.

The MSDN documentation implies that while junctions are essentially treated as being identical to the target directory, symbolic links are more leaky and often treated as the link files they are, resulting in a number of changes to API calls to treat symbol links specially. That is, some operations that would have operated on the target of junctions may only operate on the symbolic link itself.

Symbolic links might also treat access control differently from junctions. I read that access restrictions are ignored on the link itself in UNIX, but I doubt this is true for Windows given Microsoft's penchant for enforcing security so much so that features become completely and inexplicably inaccessible behind a cryptic "Access Denied" dialog.

MVP - C#

I just received this email message from Microsoft this morning:

Dear Wesner Moise,

Congratulations! We are pleased to present you with the 2007 Microsoft® MVP Award!

The Microsoft MVP Award is our way of saying thank you and to honor and support the significant contributions you make to communities worldwide. As a recipient of Microsoft’s Most Valuable Professional award, you join an elite group of technical community leaders from around the world who foster the free and objective exchange of knowledge by actively sharing your real world expertise with users and Microsoft. Microsoft salutes all MVPs for promoting the spirit of community and enhancing people’s lives and the industry’s success everyday. To learn more about the MVP Program, visit: www.microsoft.com/mvp.

Your extraordinary efforts in Visual Developer - Visual C#  technical communities during the past year are greatly appreciated....

Apparently, I am more valuable to Microsoft now than I was when I used to work there. Maybe the award is a subtle but effective way to influence me and preemptively quash any criticism I might write have about Microsoft in the likely event I become even more well-known. Or, maybe Microsoft actually appreciates my efforts in my blog and elsewhere. Nah. Either way, thanks, MS.

I gain all sorts of access to new confidential information about future products at Microsoft, which I can no longer talk about until one of the MSDN bloggers spills the beans. The information has to be something that I knew beforehand or that has been become publicly available. I used to write about "undocumented" aspects of .NET, so now each post places me in legal jeopardy. I'll have to wait in hiding and then pounce on a careless MSDN blogger who leaks information. I might have to link to my sources for all the juicy bits.

Persistent Performance

There are a number of tricks that I discovered for getting performance out of persistent, immutable data structures. I also recently noticed this MSDN post on Persistent data structures.

Persistent Arrays and Hashtables

Persistent versions of arrays and hashtables do exist with similar constant-time behavior. They won’t be as fast since they obviously do more. Of course, traditional data structures can always be treated as immutable, if we commit to not making any more modification.

Lazy Data

It’s possible to modify immutable data by creating a node that represents the operation and points to the data, since the underlying data is guaranteed not to change. This can turn a lengthy operation into a constant-time one. For example, to construct a difference of two persistent sets, we create a node representing the difference of the two sets rather than actually building an entirely new set. Looking up an element then requires checking to see if the element exists in the first set and is absent in the second.

Modification Box

Modifying a persistent binary tree needn’t actually require log(n) space. Sleator and Tarjan (the same people who invented splay trees) came up with an stunningly elegant technique called modification boxes that adds a small constant amount of space per modification. It blends the two traditional techniques for maintaining persistence (path copying and fat nodes) and comes up with a superior approach to both.

The downside of using a modification box is that rebalancing and other behavior-preserving transformations/optimizations are either no longer possible or significantly harder than path copying.

Treaps

Red-black trees are typically faster and shallower than treaps, but treaps are much easier to implement. R-B trees have a bounded depth of 2 lg n, while treaps are unbounded (ie, O(n)). The simplicity of treaps makes it straightforward to include more advanced operations such as set operations, even though the algorithms for R-B trees are similar using tree splitting and concatenation. (I noticed that the fast set operations described Blelloch and Miller could have been further optimized from O(m lg(n/m) ) where m <= n by including trivial equality checks; this could result in substantial performance gains if both treaps descended from a common parent. Another observation is the excellent potential for parallelization in their set algorithms.)

R-B Trees require a bit flag, whereas treaps require a priority value. However, the priority need not be stored, but can be obtained from the key’s hashcode. In this case, another optimization opportunity arises. The structure of the treap is completely determined by the elements it contains. This makes equality testing potentially faster and increases sharing opportunities. Some algorithms might be able to exploit this property effectively.

Equality Testing

I mentioned in an earlier post that comparing two immutable objects for equality can be made into a fast operation. Comparing hashcode values provides an instant check for inequality. However, if two equivalent objects reside in different memory locations, a positive test for equality can become very expensive, especially if the object tree is deep. Ideally, we would prefer to keep only one copy of equivalent objects, which we then share so that any two equivalent objects have the same exact reference.

The trick is to define a new Equals(ref object obj1, ref object obj2) function that compares two objects for equality and, in the case that both objects are determined equal, normalizes their references. Normalization makes both references refer to the older object, which is more likely to be shared and located in infrequently collected Gen 2. A crude approach is to compare the generation of each object using GC.GetGeneration(obj). A granular approach is to compare the actual address of each object when the first test fails: A lower address typically corresponds to an older object, especially when both objects are allocated in the same heap segment.

From what I have read and seen, the garbage collector allocates (via VirtualAlloc) a 16MB segment of memory at a time for its heap. When that segment is exhaused, a new current segment is allocated. All current Gen 0 and 1 allocations reside on the current segment; previous segments are Gen2. I suspect that GC’s special handling of pinned objects keeps this statement from being entirely true.

private struct AddressStruct
{
   public object Obj;
   public IntPtr Ptr;
}

private static int addressLocation = InitAddressLocation();

private static int InitAddressLocation()
{
    addressLocation = -1;
    if (GetAddress(null) != 0 || GetAddress("X") == 0)
    {
        addressLocation= 1;
        if (GetAddress(null) != 0 || GetAddress("X") == 0)
            throw new Exception("Assumption of CLR data layout is invalid.");
    }

#if DEBUG
// This won't always succeed since objects may be
// stored in different GC segments, but this is 
// extremely unlikely because a full GC & more would need to occur
    object obj1 = new object();
    object obj2 = new object();
    Debug.Assert(IsOlder(obj1, obj2));
    Debug.Assert(!IsOlder(obj2, obj1));
#endif
    return addressLocation;
} 

public static unsafe long GetAddress(object obj)
{
    AddressStruct address;
    address.Obj = obj;
    address.Ptr = IntPtr.Zero;
    return (long)(&address.Ptr)[addressLocation];
}

public static bool IsOlder(object obj1, object obj2)
{
    if (obj1 == obj2 || obj2 == null) return false;
    if (obj1 == null) return true; 

    while (true)
    {
        int count = GC.CollectionCount(0);
        int cmp = GC.GetGeneration(obj1) - GC.GetGeneration(obj2);
        bool result = (cmp != 0)
            ? cmp > 0
            : GetAddress(obj1) < GetAddress(obj2);
         if (count == GC.CollectionCount(0))
            return result;
    }
}

public static bool Equals<T>(ref T obj1, ref T obj2)
    where T : class
{
    if (obj1 == obj2) 
        return true;
    if (obj1 == null || !obj1.Equals(obj2))
        return false;
    if (IsOlder(obj1, obj2))
        obj2 = obj1;
    else   
        obj1 = obj2;
    return true;
}

Closures in Java Vs C# (Non-Local Gotos, Custom Syntax)

Sun is looking to add closures into an upcoming version of the Java language. Partial closures are already supported through the heavyweight inner classes feature. Interestingly, full closures were available in a prerelease version of Java and then removed due to user feedback.

I spoke to Gilad Bracha at the Lang.Net Symposium about Sun’s apparent disregard for functional programming such as closures. The last wave of new features introduced included virtually no functional programming constructs. I alluded to Guy Steele’s piece on Objects Have Not Failed. Gilad revealed his own preference for closures, saying that he was on my side in this matter and has been advocating these features at Sun for years. I yesterday noticed his post Achieving Closure, which confirmed his earlier remarks.

Sun’s Closure Proposal proposes two new features, function types and closures. These new features are almost a superset of what C# currently offers. Each language takes the other’s innovations and tries to outdo each other, but with a different syntax.

The new “function types” are structural just like C++ function pointers, not nominal as delegates are in C# and .NET. Structural typing in C#, however, is possible through the used of parametrized types (generic delegates) and special conversions for method groups. LINQ., for example, uses generics (eg, Func<A1,A2,T>) to simulate structural typing.

Java closures can read and write to locals, captured from the enclosing scope, just as in C#, but there are numerous differences from C#.

• Closures can be named, but in Java, I suspect, it’s implemented as an assignment of an anonymous function to a local variable; however, named closures may be treated more like regular methods, such as how return statements are handled.
  
• Java closures goes one step further than C# closures by allowing non-local break, continue, and return statements just as in Smalltalk and Perl.
  
• In addition, closures can be use to extend Java syntax in a clean way, so that developers can create, for example, their own for, while, if equivalents in an manner similar to Perl. Basically a function that takes a closure as an argument can eliminate the parentheses surrounding the argument list.  

In C#, List<T>.ForEach() with an anonymous method isn’t quite the same as foreach, because there is no way to exit the operation prematurely except through an expensive exception. This was one of my reasons for advocating lightweight exceptions in the past. The Java proposal would make it possible to return, break and continue from inside the closure. It’s not entirely perfect reimplementation, because breaks and continue only exit standard Java looping constructs.

The new custom syntax support could have eliminated the need for a custom lock and using keyword in C#. Java’s approach effectively refutes an argument made by Anders in the last PDC panel about the downsides of creating new syntax—that the new syntax would result in the inability to understand and maintain someone else’s code if hygienic macros were added (see C++). The proposal takes what can already be achieved through closures anyway and compresses the syntax further into a more readable version. Instead of writing the following:

FireAndForget (delegate {
   // Do action
});

One can simply write

FireAndForget {
   // Do action
};

Big Lists

As part of my goal of programming in a more functional programming style in C#, I have been looking at scalable, immutable representations of lists. Some may feel bothered by the log(n) allocations required for each operation to a persistent data structure. However, an operation can be arbitrarily complex like a set of assignments or an insertion of an array of values. Plus, persistent data structures enable a whole set of high-level optimizations.

Having built immutable sets and maps, I already had an implementation idea for lists, but I decided to look around on the web. I did build a few years ago a scalable, mutable implementation of a list using trees as detailed in my post on .NET Collections. The ideas from that post were also picked up by Peter Golde in his post on tree-based lists and eventually became the BigList class in the PowerCollections library. Peter’s BigList class can be efficiently used as an immutable list in a functional programming style or as a traditional mutable list.

His list is not as highly optimized for functional programming as I would like though: Immutable list deletion requires two substrings and one concatenation operation; this could have easily been made one operation. In addition, some other operations, such as equality testing remain slow. I liked the ability to perform differencing and merge operations very quickly, since I anticipate writing algorithms that work on two lists derived from a common list.

BigLists are based on ropes, elegantly described in this paper, Ropes: An Alternative to Strings.  A rope is an immutable representation of a list (in this particular case, a string of characters), which provides for logarithmic-time modifications of data and efficient sharing of data. The idea of ropes made me rethink my position on piece tables in an earlier post of mine, Programmer’s Myopia; the use of linked lists is still a bad design decision. Ropes were used as an alternative representation of strings in the original SGI implementation of the STL library:

Ropes are a scalable string implementation: they are designed for efficient operation that involve the string as a whole. Operations such as assignment, concatenation, and substring take time that is nearly independent of the length of the string. Unlike C strings, ropes are a reasonable representation for very long strings such as edit buffers or mail messages.

Though ropes can be treated as Containers of characters, and are almost Sequences, this is rarely the most efficient way to accomplish a task. Replacing an individual character in a rope is slow: each character replacement essentially consists of two substring operations followed by two concatenation operations. Ropes primarily target a more functional programming style.

Advantages:

• Much faster concatenation and substring operations involving long strings. Inserting a character in the middle of a 10 megabyte rope should take on the order of 10s of microseconds, even if a copy of the original is kept, e.g. as part of an edit history. In contrast, this would take on the order of a second for conventional "flat" string representation. The time required for concatenation can be viewed as constant for most applications. It is perfectly reasonable to use a rope as the representation of a file inside a text editor.
• Potentially much better space performance. Minor modifications of a rope can share memory with the original… Assignment is simply a (possibly reference counted) pointer assignment. . It is very inexpensive to checkpoint old versions of a string, e.g. in an edit history.
• It is possible to view a function producing characters as a rope. Thus a piece of a rope may be a 100 MByte file, which is read only when that section of the string is examined. Concatenating a string to the end of such a file does not involve reading the file….

Disadvantages:

• Single character replacements in a rope are expensive. A character update requires time roughly logarithmic in the length of the string. It is implemented as two substring operations followed by two concatenations.
• A rope can be examined a character at a time through a const_iterator in amortized constant time, as for vector<char>. However this is slower than for vector<char> by a significant constant factor (roughly a factor of 5 or 10 if little processing is done on each character and the string is long). Nonconst iterators involve additional checking, and are hence a bit slower still…
• Iterators are on the order of a dozen words in size. This means that copying them, though not tremendously expensive, is not a trivial operation. Avoid postincrementing iterators; use preincrement whenever possible...

Ropes provide locality benefits as well as their own rebalancing scheme, based on Fibonacci series. I’ll likely be using ropes for my own immutable list implementation.

I rediscovered an algorithm in Joe Duffy’s blog that may improve performance of my persistent data structures. Joe describes an algorithm called “Bloom Filters,”  and points to the original paper and the Wikipedia article. I also came across a well-written paper, “Network Applications of Bloom Filters.” Bloom Filters are very good for speeding up a certain category of software problems. They have been used in spelling applications.

I was intrigued by Joe’s remark that filters could improve the best-case performance time of binary-tree based structures to constant time. Operations on my implementation of persistent sets and maps take O(log n). A treap-based averages about 1.7 log2 n traversals—for a 100–element set, that would be about 12 comparisons.  In tight loops in which the same values may appear often, I cache values into a constant-time hashtable. The Bloom Filter provides an alternative screening method with dramatic space savings; however, the filter does require precomputation beforehand.

The Bloom Filter would also have special application in my natural language work. I maintain an ontology, which essentially is graph of about 30 different relationships between all the words of the English language. It is expensive for me to test for a transitive relationship, or even a direct relationship, between any two words, because I have to do a graph search each time. The probability of any two words having any relationship is very small, and the Bloom filter would allow me to quickly eliminate most negative matches from consideration.

Floating-Pointing Numbers

Working with floating-point numbers can be a pain. I have written several posts on floating-point arithmetic including Numbers in .NET, Floating Point Arithmetic I and II.

There is a good article on “What Every Computer Scientist Should Know About Floating-Point Arithmetic.” There’s also another great article which describes what, I believe, is the best overall algorithm for quickly and accurately comparing two floating numbers. The algorithm reinterprets floating-point numbers as integral values after some adjustment for negative values.

The decimal data type introduced in the .NET framework is meant to alleviate problems with binary-based representations. A decimal number is entered with “m” appended to it (eg, 3.0m). The decimal data type can represent fractional decimal values exactly up to certain level of precision, where as the standard double usually nearly always represent such decimal fraction values imprecisely. For example, 0.5 can be represented exactly as a double, but not any of the other numbers of the form 0.x, where x is neither 5 nor 0. However, division still remains problematic for the decimal data type because of its finite precision. For instance, the value (1m / 3m) * 3m will not be recognized as equal to 1m. In fact, that value will print out as “0.9999999999…” with 28 nines, the maximum precision of a decimal; in the CLR, .999… doesn’t equal one.

These problems won’t go away with either the BigInteger and BigDecimal types that are rumored to be introduced (or more accurately, ported from J#) into a future version of the .NET Base Class Library; infinite precision is required. One of these days, someone will invent a BigRational which is a ratio of two BigIntegers, or an extended BigDecimal, which can encode repeated decimals; we would then only have to worry about irrational numbers like square roots and pi.

Currently, I am adding a new numeric data type, that I called Number, to resolve some issues I have with NStatic tool. Previously, I relied on doubles and used the comparison method mentioned above for doubles. However, I decided that I wanted to represent long integers exactly (in addition to double value) and also to be able represent most fractional values, obtained from division, exactly. So, my new Number type is a 16–byte data type that basically combines doubles, long integers, and rational numbers (up to certain limit). I try to represent numbers as long integers if possible,  then transition to rational numbers, and fallback on doubles. I’m not quite ready for arbitrarily long numbers, which are much slower and whose only application seems to be cryptography. The Number type is a compromise that balances performance and exactness. However, it still won’t be able to represent the full set of values of a decimal, but programs that use the decimal data type are relatively rare and, even then, almost never need more than 64 bits of precision.

 

Miguel and Avalon

Joe Beda has a post “Avalon marks the end of the American Dream,” quoting Miguel de Icaza in the latter’s post “A J2EE Moment of Zen:”

Avalon is the J2EE of GUI APIs.

Miguel’s post originated from a conversation I had with him yesterday at the Lang.NET Symposium. It seems weird to see the remnants of that conversation immortalized on the web. (I also feel bad for Sun that the term for their technology, J2EE, has acquired an unflattering second meaning; even the Sun rep at the symposium, humorously remarked that he actually worked for J2SE, not J2EE.)

I had watched Miguel’s talk on Tuesday on the “Mono” project. He’s an entertaining speaker, who detail the history and purpose of the Mono mission (which, by the way, includes taking over the world.)

I introduced myself to Miguel, telling him, “oh, I wanted to meet with you.” I then reminded him of our brief prior intercourse in cyberspace. He seemed confused. I pointed to his critique of Longhorn changes, especially involving complexities found within Avalon. The post made Slashdot and instantly brought traffic by way of Chris Anderson to my blog post on XAML and Standards. I followed up with a blog post “Avalon Throwaway” to which Miguel responded in a comment.

I brought up the question of frameworks. I used to be an admirer of Java’s framework, particularly with the collection classes, which seemingly was better designed the the original v1.0 collections namespace in .NET. Maybe I had an inherent biased towards APIs that originate from academic circles. I, however, lost any admiration after the birth of J2EE when Java went enterprise. Miguel didn’t think much of J2EE either.

I did mention my disenchantment with the MVC paradigm, and my movement to a more persistent framework. Miguel said that he wasn’t familiar enough with functional programming to provide an answer.

I asked him then about his opinions on various frameworks, first with Avalon, since our past communication was linked together by posts we had each written about Avalon.

ME: What do you think about Avalon?
MIGUEL: It’s the same thing. It’s the J2EE of GUI APIs.

I was taken aback. I remarked well there were two versions of Avalon, and I agree the first one was absolutely complex, but that I thought Avalon was headed in the right direction. The model was more declarative and include markup support; it was relatively simple and easy to construct a user interface.

Miguel then came up with a counterexample. He talked about the lengthy inheritance chain. Despite that complexity, Avalon doesn’t have a tree control; one has to fake a tree view through a list control. My unstated opinion on the matter is resource constraints. There is only a limited amount of work that can go into version 1, but future versions will probably make that a priority.

I asked him about future support for Avalon in Mono. Unfortunately, Miguel said no way; he just wasn’t ready to waste time on an overcomplicated user interface framework. I asked him if he had seen any Avalon demos; he indicated he had seen many, but he didn’t seem impressed.

I went through various frameworks in the Macintosh and UNIX world like NextStep, Cocoa, and Motif. It just seemed like he didn’t like any framework. Now, what about WinForms, which is currently being implemented in the Mono project. Obviously, it’s worthy for his consideration; he doesn’t consider WinForms a framework, merely just a “wrapper” for a Win32 API.

“Well, Is there a framework that you do like?” I asked. “No, not yet,” he replies. I pretty sure that he wasn’t actually including the user-interface toolkit GTK, because he touted some of its benefits over WinForms such as dialog layout.

Throughout the Mono presentation, I was dazzled by the animations and 3D effects of his desktop environment with the realization that both the Linux and the Mac world had left Windows behind with Vista struggling just to catch up. [Here are sample videos of all 3 OSes in actions.] I asked him what desktop environment he was using in the presentation. He said Gnome, and that he heads the Gnome Project. It was like a double whammy. First, the environment is so cool, and, second, that I am talking to its creator.

It was wonderful to meet and talk with him. It’s nice to meet a celebrity.

I did meet about four people who wanted to greet me in the conference. One time, I was busy typing away at my computer. A guy jumps into the seat in front of my view, who wanted to meet me. I don’t know why; what have I actually done in my life?

GUY: Oh, I wanted to meet you (just as I had greeted Miguel.) I am Stephen Lees. I commented in your blog once.
ME: When?
GUY: It was about LINQ.
ME: I don’t really recall your name. Who are you?
GUY: I am the Group Program Manager of the VB team.

My memory started to rejiggle a bit. I did recall a PM from the VB team, asking for my thoughts… and I actually referred to him by name in my blog post “Late Binding Suggestions for VB 9.”

Sometimes, I think no one reads my blogs, based on the number of comments I get compared to what Jeff Atwood or Rory Blythe achieve on a regular basis, but then their posts are also more approachable than mine. Then, I surprised whenever I go to a conference, I find that people staring at my name badge and responding, “oh, I read your blog.”

Spec#

At the Lang.NET Symposium, I met up a member of the Spec# research team, Mike Barnett, shared with him information about the tool I was working on, and gave him my contact information. As I suspected earlier, Rustan Leino, who previously worked at HP/Compaq on ESC/Java, joined Microsoft to work on the Spec# programming system.

I watched an impressive presentation on the tool that included real-time IDE integration and syntax highlighting. Spec# works off of IL with the implication that eventually all the .NET languages will eventually support specifications. Indeed, the presentation was called “Why Every Language Should (Will) have Specifications.”

Spec# requires that all calls to functions with specifications be provably true either through existing conditions within code or by using explicit invariants. In this sense, specifications act like an extended type system and can result in code growth by a substantial percentage; however, the benefit is the decreased need to add in unit tests for boundary conditions. This is quite different from my approach in which any assertions are simply checked not to be violated; as a result, no new syntax is required.

I referred Mike to a paper on ESC/Java that detailed prior experience with using ESC. One issue was annotation overhead. The authors indicated that up to 10% of code would need to include some kind of specification.

ESC/Java is an annotation-based checker, which relies on the programmer to provide annotations giving lightweight specifications for each routine. Thus, one of the costs of using ESC/Java is the overhead of writing the necessary annotations. In most cases, these annotations are straightforward
and they document basic design decisions, for example, that a method argument should never be null, or that an integer variable should be a valid index to a particular array.

Our experience in annotating Javafe and Mercator indicates that roughly 40–100 annotations are required per thousand lines of code…

For both of these programs, the annotations were inserted after the program was written using an iterative process: The program was first annotated based on an inspection of the program code and a rough understanding of its behavior;
this initial set of annotations was subsequently refined based on feedback produced by ESC/Java when checking the annotated program. Typically, we found that a programmer could annotate 300 to 600 lines of code per hour of an existing, unannotated program. This overhead is expensive for larger programs and is an obstacle to using ESC/Java to catch defects in large, unannotated programs. While it is possible to use ESC/Java only on selected modules, it is still necessary to annotate all the routines called in other
modules. We are investigating annotation inference techniques [17, 16] that help reduce the annotation burden on legacy code.

Instead of writing annotations after the program has been developed, a better strategy for using ESC/Java is to write appropriate annotations and run the checker as early as possible in the development cycle, perhaps after writing each method or class. Used in this manner, ESC/Java has the potential to catch errors much earlier than testing, which can only catch errors after the entire program or an appropriate test harness has been written. Since catching errors
earlier makes them cheaper to fix, we suggest that using ESC/Java in this manner may reduce software development costs in addition to increasing program reliability.

The experience is familiar to anyone who changes parameters types in an existing interface to incorporate C++ const modifiers or .NET generic constraints.

I did comment about about some of the limits of Spec# with exceptional phenomenon like iterators, closures, virtual functions, etc. According to the Spec# website, the tool is quite sophisticated, being able to deal with callbacks, threads, and inter-object relationships. The Spec# team does not use a closed-world assumption for handling virtual functions, but which actually does make sense for a stand-alone application versus a class library that whose classes could be extended.

I asked him about loop handling and indicated to him how I was using recurrence relations to deal with the problem. Early papers on Spec# indicated that assigned variables within a loop were assigned a havoc value, which essentially means that variables are assumed to contained anything. ESC/Java attempts a different approach.

Therefore, ESC/Java approximates the semantics of loops by unrolling them a
fixed number of times and replacing the remaining iterations by code that terminates without ever producing an error. This misses errors that occur only in or after later iterations of a loop…. By default, we unroll loops one and a half times (the half refers to an additional execution of the loop guard):

He seemed to indicate some complicated analysis being done in this area.

Mike entertained questions about decidability from another attendee. Spec# can verify all linear assertions. But nonlinear expressions, like x*y == 5, are not completely handled by the system and therefore could require explicit invariants. For undecidable cases, Spec# includes a timeout and conservatively issues errors in such case.

I also inquired about patents on Spec# mentioning Patent #7,058,925. He wasn’t actually aware of any patents and stated that all the work is actually published. The patent I mentioned was more likely filed by Microsoft research group that produces the SLAM tool, used in Office and Windows. Anyway, he mentioned that Microsoft’s use of patents is primarily defensive (although, Microsoft’s recently announced Windows 12 Principles does talk about reasonable terms in licensing patents.)