Tuesday, November 27, 2007

Elegant Haskell

I'm going to post some pieces of my game so that you can see just how clean and simple and easy to understand haskell code can be. I've modified this code somewhat so that all it really does is initialize the world, create an area, count ten turns and then exit.
data World = World {
turn :: Integer,
player :: Player,
area :: Area
} deriving (Show)
This is the structure of the game, holding all necessary data to progress in the game. Deriving show is an easy way to allow any arbitrary structure to be turned into a string provided each of its members is already capable of being shown. I made Area and Player types showable myself.
main = do
gameMap <- genArea 20 20
let w = World 0 initPlayer gameMap
gameLoop w
This is the initial entry point of the program. First it generates an area of 20x20 squares using a method we won't be discussing at the moment. Then it initializes a world state. Essentially it says the value of w is equivalent to the constructor of type World where each field is equal to in, order, 0, the player init function, and the map we generated. Finally, it passes the world into the gameloop.

You might be wondering why I didn't simply pass genArea into the World constructor the way I did for initPlayer. The reason is because area generation uses random variables and randomness is outside of the system. Therefore we have to use some special syntax to execute the process that will generate a map object. Player at the moment simply sets all the player stats to initial values. Eventually when it requires actual player input (as well as randomness), it will also use the same syntax to generate the player.

It may seem odd, but there are serious advantages to this obtuseness that I will get into later.
gameLoop :: World -> IO ()
gameLoop w = do
putStrLn $ ("Turn: " ++ show (turn w))
let w' = incTurn w
unless (gameEnd w') (gameLoop w')
This will require more instruction. The dollar sign means to call putStrLn and pass the rest of the line into it. The rest of the line says to concatenate "Turn: " and the string representation of the turn field of the World variable w. The show function simply turns anything into a string.

The next line increments the turns in the game by passing the whole world into incTurn and then taking the result. The result w' is just w with turns incremented by one. Then it passes the modified world into gameEnd to see if the game is finished and if not, calls gameLoop again with the new modified world.

First thing to note is the fact that this function is recursive. Due to the miracle of tail recursion, this recursion uses no extra memory. It can recurse indefinitely without using any resources at all.

The next thing to notice is that I did not try to increment turns in place with the let and then continue to use w. Instead I made a duplicate of w only with the turns increased.

"But OnMach, " you point out, "doesn't that mean you duplicated the variable and now are using twice the memory?" The answer is no. You can be sure that this is completely optimal. It won't actually calculate w' until it is needed, when it does it will end up with only what is needed because the language is lazy. Also, though my own knowledge is lacking in this department, I believe that due to the way this language is structured the compiler can see quite plainly what I need and when I'll need it. That is one of the major advantages of haskell. The compiler can make a huge number of optimizations on your code without you having to specify anything at all.
gameEnd :: World -> Bool
gameEnd w = turn w > 10

incTurn :: World -> World
incTurn (World t p a) = World (succ t) p a
GameEnd simply checks to see if ten turns have passed and returns true if so.

IncTurn takes a World structure and returns a World structure with the turns incremented by one. The succ function is defined on all enumerated types and simply returns the successor. So (succ 3) == 3+1.

That's all there is to it. At this point you are probably thinking it looks like a less readable version of python. But there are some important things about this code that aren't immediately obvious. I called initPlayer and genArea up above, but in reality those functions are never calculated. The reason is because I never actually used the player or area. Haskell doesn't calculate what it doesn't need to.

Another issue that needs to be mentioned is why in certain places I use a do notation and others I didn't. Do notation is used to string monads together. The reason I use them above is because in each case I either needed to deal with input/output (putStrLn) or I had to deal with return values that would not be the same on each call (genArea) in this case due to randomness.

A function that is guaranteed to give the same answer with the same arguments is called a pure function. Because it always gives the same answer, it can be hugely optimized. If you need to call a function with the same arguments twice, the second time it will simply return the answer instead of calculating it all over again. This leads to huge savings in places you'd never be able to hand optimize. And it requires no extra syntax, breaking out of loops, etc to achieve that.

One more thing. Notice how I passed in w to endGame as a single variable, but when I passed the same variable into incTurn, I was able to deconstruct it into its constituent parts and manipulate them separately. This is an enormously powerful feature of haskell. You can deconstruct any type into its constituent pieces (assuming you have access to them) and manipulate them at will. This goes way beyond how I've used them here, but I'll leave it at that for now.

I think this is an ok first impression from someone who is himself just getting a handle on the sheer power of the language himself.

Current Fixation: Haskell

I tend to jump from pet project to pet project. My last project was to develop a roguelike with a completely different playing style. Also, all the code in all the major open source roguelikes is spaghetti. Some of it is so bad I'm amazed it works at all. I wanted to see if I could do better.

