Programming: December 2008 Archives

Generic Accumulators in C#

|
This was written in C# 2.0; if you're using 3.0 you might want to check out my updated version

I fell down a chain of links today and wound up reading one of Paul Graham's numerous pro-Lisp essays. I responded as I typically do by attempting to implement his examples in whatever language I have handy, which today was C# 2.0.

The example Graham cites in the appendix is a function for generating accumulators:

(defun foo (n)
  (lambda (i) (incf n i)))

For those of me who always find reading Lisp akin to reading the opening chapters of the Bible (but with parentheses standing in for the voluminous 'begats'), he also helpfully provides equivalents in a few other languages, such as JavaScript:

function foo(n) { 
  return function (i) { 
		   return n += i } }

An accumulator is a function that maintains internal state; when you invoke it with a new value it adds that value to its internal state and returns the new sum. An example usage would be to initialize it to zero and invoke it with each value in an array of integers; the result of the final invocation would be the sum of the integers -- or rather, the accumulation of the values.

For instance:

var myAcc = foo(0); // Initialize to zero
myAcc(1); // 0 + 1 = 1
myAcc(10); // 0 + 1 + 10 = 11
myAcc(44); // 0 + 1 + 10 + 44 = 55

So, can we build that in C#? The answer is an enthusiastic 'kinda'!

[TestFixture]
public class AccumulatorTest
{
	private delegate int Accumulator(int inc);

	private static Accumulator MakeAccumulator(int start)
	{
		int n = start;

		return delegate(int inc)
		{
			n = n + inc;
			return n;
		};
	}

	[Test]
	public void TestAccumulator()
	{
		Accumulator acc = MakeAccumulator(0);

		Assert.AreEqual(0 + 0, acc(0));
		Assert.AreEqual(0 + 0 + 1, acc(1));
		Assert.AreEqual(0 + 0 + 1 + 10, acc(10));
		Assert.AreEqual(0 + 0 + 1 + 10 + 44, acc(44));
	}
}

It's not actually that long -- the TestAccumulator function at the bottom is a quickie NUnit test case to verify it's doing what I think it should. It's still longer than the Lisp or JavaScript version though.

But there's one other major difference from those versions -- typing. The C# version only works on integers, whereas the Lisp and JavaScript version will work on anything that can be added. But if we try to genericize the C# code we'll run into problems at the n = n + inc statement, because you can't add two objects and thus can't add two generic objects without a generic constraint guaranteeing you can. And since there's no IAddable interface that integers and floats and strings and everything implement (and since C# still doesn't have a more generalized form of where clause that would let us specify constraints as duck types rather than static types), we're basically SOL with a generic C# accumulator.

Or are we? (Bum-bum-BUM!)

What if we passed our MakeAccumulator function two parameters: a starting value, and a delegate function to use for incrementing?

[TestFixture]
public class AccumulatorTest
{
	private delegate T Accumulator<T>(T inc);

	private delegate T AccumulationDelegate<T>(T a, T b);

	private static Accumulator<T> MakeAccumulator<T>(T start, AccumulationDelegate<T> accumulationDelegate)
	{
		T n = start;

		return delegate(T inc)
		{
			n = accumulationDelegate(n, inc);
			return n;
		};
	}

	[Test]
	public void TestIntAccumulator()
	{
		Accumulator<int> acc = MakeAccumulator(0, delegate(int a, int b) { return a + b; });

		Assert.AreEqual(0 + 0, acc(0));
		Assert.AreEqual(0 + 0 + 1, acc(1));
		Assert.AreEqual(0 + 0 + 1 + 10, acc(10));
		Assert.AreEqual(0 + 0 + 1 + 10 + 44, acc(44));
	}

	[Test]
	public void TestFloatAccumulator()
	{
		Accumulator<float> acc = MakeAccumulator((float)0, delegate(float a, float b) { return a + b; });

		Assert.AreEqual(0 + 0, acc(0));
		Assert.AreEqual(0 + 0 + 1, acc(1));
		Assert.AreEqual(0 + 0 + 1 + 10, acc(10));
		Assert.AreEqual(0 + 0 + 1 + 10 + 44, acc(44));
	}

	[Test]
	public void TestStringAccumulator()
	{
		Accumulator<string> acc = MakeAccumulator("", delegate(string a, string b) { return a + b; });

		Assert.AreEqual("" + "", acc(""));
		Assert.AreEqual("" + "" + "marklar", acc("marklar"));
		Assert.AreEqual("" + "" + "marklar" + "smurf", acc("smurf"));
		Assert.AreEqual("" + "" + "marklar" + "smurf" + "foo", acc("foo"));
	}
}

Yay!

So what is it good for? Absolutely nothing! But it sure was fun!

For a long time I've semi-seriously joked about writing a humorous non-theoretical book about computer science that isn't a total crock.  I think I've finally decided that the easiest thing to do is break the entire field down into a random series of blog posts that will in all likelihood never actually be collected into a book.  So here's the preamble.

So what is programming?  Programming a computer is all about explaining to a computer how to do things.  The big secret all programmers share is that computers are dumb.  Really dumb.  But -- and this is why we keep them around -- infallibly obedient and really, really good at math.  Have you ever called a tech support or customer service line and had to put up with a dolt who can't do anything but follow the script in the big-honking-binder his supervisor gave him on his first day?  Now imagine that guy with a calculator, and you're imagining someone maybe ten or twenty times smarter than a computer.  The job of the programmer is to write that big-honking-binder.

So if you're writing a big-honking-binder for your new friend the phone drone, what kind of instructions can you put in there?  If your employees were intelligent and informed, you wouldn't need much: just a single sheet of paper that says 'handle customer issues' at the top, and voila, you're done!  But remember, the computer you're programming here is stupid, and he's not going to understand high-level instructions like that.  You need to break it down:

  1. Ask the caller whether he or she currently owns a product.
    1. If the caller says 'yes', go to step 2.
    2. If the caller says 'no', go to step 5.
  2. Ask the caller what is wrong with the product.
    1. If the caller says 'it will not turn on', go to step 3.
    2. If the caller says 'it will not turn off', go to step 4.
  3. Tell the caller how to turn the product on. Hang up.
  4. Tell the caller how to turn the product off. Hang up.
  5. Tell the caller where to buy the product. Hang up.

If you look at that script, you'll probably notice a few things (besides the fact that we're training our human computer to be unbearably rude).  What if the answer to step one is "I don't know"?  Different people (computers) might handle that differently.  Some might hang up; some might continue on to step two; some might ask question one over and over until the frustrated customer picks 'yes' or 'no' (we'd call that "undefined behavior", which basically means we don't know in advance what's going to happen; undefined behavior is a source of some pretty nasty bugs). What if there's something wrong with the product besides an inability to turn it on or off?  What if the product won't turn on because it's broken?

Those are all bugs in our program, and they all serve to show part of what makes programming difficult; decomposing a task ('make customers happy') into tiny little steps that a mindless automaton can follow is very difficult.  You can't count on a computer to make a value judgement; you can't count on a computer to recognize that 'yeah' or 'yup' also mean 'yes'; you can't count on a computer to do much of anything except for faithfully following whatever flawed or incomplete script you give it.  That and math.

Pages