Borges, Haskell, Euler

In one of my favorite Borges stories, he describes the imaginary people of Tlön who speak a language that has no nouns.  They have only impersonal verbs, adverbs, and prepositions.  Instead of saying, 'The moon rose above the river,' they would say something like, 'Upward, behind the onstreaming it mooned.'  The story explores the ways in which language shapes what we do and how we think.  Borges writes, 'For the people of Tlön, the world is not an amalgam of objects in space; it is a heterogeneous series of independent acts.'  This raises the question: how would your life be different if you didn't have a word for 'you' or 'I'?

You don't have to merely ponder this if you learn a functional language like Haskell (named after mathematician Haskell Curry).  I've taken a deep dive into Haskell, though I still feel like one of the early explorers trying to understand Tlön.  If you're used to thinking in terms of 'objects in space'--that is, if you mostly work in object-oriented languages--Haskell is very weird at first.  You'll have to start thinking in terms of functions.  Even basic units, like the number 5, are really functions that return the value 5 and which can then be passed to other functions.

Check out this implementation of the Quicksort algorithm, taken from Miran Lipovača's awesomely-named book Learn You a Haskell for Great Good!:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

This code declares a function quicksort, which takes a list and returns a list of things that can be ordered.  It recursively calls itself, so the base case is an empty list.  It grabs the first item from the list and uses it as the pivot to generate two other lists of all items greater and smaller that it.  Then it concatenates and returns the sorted sublists.  Voila!

You might wonder why it's useful to learn a language like Haskell.  I personally haven't seen any production Haskell code, though you can find some cases of it.  I wanted to learn Haskell because it is a purely functional language, and I thought it would help me better understand some of the ways functional programming is creeping into OOP.  For example, Java 8 will have closures, the Clojure language is gaining popularity, and C# makes heavy use of lambdas and extension methods in LINQ.

I have also heard that learning Haskell will make you a better programmer.  I do think it's hard to really know any language unless you know what else is out there, just like I think it's a bad idea to maintain a belief in something if you don't consider other beliefs, whether it's politics, religion, or anything else where reasonable people disagree.  However, I'm not sure what Haskell or other functional languages teach besides recursion.  You really have to be comfortable with recursion to do any amount of functional programming.  For example, you could write a function to check if a list or string of characters is a palindrome in the following way:

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome ([]) = True
isPalindrome ([x]) = True
isPalindrome (x:y) = 
    if x == z && isPalindrome w then True else False
    where z = last y
          w = init y

Haskell is great for problems where you can break a task into a series of mathematical equivalences.  It's hard for me to imagine trying to solve Project Euler problems without Haskell.  I've done about 25 of these for practice, and I highly recommend poking around in them.  Problem 20, for example, asks you to sum the digits of 100!.  This can be done in one line of Haskell.  Problem 9, which asks you to find a Pythagorean triangle where a + b + c = 1000, can also be done in one line.  First you generate three lists of numbers (a, b, and c) from 1 to 500 or so.  Then you get a list where a² + b² = c².  Then you get a list where a + b + c = 1000.  Finally, you filter out all the items where a < b < c to get a unique tuple. 

I've written before that you have to be careful with functional languages because they abstract away the implementation from the code.  In the Pythagorean example above, for example, you do not have to write a series of for loops.  It's easy to write code that will take days or years to finish in Haskell.  I speak from experience.  (For fun, try running last [1..]).   But this kind of abstraction can be beneficial, as the logical nature of Haskell highlights the logic of your thought process.  One of the most important things I've learned in working with Haskell, especially on problems dealing with huge numbers, is just how important it is to have a good algorithm.  Because Haskell programming is nothing but functional logic, it's easy to concentrate on the essentials.

LINQ and Functional Object-Oriented Programming

It took me a while to come around to the "functional turn" in object-oriented programming. This includes the growth of Clojure and Haskell, as well as Microsoft's new LINQ and F# languages. I've been familiar with functional languages like LISP for some time, but it was hard for me to see how such an austere and limited paradigm could be fruitfully imported into the world of polymorphic objects. Furthermore, as someone well familiar with the dangers of bad SQL programming, the last thing I wanted was to allow a Zelda character to write my queries for me.

I haven't changed my mind about using LINQ to access a database, because database performance is too important to me. However, I have found LINQ to be extremely useful for shredding and joining data into custom data structures made up of generic data types. I do this to pass information between layers of abstraction, such as through WCF, or between classes. For example, you could turn a data table into a list of dictionaries, which could be serialized easily into a custom contract. You could then shred that returned structure into whatever you want, such as key value pairs in an IEnumerable of an anonymous type defining points in a chart.

