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.

Where's the Logic Go?

Typically, the business logic resides in the middle, or domain, layer

Every application has at least two components: the design of technology platforms, called the application logic, and the processes that need to happen, called the business logic. In theory, the business logic is dependent of the application logic, since a business has rules, workflows, and transactions that have nothing to do with any programming languages or database systems. In practice, however, application logic can put constraints on business 'illogic.'

One of the key design choices in developing any application is deciding where the business logic should go. Database developers think it should go in the database, since keeping the code at the database level is often most performant. The problem with this is that SQL doesn't have many of the basic niceties of any Object-Oriented language. Furthermore, since stored procedures use proprietary SQL, they can prevent the migration of database code to another vendor.

OO developers think business logic should reside in the domain layer, since objects are best at representing the real world. Libraries and IDE's like Visual Studio make it very easy to get an OO application off the ground, and they help with maintainability. For many applications, however, the amount of code necessary to create an MVC model, for example, is not necessary and may even be prohibitively burdensome.

In reality, no application design should be used for all problems. Martin Fowler provides four models that couple domain and database access logic.

Transaction Script / Row Data Gateway - Domain code simply passes requests from the UI to the database. Database access is modeled at the record level.

Table Module / Table Data Gateway - Domain code is organized in objects corresponding to tables in the database. Database access is modeled at the table level.

Domain Model / Active Record - Domain code is organized according to business rules. Database access is modeled by CRUD objects.

Domain Model / Data Mapper - Domain code is organized according to business rules. Database access is modeled by a mapping object layer.

Fowler suggests that your choice of pairings should depend upon the complexity of your business logic. An application used for reporting can simply send requests to a database, but a complex sales order process should probably be mirrored by a domain model and a data mapper. A domain model will have a higher up-front cost, but it may pay off as the complexity of an application increases.

I think this general trade-off makes a lot of sense, and it helps me understand and categorize a number of applications I've seen. But, unless I am mistaken, pretty much any enterprise application is going to require a layer for business logic objects, a layer for data mapping, a layer for data access, a layer for the data itself, and, of course, the presentation layer. If it's possible to reduce the complexity of these layers, do so!

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.

Io, Syntactic Sugar, and Performance

I had never heard of Steve Dekorte's Io language until coming across it in Bruce Tate's book. Io uses the prototype-based or classless paradigm, which is a flavor of the Object Oriented paradigm. In classless programming, classes are not declared but are cloned from the base object class. Such languages are usually interpreted and dynamically typed. The most popular classless language is JavaScript.

Io is interesting for a number of reasons, such as its actor-based concurrency model, but what struck me the most in working through Bruce Tate's examples was the ugliness of the code. There's no way around it. It's just ugly. This was especially noticeable after learning some Ruby. If you want a complex class structure, you have to do a lot of cloning. Here's an example that clones the root object class and then clones that clone in order to actually do something:

Account := Object clone do(
balance := 0
deposit  := method(v, balance = balance + v)
withdraw := method(v, balance = balance - v)
show := method(writeln("Account balance: $", balance))
)

myAccount := Account clone
myAccount show
"Depositing $10\n" print
myAccount deposit(10)
myAccount show

While the words "programming" and "aesthetics" are not often used in combination, we do regularly talk about the elegance of code--meaning its ability to solve a problem in a creative and concise manner. Elegance can come at the price of readability, since it typically involves doing something complex in a short number of lines. Io does concurrency elegantly, but its classless model doesn't allow for a lot of concision or elegance more generally. If you want to create a number of classes with a number of methods, this will take many more lines than in a language like Ruby.

Unlike Io, Ruby has a lot of syntactic sugar, or programming shortcuts that make code more readable and concise. This is different from elegance, since syntactic sugar has to do with syntax while elegance has to do with logic. For instance, instead of defining a bunch of get and set statements for a class's properties, you can define them all in one line using the attr_accessor command in Ruby. These shortcuts can make the learning curve a little steeper, since there are more commands to learn, but this might be a trade-off worth taking. Io takes minimalism to the extreme, so you can learn the basics in a short amount of time. However, understanding how to turn the small bits into something bigger is another question entirely!

