Coding Patterns

Exploring the Fibonacci Numbers

2009-06-03T18:56:00.000-07:00

Recently I decided to teach myself Haskell by using it to solve Project Euler problems. This kills two birds with one stone, since I've been wanting to tackle both. Also, it sounded like a lot of fun.

Project Euler problem #2 is simple enough:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

But, since I'm doing this for personal enrichment I decided to investigate in more detail. I did not notice this before solving it the first time (asking a stupid question in the process), but it turns out that every third fibonacci number is even. Furthermore, there is a surprising relationship between every third fibonacci number: f(n) = 4*f(n-3) + f(n-6)[1]. So it is possible to solve the problem efficiently by enumerating just the even fibonacci numbers. In this post I'll use g(n) to denote the nth even fibonacci number. The sequence can be implemented in Haskell, using list comprehension syntax, like so:


 -- g(n) = 4*g(n-1) + g(n-2)
 g :: [Integer]
 g =  2 : 8 : [ a + 4*b | (a,b) <- zip g (tail fibs2)]

But can we do better? I remembered one of Raganwald's homoiconic posts about computing fibonacci numbers efficiently using a matrix multiplication technique (pardon the ascii-art notation):


 m^n, where m = (1 1) , is equivalent to: ( f(n)   f(n-1) )
                (1 0)                     ( f(n-1) f(n-2) )

So the nth fibonacci number is the upper-left element in the matrix obtained by multiplying m by itself n times[2].

Also interesting is that a source article of the post at homoiconic gives an efficient algorithm for calculating the sum of fibonacci numbers using the matrix representation of the sequence. Now we're getting somewhere! It should be possible to modify the matrix approach so that it generates only the even fibonacci numbers, using the formula described above[3]. And if we can do that, we can calculate their sum efficiently with the provided algorithm.

You can do exactly that using these two matrices:


 b = (8 2)   m = (4 1)
     (2 0)       (1 0)

where b is the base case and m is the multiplier. Notice that if you multiply a generic fibonacci matrix (where a,b,c are consecutive even fibonaccis) by m, you get:


 (a b) * (4 1) = (4a+b, a)
 (b c)   (1 0)   (4b+c, b)

Which generates the matrix containing the next consecutive even fibonacci number (recall that the nth even fib g(n) is equal to 4*g(n-1) + g(n-2), which is 4a+b if a and b are the two previous even fibs). Using the matrix b to bootstrap the multiplication (because it contains 2 and 8, the first two even fibs), it follows that b*m should produce the 3rd even fibonacci number, b*m*m should produce the fourth, b * m^3 the fifth, and in general:


 g(1) = 2
 g(n) = b * m^(n-2) [4]

So, now we have an equation for using matrix multiplication to compute even fibonacci numbers. How can we use it to efficiently compute the sum of the first n numbers in that sequence? Let's use a concrete example, n=7. We want to calculate


 g(1) + g(2) + ... + g(7)  =  2 + b + b*m + b*m^2 + ... + b*m^5

factoring out the common b term, we have


 2 + b(m^0 + m^1 + m^2 + m^3 + m^4 + m^5)

where m^0 evaluates to the identity matrix. For convenience, let's define a function sum(n,m) that computes the sum m^0 + ... + m^n, so the above equation can be written 2 + b*sum(5,m) We can see that the bulk of the computation for large values of n will be in calculating each of the matrices m^2, m^3,...,m^n. But notice the following equivalence:


 m^0 + m^1 + ... + m^5  =  (m^0 + m^1 + m^2) + m^3(m^0 + m^1 + m^2)

by expanding the equation in this manner, we can calculate sum(5,m) with considerably less work. Notice the recursive structure of the equation: sum(5,m) = sum(2,m) + m^3 * sum(2,m). In general pseudocode:


 sum(n,m) =
   if n == 0  then return i //the identity matrix
   if odd(n)  then let s = sum(floor(n/2), m)
                   return s + m^ceil(n/2) * s
   if even(n) then let s = sum(n/2, m)
                   return s + m^(n/2) * s + m^n

the 'even' case is slightly more complicated because it needs to take into account that the sequence m^0 + ... m^n is not evenly divisible into two pieces. The algorithm can be further optimized by having our sum function return m^n as well as the current running sum. This unfortunately obfuscates the algorithm with extra bookkeeping, but it ensures that we aren't wasting any work from one call to the next, and sum(n,m) must calculate m^n or m^n/2 anyway, so it is not much overhead. The 'odd' step from the above algorithm would then look something like this:


 let s, m_exp = sum(floor(n/2), m) //m_exp is m^floor(n/2)
 return s + (m_exp * m) * s, m_exp*m_exp*n //return both the sum and m^n

One final optimization. Raganwald noted in his original post that there is redundancy in the matrix representation, and we can easily re-write our matrices as tuples of 3 elements:


 b = (8, 2, 0)    m = (4, 1, 0)

Multiplication on these tuples is essentially the same as matrix multiplication (details at homoiconic). Putting it all together, we have the final, executable haskell:

The naive implementation is faster for small n, but once you get above n=5-10k this optimized version overtakes it and never looks back. The full code, including multiple solutions to the project Euler question and benchmarking of the naive implementation against this one, is available here.

