Saturday, March 24, 2007

OpenGL Tetris in Haskell

Over the past couple weekends I've tried putting my new language interest, Haskell, through the paces by witting a version of Tetris with HOpenGL bindings. Herein is an overview of my progress, and a call for help from the more experienced in the Haskell community to show me and other newbies how this can be improved and why.

The Good
As noted, um, everywhere, Haskell is a really deep language. As a beginner, the features that have struck me are the ease of defining functions, pattern matching in definitions, currying, and the seemingly endless stream of higher order functions.

Making function definitions as easy as variable assignments in other languages encourages me to break apart logic and leads to cleaner code. Defining functions in the `where` clause I've found to be especially handy and elegant. Unlike imperative programming, where code with very similar functionality can hide in a jungle of statements, repeating code in Haskell is easy to pick out and convenient to factor out.

Pattern matching in function definitions has been incredibly handy. In Perl, I'll often use a hash to map things like tetris shapes to their set of points. Haskell's version is more useful because I can define a function which takes a shape and returns a set of points associated with it. The difference is I can pass this function around or use it in higher order functions without using extra syntax to do the lookup.

Currying without any extra syntax is a big contributer to Haskell's clarity. Now that I've experienced it's usefulness, I don't think I could go back to languages like Scheme without constantly complaining about its absence.

Besides the standard `fold` and `map`, I find myself thinking "Wow, that will be usefull" whenever I look through Haskell's standard libraries. Functions like `zipWith` or `unionsWith` make even the most useful Java classes look barbaric.

The Bad
When I first started writing Haskell, the thing I found most annoying was the big change in associativity. The downside of functions being treated exactly like data is that it becomes impossible for the compiler to correctly predict how you want things grouped. It didn't take long to become accustomed to Haskell's rules, but for whatever reason learning to use $ and . correctly took a bit time.

Monads obviously need to be included in this list, but I found understanding the simple monads such as IO, Maybe, and Either simple enough to quickly make progress. I have not implemented my own, and I suspect my Tetris code could be significantly improved with better understanding, so I'll be digging into this area again soon.

Typing has not been a problem for me. Haskell's typing inference system works great, and the times I've run into typing errors have been either an error in my code (most frequently), or, in my belief, a bad framework for what I was trying to accomplish.

The Ugly
I've basically run into the same problem with libraries and setup documented by Eric. Documentation of libraries could also use a lot of improvement. Here's an example of documentation for a function in some introspective code that I was trying to understand:
mkConstr :: DataType -> String -> [String] -> Fixity -> Constr
Constructs a constructor
Not very helpful.

What About Tetris?
First off, I don't think that Tetris and OpenGL map onto Haskell very easily. OpenGL in particular is very stateful, and even setting up a simple animation requires using Monads to work around Haskell's lack of side effects. I think this excersize is still useful, though, because in pushing a language to it's boundaries and forcing you to use it's less hyped features, you can often getter a better understanding of it's strengths and limitations. Before starting this project, I read over Michi's posts. In fact, his cube generation code is largely unchanged in mine.

What I'd like to see happen is for the amazingly helpful Haskell community (seriously, check out #haskell some time, it is the nicest, most helpful channel I've visited) to take my crappy code, explain why it sucks, and show me and other timid beginners how to do better. Just add a comment to where people should look for improved versions.

My code is available at PBWiki.

Tetris.hs
This is the code that kicks off the OpenGL loop. Callback functions are used to display objects, coordinate movements, and set state. You can see by the number of newIORef calls how much state is being passed around to each callback. The most confusing line here is probably the assignment to curMatrix. curMatrix keeps track of the matrix transformations that occur when the mouse is moved so you can use a "glass ball" type interface to rotate the tetris board around.

Display.hs
This file contains the display call backs that render the pieces and board. To implement the mouse interface, the display matrix is reset with loadIdentity. The new translations from the most recent mouse movement are applied, then the previous matrix is applied.

dropPiece drops the current piece, or sets the fallen piece and starts a new one.

idle is a callback that is continually called and it simply asks OpenGL to redisplay the screen in it's next loop. This is the alternative to calling postRedisplay after all movement changes.

TetrisPiece.hs
This file contains the code that keeps the coordinates for shapes and instructions on how to render them. translatedPoints is a function which can take the default coordinates of a shape and apply the transformations that the displayed shape receives so that collision detection can be done.

TetrisBoard.hs
Setup for the shape of the board and the boundary initialization are done here. tableMap is basically an array of all the (x,y) coordinates with False inside the boundaries (because there are no fallen pieces yet), and True along the boarders.

clearLines takes a board and clears any full lines; basically, the purpose of Tetris. Using foldl, it iterates over a list of lines given by their 'y' coordinate. For a given line, if that line is at or above 'y', it takes the contents of the line above it. The base cases are the boarders of the board, which should keep their boundaries.

Sorry for the mixed naming, by the way. 'board', 'b', 'tableMap', 'boarder' are all generally the same thing: the mapping of the contents of the Tetris board, ie the fallen pieces.

Bindings.hs
keyboardAct defines how a key press can move a shape on the board, while movePiece determines if this movement is valid.

Translations.hs
These functions are used to calculate translated points for collision detection and the "tetris unit" is defined here. Using `tunit` not only helps to keep things in correct proportion, but it also helps Haskell's typing inference when used as a unit.

