Custom Search

Friday, October 28, 2011

Leveraging Haskell's derived classes.

One of the mantras of dynamic languages is "Minimize boilerplate". By boilerplate they mean repeated code sequences that just change a few names. A typical example is the setter/getter methods of Java objects - at least most of  them. Python, for example, deals with those by providing a decorater that turns an attribute get or set into a method invocation. This eliminates the primary motivation for setter/getter boilerplate, since you can turn attribute accesses into methods without changing the external API.

I recently wrote enough boilerplate code for a Haskell application that I went searching for a way to eliminate it. Sure enough, I found one. It uses a technique that doesn't seem to be discussed on the web, even though it's so powerful that I eliminated all of the boilerplate that had driven me to this search.

A little Haskell data

This section explains some of the syntax of Haskell. If you're already familiar with that, you should probably skip down to the next section.

Haskell uses about the simplest construct possible for creating the equivalent of a record or structure (or maybe class) in other lanugages:

    data Name = Constructor [ Type ... ]

This creates the new data type Name with a constructor function named Constructor. Following that is a list of the type of each element that is going to be in Name.

A union type isn't much different, and explains why you need both a Constructor and Name in the data declaration:
    data Name = Constructor1 [ Type1 ... ] | Constructor2 [Type2 ... ] [| .... ]

Which says that an object of type Name will be either a Constructor1 object or a Constructor2 object or a Constructor from that last ..., each of which can be built by the appropriate constructor name.

The last bit of syntax is an optional
deriving clause at the end of a data statement. It lets you specify a list of typeclasses - from a relatively small set - and the compiler will automatically provide the boilerplate to make your new type implement the interfaces for those typeclasses. Besides the limit on which typeclasses this works for, all the components of your type have to implement the interfaces you want to use.

The problem data type

One of the Project Euler problems involves evaluating poker hands. So, given the appropriate definitions of Rank (the value of a card - Ace, Two, etc) and Card ( a Rank and a Suit), a data type that represents poker hands would be: 

    data Hand = HighCard [Card]
              | PairOf Rank [Card]
              | TwoPair Rank Rank [Card]
              | ThreeOfAKind Rank [Card]
              | Straight [Card]
              | Flush [Card]
              | FullHouse Rank Rank [Card]
              | FourOfAKind Rank [Card]
              | StraightFlush [Card]
                deriving (Show, Eq, Ord)

I'll get straight to the punchline: the above is sufficient for evaluating poker hands. The Ord typeclass provides the ordering functions <>, and similar as well as min and max. The automatically derived code will work such that hand1 > hand2 if and only if hand1 is a better poker hand than hand2. Provided, of course, that the code that creates the hands is correct.

The derived operators

