Higher-Order Functions and Function Composition, with Processing

I was looking for a good way to illustrate functional composition and higher order functions, and thought that something could be done with Processing, a java-based graphics tool. Among other things, Processing exposes raw pixel data for the images it renders, and you can update the pixels programatically, providing a simple kind of image filtering.

For example, here’s some code that converts a color image to grayscale. Just like with HTML, colors are represented1 as 3 channels (red, green, blue), and each channel has 255 increments. A gray pixel has equal amounts of red, green, and blue, so if you get the overall brightness of a pixel, and set its color to that much red, green, and blue, it should turn the image gray.

PImage img = loadImage("tattoo.jpg");
size(img.width, img.height);  // set the window size
image(img, 0, 0);  // render the image at x:y = 0:0

loadPixels(); // load the image's pixels into an array
for (int i = 0; i < pixels.length; i++) {
    // get the color for this pixel
    color c = pixels&#91;i&#93;;

    // get its brightness
    float bright = brightness(c);

    // Change its color to its grayscale equivalent
    pixels&#91;i&#93; = color(bright, bright, bright);
}
updatePixels();  // render the new pixels to the screen
&#91;/sourcecode&#93;

Here's the original image:

<a href="https://invisibleblocks.files.wordpress.com/2009/05/tattoo.jpg"><img class="size-medium wp-image-265" src="https://invisibleblocks.files.wordpress.com/2009/05/tattoo.jpg?w=300" alt="the original image" width="300" height="199" /></a>

...and here's the filtered version:

<a href="https://invisibleblocks.files.wordpress.com/2009/05/tattoo_grayscale.jpg"><img class="size-medium wp-image-266" src="https://invisibleblocks.files.wordpress.com/2009/05/tattoo_grayscale.jpg?w=300" alt="the image in grayscale" width="300" height="199" /></a>

You can define a bunch of routines like this, each looping through the pixels the same way, but adjusting the colors differently. But if you can separate the pixel-changing part from the pixel-looping part, then you can swap in ANY pixel-changing routine, giving you a flexible image filtering system.

The pixel-changing code is essentially a function that turns one pixel's color into a new color, and the pixel-looping code uses it to replace each pixel's original color.  The pixel-changing function could be described like this:


color transform(color c) {
    ...
}

Many modern programming languages support first-class functions, which are a natural way to model this. Processing uses a form of Java, which doesn’t have first-class functions, but we can wrap the functions in a class, giving us an object called a functor. I called this one ColorTrans, for “color transformer”.

abstract class ColorTrans {
    public abstract color transform(color c);
}

The ColorTrans class’ only method, transform, is our pixel-changing function. We can re-write the loop from before to use a ColorTrans filter, and while we’re at it, we’ll move it into a method that takes the filename as a parameter, too.

void filterImage(String path, ColorTrans filter) {
    PImage img = loadImage(path);
    size(img.width, img.height);
    image(img, 0, 0);

    loadPixels();
    for (int i = 0; i < pixels.length; i++) {
        // use the filter parameter
        pixels&#91;i&#93; = filter.transform(pixels&#91;i&#93;);
    }
    updatePixels();
}
&#91;/sourcecode&#93;

We can easily recreate the grayscale filter from earlier as a ColorTrans.

&#91;sourcecode language="java"&#93;
ColorTrans grayscale = new ColorTrans() {
    color transform(color c) {
        float bright = brightness(c);
        return color(bright, bright, bright);
    }
};

filterImage("tattoo.jpg", grayscale);
&#91;/sourcecode&#93;

Another really easy filter to write is an inverter. If a pixel has R:100, G:30, B:255, an inverter will return the color R:(255-100), G:(255-30), B:(255-255), or R:155, G:225, B:0.

&#91;sourcecode language="java"&#93;
ColorTrans invert = new ColorTrans() {
    color transform(color c) {
        return color(255 - red(c),
                     255 - green(c),
                     255 - blue(c));
    }
};

filterImage("tattoo.jpg", invert);
&#91;/sourcecode&#93;