Besides having a more gradual syntactic learning curve, Io's lack of syntactic sugar enables it to have a very small virtual machine (about 9k semicolons). This means it can fit on small embedded systems, though I'm not sure how many production environments use it. I should also mention that, despite its small footprint, it is not known for being performant, given its message-passing structure and the fact that it is not compiled.

Io has helped me to understand and appreciate JavaScript better, instead of simply thinking of it as a more difficult to debug version of C++, but it made me pine for more readable languages like Ruby or VB.NET.

Links:
-The Io Language

Metaprogramming in Ruby

I've started learning some Ruby, one of the most popular object-oriented languages today. In OO programming, data and actions upon data are bundled together in objects that represent real-world things, such as cars, financial transactions, or database connections. Ruby is remarkable because it allows you to change object definitions on the fly due to 1) its open class structure (no methods are private) and 2) the fact that it is interpreted (not compiled beforehand). Since binding occurs at run-time, you can call any method on any object. If that method is not supported, it will call the method_missing method, which itself can be overridden to interesting effect.

Though Ruby does not support multiple inheritance, you can alter classes dynamically by extending them with modules. These modules are called mixins, since you can mix them in whenever you want. This allows for amazing flexibility and an advanced programming technique called metaprogramming, or the programming of programs by programs.

Metaprogramming sounds esoteric, but it is particularly useful when you're designing classes that need to have dynamic metadata. For example, Ruby's Active Record class implements Object Relation Mapping, creating wrappers for database objects. A table, view, or stored procedure can be accessed with standardized methods that can be automatically generated according to the database object to be instantiated once a database connection is established.

I put together some (unfinished) code that shows how this might work. The DBObject class includes the BuildDBObjects class, which extends the BuildIncludes class, which in turn mixes in the appropriate modules as dictated by the constructor. If you construct a table wrapper, only the BuildTable class is included. Each database type could use the same wrapper properties: metadata, data, and name.

module BuildDBObjects
    def self.included(base)
        base.extend BuildIncludes
    end
  
    module BuildIncludes
        def initialize(dbtype, name)
            case dbtype
                when "table"
                    include BuildTable
                    define_table(name)
                when "view"
                    include BuildView
                    define_view(name)
                    #...
            end
        end
    end

    module BuildTable
        def define_table(name)
            # query the database...
            @metadata = %w(SaleID ProductID DateSold)
            @data = %w(1101421 15981923 11/4/2006)
        end
    end

    module BuildView
        #...
    end

    attr_accessor :metadata, :data, :name
end

class DBObject
    include BuildDBObjects
end

tbl = DBObject.new("table","SalesOrders")
puts tbl.name
puts tbl.metadata
puts tbl.data

This is metaprogramming, since the code itself writes the class definition for each instantiation of the DBObject class. The great thing about using metaprogramming to implement object relation mapping is that your classes can change as your database schema changes. This cuts down on the amount of code you might have to write, depending on the way you're accessing data. (Of course, you should create a data access class that uses the ORM in order to decouple the database schema from the application code--otherwise your application code might break with the slightest changes to the database.)

Though this example isn't exactly esoteric, it's probably not something you're going to do every day. It also shows a downside to metaprogramming: you have to write code that is meant to be read by computers. That means it might not be particularly readable by humans. One of the many reasons people like Ruby is that it is very programmer-friendly. It's very easy to read while at the same time cutting down on a lot of "extra" code, like class accessors. Since metaprogramming is often less easy to read and understand, it's often more difficult to maintain.

A few links:
-Paolo Perrotta's book dedicated to metaprogramming Ruby, which contains an extended look at Active Record
-Ruby's core API
-Programming Ruby Pragmatic Programmer's Guide (2001)
-A good mixin tutorial