Monday, October 5, 2009

Here's a first cut at another Halloween poem. I reserve the right to revise it.

Their Woods

There in the dark
Everything seemed older than me
My uncle, my cousins, the woods
But especially the woods

After a day of fishing at the creek
We gathered on the road to the barn
At the place by the henhouse
Where it forked and went down
To the pond in the woods

A small expedition
Launched at night
To carry the bait trap
Down to the pond
Where the crawdads
Would keep fresh

I didn’t want them to go without me
I was worried they might come back changed
Bonded in some way I could not know
Or caught and replaced by monsters
And I would never know

But I was scared
And the white circle of light
From the hissing gas lantern
Seemed too small and fragile
To keep back the woods and the dark

Or perhaps I was afraid
That they might change
Down there in the woods
And I would not

So I stayed behind
And I’ll never know
What the pond was like
In the woods that night
And whether they changed

Thursday, October 1, 2009

For a Departed Swimming Pool

The man we hired to fill the old pool
Got the backhoe through the fence, but
To get his dump truck into the yard
Had to uproot a burning bush
Which proved to have a nest of bumble bees
In its roots

And now they swarm there
Awaiting Diaspora from the from the only home
They’ve ever known
A world of shade and green
Become a wasteland of mud and straw

Milling about not enraged but hapless
Longing for the promised land
Waiting for their Moses
To lead them across the dirt filled pool
Away from pharaoh and his backhoe

But until they depart
We must go quietly
And put on our shoes
As though crossing holy ground

Tuesday, September 29, 2009

Here's a Halloween poem, a bit early.

The Dark Orchard

I used to live in a old house
Perhaps sixty or seventy years old
From the 1910’s or 1920’s
And it had an orchard

Almost as old and gone to seed
Almost as long
Grown up with low limbs
And brush, and small trees
The ground was spongy with
Rotting apples
Smelling of
Rotting Cider
Full of the sound of
Wasps

There was a hostility about the place
As though, having been abandoned by Man
Man was no longer welcome

And the trees seemed to watch
And to whisper among themselves
As though waiting
For some Man to go there alone
In the dark
Or in a storm

To the point where
I worried for the deer
That browsed there at night
That the trees might sense them
And decide to get in
A bit of practice

Monday, September 28, 2009

I've been studying to have my poetic license renewed, so I will post a series of poems. The first has two versions, because I can't decide which I like the best. The first version has a quality like transliterated haiku, which I like, but the second version flows better:

Embrace

I saw a glove
Stomped into the parking lot
Of an old warehouse

The fingers spread like wings
At first I thought
It was a bird

It grasped the asphalt
To its palm
The way a dead bird
Clutches the earth
To its breast


(Alternate Version)

I saw a glove
Stomped into the parking lot
Of an old warehouse

At first I thought
It was a bird

The fingers spread like wings
And grasped the asphalt
To its palm

The way a dead bird
Clutches the earth
To its breast

Monday, July 6, 2009

Pause

Code to follow soon. In this meantime, this copied from a letter to a friend:

The hamburgers on the fourth were good, but the fireworks were somewhat rained out. Small loss, though, since various neighbors let off fireworks all summer long every year, and there's still a lot of summer left.

This morning I am mourning the loss of five ripening green peppers, which met an untimely end last night at the paws of a raccoon. He ate most of two fancy Italian peppers, but only picked and scattered the three common green peppers (presumably they were beneath his taste). The miscreant in question is well-known in the neighborhood; he cruises through periodically like a biker hoodlum in a 1950’s film, wreaking all sorts of havoc with the innocent townsfolk. To this point, however, he has largely confined his attention to chewing and scattering small plastic objects, etc., and has left the plants alone.

It’s an interesting comment on the universe that one of the first acts of incipient intelligence in the animal kingdom is apparently the desire to pull Halloween-style pranks characteristic of a small-town hood. I’m not certain it bodes well. Perhaps not, but perhaps so, since not a few delinquents do go on to become productive, upstanding members of the community. In any case, as in so many things in the universe, we see the large mirrored in the small, the universal in the particular.

So I am able to recover some of the loss of increase of my garden by reflecting on the idea that I have exchanged five peppers for a good story. Was it worth it? Well, I think I would rather have traded one pepper for not quite as good a story. But life is about extracting meaning from events, and not the converse (which is art).

I hope in the meantime, however, that raccoon doesn't get his hands on fireworks...

-Neil

Tuesday, June 30, 2009

Enumerators for Dependency Injection