The image produced by an inverter is like a film negative.

<a href="https://invisibleblocks.files.wordpress.com/2009/05/tattoo_invert.jpg"><img class="size-medium wp-image-268" src="https://invisibleblocks.files.wordpress.com/2009/05/tattoo_invert.jpg?w=300" alt="inverted, like a negative" width="300" height="199" /></a>

Now we begin to see the benefits of keeping the-parts-that-change separate from the-parts-that-don't: we can easily define and swap in new filters. This is one of the big parts of higher-order programming: writing routines that are configured by passing in functions (or functors, in this case) to do part of the work.
<h3>Manufacturing a ColorTrans</h3>
A useful kind of filter is one that increases (or decreases) the color on one channel: add some red, or remove some green. This kind of filter is easy to create:


ColorTrans aFifthMoreRed = new ColorTrans() {
    color transform(color c) {
    	return color(red(c) * 1.2, green(c), blue(c));
    }
};

This filter will increase the amout of red in the image by 20%. But 20% is a pretty arbitrary number; it’d be better if we could tell the filter how much to increase the red by. Generally, you’d add an “amount” parameter to the transform method, but then filterImage would have to know that this ColorTrans object takes an extra parameter. It’s kind of nice having filterImage treat all ColorTrans objects the same, just passing in the color.

Instead, we can make a method that builds ColorTrans objects: we tell it how much to increase the red by, and it builds a ColorTrans that does it for us.

ColorTrans ampRed(final float amount) {
    return new ColorTrans() {
        color transform(color c) {
            color(red(c) * amount, green(c), blue(c));
        }
    };
}

ColorTrans aQuarterMoreRed = ampRed(1.25);
ColorTrans aThirdLessRed = ampRed(2/3);
ColorTrans noRedAtAll = ampRed(0);

(If you’re curious why amount is final, the short answer is “because the compiler says so,” but there’s a better answer2.)

This is pretty nice, because we can use this inside an animation loop, animating the amount of color amplification.

float theta = 0.0;

void setup() {
    filterImage("tattoo.jpg", noChange);
}

void draw() {
    float ampRedAmount = sin(theta) * 1.2;
    filterImage("tattoo.jpg", ampRed(ampRedAmount));
    theta += 0.1;
}

[Here’s where I’d link to the applet, nicely hosted somewhere, if I had a hosting service that allowed applets. I’ll try to find a place to put all the code, so you can try it yourself.]

Processing calls setup to initialize the animation, and calls draw once per “tick”, to advance the animation. Here, in each frame of the animation, a new ColorTrans is constructed by ampRed, with the amount tied to the sine wave function, oscillating between 0 and 1.2. When viewed, the amount of red in the image swells and falls, and back again3.

This is another big part of higher-order programming: writing functions that build other functions, based on some arguments. Combined with routines that take functions as arguments, it’s a handy way to break down some problems. If done well, the routines that take functions as arguments, and the functions that build those functions, can become a sort of mini-language, a fluent interface, or almost an embedded DSL.

Plugging filters together – filter composition

This is where it gets fun. Suppose you’ve created an ampBlue that works just like ampRed, and now you want to filter an image with both of them. One approach might be something like this:

void draw() {
    filterImage("tattoo.jpg", ampRed(sin(theta) * 1.2));
    filterImage("tattoo.jpg", ampBlue(cos(theta) * 1.2));
}

Using the sine and cosine functions, the image should pulse nicely through reds and blues. The only problem is that it doesn’t really work, because filterImage loads the image fresh from the filesystem each time, so you only get the effect of the ampBlue filter. So how can we apply multiple filters?

We plug them together. We want a filter that does the work of two other filters, and we want it to look like any other filter, so filterImage won’t know the difference. To get this, we can add a method to ColorTrans that returns a new ColorTrans, which calls first the one, and then the other.