Many of the recent changes to the C# language have been to make it more functional. C# 4.0 is mostly about dynamic typing, but 3.5 is all about LINQ--or rather, the typing and syntactical changes that make LINQ possible. If you've been away from C# for a few years, the language might look almost completely alien to you due to the introduction of Lambda expressions, expression trees, extension methods, implicit typing, nullable types, anonymous types, and anonymous functions. These features let you do pretty much anything you want with data on the fly.

var Points =
   from DataRow dr in dt.Rows
   where (String)dr["Program"].Trim() == Program
   select new
   {
        Date = (DateTime)dr["Date"],
        Value = Convert.ToDouble(dr[Metric] ?? 0.0)
   };

Though applications like this are where I use LINQ primarily, I can see its attraction for database querying. One of the ugliest and most difficult-to-debug pieces of OO code is SQL statements defined as string literals in application code. It's particularly ugly in VB.NET, since you have to include ampersands and end-of-line characters. The solution has always been to used stored procedures for all data access, but this best practice is not always practiced. LINQ provides you with strong typing, which is nothing to sneeze at. One of the biggest problems with SQL is its lack of type checking, especially when creating dynamic SQL. You could create some really cool data access classes that use LINQ instead of dynamic SQL.

Whether or not you use C#'s LINQ or Java's Clojure, the functional turn in object-oriented programming is interesting for its own sake. On the one hand, languages are becoming more and more flexible and intuitive. They allow you to do a lot with a few lines, and in an intuitive manner that abstracts away details. On the other hand, languages are becoming more complicated than ever. In reading Jon Skeet's C# in Depth, I kept thinking how much more information it provided than I needed to get the job done. I'll be very interested to see how further hybridizations of language provide ever more useful tools, especially for manipulating data.

Erlang and Concurrency

I was excited to learn me some Erlang, since the mysterious language has recently gotten a lot of press for being the tool of choice for Facebook Chat. It's often cited as a way to break the performance barriers of multi-processor architecture and mainstream programming languages that use multi-threading. A program is as fast as its slowest part, and this is typically the resources shared by threads. These resources also require some fancy coding techniques to ensure their integrity. And, of course, the more complicated the code, the more likely it is to break and be difficult to maintain.

Erlang's simple model is based around processes that pass messages to each other, crash, and respawn very quickly. After compiling a module, you spawn a process using:

handle = spawn(module, function, parameters).

The process is defined as a function that shreds out the parameters with a series of case statements:

function -> receive
	{parameter1} ->
		%do something
	{parameter2} ->
		%do something else
	Unexpected ->
		%handle exceptions
end.

You can pass messages to a spawned process using:

handle ! parameters.

This architecture allows you to quickly create, monitor, message, and respawn processes whenever they fail. Because Erlang is a functional language, there are no variables or any other shared resources that can form a bottleneck between processes liked global variables. Processes communicate using messages, and these can be processed asynchronously or independent of any other processes.

Erlang's concurrency model is similar to Service Oriented Architecture, except that concurrency is built into the system at the lowest level, not added on top of an Object Oriented framework and requiring several other technologies. Note also that concurrency is very different from parallelism. If you need to crunch a lot of numbers, you'd need to use a parallel processing system, not a concurrency model.

Erlang is best for soft real-time, distributed, and highly-available applications that could be composed of message-handling systems, like Facebook Chat or low-level telecommunications software. (These are very specific applications that I tend not to think about very often, so I don't have a mock-up like I have tried to have in other posts.)

For these reasons, Erlang is not a cure-all for performance-related problems, though it is important to note that there are limits to any concurrent or parallel approach. Amdahl's law states that even with 95% parallelism, performance benefits will quickly plateau as the number of processors increase.  E.g., if your program takes 20 seconds to run, and 1 second of it cannot be parallelized, the least amount of time it could run in is 1 second.  No matter how many processors you add, you cannot break that 1 second barrier without further parallelizations.


As a side note, I had not heard of Amdahl's law before researching Erlang. Interestingly, I also just learned of IBM's SyNAPSE project, which has the grand aim of functionally replicating the human brain. One argument for a new hardware architecture based on neural networks is that, though the firing of individual neurons is slow, the massively parallel processing power of a brain more than makes up for the performance of any individual part. I'm not sure how this argument stacks up against Amdahl's.

I'll be looking for opportunities to write me some Erlang, but--given my own limits to processing in parallel--this may not be any time soon.

Links:
-Erlang home page
-Eugene Letuchy's notes on designing Facebook Chat
-Learn You Some Erlang, a free online book