Normally, I wouldn’t make such a brief post, but I’ve encountered (several times) some very bizarre and complicated algorithms to round to the nearest multiple-of-n (where n is 5 or 7 or whatever).  Say, for example, that you’re pricing your product for an overseas military base, and, as we know, overseas military bases don’t use pennies, so all prices must be multiples of 5.  So, you want to have your program round the price off to the nearest multiple-of-5. It’s really very simple:

public static int RoundToNearestMultipleOfN(double val, int n)
{
     return (int)Math.Round((val / n)) * n;
}

So seriously, don’t get all bent out of shape.

January 20th, 2009 | Comments (2)

Last time, we talked about how anonymous functions could be created in most any language that supports first-class functions.  In brief, we discussed how a function definition can be used as an expression in these languages, stored in a local variable, or passed back as a return value from another function.  The one key piece we didn’t discuss was the thing that makes anonymous functions so cool: they have access to the lexical scope in which they are defined.

First, what do we mean by “lexical scope”?  Nearly all languages are lexically scoped, meaning that an identifier’s scope is determined by where it is declared (or defined) in the source code.  For example, the following should cause a compiler error in C#:

for (int i = 0; i < 5; i++)
{
     int i_squared = i * i;
     Console.WriteLine(i_squared);
}
Console.WriteLine(i_squared);

This should cause an error because i_squared is declared inside of the for loop, and it is only a valid identifier inside of the for loop.  If we want access to the value of the variable inside of the loop, we need to assign it to variable which is valid outside of the loop (and, hence, in a different lexical scope).  So let’s say we do this:

int final_value;
for (int i = 0; i < 5; i++)
{
     int i_squared = i * i;
     Console.WriteLine(i_squared);
     final_value = i_squared;
}
Console.WriteLine(final_value);

This should compile and give us the value of i_squared the last time through the loop in final_value. A key thing to note is that we’re getting the value of the variable, and not the variable itself. This might sounds a little pedantic, but you’ll see in a minute why this is relevant.

Now, we’ll take the jump and make our first closure:

Action print_final_value = null;
for (int i = 0; i < 5; i++)
{
     int i_squared = i * i;
     Console.WriteLine(i_squared);
     print_final_value = () => Console.WriteLine(i_squared);
}
print_final_value();

As you might expect, this will print out: 0 1 4 9 16 16.

The most important point here is that we’ve captured the local variable i_squared inside of our function called print_final_value. We’ve taken a variable from one lexical scope and effectively frozen it for use outside that scope. When we do this, we’re creating a separate environment that rides along with the function definition wherever it is passed. This combination of a function definition and an associated environment is called a “closure.” Note the distinction that we’ve captured the actual variable and not just the value of the variable. You can see the significance of this by making the following modification:

Action print_final_value = null;
for (int i = 0; i < 5; i++)
{
     int i_squared = i * i;
     Console.WriteLine(i_squared);
     print_final_value = () => Console.WriteLine(i_squared);
     i_squared = 0;
}
print_final_value();

So what does this print? If you guessed 0 1 4 9 16 0, you’re right! When we create the closure, we don’t just get a copy of the variable values at the time the function is defined, we get the actual variables in the closure, and any modifications made to those variables are reflected in the closure’s environment.

Of course, each time we go through the loop, we get a new lexical scope for the loop body, so the i_squared variable is a different variable for each time through the loop, despite having the same name. If you want to see a very contrived example of this:

Action a = null;
Action b = null;
 
for (int i = 1; i < 3; i++)
{
     int i_squared = i * i;
     if (i == 1)
     {
          a = () => Console.WriteLine(i_squared);
     }
     if (i == 2)
     {
          b = () => Console.WriteLine(i_squared);
     }
}
 
a();
b();

This prints out: 1 4. The a function gets the i_squared from the the first iteration of the loop and the b function gets the i_squared from the second iteration. Because these are separate scopes, there are separate variables, and the two closures have different i_squared variables in their closure environments.