class ColorTrans {
    ...
    public ColorTrans then(final ColorTrans applySecond) {
        final ColorTrans applyFirst = this;
        return new ColorTrans() {
	    color transform(color c) {
	        return applySecond(applyFirst(c));
	    }
	};
    }
}

filterImage("tattoo.jpg", grayscale.then(invert));

first grayscaled, then inverted

Combining filters becomes a matter of chaining them together through then. The red-and-blue example becomes:

void draw() {
   filterImage("tattoo.jpg",
        ampRed(sin(theta) * 1.2).then(
            ampBlue(cos(theta) * 1.2)));
}

Processing does it kind of this way, too

If you look at the source for Processing, in PImage.java on line 619, you’ll find code that looks kind of like this:

  public void filter(int kind) {
    loadPixels();

    switch (kind) {
      case BLUR: ...
      case GRAY: ...
      case INVERT: ...
      case POSTERIZE: ...
      case RGB: ...
      case THRESHOLD: ...
      case ERODE: ...
      case DILATE: ...
    }
    updatePixels();  // mark as modified
  }

It basically does just what I’ve been doing, except the operations are hard-coded into the source, rather than being separated behind a class interface. The filters aren’t composable directly, though you can call a number of them in a row:

filter(INVERT);
filter(THRESHOLD);
filter(DILATE);

One benefit of this approach is that it’s easy to see, line-by-line, exactly what’s happening. I’d bet it beats the pants off of the ColorTrans version in benchmarks, too. But filters aren’t composeable, and it’s certainly not extendable. When you’re doing computation-intensive graphics, every bit of speed is important; when you’re illustrating a programming idea, it’s not. Decide for yourself which is more important for your needs.

____________________________________


1. It may seem weird, if you know Java, that the parameter’s type is color — it’s not a java primitive, but it doesn’t follow the normal classname conventions. It’s just the way Processing does it. You can read more about the color constructor in the Processing reference. [back]


2. Taken from the AnonymousInnerClasses page on the Portland Patterns Repository, 2009-04-30:

AnonymousInnerClasses can also be used to create something like closures in the JavaLanguage. However they do not “close over” the lexical environment so they aren’t TrueClosures. (They can capture the value of local variables, but they do not have access to the variable binding so they can’t change the original variable. Which Java makes quite clear by only allowing InnerClasses to refer to local variables that have been declared final (so no-one can change them)).

[back]


3. The noChange filter returns the same color it was given — an identity function. filterImage is called inside setup only so the window size is set correctly, since setting the size inside draw has no effect. And theta is just a Greek letter often used for angles and trigonometry.[back]

Advertisements

Heading to the Int’l Lisp Conf, 2009

My next step on the road to lisp is at the International Lisp Conference in Cambridge, MA, this March.

A lot of people are surprised to hear I’m interested in Lisp, but I’ve been studying scheme informally for about 3 years, reading SICP, and finishing The Little Schemer last year. I’ve been interested in clojure for about 18 months, especially after seeing Rich Hickey talk about it last March.  Now I’m studying it in earnest with Stu Halloway’s Programming Clojure.

I don’t use lisps of any sort at work, so it’s not a “practical” language to study like, say, C# is.  But that’s short-term thinking.  Learning lisp is plenty practical, if you’re looking longer-term — even if it’s only three years out.  Learning lisp teaches you about some of the core issues of programming.

I like learning lisp because it’s a window into the workings of programming languages, being so close to the AST.  I want to learn more about meta-programming with macros, hygienic or not.

And for the record, the functional techniques in The Little Schemer have improved my Ruby, JavaScript, and C# in some really solid ways. Functional programming is making its way to the rest of the programming world, and lisp does functional programming.

If you’ll be at the conference, I’d love to hear from you.

The Twelve Bugs of Christmas, via Ruby

Here’s a little bit of post-Christmas fun, based on the Twelve Days of Christmas.

bugs = %{
     Tell them it's a feature
     Say it's not supported
     Change the documentation
     Blame it on the hardware
     Find a way around it
     Say they need an upgrade
     Reinstall the software
     Ask for a dump
     Run with the debugger
     Try to reproduce it
     Ask them how they did it and
     See if they can do it again.
}.strip.split("\n").map { |bug| bug.strip }.reverse