A situation came up where I needed to select elements based on dependency injection. The elements were portions of a larger bitmap that were being used as tiles in a 2D graphics engine. Selection might be sequential, random, fixed, etc., but needed to be hidden from downstream processes. In particular, I needed to inject not the enumerators themselves, but enumerator factories.

At first I was going to use a custom interface. After some thought, however, I decided that the .NET IEnumerator<> interface fit the bill nicely. Technically an enumeration is some kind of ordered or unordered sequence from a collection. But a randomized sequence fits that bill, and it’s not too much of stretch to think of an infinitely looping sequence as an enumerator. (For example, think of the original collection as specifying the set of allowable items of an infinite sequence.)

So I came up the following helper functions:
static IEnumerator<TOutput> MakeEnumerator <TInput,TOutput,TState> (
TInput inputIn,
TState stateIn,
Func<TInput,TState,TState> funcMoveNext,
Func<TInput,TState,bool> funcMovedNextOk,
Func<TInput,TState,TOutput> funcCurrent)
{
while (true)
{
stateIn = funcMoveNext(inputIn,stateIn);

if (!funcMovedNextOk (inputIn,stateIn))
break;

yield return funcCurrent(inputIn,stateIn);
}
}


static Func<TInput,IEnumerator<TOutput>> MakeEnumeratorFunc <TInput,TOutput,TState> (
TState stateIn,
Func<TInput,TState,TState> funcMoveNext,
Func<TInput,TState,bool> funcMovedNextOk,
Func<TInput,TState,TOutput> funcCurrent)
{
return
(i)=> (
MakeEnumerator(
i,
stateIn,
funcMoveNext,
funcMovedNextOk,
funcCurrent));
}

The first helper is a generic enumerator builder that takes three functions and a state which control the enumeration. The functions transition from state to state, determine whether a transition has exhausted the enumerator, and select an enumerated item. (I separated the move next functionality and inverted its typical order because it makes things a lot more convenient.)

The second helper uses this first helper to build an enumerator factory function.

Below shows how this could be used to build an enumerator factory for canonical list enumeration. (You wouldn’t want to use these functions for this in a typical scenario; the traditional way would suffice there. They are mainly useful in dependency injection situations.)

Func<List<int>,IEnumerator<int>> xMakeEnumeratorFunc =
MakeEnumeratorFunc<List<int>,int,int>(
-1,
(i,s)=>(s+1),
(i,s)=>(s<i.Count),
(i,s)=>(i[s]));

List<int> xList = new List<int>() { 1, 3, 5, 7 };

IEnumerator<int> xEnumerator = xMakeEnumeratorFunc(xList);

// Inject xEnumerator here.

Fun, func, function!

(Tomorrow: I find a situation where a tradition boolean MoveNext is superior and post the overloaded functions.)

-Neil

Thursday, June 11, 2009

Enumerating Bits

OK, so the enumerating the set of subsets of non-zero bits is not a common task. But what about enumerating the set of non-zero bits in an integer? That’s something that tends to happen at least one or twice in any large project. Here’s how that can be done use a related function.

Given an integer (i), the least significant non-zero bit (b) can be found using this equation:

b = (i & -i)

(This is discussed as equation (37) in Donald Knuth’s The Art of Computer Programming, Volume 4, pre-fascicle 1A, page 8.)

It is easy to turn this into a loop which enumerates the bits in an integer:
while (xInteger>0)
{
int xBit = (xInteger & -xInteger);
xInteger &= ~xBit;
// Do something with xBit here.
}

(This is probably a case where one wouldn’t want to use a generic “yield return” enumerator, since if one is working at this level of detail, efficiency is probably the main concern.)

This can also be made to work in C# with unsigned integers by using various types of casting. But if efficiency is paramount, pay attention to the generated MSIL, since casting at some points generates more efficient code than does casting at other points.

Tests in release mode show that this construct is nearly four times faster in C# (.NET 3.5 version) than is shifting! But it looks arcane at first glance, so be sure to document the code well.

Tuesday, June 9, 2009

Power Set of a Bitmask

Here’s a cute trick for enumerating the power set of an integer bitmask. It’s based on equation (84) in Donald Knuth’s The Art of Computer Programming, Volume 4, pre-fascicle 1A, page 18, available in an "alpha test" version at:

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