[1] This is easy to verify yourself. Start with 4*f(n-3) + f(n-6) and keep simplifying until you get f(n)
[2] For convenience, define the first two fibonacci numbers to be 1,2. Take some time to convince yourself of this, if you like. The computation can be done in O(log n) multiplications (instead of n multiplications) by multiplying in a clever order. See the source articles for details.
[3] g(n) = 4*g(n-1) + g(n-2)
[4] I'm abusing notation slightly here. Technically this is the 2x2 matrix containing g(n), not g(n) itself. Also, note that when n=2, m^0 evaluates to the identity matrix. b * m^0 = b * i = b, so no special case is needed for 8.

Data as code: Storing Configuration in C# & Asp.net

2008-12-03T21:19:00.000-08:00

I've been thinking about the best way to store configuration information in c# since I started this blog more than a year ago. I'm a little embarrased that it's taken me so long, but I think I've hit on the best way of doing it (largely inspired by Ayende's JFHCI). Here it is:

Just use c#

That's right! No xml. No web.config. No database. Just use c#.

The benefits are pretty obvious. The reason configuration is a pain is because you have to spend several lines of code extracting information from some foreign (and usually weakly-typed) source, and loading it into c#. You have to worry about checking for null "just in case", etc. Keeping everything in c# saves a lot of code and is radically simpler. This approach is popular in scripting languages like Ruby.

It's less obvious why the apparent drawbacks aren't actually drawbacks. Some typical objections:

But then the configuration is compiled-in. You can't modify it on the fly!
This is false in Asp.net. Although there is a pre-compilation option, ever since 2.0 the default has been to read the source files and compile them into temporary assemblies on the fly. This would be a valid criticism for a WinForms app. But seriously, who uses WinForms?
But that's just hard-coding!
Yes, it is! Embrace it.
Storing configuration data in c# is ugly and unintuitive because c# isn't a good data format.
True, c# is not lisp or json or xml. Initializing a complex data type the traditional way would involve declaring the type, then initializing it imperatively in a constructor. This separation means that the code does not look like data in the way that traditional config files do.

But with c# 3.0, I think the language is good enough at representing data to overcome this objection. Collection initializers and object initializers are expressive enough that you should never need a constructor to do initialization.

Let's run with this a little bit. Say you need to add a list of email addresses for generating error emails. Just pop open config.cs, and type this:


public static var ErrorEmails = new List<string>() {
    "joe@bob.com",
    "jane@bob.com",
    "julie@bob.com"
}

That's not so bad, is it? Clear, strongly typed, native c#, at least as easy to modify on-the-fly as xml or database configuration. Let's take a more complicated example: Suppose our application allows the user to submit different types of Requests, and each Request has a bunch of metadata associated with it: a code, request group, name, and description. Also suppose we want to look up the Request metadata given a code. We can do something like this:


public static var Codes = new Dictionary<string, CodeData>() {
    { "Code1", new CodeData { Group="...", Name="...", Desc="..." } },
    { "Code2", new CodeData { Group="...", Name="...", Desc="..." } },
    { "Code3", new CodeData { Group="...", Name="...", Desc="..." } },
    { "Code4", new CodeData { Group="...", Name="...", Desc="..." } }
}

That is the sort of information that I probably would have placed in a database before. The benefits of doing it this way should be obvious. Instead of dropping down into SQL to query the data and loading it into c#, I can now start off in c#. I can use LINQ to easily query the data to return anything I need.

Yes, it's unconventional. Do it anyway.

Javascript Dom Builder

2008-06-03T20:23:00.000-07:00

I hate the Dom. So I decided to fix it.

basic usage


   1         domBuilder($get('basic'))
   2         .div({id: 'div1', style: 'height:50px;border-style:solid;border-width:4px;padding:1px;'})
   3           .div({style: 'float: left;' })
   4             .span().text('purple, ').end()
   5             .a({href: 'http://www.google.com'}).text('google').end()
   6           .end()
   7           .div({style: 'float: right;' })
   8             .span().text('cat').end()
   9           .end();

Adding event handlers


   1         domBuilder($get('event'))
   2           .div()
   3             .span().text('some text').end()
   4              .input({id:'evt_test', type: 'text'})
   5                .on('blur', function() {alert('blur!!');})
   6                .on('focus', function() {alert('focus!')})
   7              .end();

using custom (not pre-defined) tags


   30         domBuilder($get('custom'), ['select', 'optgroup', 'option'])
   31         .select({id: 'select_test'})
   32           .optgroup({label: 'swedish cars'})
   33             .option({value: 'v'}).text('Volvo').end()
   34             .option({value: 's'}).text('Saab').end()
   35             .option({value: ''}).text('').end()
   36           .end()
   37           .optgroup({label: 'german cars'})
   38             .option({value: 'm'}).text('Mercedes').end()
   39             .option({value: 'a'}).text('Audi').end()
   40           .end();

Essentially the DomBuilder function takes a dom element and returns an object that lets you add nodes to it easily. The most common html tags are pre-defined. You can also insert an arbitrary tag with the 'add' method: .add('foo', {id: 'foo'}, although the expected usage is to tell dom-builder about the custom tags you want to use and let it create helper methods for you, as in the third example above. One gotcha of the fluent-interface style is that you may be tempted to leave off the end() calls - proper indentation can make the code look correct when it is not. end() is only optional at the end of the method chain - in other words, final end()s are implicit.

One benefit of the fluent interface style is that it is easy to extend. For example, you could add a css() method, some sort of auto-close method or parameter (analagous to <tag />) so that an explicit end() is not required, etc.

dom-builder is built on top of the YUI library, and is inspired slightly by Ruby's xml-builder. It is not an original idea - it has been done before in similar ways and by smarter people. Still, it's always helpful to work something out for yourself, and from an aesthetic point of view I prefer my API decisions over those solutions anyway. Examples, tests, and source are available here.

Pluggable Type Systems and the future of Programming Languages

2008-04-18T21:40:00.000-07:00

Programming languages come and go at an astonishing pace, and few enjoy the spotlight of geek popularity for long. Heck, Java used to be cool. And so did Perl. The pace at which technology moves sometimes makes me wonder if we are actually getting anywhere, or if we are just moving to be moving. There's a sort of elite snobbery among hackers that shuns popularity. Did Java fall out of favor simply because it became too popular?

Although I certainly wouldn't put it past some corners of hackerdom to shun something just because it is popular, I do not think this is what is happening in the mad race for newer and shinier programming languages. After all, Isn't Java better than c++? And aren't Python and Ruby better than Perl? And isn't Javascript... well, never mind about that.

The point is that languages don't fall out of favor among hackers simply because they become popular. They fall out of favor because hackers are very promiscuous about their programming languages and move on to something better when they find it. And since there is a whole lot of creativity in that community, something better comes along pretty regularly.

I don't expect innovation to continue at this pace forever, though. Many of the good ideas making their way into the mainstream today were invented in academia 30 or 60 years ago. Eventually the popular languages are going to converge around a more-or-less standard set of features, and there will be less need for such rapid innovation.

Encouragingly, I think we're catching a glimpse of one area around which programming languages are going to converge in the near future: pluggable type systems (that is, optional type systems which are dynamic in nature and can be removed, modified, or extended). This is happening from both directions: dynamic languages are adding optional static features, and static languages are becoming more dynamic. Consider the signs:

Javascript 2 will have optional typing
Python 3 will have function annotations, which have no semantic meaning on their own but can be interpreted by 3rd-party libraries.
One of the JRuby developers is working on a toy Ruby dialect that adds type annotation to the language. Interestingly, the type annotations are valid Ruby and would just be ignored (or immediately garbage-collected) by a normal Ruby interpreter - giving them a pluggable flavor.
The next version of c# will support dynamic method lookup.
Qi, an interesting lisp-like language, has an optional type system.
Boo, a statically-typed scripting language for the CLR, has a "duck" type which allows method lookups to be done at runtime.

Granted, some of these examples are obscure. But the number which are not is pretty remarkable. It shows that with regard to type systems, we as community of programmers are learning to be pragmatic rather than purist. I think this is a real sign of maturity because it means we are transcending the static/dynamic holy wars. The Java design philosophy of ruthless consistency is no more. We've been down that road, and we don't like what we saw. We know that not everything is an object and that gee, it would be nice to be able to remove checked exceptions if we wanted to. And although I don't know where we will end up, I do know that it will be better than where we are today.

Switching Keyboard Layouts: Colemak

2008-01-28T08:05:00.001-08:00

In an effort to preserve my hands, I've switched my keyboard layout from the contorted-and-inexplicable Qwerty to the comfortable, ergonomic upstart Colemak. I spent a day using Dvorak before doing some more research and settling on Colemak. Both layouts require startlingly less hand motion than Qwerty, and greatly reduce awkward finger motions. The best way to get a feel for the magnitude of the difference is to go to this typing-test site and replay one of the high scores. You can toggle between Qwerty, Dvorak, and Colemak, and see visually how much your hands would be moving in that layout. This applet will let you compare layout statistics on a given piece of text.

All in all, I think Colemak is the clear winner over Dvorak. Here they are, for reference:

Dvorak:

Colemak:

I was initially skeptical of Colemak because one of its main selling points is that it is much more similar to Qwerty than Dvorak is, and therefore easier to learn. I was afraid that it might have sacrificed ergonomics for similarity to Qwerty. This is not the case. Dvorak is optimized for alternating work between the left and right hand, and using it felt like a delicate left-right dance. Colemak on the other hand is optimized for grouping common letter pairs (digraphs) together so that you can hit them with one smooth hand motion. I find this more comfortable than the focus on alternation in Dvorak. Colemak also remedies two minor annoyances I had with Dvorak: "R" isn't on the home row, and "L" is delegated to the right pinkie, making it harder to reach than it's frequency warrants. Other Colemak benefits:

Caps Lock is mapped to backspace. Brilliant!
The punctuation keys are in the same place as in Qwerty. I didn't find the top-row Dvorak placement any worse, but I didn't find it any better either, and this is one less thing to relearn.
The Z/X/C/V keys don't move, so the most common shortcut keys don't need to be relearned.

Pretty much the only thing I liked better about Dvorak is the convenient placement of the "-/_" key, which as a programmer I use a lot. But nothing is perfect, I guess.

One of the most interesting (to me) aspects of switching was getting an insight into how the body learns to type quickly (I got up to about 80 WPM in Qwerty, although typing that fast is so uncomfortable that I rarely do it). It happens largely by burning common words and letter combinations into your muscles, not by stringing together individual keys. After almost 3 weeks on Colemak, I find that my most common mistakes aren't on particular letters but in particular contexts. I may get "I" right most of the time, but I still invariably type the Qwerty "I" in certain words. Because of the Colemak emphasis on digraphs, I get the feeling that as I burn it into my fingers it will make for more comfortable and smoother typing.

All things considered I'm very glad I made the switch, and I'd recommend it to anyone who makes a living on a keyboard. Your hands have to last you the rest of your life, and Colemak will help them to.

Code Organization

2008-01-04T13:13:00.001-08:00

Even though I read Steve McConnell's seminal Code Complete years ago, there is one piece of advice in it that I use every day. In the section Making Code Read from Top to Bottom, he presents a poorly organized code fragment and reorganizes it:

    1 /* C Example of Bad Code That Jumps Around */
    2 InitMarketingData( MarketingData );
    3 InitMSIData( MSIData );
    4 InitAccountingData( AccountingData );
    5 
    6 ComputeQuarterlyMarketingData( MarketingData );
    7 ComputeQuarterlyMSIData( MSIData );
    8 ComputeQuarterlyAccountingData( AccountingData );
    9 
   10 ComputeAnnualMarketingData( MarketingData );
   11 ComputeAnnualMSIData( MSIData );
   12 ComputerAnnualAccountingData( AccountingData );
   13 
   14 PrintMarketingData( MarketingData );
   15 PrintMSIData( MSIData );
   16 PrintAccountingData( AccountingData );
   17 
   18 
   19 /* C Example of Good, Sequential Code That Reads from Top to Bottom */
   20 InitMarketingData( MarketingData );
   21 ComputeQuarterlyMarketingData( MarketingData );
   22 ComputeAnnualMarketingData( MarketingData );
   23 PrintMarketingData( MarketingData );
   24 
   25 InitMSIData( MSIData );
   26 ComputeQuarterlyMSIData( MSIData );
   27 ComputeAnnualMSIData( MSIData );
   28 PrintMSIData( MSIData );
   29 
   30 InitAccountingData( AccountingData );
   31 ComputeQuarterlyAccountingData( AccountingData );
   32 ComputerAnnualAccountingData( AccountingData );
   33 PrintAccountingData( AccountingData );

McConnell explains why the refactored layout is superior:

This code is better in several ways. References to each variable are "localized": they're kept close together. Values are assigned to variables close to where they're used. The number of lines of code in which the variables are "live" is small. And perhaps most important, the code now looks as if it could be broken into separate routines for marketing, MIS, and accounting data. The first code fragment gave no hint that such a decomposition was possible.

The idea is to structure your code so that statements are grouped by the data they operate on, not the operations they perform. I'm often tempted to organize code so that grouped statements "line up" as in the first example. This may be something that I have particular trouble with because a lot of my early coding was done in Pascal, which enforces poor layout in the language syntax. Variables must all be declared in one place, at the start of a method. In class definitions fields must come before properties and methods, when it is clearly better to group related private fields, properties, and getter/setter methods together.

At any rate, this idea can be extended beyond code layout. Just one example: the Rails directory structure is organized by file kind. All the models go in one directory, all the controllers go in another, the tests in another, etc. This is analogous to grouping statements so they "line up", and is exactly backwards. The file groups that belong together logically are those which all relate to the same concept. Folders in Rails ought to be organized by model name (or controller name, for model-less controllers). One folder should hold the model, its controller, tests, and views. This is the important relationship between files: what data they operate on, not what type of file they are.

Because developing in Rails forces you to frequently jump between related files in different directories, every Rails editor or IDE has shortcuts to help you do it. Essentially these editors are plastering the proper logical organization on top of the Rails folder structure, which alleviates the problem. The uniform structure imposed by the the fixed folder layout in Rails is a stroke of genius, but having to use a nonstandard, editor-specific abstraction layer on top of it for actual development limits its awesomeness somewhat.

Encapsulating the Lazy-Load Pattern

2007-12-24T11:26:00.001-08:00

In a previous post I suggested a helper method to wrap the Lazy-Load pattern. I'm now convinced that this was the wrong approach to take. For the specific case I mentioned (lazy-loading a property value), the straightforward test for nil is irreducibly simple. Trying to wrap it in a generic procedure introduces more complexity than it alleviates.

For the more general case in which you have a value which you don't want to compute more than once, the correct pattern is to create a generic wrapper class or method which bolts added functionality onto the type in question. This is a common pattern in the .Net framework: some examples are Nullable<T>, Expression<T>, and Future<T> in the next version of Chrome.

So what we want is some sort of Lazy which will wrap the lazy evaluation. There is one example implementation here. You can consult the article for the (mostly trivial) implementation details. But it enables you to write code like this:

    1 int a = 22, b = 20;
    2 var lazy = Lazy.New(() => {
    3     Console.WriteLine("calculating...");
    4     return new { Mul = a*b, Sum = a+b };
    5 });
    6 Console.WriteLine("Mul = {0}, Sum = {1}",
    7 lazy.Value.Mul, lazy.Value.Sum);

The block passed to Lazy.New is evaluated only once, in the first call to lazy.value. The Lazy.New function is a helper which basically exists to trick the compiler into providing type inference for us so that we don't have to specify the generic parameter.

The main downside to this is that Lazy<T> is a custom class. In order for a function to accept one of these lazy objects as a parameter, it needs to be written specifically with that type in mind. Wouldn't it be cleaner if Lazy.New returned an Func<T> delegate instead?

Well, it can. What we basically want to do is memoize a function of no arguments. And for that the solution presented here is much cleaner:

    1 static class FuncLib
    2 {
    3     public static Func<R> Memoize<R>(this Func<R> f)
    4     {
    5         R value = default(R);
    6         bool hasValue = false;
    7         return () =>
    8         {
    9             if (!hasValue)
   10             {
   11                 hasValue = true;
   12                 value = f();
   13             }
   14             return value;
   15         };
   16     }
   17 }

Let's walk through this. Memoize<T> takes a function with no parameters, and returns a function of the same signature. Here's where it gets sneaky: whereas Lazy<T> defined a new class to hold the cached function value, Memoize<T> takes advantage of the fact that closures have access to their containing scope. The return function carries around a pointer to the local variables value and hasValue, which allows it to remember if the result has been calculated or not.

As an added bonus Memoize<T> is an extension method, which allows us to use it in two ways: either as a helper method similar to Lazy.New, or as a method on a Func<T> object. We can then create lazily-evaluated functions like so:

   32 //using Memoize as a helper method, with type inference
   33 var lazy = FuncLib.Memoize( () =>
   34 {
   35     Console.WriteLine( "calculating..." );
   36     return 42;
   37 } );
   38 
   39 //using Memoize as an extension method, 
   40 //  but without type inference
   41 Func<int> lazy2 = ( () =>
   42 {
   43     Console.WriteLine( "calculating..." );
   44     return 42;
   45 } );
   46 lazy2 = lazy2.Memoize();
   47 
   48 Console.WriteLine( "starting..." );
   49 Console.WriteLine( "result = {0}", lazy() );
   50 Console.WriteLine( "result (again) = {0}", lazy() ); 
   51 Console.Read();

This can't be beaten for elegance, in my opinion.

Thinking Well about OO Design

2007-10-26T12:06:00.000-07:00

Good object-oriented design is hard. Unfortunately, most people don't know how hard it is. The best way to improve your OO design is to ask hard questions about it. And the best way to know which questions to ask is to read people who have thought deeply about where OO sits in the design space: what it is good at and what it is not good at, what you can do to minimize the effects of the things it is not good at, and how best to use the tools it gives you. Design Patterns is a great place to start (read it more than once), and I've found these recent articles to be helpful in getting me to think well about OO design:

Reflection joke

2007-10-26T09:31:00.000-07:00

In the spirit of Steve Yegge's Kingdom of Nouns, Scott Bellware pokes fun at the .Net reflection API compared to Ruby's:

I say :tomato
You say typeof(Fruit).GetField('tomato', BindingFlags.Instance | BindingFlags.Public)

I say :potato
You say typeof(Tuber).GetField('potato', BindingFlags.Instance | BindingFlags.Public)

:tomato
typeof(Fruit).GetField('tomato', BindingFlags.Instance | BindingFlags.Public)

:potato
typeof(Tuber).GetField('potato', BindingFlags.Instance | BindingFlags.Public)

Let's call the whole thing off

Priceless! Be sure to read the comments on Scott's post.

Parsing Enterprise Library Trace Output in Ruby

2007-10-22T22:57:00.000-07:00

The Enterprise Library Tracer class is really handy, and I use it all the time for profiling slow pieces of code. The only problem is that its output is illegible. Using the default formatter, this is what one trace looks like:

    1 ----------------------------------------

    2 Timestamp: 10/24/2007 12:42:00 AM

    3 Message: Start Trace: Activity '03952c36-9e3c-4175-bd5a-9f2ea108ae7e' in method 'App.Results.LoadData' at 1981206585161 ticks

    4 Category: GetPhotoQuery

    5 Priority: 5

    6 EventId: 1

    7 Severity: Start

    8 Title:TracerEnter

    9 Machine: GABE-THINKPAD

   10 Application Domain: /LM/W3SVC/1/Root/App-11-128376599444062500

   11 Process Id: 3564

   12 Process Name: C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\aspnet_wp.exe

   13 Win32 Thread Id: 4164

   14 Thread Name:

   15 Extended Properties:

   16 ----------------------------------------

   17 ----------------------------------------

   18 Timestamp: 10/24/2007 12:42:09 AM

   19 Message: End Trace: Activity 'b7b7c71f-30ae-486c-8206-4d87dd44e2fc' in method 'App.Results.LoadData' at 1981236796826 ticks (elapsed time: 0.07 seconds)

   20 Category: GetPhotoQuery

   21 Priority: 5

   22 EventId: 1

   23 Severity: Stop

   24 Title:TracerExit

   25 Machine: GABE-THINKPAD

   26 Application Domain: /LM/W3SVC/1/Root/App-11-128376599444062500

   27 Process Id: 3564

   28 Process Name: C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\aspnet_wp.exe

   29 Win32 Thread Id: 4164

   30 Thread Name:

   31 Extended Properties:

   32 ----------------------------------------

If you are using multiple nested traces, it's impossible to interpret. A custom log formatter can help.

    1 <formatters>

    2   ...

    3   <add template="{category}({timestamp}): {message}"

    4     type="Microsoft.Practices.EnterpriseLibrary.Logging.Formatters.TextFormatter, Microsoft.Practices.EnterpriseLibrary.Logging, Version=3.1.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a"

    5     name="Short Text Formatter" />

    6 </formatters>

Each entry is now compressed onto one line, and I've gotten rid of the information I don't need:

    1 GetPhotoQuery(8/24/2007 12:16:48 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.Results.LoadData' at 2228474435074 ticks

    2 GetRecords, GetPhotoQuery(8/24/2007 12:16:48 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.DataLayer.getPhotoQuery' at 2228474857791 ticks

    3 GetRecords, GetPhotoQuery(8/24/2007 12:16:48 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.DataLayer.getPhotoQuery' at 2228475263799 ticks (elapsed time: 0.113 seconds)

    4 CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:48 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.DataLayer.getPhotoQuery' at 2228475271352 ticks

    5 LoadAdditionalImages, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:48 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228475285334 ticks

    6 LoadAdditionalImages, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:48 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228475413732 ticks (elapsed time: 0.035 seconds)

    7 LoadPhotoList, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:48 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228475416500 ticks

    8 LoadPhotoList, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:52 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228491499906 ticks (elapsed time: 4.493 seconds)

    9 SortingResults, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:52 AM): Start Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228491505534 ticks

   10 SortingResults, CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:52 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.PhotoRecList..ctor' at 2228491518346 ticks (elapsed time: 0.003 seconds)

   11 CreatePhotoRecList, GetPhotoQuery(8/24/2007 12:16:52 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.DataLayer.getPhotoQuery' at 2228491520681 ticks (elapsed time: 4.539 seconds)

   12 GetPhotoQuery(8/24/2007 12:16:52 AM): End Trace: Activity '466569a2-9713-4e66-aeca-d7d9f87aaae5' in method 'App.Results.LoadData' at 2228491521707 ticks (elapsed time: 4.773 seconds)

Better, but still hard to interpret. If you squint you can tell that this is a series of nested traces. Execution time is at the end of the line. I used to be in the habit of manually reformatting these files: adding indentation to show nesting and removing the attributes I didn't care about. But this kind of busywork is the problem computers were invented to solve. 37 lines of Ruby later, I had a script which would parse trace output like so:

    1 GetPhotoQuery

    2     GetRecords

    3     GetRecords completed at 8/24/2007 12:16:48 AM (0.113 seconds elapsed)

    4     CreatePhotoRecList

    5         LoadAdditionalImages

    6         LoadAdditionalImages completed at 8/24/2007 12:16:48 AM (0.035 seconds elapsed)

    7         LoadPhotoList

    8         LoadPhotoList completed at 8/24/2007 12:16:52 AM (4.493 seconds elapsed)

    9         SortingResults

   10         SortingResults completed at 8/24/2007 12:16:52 AM (0.003 seconds elapsed)

   11     CreatePhotoRecList completed at 8/24/2007 12:16:52 AM (4.539 seconds elapsed)

   12 GetPhotoQuery completed at 8/24/2007 12:16:52 AM (4.773 seconds elapsed)

Which shows me exactly where the bottleneck is. Some highlights of the script:

It chooses the file to parse based on the the script's own filename. Just copy it to the directory your trace file is in and rename it to, eg., mytraces.log.trace_parser.rb to parse the file mytraces.log. This piece of convention over configuration was inspired by Rails.
It generates the readable trace and automatically opens it in notepad for you, so getting the parsed output is a one-step process.

The Ruby source looks like this:

    1 #outputs a file with the trace information in a more readable format

    3 #convention: the log filename is the script filename minus

    4 #   the trailing name and rb extension

    5 src_filename = __FILE__.chomp ".trace_parser.rb"

    6 dest_filename = "#{src_filename}.readable"

    7 dest = File.open(dest_filename, "w")

    9 File.open src_filename do |src|

   10   #need to keep track of how deeply nested we are

   11   indent_level = -1

   13   #print a line with the correct indent

   14   print_line = lambda { |s| dest.puts(" " * 4 * indent_level + s) }

   16   while line = src.gets do

   17     ##### try to capture the start of a trace #####

   18     _, name = /^(\w+).*\Start\sTrace/.match(line).to_a

   19     if name then

   20       indent_level += 1

   21       print_line.call(name)

   22       next # move along to the next line

   23     end

   25     ##### try to capture the end of a trace #####

   26     _, name, time, sec = /^(\w+).*\((.*)\).*End\sTrace.*elapsed time: (\d+\.?\d*) seconds/.match(line).to_a

   27     if name then

   28       print_line.call("#{name} completed at #{time} (#{sec} seconds elapsed)")

   29       indent_level -= 1

   30       next # move along to the next line

   31     end

   32   end

   33 end

   35 dest.close

   37 `notepad #{dest_filename}`

Exploiting Closures: What I learned from Ruby that made me a better .Net Developer

2007-10-17T22:19:00.001-07:00

The .Net framework has had closures (anonymous delegates) for quite a while, but it never occurred to me how I could utilize them until I was exposed to Ruby. Ruby has a beautifully clear and concise syntax for passing a closure to a method, and its libraries make extensive use of them.

The .Net languages I use (c# and Chrome) are statically typed, which introduces some restrictions and syntactic overhead that Ruby doesn't have. But both c# (3.0) and Chrome are fairly good at type inference, so the overhead isn't as high as you might think. Some examples of how my Ruby-inspired appreciation for closures has allowed me to encapsulate common .Net patterns:

Data Access

My usual data access pattern looks something like this:

    1 using (IDataReader rdr = db.ExecuteReader(CommandType.Text, sql))

3 {

    4     while (rdr.Read())

    5     {

    6         result.Add( new BusinessObject(...) );

    7     }

8 }

    9 return result;

Execute the query, loop through the result set, and return a collection of business objects. Rinse. Repeat. Not only does this get repetitive, but I have trouble remembering the using statement. It's not uncommon for me to just forget to dispose the reader when I'm done, which means leaving a database connection open in memory until the garbage collector gets around to cleaning up. Enter GetList:

    1 public static List<T> GetList<T>(Database db, string sql, Func<IDataReader, T> create)

2 {

    3     List<T> list = new List<T>();

    4     using(IDataReader rdr = db.ExecuteReader(CommandType.Text, sql))

    5     {

    6         while(rdr.Read())

    7         {

    8             list.Add(create(rdr));

    9         }

   10     }

   12     return list;

   13 }

GetList needs a Database object, the sql to work with, and a closure describing how to turn a row in the result set into a business object. It then returns a typesafe collection representing the query. An example use might be to get a list of name/id pairs, and would look something like this:

    1 //Get the results from the database

    2 return DbUtils.GetList<KeyValuePair<int, string>>(db, sql,

    3   row => new KeyValuePair<int, string>(

    4           DbUtils.AsInt(row.Item["id"]),

    5           DbUtils.AsString(row.Item["name"]))

    6 );

Where AsInt and AsString are utility methods of mine to handle cases with null fields.

This is, by the way, one example of a very handy use for closures: encapsulating resource allocation and disposal so that you, the developer, don't have to remember to do it. Anyplace you acquire a resource (file access, database access, network operations, etc.) is a candidate for a method like this.

Lazy Loading

Another common pattern of mine is lazy loading: a business object may have some properties which are rarely used and expensive to calculate. In that case, the object defers calculation until they are needed:

    1 private List<string> names;

    2 public List<string> Names

3 {

    4     get

    5     {

    6         if (names != null)

    7         {

    8             names = ExpensiveComputation();

    9         }

   10         return names;

   11     }

   12 }

Using closures, I've extracted this pattern into the library function LazyLoad:

    1 public static void LazyLoad<T>(ref T stateVar, Func<T> generateVal)

2 {

    3     if ( stateVar == null || stateVar.Equals(default(T)) )

    4     {

    5         stateVar = generateVal();

    6     }

7 }

Which transforms the Names property into:

    1 private List<string> names;

    2 public List<string> Names

3 {

    4     get

    5     {

   6         SysUtils.LazyLoad(ref names,

   7             () => ExpensiveComputation()

   8         );

   9         return names;

   10     }

   11 }

Notice that even though LazyLoad is a generic method, I am calling as if it were a normal method. The type is inferred from the names parameter, so I can leave out the angle brackets. Type inference wasn't smart enough to figure out the type in the GetList case, but it is here.

The jury is still out for me on whether or not LazyLoad is really a good idea. On the one hand, it encapsulates something I do a lot and gives it a name. On the other hand, it isn't actually much shorter than explicitly testing for null and requires passing the private field by reference, which I try to avoid (although in this case I think it's pretty clear what is happening).

Sort By

Finally, an example that was someone else's idea, but which was also inspired by Ruby: an extension method that implements SortBy on List collections:

    1 public static List<TElement> SortBy<TElement, TSortBy>(

    2     this List<TElement> coll,

    3     Converter<TElement, TSortBy> converter,

    4     Comparison<TSortBy> comparison)

5 {

    6     return coll

    7         .ConvertAll(el => new { Key = converter(el), Value = el })

    8         .Sort((a, b) => comparison(a.Key, b.Key))

    9         .ConvertAll(x => x.Value);

   10 }

   11 ...

   12 //sample use:

   13 List<string> files = ...//Get some files

   14 files.SortBy(x => GetDate(x)); //sort by modified date

Notice how type inference cleans up the syntax. This function is as elegant (I think) as the Ruby equivalent, but is still fully type-safe.

Conclusion

The point of all this is that closures provide powerful, additional ways of encapsulating common patterns in code. They are fairly new to .Net, but we can look to other languages to gain clues about how to use them best.

New Asp.Net MVC Framework

2007-10-11T21:54:00.001-07:00

At the recently-concluded Alt.Net conference, ScottGu demoed a new pre-pre-alpha MVC framework for Asp.Net. The presentation is definitely worth a look.

This is a great example of why Rails is such a good thing even for those of us who don't get to use it professionally. Something as subversive as Rails is bound to have wide-reaching effects far beyond the actual framework. It's already motivated MVC frameworks in just about every language imaginable - including the open source MonoRail implementation built on top of Asp.Net.

Microsoft seems to be consistently a few years behind the state of the art (in unit testing, ajax, mvc web frameworks, etc.) and they have this irresistible urge to write their own versions of perfectly good open-source tools. But at least they realize a good idea when they see one. The next version of the .Net framework has some really exciting new features like extension methods and lambda expressions, which make them look almost (dare I say it) as clean as Ruby blocks.

Some scattered thoughts from the presentation:

The whole talk was giving me Rails flashbacks. All the terminology seemed to be borrowed from rails, as was the default routing format. Visual Studio was even set up with a dark color scheme that evoked the popular textmate theme.
Routing uses a tokenized-string format. I like the syntax: it's very intuitive and clean. But Scott mentioned that an earlier version used Regular Expressions, and that was changed because they found that, while Regular Expressions are super-powerful, only like 10% of people actually understand them (~10:30 in the video). This shows some of the self-imposed constraints Microsoft is working under. No Regular Expressions because they are too hard to understand?

This mentality is, I think, the source of most of the problems with Asp.Net in the first place. The drive to make web programming "just like" windows programming and cater to the lowest common denominator is behind some of asp.net's worst features: The page lifecycle. and viewstate(love it/hate it) are the two biggest offenders, IMHO. Getting closer to the html and http metal means knowing more about them, yes, but it also makes the framework vastly simpler. You won't get an OnChange event on your texboxes. But I'll bet that the time you save learning about html and http is spent debugging page lifecycle issues or figuring out that you need to use Control.UniqueID instead of Control.ClientID.
Scott emphasized many times that the entire architecture was designed to be very pluggable (don't like it? change it!) and easily unit-testable. There will be support for mock objects using common frameworks (Rhino mocks/Typemock were mentioned by name). Very cool.
The community seems to be very excited about this. You can see a lot of enthusiasm, both in the audience for Scott's talk and in the comments to this blog post. You can also tell what (this part of) the community cares about. Scott fielded a lot of "is that class sealed?" questions (to which his answer was always no), and lots of people seem to be happy about getting rid of the postback model.
Along with all the extensibility points that Scott mentioned, he gave some specific examples of alternate implementations that could be plugged in. At just about ever point, there was a Castle/Monorail alternative that could be used. It left me wondering, if you plug in all the Monorail components, how much of the MS framework would be left? Doesn't seem like much.
Model classes take a hash, just like in Rails, so that you can update them directly from form parameters: Customer.UpdateFrom(Request.Form).
The framework will ship with a bunch of MVC-specific controls, but many of the standard ones (the Repeater was mentioned by name) apparently do not require webforms and can be used as-is. Master pages and user controls can also be used.
The first public release should be in 6-8 weeks, with a final release in spring 2008.

YCombinator in Chrome

2007-10-09T16:50:00.001-07:00

When Chrome 2.0 was released I spent some time playing with its new support for anonymous methods. One of the things I did was to derive the Y Combinator, which lets you generate recursive anonymous methods.

Anyway, I wrote a series of blog posts about the experience over on the company blog. Low on usefulness, but high on bizarre, esoteric, and fun! Enjoy:

Anonymous Methods in Chrome

Y in Chrome Part 1: Currying

Y in Chrome Part 2

Y in Chrome Part 3

Executable Configuration Files

2007-10-03T19:12:00.001-07:00

Ever since I got my start in Delphi with ye olde ini file, I've had this feeling that there must be a better way of storing application configuration information. Even with a good API, there is just too much boilerplate code involved in parsing the file, loading it into a data structure so it can be operated on, and then converting it back to text so it can be saved. Writing boilerplate code makes me feel braindead, and I don't like feeling braindead.

My company's move from Delphi to .Net a few years ago brought incremental improvement: a built-in api for reading/writing custom settings in app.config. In .Net 2 you can even have a config class auto-generated for you, which provides type-safe and intellisensy access to your configuration settings. And, of course, there's the .Net support for serializing objects to Xml. I confess I don't have much experience with that.

Life was easier, but there were still significant restraints: you need to design your configuration in just such a way in order to get the boilerplate auto-generated. For an example of the issues, see this blog post about storing configuration in .Net, and read the caveats pointed out by the commenters. The solution presented is a pretty good one, but there's still bookkeeping: copy this here, add that there, store in the app.config and hope you have read access, use public fields in your settings class.

It wasn't until I learned Ruby that I realized these restrictions are largely inherent in the strongly-typed, compiled languages I've been using. I had two configuration epiphanies using Ruby:

The Yaml parser in Ruby blew me away. Yaml is a lightweight configuration language meant to be easier on the eyes than Xml. Here's a snippet:
```
development:
```
```
  adapter: mysql
```
```
  database: members
```
```
  username: root
```
```
  password: pwd
```
```
  host: localhost
```
With the ruby Yaml parser this can be loaded with one line of code, and accessed as a hash table: config["development"]["adapter"] would return "mysql".

Because ruby is an interpreted language, you may be able to write all of your configuration in ruby itself. One of the main reasons for using a config file (to update settings without having to recompile) doesn't exist in ruby. This is done a lot in Ruby on Rails, for instance. Here's a short snippet of production.rb:
```
# Code is not reloaded between requests
```
```
config.cache_classes = true
```
```
 
```
```
# Use a different logger for distributed setups
```
```
config.logger = SyslogLogger.new
```
beautifully simple, isn't it?

Just recently I came across an idea that pushes the executable-configuration envelope even further: using Lisp as a data representation. Lisp is the ideal format: hierarchical like Xml, cleaner than Xml, executable. As Steve Yegge points out, if Xml was really sufficient why would we keep adding extensions to make it more programmable? Might as well start off with a real language, like Lisp.

This is really only a proof-of-concept, of course. You can't use Lisp in a real project because nobody knows Lisp. And besides, I'm not sure that communicating between Java and Lisp would be any easier than communicating between Java and Xml. What you can do is use that example to show you how easy configuration ought to be. It prevents you from being really satisfied with a suboptimal solution, which is good even if all of your options are suboptimal. You at least know what you're aiming at.

So, where does that leave someone using a statically type language? What lessons can you take away from Lisp and Ruby that will make life easier in C#?

To be honest, I'm really not sure yet. Nothing in C# prevents you from writing an Xml or Yaml parser that loads the data into nested hashes/arrays. That's one option. And the support for storing settings in the app.config really is pretty good. But I'm on the lookout for a better way, and that is the point.

[1] Of course there's no reason that Xml couldn't be interpreted in the same way, and there is a Ruby library, XmlSimple, which does exactly this.

Welcome

2007-10-03T08:31:00.001-07:00

By way of introduction, I intend Coding Patterns to be a repository for the various patterns and practices that I come across - either on my own or via the great hive mind that is the blogsphere - which make my programs easier to develop, easier to read, and easier to use. As I am using it, this phrase extends beyond the particulars of good software design to include good user-interface design and the tools/utilities that remove the accidental difficulties of software development.

In addition, I'll likely throw in anything that strikes my fancy, particularly regarding Chrome (a .Net Pascal dialect), Ruby, .Net, and the future of technology.

I also contribute to the periodically-updated Imagine Systems Dev blog, and may cross-link from time to time. A few highlights:

By the way, I apologise for the pretentious title. It isn't meant to make me sound like an expert or an authority on the subject, just to describe what I'm trying to do here.