days = %w[first second third fourth fifth sixth seventh eighth ninth tenth eleventh twelfth]

0.upto(11) do |day_num|
  puts "For the #{days[day_num]} bug of Christmas, my manager said to me"
  day_num.downto(0) do |bug_num|
    puts bugs[bug_num]
  end
  puts
end

Simplifying Boolean Expressions

(Apologies if this material seems elementary, but I’ve found enough code to make me think it should be talked about.)

I found some C# today that looked kind of like this.

if (someCondition) {
    return true;
}
return false;

This code says the author missed some key points about booleans. You can find it in almost any language.

Any code that fits into an if or while eventually becomes a boolean.  Using an if to “return true, else false” is redundant — just return the condition. That code can be simplified down to this one-liner:

return someCondition;

The same goes for assigning a variable. This:

bool result = false;
if (someCondition) {
    result = true;
}

…is the same as this:

bool result = someCondition;

(If you feel the longer version is clearer, as some do, I respectfully disagree with you, but that’s a different point, and I’m not interested in debating preferences.  You can probably stop reading here, but thanks for stopping by.)

What if your boolean values are swapped? You can invert your condition:

if (someCondition) {
    return false;
}
return true;

// is the same as:
return !someCondition;

As the nesting gets deeper, it gets hairier, but it can still be tamed:

if (condition1) {
    if (condition2) {
        return true;
    }
    return false;
}
return false;

// is basically:
return condition1 && condition2;

And…

if (condition1) {
    return true;
}
else if (condition2) {
   return true;
}
else {
   return false;
}

// is just:
return condition1 || condition2;

There are many other ways to tame a wild boolean — follow that link, and check the first table. It’s like simplifying an algebraic equation: x+0 is always x, and y && true is always y.

An Example

Let’s work through a contrived, yet nasty, example, to see how some of this works.

function contrivedYetNasty(hasYirmish, isNingle, amount) {
    var tooMuch = false;
    if (amount > 100) {
        tooMuch = true;
    }

    var foo = false;
    if (hasYirmish == false) {
        if (!!tooMuch) {
          foo = true;
        }
        else {
          foo = false;
        }
    }
    else {
        foo = true;
    }

    if (isNingle == true) {
        if (foo == false) {
            return false;
        }
        else {
            return true;
        }
    }
    else {
        return false;
    }
}

I have no idea what this does, but it’s nasty (which is often the situation with legacy code). These handy unit tests tell us how it behaves:

assert(false, contrivedYetNasty(false, false, 0))
assert(true,  contrivedYetNasty(false, true, 110))
assert(false, contrivedYetNasty(true, false, 0))
assert(true,  contrivedYetNasty(true, true, 110))  

assert(false, contrivedYetNasty(false, false, 0))
assert(true,  contrivedYetNasty(false, true, 110))
assert(false, contrivedYetNasty(true, false, 0))
assert(true,  contrivedYetNasty(true, true, 110))

First, let’s tackle tooMuch. It’s false, but if amount is over 100, then it’s true. If it always has the same truthiness as amount > 100, then it’s equivalent to amount > 100. Let’s write it that way.

var tooMuch = amount > 100;

The tests pass.

Next, let’s look inside the if (hasYirmish == false) block, lines 9 – 14 in the original. First, !!tooMuch is a double-negative: the first ! cancels out the second. We can just say if (tooMuch). “If tooMuch is true, foo is true; else (if tooMuch is false), foo is false.” So foo is the same as tooMuch, and we can rewrite the block like this:

if (hasYirmish == false) {
    foo = tooMuch;
}
else {
    foo = true;
}

Tests pass.

“If hasYirmish is false, foo is tooMuch; else, foo is true.” This is just like a boolean OR expression. When a || b is evaluated, if a is true, the expression evaluates to true, without even checking b; but if a is false, then the expression evaluates to the value of b. And that’s exactly what we want here. That block just becomes:

var foo = hasYirmish || tooMuch;

The tests still pass. So far, we’re down to this:

function contrivedYetNasty(hasYirmish, isNingle, amount) {
    var tooMuch = amount > 100;
    var foo = hasYirmish || tooMuch;

    if (isNingle == true) {
        if (foo == false) {
            return false;
        }
        else {
            return true;
        }
    }
    else {
        return false;
    }
}

Not bad!

Inside the isNingle == false block, on lines 6 – 11 above, we have: “if foo is false, return false; else (if it’s true), return true.” Again, we just want to return the value of foo. Let’s re-write it that way, test it (they pass), and take a look at the isNingle == true block.

if (isNingle == true) {
    return foo;
}
else {
    return false;
}

Now, we have a similar situation to when we introduced the OR expression, but it’s slightly different. If isNingle is false, the whole thing is false; if it’s true, then it’s the value of foo. Sounds like an AND expression. Let’s try it.

return isNingle && foo;

The tests still pass. Let’s step back and look at our progress:

function contrivedYetNasty(hasYirmish, isNingle, amount) {
    var tooMuch = amount > 100;
    var foo = hasYirmish || tooMuch;
    return isNingle && foo;
}

From 31 lines down to five, and it’s actually readable. We can in-line those variables, and it gets even clearer:

function contrivedYetNasty(hasYirmish, isNingle, amount) {
    return isNingle && (hasYirmish || amount > 100);
}

It returns true “if isNingle, and either it hasYirmish, or amount is over 100.” Much better.

Beyond the Basics

Once you’re comfortable with simplifying boolean expressions, there’s a number of rules you can employ to refactor nastier boolean expressions. Most of them are easy to remember, and can be easily illustrated in real-life terms. Meet DeMorgan:

  • !(a || b) == !a && !b. “It’s not red or green” is the same as “It’s not red, and it’s not green.”
  • !(a && b) == !a || !b. “I’m not rich and handsome” is true if I’m not rich, OR if I’m not handsome. (Or if I’m neither.)

These rules are part of a larger topic called Boolean algebra, which is useful for simplifying circuits, and (of course) programming. At my university, Boolean algebra was taught in Discrete Math, which was required for CS majors. Maybe programmers without a CS degree have a harder time with booleans because they missed this class, but the good news is, it’s easy enough to pick up.

Next Hartford Ruby Group meeting: 11/24

The Hartford Ruby Group is meeting this Monday, 11/24, from 6 – 8 PM.

Flinn Mueller will be talking about rspec, and we’ll hopefully hear stories from the Voices that Matter attendees.

We’ll raffle off The Professional Ruby Collection: Mongrel, Rails Plugins, Rails Routing, Refactoring to REST, and Rubyisms CD.

GeeZeo offices
750 Main St, Hartford
Suite 1314
(next to the CVS)

Thanks to GeeZeo for hosting us, to Sun for feeding us, and to Addison Wesley for giving us books to raffle off. Hope to see you there!

Hartford Ruby Brigade next meeting: 10/27

The Hartford Ruby Group is meeting this Monday, 10/27, at 6:00 PM.

We’ll be tackling a Ruby Quiz problem, pairing up newcomers with veterans, and we’ll be raffling off a copy of Design Patterns in Ruby, by Russ Olsen.

GeeZeo offices
750 Main St, Hartford
Suite 1314
(next to the CVS)

Thanks to GeeZeo for hosting us, to Sun for feeding us, and to Addison Wesley for giving us books to raffle off.  Hope to see you there!

Hartford Ruby Brigade meeting tonight

If you’re in the area, feel free to drop in:

The Hartford Ruby Brigade’s September meeting is tonight, from 6 to 8 PM, at GeeZeo’s offices on 750 Main St, Suite 1314, in Hartford (next to the CVS).