So, now that you’ve got your feet wet with closures, there’s a lot of other things you can try with them (in C# or any other language that supports them):

• Use a closure instead of a subclass. When you need specialized functionality and/or data-hiding, but you don’t want the overhead of introducing new types in your namespace, you can use a closure instead of a subclass. If you really wanted to, you could roll your own object-oriented type system just using closures, and then you’d have JavaScript.
• Use currying to build a family of related functions. Currying is the process of taking a multiple-argument function and turning it into a chain of functions, each of which takes a single argument. This is handy when you want to “fix” one of the parameters of a function, but still allow the other parameters to be passed in as variables. For example, you could write a function for logging messages that takes a handle to a file and a string to write to that file. You could curry it and fix the handle to the log file, and then pass around a function that just takes one parameter (the message to write) and automatically writes to the file handle that you baked into the function earlier.
• Multi-thread with closures. Instead of messing with locks and so forth, build a thread’s state in the lexical scope where the thread function itself is defined. This is more complicated that I’m making it sound, but using closure variables instead of global variables can make working with multi-threaded code simpler. There’s also a huge body of research on implicit parallelism, which has to do with the fact that certain language constructs are inherently thread-safe (for example, a closure with no side-effects inside of it) and can be parallelized by the compiler or the runtime.¹

If you already knew about closures, hopefully this article renewed your faith in their importance, and, if you didn’t know about them before, then welcome to a new world. Closures are an elegant weapon…for a more civilized age.

1. The PLINQ project at Microsoft is working towards making parallelism mostly implicit in .Net (when the developer gives the “hint” to parallelize a certain LINQ query). [↩]

November 24th, 2008 | Tags: functional programming, microsoft, performance | Comments (3)

Think back to some of your earliest programming days.  Unless you first learned LISP or the like (bless your little heart), you probably learned on an imperative programming language like C, PASCAL or BASIC.  I say you learned “on” a language, because this initial experience shapes our idea of what a computer can and can’t do and what a programming language is “supposed” to be like.  One of the most basic assumptions that these common first languages is that everything in your program has a canonical name. A variable has a name, and when you want to refer to it, you call it by name. A method has a name, and to invoke it, you use the name (and pass any parameters).  Likewise, classes, modules, packages all have names, which you define when you write the program and the compiler interprets.  Something which you may not have been exposed to early on is methods without names — so-called “anonymous methods.”

A Name for Every Function (The View from C)

Let’s start out looking at a language that doesn’t support anonymous methods: C¹.  In C, a function name is more or less identical to a label in assembly language, that is, it’s a mnemonic for a memory address to be jumped to from other code.  You can pass function pointers in C, but these are just pointers to that same address that you originally defined the function at.  You can’t create a new function at runtime in C and assign it to a function pointer.  So, if I want to do a dynamic sort routine in C, I might do something like this:

#include 
 
void BubbleSort(int *numbers, int array_size, int(*comparer)(int, int))
{
  int i, j, temp;
 
  for (i = (array_size - 1); i >= 0; i--) {
    for (j = 1; j <= i; j++)	{
      if (comparer(numbers[j-1], numbers[j]) > 0) {
	temp = numbers[j-1];
	numbers[j-1] = numbers[j];
	numbers[j] = temp;
      }
    }
  }
}
 
int IntegerComparer(int a, int b)
{
  return a - b;
}
 
int ReverseIntegerComparer(int a, int b)
{
  return b - a;
}
 
int main(int argc, char** argv)
{
  int nums[] = {3, 4, 21, 17, 100 };
 
  BubbleSort(nums, 5, IntegerComparer);
 
  printf("Regular order:\n");
  int i;
  for (i = 0; i < 5; i++) {
    printf("%d\n", nums[i]);
  }
 
  BubbleSort(nums, 5, ReverseIntegerComparer);
 
  printf("Reverse order:\n");
  for (i = 0; i < 5; i++) {
    printf("%d\n", nums[i]);
  }
 
}

Pretty verbose, I know, but we’ll use this as the basis for all of our future examples. The point is, I can implement a “generic” bubble sort in C that takes a function pointer as an argument that I can use to compare two integers. If I wanted to, I can sort all the odd numbers to the beginning of the list, or I can sort all the primes to the end, etc. just by passing a different comparer.

However, these comparer functions have to be defined separately in the module and I refer to them by their canonical name (the name I used when I defined them) when I pass them as pointers.  Looking at the assembly code generated by gcc, you can see that these canonical names are directly translated into assembly labels:

.globl _IntegerComparer
	.def	_IntegerComparer;	.scl	2;	.type	32;	.endef
_IntegerComparer:
	pushl	%ebp
	movl	%esp, %ebp
	movl	12(%ebp), %edx
	movl	8(%ebp), %eax
	subl	%edx, %eax
	popl	%ebp
	ret
.globl _ReverseIntegerComparer
	.def	_ReverseIntegerComparer;	.scl	2;	.type	32;	.endef
_ReverseIntegerComparer:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %edx
	movl	12(%ebp), %eax
	subl	%edx, %eax
	popl	%ebp
	ret
	.def	___main;	.scl	2;	.type	32;	.endef
	.section .rdata,"dr"

And, when I call the BubbleSort function with my function pointer, I’m just passing the addresses of these labels:

	movl	$_ReverseIntegerComparer, 8(%esp)
	movl	$5, 4(%esp)
	leal	-40(%ebp), %eax
	movl	%eax, (%esp)
	call	_BubbleSort
	movl	$LC2, (%esp)
	call	_printf
	movl	$0, -44(%ebp)

This is the closest thing to an anonymous method in a language like C, and, as you’ll see, it’s pretty far from that target.

Introducing “Anonymous”

At this point, I’ll switch from C into C# 3.0, a language that allows for anonymous methods.  Truly anonymous methods were introduced in C# 2.0 with a much more verbose syntax; I’ll use the simpler “lambda” syntax introduced in 3.0.  The key conceptual difference between languages that allow for anonymous methods and languages that don’t is that all languages with anonymous methods have first-class functions.  In brief, this means that a function definition is an expression and has a value at runtime which can be passed around, used as a function parameter or returned as a return value.

In contrast, in C, our function definition was a statement to the compiler which told it, in essence, to create a label and handle our parameters and return value according to some standard.  The definition had no value at runtime.  The only thing we had access to at runtime was the address of the label the compiler created for us.

In C#, the following is completely valid:

public void Foo()
{
     Func  sorter = (a, b) => a - b;
 
     Console.WriteLine(sorter(1, 2));
}

This prints out -1.  The right-hand side of that assignment to “sorter” is what is lovingly referred to as “lambda” expression by the C# team and lovers of the lambda calculus the world over, and it’s a way of defining an anonymous function at runtime.  In this case we defined a function that takes two integer parameters called “a” and “b” and returns an integer a - b.  Then, we called this function with a = 1 and b = 2, which returned -1.

You might be saying, wait a minute, that function does have a name: “sorter”!  Well, let’s change things up a bit:

public Func GetSorter()
{
     return (a, b) => a - b;
}

This is still perfectly valid, and now the function doesn’t have any name that we can refer to in this block of code, and it returns a function.  So, you might now well ask, what does it mean to return a function?  Is it an address to jump to?  Is it some kind of intermediate data structure defined by the runtime?  Is it text that will be interpreted by some sort of runtime interpreter? It could be any of these, although for C# it is more or less a combination of the first two.

Generally speaking, in a compiled language such as C#, anonymous functions do actually have a canonical name (and an associated assembly label), but this name is auto-generated by the compiler.  What you’re passing around when you define a local variable to point at an anonymous method, or you return one from another function is an intermediate data structure that, at some level, contains a pointer to this label, and, therefore, the compiled body of your function.  In this structure, the compiler also stores a reference to the lexical scope in which the anonymous function was defined.  This combination of function-body and lexical scope is called a “closure” and is of paramount importance in functional programming (more on this in a future post).

Implementations will obviously vary, but these two pieces of data are essential to any proper implementation of anonymous methods.

So, using anonymous methods, we can redefine our dynamic sorter as follows in C#:

static void BubbleSort(int[] numbers, Func comparer)
{
     int i, j, temp;
 
     for (i = (numbers.Length - 1); i >= 0; i--)
     {
          for (j = 1; j <= i; j++)
          {
               if (comparer(numbers[j - 1], numbers[j]) > 0)
               {
                   temp = numbers[j - 1];
                   numbers[j - 1] = numbers[j];
                   numbers[j] = temp;
               }
          }
     }
}
 
static void Main(string[] args)
{
     int[] nums = {3, 4, 21, 17, 100 };
 
     BubbleSort(nums, (a,b) => a - b);
 
     Console.WriteLine("Regular order:");
     int i;
     for (i = 0; i < 5; i++)
     {
          Console.WriteLine(nums[i]);
     }
 
     BubbleSort(nums, (a, b) => b - a);
 
     Console.WriteLine("Reverse order:");
     for (i = 0; i < 5; i++)
     {
          Console.WriteLine(nums[i]);
     }
}

So, it’s shorter and sweeter, right? In fact, there are a couple more reasons to use anonymous methods whenever you can:

• They keep your namespace clean. Your namespace isn’t polluted with lots of one-off functions and helpers.  You don’t have to worry about if you already have a function defined called “SorterHelper,” or the like.
• Your function bodies are in the code where they are used. This makes it easier to see what’s going on in your code.’

But I haven’t shown you anything here yet that you can’t do with C, I’ve just shown you an easier and more terse way of expressing things.  If you know anything about functional programming, you’re probably screaming at me right now for glossing over the most important fact about anonymous functions:

• The have access to the lexical scope in which they are defined.

I’ve been intentionally avoiding this topic, because it’s big. Really big.  So big, in fact, that it needs its own post.  Check out part 2 of this post, dealing with closures and other big functional programming ideas!

1. Some may note that, if you want to, in C, you can dynamically generate machine code in memory and jump to it, allowing you all the flexibility that an anonymous function might give you. While technically correct, these people are crazy. Also, this isn’t really C programming, but, rather, assembly language programming, in that your “anonymous function” would be written in machine code. [↩]

November 18th, 2008 | Tags: functional programming | Comments (3)

It’s widely believed that there’s such a thing as a “trade secret” in software development: some algorithm or data structure that makes your product better than all the others in your industry, and that you shouldn’t reveal it to your competition or else they’ll steal it and out-compete you.  Our industry is rife with NDAs, non-competes and other legal instruments to prevent software engineers from walking out the door and blabbing all of our secrets to the world (or at least to the competition).

That being said, I’m not really afraid of having my ideas stolen by anybody.  The’s because the only true trade secret, from a development perspective, is the actual source code. That’s where the rubber hits the road, and anything less is about as valuable towards actually developing a deliverable product as a first-pass brainstorm session.  The other thing to remember is that there are overpowering forces at work in the minds of most developers that prevent them from stealing ideas, including the “I’m smarter than everyone” force and the “not-invented-here” force.  As computer scientist Howard Aiken said:

Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats.

More than likely, you work for a company like Microsoft or Apple, which closely guards anything that it thinks it can monetize, and you, and the contents of your head, are treated accordingly.  Microsoft has its research division which publishes some pretty interesting stuff, but you’ll never see a paper describing, for example, how SQL Server optimizes queries down to the last detail.  These are things that they’ve worked hard to develop, and they keep to themselves.

On the other hand, you have a company like Google which has made public a number of details about its internal operation, including the PageRank Algorithm, Map-Reduce Architecture, Google File System, and a whole slew of other topics. Of course, many of these algorithms are encumbered by software patents (which may or may not still be valid), but they aren’t “secret,” per se.

What is a secret is the implementation. Just because I know about PageRank and Map-Reduce and GFS doesn’t mean I can build a Google-killer in my basement; there are a hell of a lot of important details that are intentionally left out in published papers (and in patents, for that matter).  The big ideas are there, but it’s not detailed enough to go straight to a correct implementation.  Google has a big team of really smart people that work on the details all the time, and they aren’t about to walk out the door any time soon, unless the execs at Google really screw up.

That being said, even if I did get together a functional version of all the key technologies that make Google work, it doesn’t mean that I’ll have a successful product.  In fact, what makes most products successful isn’t the core algorithms and data structures (the computer science part), but all of the details, polish and integration between these components.

We often necessarily focus on only one aspect of a project to the exclusion of others, and this tunnel-vision can dictate how we evaluate whether or not the project is a “success.”  For example, if you’re working on optimizing a search algorithm, your metric for success is the speed of the response.  For somebody else, the correctness of the search results may be their primary concern.  No matter your focus, there ultimately has to be a compelling product that links all of these components together into a well-oiled machine.  Your search optimization may be the single greatest development in search algorithms in the 21st century, but, if your product doesn’t do anything useful for anyone, that’s not going to be worth much in the long run.

To my mind, functional, polished products are the true “trade secrets” that good companies have, and they aren’t the kind of thing that someone can just walk out the door with.  So, I’m not that worried about people stealing my ideas.

November 12th, 2008 | Tags: apple, google, microsoft, performance | Comments (1)