I started writing it in C because there is a possibility I would open source something like that and C tends to get more contributions. The problem is that as I wrote, and as my code grew, despite all my efforts to the contrary it became progressively messier. It also became increasingly harder to modify something in the base behavior without having to rewrite things that interact with it.

I also saw that it was going to get worse as time progressed. At first I was just trying to place rooms randomly and then passages between those rooms in realistic fashion. Soon it would be monsters attempting to find paths to flee and chase and plan out how to attack. It was either going to be completely unmanageable or I'd have to make huge sacrifices as to what features I wanted in this game.

I eventually stopped coding and started looking for a solution. That lead to my current fixation: Haskell.

I call it a fixation, but in truth I'm really, really impressed by it. So impressed that I will probably be using haskell until some better language comes along, if that is even possible. By the way, this is from someone who absolutely loathed lisp.

Haskell is a functional language, like lisp. I never really got to the point where I understood the benefits of functional programming because lisp has so many other warts that it is impossible to see past them. Don't even get me started on it, but as far as I'm concerned lisp is the reason functional programming died young.

Haskell is a language I've attempted off and on for some time now. The process was similar to my adoption of Linux. I used it, couldn't do what I wanted and waited six months to try it again. On about the fourth attempt I finally see the light. It helps that ghc (haskell's main compiler) is becoming more advanced and good documentation is finally proliferating.

Haskell is a pure functional language, and that lends a whole lot of advantages to it. It can perform concurrency and parallelism effortlessly and efficiently. You can often look at a function prototype and guess what it does. Its type system is very strict, but I'm seeing the advantages already, and I've only been using it for a month total. Entire classes of bugs are nonexistent. I just can't cause them. Most are eliminated before the program compiles due to the type system. All the code is clean. Unlike lisp I can look at something I did weeks ago and tell exactly what it does. I can also read other peoples' code. It is also very compact. About 1000 lines of C code generally compile down to 100 of haskell.

Bereft of an interesting project to take on, I started rewriting my roguelike in haskell. I haven't gotten that far just yet, mostly just area generation. But I did it in a comparable time frame and the resulting code is so easy to understand and intuitive. Also my preliminary results say it is very fast.

Some people who have attempted haskell claim it is too hard. I would have been one of those people six months ago. The problem is not haskell but rather the people who designed the language. As researchers and academics, they tend to think mathematical explanations are all that is needed. Unfortunately for people like me who are practical and imperative minded this is not sufficient. You just don't need to understand the math. There is good documentation out there, but it is hard to find amongst piles academic research papers. Also one of the main concepts "Monads" seems extremely hard to grasp when you first come across it. In truth monads are very simple, but finding the good documentation on them was a real bastard.

If you are really having trouble with monads like I was, I would like to suggest the first part of this research paper which is more like a tutorial called "Tackling the Awkward Squad" link

I think I'll devote a few future posts to examples from whatever code I'm working on. It is something you have to see to understand. I believe people should give this language some serious consideration.

Wednesday, November 21, 2007

The Theory of Comedy

I like to read books on psychology. People fascinate me. They are like the ultimate puzzle.

While most behavior is explainable, one aspect of personality that has always bugged me is laughter. Every other behavior seems to have an underlying purpose. But why laugh? Why make jokes? There seems to be no practical use. Meanwhile people are basing their choices of friends and lovers on it, so there must be something to it.

I've read books on comedy that tried to explain what funny is, such as "Comedy Writing Secrets" by Melvin Helitzer. I've also read a few accounts by comedians who try to explain why the jokes they tell are funny. None of these have completely explained the phenomenon to my satisfaction and so I have developed my own theories.

Describing how to write a joke is a lot like describing how to walk. "Well you just put one foot in front of the other." But it isn't that simple. There is a lot of wiring underneath that we simply don't understand. What makes one punchline funnier than another? What about timing and execution? Most people learn through trial and error and emulation.

So, let's break it down. Laughter can be broken divided into two categories.

Laughter derived from status

When someone wants to impress someone else, they will laugh at their jokes as a form of flattery. Even if the jokes are horrible. If you stand back and listen to people talk you will often notice women are laughing at the stupidest jokes men tell. This aspect of comedy plainly obvious to anyone with ears. Sometimes this is known as the Dane Cook Effect. Conan O'Brien describes it as courtesy laughter.

This is also the origin of the much despised laugh track. They have done studies where they found that people laughed more when there was a studio audience to laugh along with. The studio heads naturally believe that adding in a laugh track is a cheap way to make their shows funnier and it is typically forced onto content creators.

Unfortunately, any laughter derived from this effect is not real and doesn't generate enjoyment or increase status. Based on conversations I've had with others, I think I'm not alone in thinking this. If you don't think a gag is funny, no amount of forced laughter is going to make you enjoy it more.

In other words the problem with exploiting this property is that in order to make people laugh in the first place you have to acquire status to get the ball rolling. If you were attempting to tell jokes to obtain status in the first place, and the jokes were bad, you are in trouble. People can only handle so many so-so jokes before they will tune you out. On the other hand, telling good jokes often enough will raise your status so that when you finally do bomb a joke, you will get a courtesy laugh instead of cricket noises.

I don't think anyone is going to argue with this so far. Real laughter is derived from this second idea which I've never seen written in any book.

Laughter derived from the unexpected

More specifically: laughter derived from the unexpected, but from what should have been obvious. Actually it isn't quite that simple.

Imagine you are five years old and you are watching the Three Stooges. Moe has a pie in his hand and Curly says something stupid. At this point, we all know what is about to happen. But a five year old doesn't. He might not have seen it before, or at least, not often. When the pie hits Curly in the face, to the five year old, that was completely unexpected, but at the same time in his mind he realizes he should have seen it coming. That is, the scenario was laid out such that there was only one logical conclusion, the conclusion of which escaped the mind of the child until the event occured.

That triggers a laugh. For the kid, anyhow.

But I didn't laugh. I saw it coming a mile away. My brain had already processed the scenario and come to a conclusion. The only way to make me laugh now is to extend the situation by having Curly retaliate in a particularly creative fashion. The only way I will laugh is if something is about to follow that should be expected, but that I haven't yet grasped.

Maybe this isn't clear. Let me use another example. Perry Bible Fellowship is one of my favorite web comics. It is usually very funny, but it is often hit or miss.

What is the difference between these two jokes?

Both follow the same format but one is kind of lame and the other is hilarious.

In the first comic, you see the janitor is going to write something on the chalkboard. In your mind you narrow it down. He's either going to answer the problem (not funny) or write something lewd (expected). You ran it through your head and those possibilities are what you came up with. In the last frame you were let down when you found you had guessed correctly.

In the second, a scenario is set up where there are corpses everywhere and there also seems to be some sort of relationship, the nature of which you can only suspect. Examining the environment, her reaction, and the dumpiness of the bald guy, your brain goes into overdrive to figure out how they are related. It is fruitless, there are too many possibilities, none of which seem likely. When the final frame hits, you realize how it all fits together. The joke has beat you to a seemingly obvious conclusion. So you laugh.

There are two ways this comic could have fallen flat. You could have guessed what was going to happen before you read it. That is a killer. The other alternative is that the punchline didn't follow from the setup. In that case your brain would continue searching for some connection and not finding one you would close the comic in disgust. I should also mention a third potential for failure is if the content is morally objectionable to the reader, they will steel themself against laughter. This is a special case I won't dwell on.

So to summarize. A joke needs to set up a problem and reach a seemingly obvious conclusion before you can. Then it is funny. If you reach it first, it isn't funny. If you can't figure out how the punchline relates to the setup, it isn't funny. Simple.

Now you may have already started mumbling exceptions to this rule. For example deadpan humor. Mitch Hedberg:
"I order the club sandwich all the time, but I'm not even a member, man. I don't know how I get away with it."
Funny, but not so funny it'd pay the bills.

For a stand up comic, setting up a joke is more than just speaking words. Any comic knows you need a persona. In Hedberg's case, he is a stoner. Stoners in and of themselves aren't funny. What makes it funny is that he is making observations from a stoner perspective that seem fitting, once he makes you think about it. The persona ends up being half the puzzle. Putting the persona together with a joke is sort of like putting the first couple of frames together in a comic. It is part of the setup.

What's the point?

With the anatomy of laughter in hand the purpose of humor starts to become clear. If I'm correct, laughter is a human instinct used to measure intelligence.

To the joke teller, a successful joke shows that you are capable of complex thinking. You created a clever logic puzzle for others to solve.

On the recipient side, laughing at the appropriate time lets others in the group know that you are intelligent enough to understand the logic behind the joke. Anyone who is incapable of laughing at the right time will quickly become an outcast. Knowing a good joke from a bad one is not fakeable. You only have an instant to decide.

That is my theory. Maybe you agree with it, and maybe you don't but in my mind this is an open and shut case. Good day and beware people with no sense of humor.

Thursday, November 8, 2007

Starting is always the hardest part

I'm a full time programmer by day, but at night I tend to tinker. Unfortunately I have few outlets for my more outlandish pursuits and I feel that I'm missing something.

While I tend to do a lot of small personal projects, I never release them and rarely talk about them with others. My peers, while good people and good at what they do, have historically not been very interested in whatever tangent I've gone off on on any particular week.

Also, a lot of my best ideas come to me when I am not programming. Sometimes I'll suddenly hit upon an answer to a problem in the middle of the night and there is no choice but to get dressed and run to the computer. I'm curious to see if writing will have a similar effect.

Hopefully this won't turn out to be more work than I'm willing to do.

So this blog will be mostly about programming, economics, and business related stories. I'll try to keep the politics to a minimum, I promise.