The big news is Addison Wesley has a ticket for the Voices That Matter: Professional Ruby Conference this November, and we’ll raffle it off. It looks like a sweet conference, go take a look. You have to be there to win, so if you’ve been waiting for the right time to make an appearance, this is it. And since only one of us can win the ticket, we’ll also raffle off a great Ruby book, Hal Fulton’s The Ruby Way. A big thanks to Addison Wesley!

Aaron will give his long-promised IronRuby talk, and I’ll show a mini-project of mine that generates MSWord .docs from Textile, with RedCloth. It’s flashy, I promise.

Remember, if you have a topic you’d like to talk about, or one you’d like to hear about, or even if you just have an idea for what to do for the evening, don’t be shy, speak up! The group is what we make it, and it belongs to all of us.

As always, we’ll have free pizza and soda, courtesy of Sun Microsystems.

Hope to see you there!

Use Ruby’s method_missing to see what happens to an object

Lately I’ve been generating MS Word .docs from text files, with RedCloth and Hpricot (thank you, why, for both of those), and win32ole. It’s been fun, except for the OLE parts: the ruby bridge is great, but the OLE API itself is strange, good documentation is sparse, and things get…flaky, sometimes.

In troubleshooting a bug that turns bold text on and off at the wrong times, I thought “it’d be nice if I could see all the calls that happen to this ‘selection’ object, in order they happen. Maybe I don’t realize I’m turning the ‘bold’ on at the wrong times.” Enter the Echoer:

class Echoer
    def initialize(name)
        @name = name
    end
    def method_missing(method_name, *args)
        puts "#{@name}.#{method_name}: #{args * ', '}"
        Echoer.new("#{@name}.#{method_name}")
    end
end

The Echoer is a stand-in for a regular object. Whenever a method is called on it, it prints its own name, the name of the method called, and the arguments.

def get_me_my_object
    # RealObject.new
    Echoer.new('obj')
end
obj = get_me_my_object
obj.puts 'Hello there'
obj.name = "Puddin'head Wilson"

# prints:
obj.puts: Hello there
obj.name=: Puddin'head Wilson

Each method call returns a new Echoer, whose name is based on its name, and the method name, so you can chain method calls.

obj.next.upcase.match /pattern/

# prints:
obj.next: 
obj.next.upcase: 
obj.next.upcase.match: (?-mix:pattern)

I should probably make Echoer a BlankSlate object, but I haven’t run into a need for it just yet. I could also inspect the method’s arguments with args.map { |arg| arg.inspect }, so you can tell strings and symbols apart.

Back in OLE-land, I replaced all instances of the selection object with Echoer.new('selection'), re-ran my code, and watched the output. I still haven’t found the source of the bug, but at least I know I’m not turning bold on or off when I don’t expect to.

Thanks to Michael Feathers for this idea. He wrote on the Beautiful Code blog about Spelunking Ruby Methods with Pebbles, but it seems O’Reilly took the blog down. All that’s left are the links from sites like reddit…does anyone know if the content is floating around somewhere out there?

Working Faster, Avoiding the Mouse

I’m moving away from my mouse all the time. On the one hand, it’s so much faster to keep my fingers in the same place, and on the other, it’s easier to automate keystrokes than mouse motions & clicks. I especially don’t like mousing through menus, so I’m always on the lookout for keyboard shortcuts. Here are two tools that help me stay away from the mouse.

SlickRun

SlickRun is an application launcher: a special keystroke brings up a small pseudo-command-line window, you type in a command, and it launches the associated application. By default, it uses a tiny window, but I made mine use an 18pt font, right in the middle of the screen — it’s my main focus when I use it, and it disappears right after. When it first pops up, I have it display the date & time.

You can type in URLs, and it launches them in the default browser. It includes the Ctrl+Enter shortcut, so “google” + Ctrl+Enter launches “http://www.google.com&#8221;, just like in Firefox and IE. You can type in file paths, and it helps you with tab completion.

You define “magic words”, short names for applications, so “mail” launches Outlook, “ffox” for Firefox, etc. But long, descriptive magic words are no problem, because it auto-completes them for you. I can launch “editor_programmers_notepad” with only “ed”.