The operators you get from Ord have straightforward behavior (though I couldn't seem to find an explanation of it outside the language specification). A list - which in haskell holds homogeneous types, but can be of different lengths - is compared elementwise from front to back. The first non-equal pair determines the result. If one list ends before that and before the other then it has a lesser value. If they end at the same time without any differences, they're equal. This is a pretty standard behavior for list comparison, implemented by most modern languages. Tuples (not used above) are a fixed-size list of heterogeneous types. The elements are also compared in order. If two tuples are of different lengths, comparing them is a compile time type error. Ditto if a pair of elements that need to be compared aren't comparable. Again, the derived behavior is pretty standard behavior for modern languages.

A record data type is, to a large degree, isomorphic to a tuple of the same list of types. The derived behavior follows that - the elements in the record are compared in the order they appear in the constructor. This is rather unusual. At least, I'm not aware of other languages that do this automatically, or advertise it if they do. Many modern ones don't really have a record type, but instead have a class type that mixes in other behaviors as well.

Finally, the union type. The comparison is simple: those that appear first in the data statement have lower values. The closest thing to this I've seen elsewhere are enum types. Oddly enough, if none of your constructors have an argument - meaning they're just a bare token - you have what amounts to an enum type, and that same ordering rule applies.

In action

So, we now know how the derived ordering behaves, and have a relatively complex data type to see how it works.

Given two hands to compare, the first check will be whether or not they use the same constructor. If so, those will be compared as such. If not, then the first one in the list is the lesser value. Checking the declaration, that means  a StraightFlush beats everything, FourOfAKind everything but a flush, etc. Exactly what we want.

If the two hands are the same type, then the elements of the hand are compared. That's why there's a Rank or two for some hands - you compare the cards that give the hand it's type before comparing high cards in the rest of the hand. So if those Ranks are correct - and in the right order for TwoPair and FullHouse - then the derived comparison will work correctly. As an aside, for some games you only need the first rank for a FullHouse and don't need the [Cards] for it, ThreeOfAKind and FourOfAKind, because two hands where those match are impossible. But providing them makes the code more symmetric and saves code in the long run.

Finally, if any Ranks present are the same, the [Card]s are compared. It's sufficient to make sure the [Card]s are sorted. While the cards in the Ranks aren't part of that comparison in poker, they will either wind up in the same place in the lists and be equal or the comparison will be done before their places are checked.

Conclusion

So, having written the data statement properly, and making sure that all Hands are properly formed, the derived code will do the right thing. All of the essentially boilerplate code to compare two Hands has been eliminated.  I can make sure that all Hands are properly formed by exporting a Hand-making function that does that, and not exporting any of the Hand constructors. This means the only way client code can get a Hand to compare is to use my Hand-making function, and anything else compared to a Hand will cause a compile time type error.

Wednesday, October 19, 2011

"More Power" is not always a good thing

In Succinctness is Power, Paul Graham ponders why Python — or any language — would choose readability over power. He isn't sure what is meant by regularity, and discusses several definitions of readability, but never gets to what I think is the core of the what Paul Prescod meant by his statement.

Readability isn't simply about the line or character counts that Paul talks about. It's about how quickly you can pick up code that someone else wrote, or that you wrote six months ago, understand it, and fix a bug or add a feature. Paul's discussion of programming features focuses on how easy it is to write code to do new things. If you're developing new code, that's what you want. On the other hand, if you're maintaining code, the hard part is usually figuring out what the original coder was up to, not making the required changes. In this latter case, readability is more important than power. In extreme cases, it's easier to rewrite the code from scratch than to figure out what it's doing. In fact, this is one of the rules Kernighan and Plauger's Elements of programming style: Don't fix bad code, rewrite it.

Readability also helps when the goal is to explain new things to other people. If you're planning on publishing the code to demonstrate or document a new algorithm of some kind, then readers need to be able to pick it up and understand it. A powerful feature that saves you 60 minutes of development time but costs thousands of readers a minute or two each to understand is a net loss.

Regularity is part of this. If a language is regular, then you can expect that if some language feature works for some type in the language, it'll work for all similar types; that all statements will be terminated in a similar manner; that function arguments will be evaluated in the same order everywhere; that — well, the list is potentially infinite. A language being regular improves readability by making it reasonable to infer the behavior of things you aren't familiar with based on the behavior of things you are familiar with, which saves you time when reading a program.

Paul argues that a language can't be too powerful, because the author can always write things out in the less powerful idiom if they don't like the more powerful one. The reader doesn't have that option. If the author is allowed to choose the more powerful option and does, then the reader has to read — and understand — the more powerful version.

Some people claim that a language is powerful if it has lots of features, so that whenever you need to do something, you have lots of ways to choose from for achieving the task at hand. This is in line with succinctness being power, in that if you get to choose between lots of ways to do something, you can chose the most succinct way. This form of power also leads to a less readable language. Some very popular languages have so many features that few, if any, people actually program in the entire langauge. Almost everybody programs in a private subset of that language — their dialect. So when you sit down to read a piece of code, you have to translate from the authors dialect to yours — which may require consulting the manual if it's sufficiently different from yours. In the worse case, you'll be reading code that was written by one person and then maintained by others, so you may well be switching between multiple dialects in reading a single piece of code — meaning that two apparently different bits of code may well provide identical functionality, but the dialect is different.

Examples

Let's look at some language features to see how power and readability trade off. We're going to look at one area of language design: passing arguments to a function. Functions are one of the most powerful features of modern languages. They allow code to be reused in multiple places. The arguments to the function allow the same code to be used with different data. Functions also improve readability. Once you read and understand a function, you don't have to do it again. If the author failed to use functions, but simply repeated the code each time, you'd have to read the code to verify that it's actually the same in each case. So functions are pretty clearly good for everyone involved. In particular, we're going to look at one task: figuring out how a variable in our source code gets the wrong value.

Let's start with the least powerful version of arguments, and one found in many modern languages. The language simply evaluates each argument, and passes the resulting value to the function. The function can't change the value of any variables named in the arguments. This is a very readable construct, as if you're trying to figure out what happened to a variable, you can ignore the function calls, because you know they didn't change the variable.

Now let's add a feature: let's let a function be able to change the value of a variable passed to it. This provides a more succinct way of using a function that changes the value of a variable. You can simply write:

def inc m
    m = m + 1

x = 3
inc x
inc x
inc x
print x

And it would print 6. If inc can't change the valaue of it's argument, then the equivalent code would have to be written something like so:

def inc m
   return m + 1

x = 3
x = inc x
x = inc x
x = inc x
print x

Each of the lines that comprise the function has twice as many symbols. More complex examples, involving changing more than one variable and possibly having a return value from the function as well, are much worse. So this new feature make the language more succinct, and hence more powerful.

From the readability standpoint, this is a disaster. Now you have to read every function that the variable you're interested in is passed to, because they may well change it. The amount of code you've got to examine has gone up by an indeterminate amount.

So if your language prefers readability to power, you'd want to give some serious thought to whether or not you want to add this feature to your language. If you do so, you will probably eventually realize that the problem is that there's nothing at the point the function is called to note that the variable could be changed. If you do things that way, then you only need to read functions that are passed variables flagged as changeable at the call point. The language has the same number of features as before, is only slightly less succinct, requiring one more symbol than the original version.

Now that we can change a variable passed to a function, let's look at the case where the variable of interest is passed to multiple function that are allowed to change it, and the values returned by those functions are passed to a function. That isn't inherently harder to read, until you ask the question What order are the arguments evaluated? If the language specifies an evaluation order, then you can read the functions that might change your variable in that order, and ignore the function those functions return values are passed to, unless it has your variable as an argument. If the language doesn't specify the order of evaluation, then you have to consider each possible calling order. But let's make our language really powerful! Let's let the called function decide not only what order the arguments are evaluated in, but allow it to evaluate them multiple times, including not at all if it decides that's appropriate. Lisp macros have this ability, and it's part of what makes Lisp programmers hate programming in languages without them. The invocation syntax is the same as functions, so for the purpose of reading code that uses them, they are the same as functions.

From a readability standpoint, this is a disaster of the same order as letting functions change the values of variables passed to them. It's not quite as bad, because it only affects functions which are called as part of evaluating arguments to other functions, which may or may not be all that common. But every time you examine such a case, you have to read through the outer function to figure out whether or not the function call you're actually interested in is evaluated. Worse yet, the answer may be maybe, as it will depend on the value of some variable in this new function. So now you're starting over with a different function and variable.

Conclusion

While these last examples are exaggerated, and real-world LISP programs are generally better written than that, the point is not to say that these features are bad, but to explain how more powerfull is not the same thing as more readable, and provide some motivation for preferring the latter to the former. I don't expect to change anyones mind about what programming features — and hence languages — they prefer. I hope I've helped someone understand why other people might prefer readability — and a language that values it.

Thursday, October 6, 2011

Satisfaction

I was listening to a podcast review of the game Dark Souls, and the reviewer gave it a near-perfect score of 9.5 out of 10. He believes that it will be a contender for one or more Game of the Year awards. What was interesting was that he didn't think the game was fun. Instead, it was frustratingrewarding and satisfying. The problems the game presented were frustrating, but so well done that when he finally solved them, he felt satisfaction at a job well done and properly rewarded for his efforts.

What's funny is that I knew exactly what he was talking about. I stumbled on Project Euler a week or so ago, and have been working the problems there. Yeah, they're frustrating. But the ones that are the most frustrating are also the most satisfying when solved. That's only part of the reward of solving them, as you usually learn something interesting along the way (but don't tell the kids!). Anyone who took any of Dr. Andree's computing classes at the University of Oklahoma will recognize the feel of the problems there - he would have loved this site. The real puzzle is how I managed to fail to find it before now.

Until hearing that podcast, I never would have thought of Project Euler as a game. But it has badges, awards and trophies like many modern games. It also provides the same sort of satisfaction as a game expected to contend for a game of the year, so I'd have to say it is a game.

If you're interested in logic and math puzzles, especially those which a computer can help with, it's definitely worth a look. I feel that the proper tools are a programming language that supports infinite lists (aka streams) and has a REPL to use as a calculator. I'm using Haskell, switching to Python if I want a mutable array.