In the last entry, I wrote about an interesting discovery I made as I began to learn more about functional programming. In the first chapter of a book about the Ocaml language, I found a few lines the emphasized the ease and power of being able to supply functions as parameters to other functions (see code in last entry). I also mentioned how it was a little more cumbersome to implement in a language like C#, but not impossible. I didn't share that code, though, because I am a code tease. (Note: that's coDE tease. I don't want any getting the wrong impression.)
Can you pass in functions as parameters in C#? Sure you can, using delegates. In fact, when it comes to passing around these functions using delegates, the functions don't even have to be actual, named functions. (That's thanks to a new feature in C# 2.0, anonymous methods.) While you can definitely implement the same functional in C#, it looks a lot different.
public delegate T mydelegate(T x); public static void Main()
{
mydelegatesuccessor = delegate(int x) {return x + 1;};
mydelegatesquare = delegate(int x) {return x * x;};
Console.WriteLine(Compose(square, successor, 5));
}public static T Compose
(mydelegate method1, mydelegate method2, T x)
{
return method1(method2(x));
}
The code I just presented is the functional equivalent of the code presented in the last entry. Regardless of your expertise with either language, which one is easier to understand? Which would you rather write?
I'm a total C# dork, but I must say that I find the Ocaml/F# code easier to understand. Look how succint it is. Notice how it never once mentions anything about generics, or even data types. We don't need to create or understand a construct like a delegate in order to pass our functions around; we just pass them. That's very nice.
Like a lot of other people, I've been dipping my toes into functional programming lately. This is for three reasons. First, I've read a lot about the new language features in C# 3.0, and a lot of them are rooted in fp (check out LINQ for references). Second, about a year ago, I wrote a gigantic amount of number-crunching code that had some really nasty state issues. Third, a gang of roving Lisp hooligans shang-haied me on 6th Street and tattooed a lambda on my forehead; in case anyone asks, I should at least know the lingo.
I don't know if y'all have been following it, but Microsoft Research released a really interesting functional language recently, F#. It runs on the .NET framework and it has Visual Studio support, both of which lessen the scariness factor for wimps like me. And so, I'm learning F#. Actually, I'm not sure that I can call this learning yet; the process thus far has been like handing the abominable snowman a fax machine manual. However, again like the abominable snowman, I am resourceful and tenacious, so I haven't given up.
F# is very similar to OCaml, or so they tell me. I found F#'s documentation to be a little cryptic, and I discovered that it's a lot easier to read OCaml docs and port those concepts to F#. For some good OCaml reads (a phrase not often heard), check out the online translation of Developing applications with Objective Caml.
Even in Chapter 1's throwaway sample code, I found something that validated my reasons to learn more about functional programming. (All of the following code works in F# and should work in OCaml if you replace the Console.WriteLine part, although I honestly haven't tried compiling anything in OCaml. I've got to draw a line at the nerdiness somewhere.) I've built on the example a little bit to make it easier to understand.
First, we define a couple of functions, square and successor.
let successor x = x+1 ;;
let square x = x*x ;;
Okay, that's simple. When given an integer, successor gives you the next one. Square just squares a number. Now we do some functional magic.
let compose f g x = f(g x) ;;
System.Console.WriteLine("The successor to 5's square is " + (compose square successor 5).ToString());
The Compose function just lets us chain two functions together simply. With it, we call a function to increment successor by 1, then we call the square of that method. Couldn't you do that with square(successor(5)) in any normal language? You could, but that would ruin this whole post. Also, it'd miss the cool part of Compose, which is how easy it is to supply a function as a parameter to another function.
Now, you could most certainly implement the exact same functionality in C# using delegates. I've done just this, and let me tell you, it contains 10% of the elegant with 1000% of the confusion. In the next post, I'll share that code. I may also furnish some smores, we'll see how I'm feeling.
I'm an idiot when it comes to functional programming, but it's only taken me a few pages of a book to see why it offers such a compelling alternative to imperative programming. Through a little comparison, you may agree. If not, well, at least you're not paying for any of this information.
Remember last entry where I was talking about depth-first vs. breadth-first searching when trying to find the best chess move? Well, that particular tickled my organic memory banks, and I soon remembered that there's a section of Godel, Escher, Bach that expands and elucidates this topic. Computer, begin expansion and elucidation!
A classic example of a recursive procedure with parameters is one for choosing the "best" move in chess. The best move would seem to be the one which leaves your opponent in the toughest situation. Therefore, a test for goodness of a move is simply this: pretend you've made the move, and now evaluate the board from the point of view of your opponent. But how does your opponent evaluate the position? Well, he looks for his best move. That is, he mentally runs through all possible moves and evaluates them from what he thinks is your point of view, hoping they will look bad to you. But notice that we have now defined "best move" recursively, simply using the maxim that what is best for one side is worst for the other. The recursive procedure which looks for the best move operates by trying a move, and then calling on itself in the role of opponent! As such, it tries another move, and calls on itself in the role of its opponent's opponent---that is, itself.This recursion can go several levels deep---but it's got to bottom out somewhere! How do you evaluate a board position without looking ahead? There are a number of useful criteria for this purpose, such as simply the number of pieces on each side, the number of types of pieces under attack, the control of the center, and so on. By using this kind of evaluation at the bottom, the recursive move-generator can pop back upwards and give an evaluation at the top level of each different move. One of the parameters in the self-calling, then, must tell how many moves to look ahead. The outer-most call on the procedure will use some externally set value for this parameter. Thereafter, each time the procedure recursively calls itself, it must decrease this look-ahead parameter by 1. That way, when they parameter reaches zero, the procedure will follow the alternate pathway---the non-recursive evaluation.
- Hofstadter, p. 150-151
It goes without saying that if you haven't read GEB, we probably can't be friends.
One point that's not in that selection is how, while there are useful criteria for evaluating a board position without looking ahead, each specific criterion isn't that useful. That is to say, only a stupid chess program would select a move based solely on the number of pieces on each side. (I say that because, going only by that metric, 4 pawns + 1 king implies a stronger position than 1 rook + 1 queen + 1 king. I am a chess moron and even I wouldn't take that trade.)
The reason I've been on a chess tangent lately is because, for a while, I was working on a chess program. The part that Hofstadter's discussing here, weighing the strength of a potential move, is the part where I had a lot of trouble. Each metric he lists (number of pieces, pieces under attack, control of the center) is useful, but depending on how the application weighs each one (and several others), it gets very different optimal moves. If anyone has any good resources on weighing these factors when calculating the strength of a move, please let me know. (Also let me know if you have good resources on free money.)
For reasons I can't exactly recall, someone asked me the other day about the differences between breadth-first vs. depth-first search. I provided a decent answer, and since this is the ideal place for such dorky discussions, I have elected to throw it up here. Computer, throw up search discussion!
First and foremost, a breadth-first search isn't what you do when you're in a bakery and you're looking for some rye. (That was the dumbest thing I've ever typed.)
Imagine you're looking at a tree structure. A depth-first search would start at the root and descend down a single path of lineage until it reached a childless node at the bottom; then it'd start on the next line of lineage and work its way down again, and so forth until we're out of nodes. A breadth-first search, meanwhile, would start at the root (level r), descend a level (level r+1), examine all nodes at that level, and would then repeat that action at the next level (level r+2). You could find a similar description in a textbook, so maybe that's not so helpful. Perhaps yo-yo vs. typewriter analogy is more fitting? No, I think not. Let's try again.
Imagine you're looking at a chess board, and you're trying to determine the best opening move you could make. You could do this two different ways.
The first way would be to concentrate on a single pawn. You think to yourself, "I could move THIS pawn two spots forward." Then you think what your opponent may do in response. You think, "He could move THAT pawn one spot forward." Then you think to yourself, "With THIS pawn here and THAT pawn there, I could move my bishop diagonally 3 spots." You're looking at a single possible sequence in great depth. That's a depth-first search.
The second way would be to look at the board and examine every possible first move. You realize you could move any of your pawns, or you could move any of your knights. Then what happens? Well, your opponent could move one of his pawns or one of his knights. Then what happens? Well, you could move your pawns some more, make your rooks dance, unleash your queen, etc. Instead of looking at a single sequence, you're looking at each possible move, one level at a time. That's a breadth-first search.
If you had to implement something that could advise you on chess moves, what would you pick? Clearly, the number of potential moves explodes combinatorically as we get deeper into the game. Just as clearly, humans aren't immortal, so we'd need a definitive answer before the heat death of the universe. Since we don't have time to examine each chain of possibilities and breadth-first is the only way to examine each path equally, I'd use breadth-first search. Of course, this may explain why I'm such a crappy chess player.
I realize it's been a long time since I posted anything in this space. "Surely," you think, "he's been working on fascinating projects. I can't wait to hear about these fascinating projects. Let the cavalcade of fascinating projects begin!" If you are thinking that, you're largely incorrect and you're also a little scary.
While I don't have anything particularly momentous to share, I do plan to share some stuff here in the near future. Before I do that, I must first think of this stuff, then type it up. It's in the pipeline, however, and I give everyone permission to get really excited.