Magic words can take parameters too. Here, the magic word “release” opens explorer to a network share where my team stores release information, each release in its own folder. The magic word uses the release name to create the path, and launches explorer.

SlickRun can export and import its list of magic words, which is great, because I move between three computers regularly. If you’re curious, you can import my magic words.

SlickRun comes with Jot, which is a pop-up notepad for short-term notes. It’s kind of strange, coupling this with a launcher. I never really use it, but if you have a use for it, it’s there.

I’ve used SlickRun for about a year, and at this point, I don’t think I could live without a launcher. I’m thinking of trying Launchy, which looks very promising.

StExBar

StExBar is an add-in for Windows Explorer that I found on the wiki for The Productive Programmer. It creates hot-key shortcuts for common actions: Ctrl+Shift+N creates a new folder, Ctrl+M opens a command prompt in the current folder, Ctrl+Shift+C copies the full paths of selected files, Ctrl+Shift+R renames files in the current folder with regular expressions. This is really nice — it shows the current file name on the left, and the new on the right, based on the pattern you typed in. You know exactly how the rename will work before you run it.

It also lets you define custom commands. So far, I have Ctrl+E opening the file for editing in Programmer’s Notepad, Shift+U running svn update on the selected items, and Ctrl+B opening a cygwin bash shell in the current folder.  UPDATE: I just added Ctrl+Shift+D for running a diff.

I just installed StExBar three days ago, so it’s not ingrained into my fingers yet, but I already missed it at home this weekend.  It fills a narrow spot, adding hotkeys to Explorer, but it does it really well.

Long-running averages, without the sum of preceding values

Here’s a little lunch-time diversionary math.  Suppose you want a function that takes a number, and returns the average of all the numbers it’s been called with so far.  Handy for continuously updated displays, that kind of thing. Here’s a method that will return this averaging function.

private static Func MakeAverager()
{
    float sum = 0;
    int count = 0;
    return delegate(float x)
    {
        sum += x;
        count += 1;
        return sum/count;
    };
}

It creates sum and count variables for the function to close over.  The function takes a number, x, and adds it to sum.  It increments count, and divides.  Pretty standard.

Now, let’s get crazy, and pretend this code is going on Voyager, and it’ll be running for ever.  sum will get pretty high, right?  We’ll blow through 231, the upper-bound for .Net 32-bit ints.  Sure, we could make it a long, and go up to 263, but that’s not the point.  The point is, it’ll eventually run out, because sum is too high.

I’ve been chewing on this brain-teaser for a while.  I knew there must be a way to calculate a long-running average without storing the sum and the count; it seems the average so far, and the count, should be enough, but I don’t want to resort to ((average * count) + x) / count++, because that’s the exact same problem. (Of course, count could still get so high it overflows, but that’s somewhat less likely. Hush, you.)

I finally sat down and figured it out.  The trick is, each successive x tugs your average up or down — first by a lot, but by less over time.  With each x, the average gets harder to move:  the effect each new x has on the average is inversely proportionate to the count.  We can put it like this:

average += (x - average) / count

We tug average by x - average, the distance between them, scaled down by count.  Then, add that on to average (of course, if x < average, then x – average is negative, so it’ll tug the average down).

Let’s make a new averager.

private static Func MakeNewAverager()
{
    float average = 0;
    int count = 0;
    return delegate(float x)
    {
        average += (x - average) / ++count;
        return average;
    };
}

It works the same, but it’ll take a lot longer for count to overflow than sum.

For the record, here’s the ruby I used to sketch this idea out.  Of course, in ruby, this problem is even more bogus, because ruby’s Bignum can handle any number that your machine has enough free RAM to store.  But still.

def make_averager
    sum, count = 0, 0
    lambda { |x|
        sum += x
        count += 1
        sum.to_f / count
    }
end

def make_sum_free_averager
    avg = 0.0
    count = 0
    lambda { |x|
        count += 1
        avg += (x - avg) / count
    }
end