The idea is that, given a subset (x) of a mask (M) the next largest lexicographic subset (x') is:

x’ = (x – M) & M

Combined with the C# "yield return" statement, this allows a simple enumeration of the power set of a mask. You simply seed the subset with zero, and iterate until it is once again zero.

public static IEnumerable<int> PowerSet (
int maskIn)
{
int xSet = 0;

do
{
yield return xSet;
xSet = (xSet - maskIn) & maskIn;
}
while (xSet!=0);
}

For example, calling PowerSet(0x19) returns an enumerator which yields (in binary):

00000
00001
01000
01001
10000
10001
11000
11001


I can’t think of a specific use for it right off hand, but if a project uses enough bit manipulation, I’m sure something would arise.

Code Generator Oddity

The following is a exerpted example of my implementation of a well-known permutation algorithm. Note the code generation oddity flagged by the comment. This occurs in .NET 3.5 and Visual C# 2008. I leave the solution to the mystery to readers who like to disassemble and read MSIL, and think about what the JIT compiler may do to it.

protected static void Permute <TDatum> (
int beginIn,
int endIn,
TDatum[] dataIn,
Action<TDatum[]> dataActionIn)
where TDatum : IComparable
{
TDatum xDatumBegin;

if ((endIn-beginIn)<=1)
{
dataActionIn(dataIn);
}
else
{
Permute(
beginIn+1,
endIn,
dataIn,
dataActionIn);

for (int i=beginIn+1; i<endIn; i++)
{
xDatumBegin = dataIn[beginIn];

dataIn[beginIn] = dataIn[i];
dataIn[i] = xDatumBegin;

Permute(
beginIn+1,
endIn,
dataIn,
dataActionIn);

// Believe it or not, the compiler/loader
// will optimize the first block below
// to be almost 10% faster than the second.

#if thisIsFasterInDotNet
xDatumBegin = dataIn[beginIn];
dataIn[beginIn] = dataIn[i];
dataIn[i] = xDatumBegin;
#else
dataIn[i] = dataIn[beginIn];
dataIn[beginIn] = xDatumBegin;
#endif
}
}
}

Sunday, May 24, 2009

Zen Dream

Here’s something I once posted in a newsgroup.

Last night, I was practicing with some water-colors and I painted a series of concentric black and white circles, kind of like an archery target. Later, while I was asleep, I dreamt I was in a store. I saw that there were bows and arrows for sale, and I realized I had a consuming desire to practice archery. I picked out a bow, but I couldn’t find any arrows. Then I realized that they were haphazardly scattered about the floor, intermixed with long-handled paintbrushes. The arrows were missing feathers, and then other difficulties began to intervene, until I despaired of ever putting to together a decent archery set.

Then I woke up and realized I wasn’t interested in archery at all; I wanted to paint.

I had intended to end this story with the Zen saying "The skilled archer does not aim for the center of the target,” but I wanted to look it up in Yahoo to see if I could find the original reference. The first Yahoo hit I found was a newsgroup thread where I had quoted it earlier without reference. And if that's not some kind of koan, I don't know what is.

Monday, April 27, 2009

LINQ

It would not take even a Dr. Watson to notice that this blog has been idle for over a year. It might, however, take a Sherlock Holmes to discern the reason why. So I will sum it up with a word:

LINQ

Shortly after the last post, I began playing around with the new version of Microsoft Visual Studio, which included LINQ and all the new lambda programming goodies. I realized they made obsolete many of the issues I had discussed in the previous entry.

Concurrently, I decided to port a professional expert system engine I wrote and maintain to the new version of Visual Studio. It was written mainly in C++, with .NET interface code in C#. As I went along, I found myself thinking: “Perhaps I should just re-write the whole engine from scratch, using the newest C# technology.”

And so I did. And interspersed with other projects, etc., it took the better part of nine months to complete the engine, and another couple of months to work out the kinks and get it hooked up to the external components (UI, etc.). It was a lot of fun, but it did interfere with my blogging, to say the least.

In retrospect, it was a good decision. I learned the new lambda elements of C# in a way that would have been tough using a less whole-hearted approach. I also learned possibly more than I ever wanted to know about C# generics, lol. I want to share some of the things I discovered in subsequent posts in this blog, but for now I’ll just share what I consider the most important discovery:

Every programmer, it seems, hates exception handling, and I am no exception. So, when I started the re-write, I decided that I would, for once in my exception handling life, be good and pay attention to it from the ground up. So I started my re-write by crafting a set of classes to let me handle and pass exceptions and returns. They were not intended to replace the existing .NET exception handling, but rather to work hand in glove with it. Also, I began a discipline of handing errors and exceptions fully and correctly in the code at the exact moment I was writing the code. No more “I’ll save error handling for a rainy day.” It took a few weeks, but it stuck; it’s now a habit and I don’t fear error handling any longer.

Best programming discovery I ever made.