Thursday, March 15, 2007

Lessons from Ops

I am a programmer who enjoys working "only slightly removed from pure thought-stuff." But when I left college I chose a job that was decidedly oriented toward beating this thought-stuff into the ground of reality. I wanted to learn the details of how to program large-scale, heterogeneous systems that were possible, if not easy, to maintain. Not "maintain" in the programmer sense of the word (ease of adding new features, finding bugs, etc.), but maintain as in enabling users to understand, control, build upon, and rely on the system.

Oh, That's Typical
I'm going to stay away from the common recommendations such as DRY because I'd like give specific pointers that apply to the situations I've seen. The hope is when I write programs in the future, the tips herein will pop back into my mind and I'll produce systems that are easy to debug, understandable by people uninvolved in the development, and predictable.

Doesn't Play with Others
A data problem was reported to our team the other day. Typically, finding the source problem requires a large amount of domain knowledge: where are the files that configure the various transformations that this data goes through? Who typically publishes this data type? Where are the logs that may have information about this document? The path to resolution is like a little known covered wagon trail through the Sierras: you need an expert guide and most of the time you get stuck at Donner pass. What should be provided is a yellow brick road: it may require a little work to get there, but you know where you need to take your next step.

Introspective vs. Transparent
At it's root, debugging is about figuring out what happened and why. To provide an easily debuggable system, simply provide the what and why at every step that business rules are applied. Just as importantly, provide it as a service in the same way that interested parties normally interact with your system. Adding `printf`s to your code is great for programmers who usually interact with a service on the command line or `tail` files, but it is nearly useless for clients.


The Boudin bakery in San Francisco is transparent, literally. You can see them mix the dough, cut bread, and bake it. But that doesn't let me understand any of the decisions they've made; I couldn't go home a bake delicious sour dough in which to put clam chowder. In order to do that, I'd need to interact with the cooks in the normal way: ask questions, have them explain what's going on.

Except for the most basic services, data transparency is not that helpful. Think about the questions you'll get from users. When did this data change? Who changed it? Where did it come from and how did it get transformed? How would the system react in different situations? These are the questions that need to be answerable in a straightforward manner.

If you're worried about performance, or exposing too much information to customers, keep in mind that introspection is a system property. It doesn't have to live in your main service, especially when lots of historical data is desired. It would be nice, since people don't have to learn a system with more components, but it's not a requirement. Unique identifiers (database keys, document IDs, URLs) should be usable across the system so a story can be put together programmatically. A coworker of mine suggested that the public password for a system we are developing should be the URL of a wiki page they should read before using the service. I love this idea because it eliminates an often fruitless search for information and directly ties the wiki service into the overall design. Think how useful it would be to have wiki links for each error your service produces along with the ID of the data that was involved in the problem.

You From Around Here?
Even programs with great documentation can't cover all of the potential questions from a new user. Often users can't express their issue in the jargon that would enable them to find and understand the solution. Providing a way to "show and tell" what's going on gives users a chance to understand from experience. Just as languages with an interactive shell and introspection let users get an intuitive feel, systems should provide users with meta-information that they can manipulate.

To Be Continued
This turned out longer than expected, so I'll continue in a later post. Leave comments so I can improve my writing and ideas.

Wednesday, March 14, 2007

Medium Work Route with Shortcut

This bike route to work takes me through Arastradero Open Space Reserve. This year I have only ridden the route with the Alpine shortcut. The ride takes about an hour at a strong pace. Two quick but steep climbs make the ride good for training even given its short length.


Since last year, they've repaved many of my common routes. Especially improved is the Ellen Fletcher bike boulevard that I take home from work. All last year I had to worry about flat tires, hidden potholes, and a generally jarring ride on a road supposedly designed for bikers.

With the weather getting up to the 80s, my whole house now a fan of cycling, and increasing time pressure to get ready for the AIDS ride, I hope to get out a lot more in the coming weeks.

Tuesday, March 6, 2007

Cycling the Saratoga Loop

J and I decided to bike out to Saratoga, he to get to I's house, and me to burn off some of the cookies I'd had at my folks' place over the weekend. We started off a moderate pace, and J, champion that he is, requested we kick it up a notch. Soon we were at the top of our first hill overlooking the Steven's Creek Reservoir. Here's the map on Google Maps.

The climb up to the Reservoir is about 250 feet, and the view is pretty nice up there. I've been meaning to have a picnic by the river in the valley; it's very lush and peaceful. Next was Mt. Eden, a tough hill for anyone, especially a beginning cyclist. In fact, it was about 1 year and 1 month ago that I had climbed this hill as a newbie and was so tired afterward that S came to pick me up from Saratoga. It's also about 300 feet, but squeezed into a single mile. But it too was conquered, and we wound our way down the hill and made it to I's house in about 1 hour. There I made my questionable decision to take a different route back.

With J dropped off, I decided I wanted to take a loop back. An additional draw was the fact that I hadn't taken the Hwy 9 to Hwy 35 route before, but I knew it had great views of San Jose and wound through the forest most of the way. The climb up 9 turns out to be just over 2000 feet. Who knew? Well, I do now, and it was pretty painful. It's good to know that I haven't lost too much cycling power over my break, but I think it would have been healthier for me to work up to rides like this.