The Price of Free

Prelude

I’ve had free software on my mind quite a bit lately. This is likely due in part to the recent RMS interview on the Linux Action Show, reading The Cathedral & The Bazaar, and my recent purchase of a ZaReason laptop, which is the first time I’ve made such a major hardware purchase with Linux support as the top priority.

Before any of my thoughts here make sense, it’s important to emphasize how I view and approach software. Computers are first and foremost a tool, but to the vast majority of the world, that’s all they are. There is by and large no appreciation for the complexity (and dare I say, art) of computer software beyond “I love how the little elves inside my Mac make it possible to watch cat videos.” On the contrary, people who actually know a little bit about how computers work are classified as nerds. You’re not supposed to care, since Apple and Microsoft will take care of all that hard stuff for you if you just hand them a little bit of money.

I firmly believe that capitalism is both the best and the worst thing to happen to software. I say best because without the funding provided to groups at Bell Labs and MIT, software as we know it would likely not exist. In the span of a generation, we’ve gone from simple number crunching with computers the size of a room to having, quite literally, the entire knowledge base of mankind in the palm of our hand.

But this comes at a cost in the form of demand. The usefulness of computers cannot be overstated, and neither can their demand. Because demand is so high and the number of people who know enough to fulfill that demand is so low, Apple and Microsoft (among others) can charge users much more than they would otherwise be able to. In dollars, how much is an operating system worth? $200? $1,000? $5?! Nobody knows. This excess demand is seen most sharply on the internet, where good programming and security practices are often eschewed in favor of getting it done now. Everyone and their mother wants a website or an app; entrepreneurs are coming up with grandiose ideas for the next great product, but just need someone to “code it up for them.” The appreciation for the process of software development is almost completely overshadowed by the rabid desire for what it produces.

This isn’t to say that everyone should drop what they’re doing and go learn to program; I do want some job security, and specialization is what made society what it is today; but given the prevalence of computers in our day-to-day lives, I do believe it’s important to have a more fundamental understanding of how they work. It should not be socially acceptable to proudly admit knowing nothing about computers while those who do know something about computers are, quite often, ridiculed for that knowledge.

On Users of Free Software

The existence of free and open-source software like Linux is a modern miracle that goes largely unnoticed. We live in a capitalist-driven society, yet for the past few decades, people have been contributing source code for free to improve the quality of many different software projects. Why? Because we love software. Somewhere out there in this capitalist, algorithm-illiterate world, there are enough people who are not only smart enough to write software, but are passionate enough about it to spend their free time doing it. Linux is a labor of love, as is almost every other free software project in existence. We want software to get better, but more important than that, we want it to be more than just a tool. We want it to be our tool.

I want more people to use Linux, because an increased user base would help prove its validity as a day-to-day operating system. More users = more testers = more bugs reported = more bugs fixed. But, due to the lack of large numbers of paid developers (Red Hat and GNOME are examples of paid free software developers, but their size pales in comparison to Apple and Microsoft), there is a price to be paid for using free software: to get the most out of free software, you must participate in it. Linux is not a tool to be consumed in the same way as Mac and Windows. If something goes wrong, you must put in some effort to fix it, either by searching Google for people who’ve had a similar problem, filing a formal bug report, or attempting to implement a fix yourself, but there is no company standing by to take your complaints.

There is nothing in the free software world that I hate more than non-constructive criticism, since the whole point of free software is to spread ideas and introduce new ones, not to tear down someone else’s. It is quite literally impossible to please everyone, so there’s no point in even trying to. This means that those of us who use free software will, ultimately, run into something that we don’t like. And that’s okay, because we have every right to change it, either through a patch or a new extension; in fact, given how short-handed the developers of that software likely are, we’re almost obligated to. This doesn’t mean that you have to be a programmer in order to use free software (it is free, after all), but it does mean that you should put in a little effort to become part of the community if you’re going to criticize the software for an outstanding bug or strange design decision. Quite often it’s enough to share your experience, either through a bug report or as a feature suggestion, where someone can see it and create a solution.

Joining a free software community is, however, easier said than done. The first step is to locate the project’s official communication channels. As an openSUSE user, this would be the forums, IRC, and mailing lists. Once you begin to run into specific issues that you want to solve, you’ll want to find out where to submit bugs and suggest features. Taking a glance through the project’s home page, we can find the wiki and even a social network. Other, smaller projects likely won’t have quite as many different places to communicate, but almost all of them will have a mailing list and a place to report bugs.

Bottom line: if you use Linux or other free software and you’ve run into an issue ranging anywhere from severe bug to minor annoyance, talk to someone about it. Someone who can help. That’s what free software is about, and we as a community want nothing more than to see the user base grow and the software improve. Post on the forums. Lurk in an IRC channel. Because without community support, you will eventually run into something you don’t like, get frustrated, and wonder why you didn’t just stick with Windows. And that’s the price of free software.

Haskell Code Jam

Google Code Jam is coming up soon, so it’s time to practice. This post will cover two practice problems, with full solutions provided at the end of each one. Clicking on the title will open up the corresponding page for that problem.

At the end, I provide a re-usable module incorporating many of the techniques that will be discussed.

Reverse Words

Let’s start off easy. The goal of this problem is simply to take a string and reverse the order of its words. Input looks like this:

3
this is a test
foobar
all your base

And output should look like this:

Case #1: test a is this
Case #2: foobar
Case #3: base your all

Alright, so first we need to figure out how to read the input. Since we’re reading from standard input, it’s fairly easy:

main :: IO ()
main = do
    input <- fmap lines getContents

Now we have the required input as a list of strings. The head of the list will be the number of cases (in this case, 3), followed by one line for each case. Since we know in advance that each case only needs one line and we have all the lines stored in a list, it’s not really necessary to read in the number of cases. The input we’re really interested in is everything else:

-- inside main
let input' = tail input

Here’s our first big stumbling block. We have the input in a list, but how do we loop through it in a way that lets us print out the case number with it? Haskell is stateless, so a standard for loop won’t work.

There are probably other ways to do this, but my solution is to create some new data types:

data Unsolved = Unsolved { unsolvedNumber :: Int, input :: String }
data Solved = Solved { solvedNumber :: Int, answer :: String }

Notice that there are two separate types, one for unsolved cases and one for solved cases. We’ll see why in a minute, but the important thing is that this gives us the ability to tie a case number to its input. We can use zipWith to turn a list of strings (the input) into a list of unsolved cases:

-- inside main
let cases = zipWith Unsolved [1..] input'

This makes solving the problem very straightforward: we want to take a list of Unsolved cases and turn it into a list of Solved cases, then print them out. In order to print, Solved needs to be a part of Show:

instance Show Solved where
    show (Solved n ans) = "Case #" ++ (show n) ++ ": " ++ ans

There’s one last thing to take care of before we can start implementing the solution. The method that will actually solve the problem for us should take an unsolved case and return a solved one, so we want to map that over our list of cases and print out each result:

-- inside main
mapM_ putStrLn $ map (show.solve) cases

This takes our list of unsolved cases and maps (show.solve) over it, a composite function which solves the case and returns its string representation. The result of that is our list of output lines, which we then print to the screen.

Okay, now let’s get down to the solution. The structure of solve will look like this:

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = ...

But how do we get the answer? Well, what we want to do is take a string, break it into its separate words, reverse them, and put them back together. Fortunately, Haskell provides built-in methods that will do these, so getting the answer is as simple as composing them together and feeding it the input:

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = (unwords.reverse.words) input

The full solution can be found here.

Store Credit

This problem is a little trickier. The goal is, given a store credit and list of available items, which two items can you buy to use up all of the credit? In other words, which two numbers in the list of item prices will add up to the value of the store credit?

Our sample input:

3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3

and the desired output:

Case #1: 2 3
Case #2: 1 4
Case #3: 4 5

These require a little explanation, which can be found on the problem’s page. To summarize, each case consists of three lines: the store credit, number of available items, and a space-separated list of item prices. The output consists of two numbers, which are the indices (starting at 1) of the two prices which will add up to the available credit, with the lower index appearing first.

We can see that each case now has multiple lines of input, so we need to make a slight change to Unsolved:

type Input = [String]

data Unsolved = Unsolved { unsolvedNumber :: Int, input :: Input }
data Solved = Solved { solvedNumber :: Int, answer :: String }

For convenience, we now define Input as being a list of strings. Solved remains unchanged since our final answer must still be a single string.

Just like in the previous problem, we can ignore the first line of input, since Haskell is high-level enough that knowing the number of cases is not only optional, it’s almost a handicap. It’s much easier to simply deal with a list of strings than it is to try and incorporate additional information with it.

main :: IO ()
main = do
    input <- fmap (tail.lines) getContents

Note that instead of simply mapping lines over the contents, we can use the composite function tail.lines, which will convert the contents into a list and drop the first element for us, saving us a line of code.

But we can’t simply create our list of cases using this result, because each case requires multiple lines of input. We need to convert this list of strings into a list of inputs, where each element is a list of three strings (since each case requires three lines of input). The following method will do that for us:

splitIntoCases :: [String] -> [Input]
splitIntoCases input
    | post == [] = [pre]
    | otherwise = pre:(splitIntoCases post)
    where (pre,post) = splitAt 3 input

This method will convert the input

["100", "3", "5 75 25", "200", "7", "150 24 79 50 88 345 3", "8", "8", "2 1 9 4 4 56 90 3"]

into this:

[["100", "3", "5 75 25"], ["200", "7", "150 24 79 50 88 345 3"], ["8", "8", "2 1 9 4 4 56 90 3"]]

Now we have a list of inputs that we can use to create our cases.

-- inside main
let cases = zipWith Unsolved [1..] (splitIntoCases input)

Using the same Show instance and mapM_ call from the previous problem, we then just have to work on solve.

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = ...

The first step to solving this is to parse the input, which we can do with pattern matching and some calls to read:

solve (Unsolved n input) = Solved n ans
    where (l1:l2:l3:_) = input
          credit = read l1 :: Int
          prices = map read $ words l3 :: [Int]
          ans = ...

The first line contains our credit amount, which we read in as an Int. The second line tells us how many items there are, but since this is Haskell, we can skip that. Lastly, the third line is our space-separated list of prices; we can convert it into a list of Int‘s by first splitting it into words and then mapping read over it.

But now we’ve run into another “state” problem; the output requires us to print out the index of the items, but we have no for loops. Time to create another data type.

data Item = Item { index :: Int, price :: Int }

instance Show Item where
    show (Item index price) = show index

Fantastic, now we can zip it up:

-- inside solve
items = zipWith Item [1..] prices

Okay, we have a list of items, complete with index and price. Now we just need to find two whose prices add up to our credit. My preferred method in this scenario is to throw everything into a list comprehension:

-- inside solve
results = [(item1,item2) | item1 <- items, item2 <- items,
                           (index item1) < (index item2),
                           (price item1) + (price item2) == credit]

Using the list of items, this comprehension gives us a list of item pairs where 1) the index of the first item is smaller than that of the second, and 2) the sum of their prices equals the available credit.

Reading through the problem closely, we can see that each case has one and only one valid solution, so we can assume that this will return exactly one item. Knowing this, it’s easy enough to pattern match against it and extract the final answer:

-- inside solve
(res1,res2) = head [(item1,item2) | item1 <- items, item2 <- items,
                                    (index item1) < (index item2),
                                    (price item1) + (price item2) == credit]
answer = (show res1) ++ " " ++ (show res2)

The full solution can be found here.

Creating a CodeJam Module

After doing several problems, it’s clear that there are elements common to each one. Reading input, creating a list of Unsolved cases, and displaying the output are actions common to all code jam problems. So to make things easier (and faster), we can move the common code into a module.

As it so happens, I’ve already done that. But it may require a little explanation.

The goal of the module is to minimize the effort necessary to write a solution. Each solution needs just two things: the list of inputs and a method to convert an input into a result. Given both of these, the codeJam method will convert each input into a Case, solve it, and print the result.

But we can take it one step further. Remember, code jam problems have input that look like this:

N
...
...

The first line is the number of cases, followed by the lines for those cases. For most problems, each case requires the same number of lines. This means that we can programmatically determine how many lines each case needs by dividing the number of input lines past the first by the number of cases. Using this, we can automatically split up the input by case, which means we only need to provide a method that turns that input into an answer. The codeJam' method only requires one argument, which is the method that will solve each case.

This effectively turns the Reverse Words problem into a one-liner:

import CodeJam

main :: IO ()
main = codeJam' (\input -> unwords.reverse.words $ head input)

Store Credit also receives a facelift:

import CodeJam

data Item = Item { index :: Int, price :: Int }

instance Show Item where
    show (Item index price) = show index

main :: IO ()
main = codeJam' solve

solve :: Input -> String
solve input = (show res1) ++ " " ++ (show res2)
    where (l1:l2:l3:_) = input
          credit = read l1 :: Int
          prices = map read $ (words l3) :: [Int]
          itemlist = zipWith Item [1..] prices
          options = [(item1,item2) | item1 <- itemlist, item2 <- itemlist,
                                     (index item1) < (index item2),
                                     (price item1) + (price item2) == credit]
          (res1,res2) = head options

As you can see, being able to determine which parts of a solution are unique and which are re-usable drastically reduces the average number of lines of code necessary to solve each problem.

Good luck at the Code Jam!

Packaging with the Open Build Service

One of the reasons I like and use openSUSE is its (oddly) unique approach to repositories. The other major distros all trend towards having one single massive repository, occasionally adding more if absolutely necessary. openSUSE, on the other hand, proudly wears its modular repository system as a badge of honor, as evident by the existence of such projects as SUSE Studio and the Open Build Service (formerly the openSUSE Build Service). While this carries with it both pros and cons, one of its biggest pros is how easy it makes getting started with packaging; simply create a login at build.opensuse.org and you already have your own personal (public) repo.

As easy as it is to set up your own repo, actually putting software into it can be a little tricky, but that’s the nature of packaging. The easiest method is to find an existing package that you want to modify, tweak it with the desired changes, and either push it to your home repository or formally request that your changes be merged back into the original.

The rest of this post won’t focus much on the details of RPM packaging, but instead will go over the steps necessary to begin modifying existing packages.

Creating an Account

First things first, you’ll need to create an account at build.opensuse.org (click on “Register” in the top-right). Once you’re logged in to your new account, the main page should look like this:

Click on “Home Project” in the top-right to go to your own personal repo:

From here, you could go to “Packages -> Create package / Branch package from other project” and begin uploading/modifying files to it, but we’re going to do this the hard way. The command-line tool takes some getting used to, but will be quite a bit more efficient in the long run.

Getting OSC

The Build Service’s command line tool is called osc and resembles command-line subversion. You can think of osc as a glorified version control system that builds your package on the OBS servers with every commit (Note: osc is NOT a replacement for your version control system).

To install it, you’ll need to add the Tools repository (be sure to update the URL with your openSUSE version if you’re not using 12.1), then search for and install the package osc. You can make sure it’s installed by typing man osc.

Configure Your Project

Before you can start building packages, you have to make sure your project is linked against the correct repositories. For example, if you’re packaging programs for openSUSE 12.1, you’ll need to make sure the standard 12.1 repo is enabled. Other repositories can be added later on if your packages require external dependencies, but don’t worry about that for now. As an example, here’s the metadata for my home project:

<project name="home:kog13">
  <title>kog13's Home Project</title>
  <description></description>
  <person userid="kog13" role="maintainer"/>
  <person userid="kog13" role="bugowner"/>
  <repository name="openSUSE_12.1">
    <path project="openSUSE:12.1" repository="standard"/>
    <arch>i586</arch>
    <arch>x86_64</arch>
  </repository>
</project>

Project metadata can be modified with osc meta prj -e home:<username>.

Branching a Package

Begin by opening a terminal, creating a new folder for OBS packages in your workspace, and cd‘ing into it. I store my OBS projects in ~/workspace/home:kog13.

So, let’s say you installed someone’s hello world program, but you didn’t want it to print out “hello world.” You wanted it to print out something more interesting. The solution: branch their OBS “hello world” package, modify their code, and release your improved version.

A note on branching: when you branch someone’s project, it isn’t available to download through a URL like normal packages. The intent behind branching is to make modifications that you then request be applied to the original via osc submitrequest. If instead you want to fork it completely, you’ll need to create a new package and then copy its contents over. Don’t worry, I’ll cover both scenarios.

It just so happens that I already have “hello world” packaged up. But you’re not happy with it. So you want to branch it. You can do so fairly easily:

osc branch home:kog13/hello-world

This command specifies that you want to branch the hello-world package from the home:kog13 project (my personal repository). After running it, you’re told that you can then check out a working copy:

A working copy of the branched package can be checked out with:
osc co home:<username>:branches:home:kog13/hello-world

This means that the branch has been created server-side, and you can now create a local working copy by entering that command. Note: if you’re not a fan of long colon-riddled folder names, you can specify the name of the new folder using the -o option, e.g. osc co home:<username>:branches:home:kog13/hello-world -o hello-world.

Check out the folder and cd into it. You should see two files: hello-world.spec and hello-1.0.tar. The spec file is the RPM build recipe, which doesn’t need to be changed. What does need to be changed is inside the source tarball:

$ tar -xf hello-1.0.tar
$ cd hello-1.0/

The source consists of just one file, hello.c. To modify its message, open it in a text editor and replace “hello world” with your desired new message. After that’s done let’s package it back up again:

$ cd ../
$ rm hello-1.0.tar
$ tar -cf hello-1.0.tar hello-1.0/
$ rm -r hello-1.0/

This re-creates the source archive with your changes and cleans up the extracted copy. To build it locally, run osc build; to submit your changes and schedule it to be built server-side, run osc commit -m "Your commit message here.". You can check on the server-side build status by running osc results periodically.

Once it’s committed, you can request the owner of the original package (me) to accept your changes with osc submitrequest -m "Please accept my awesome changes."

But what if I refuse to accept your changes? In a bout of righteous fury, you decide to fork my package and distribute it separately through your own home repository.

Creating a Package

Use this command to create a new package server-side:

osc meta pkg -e home:<username>/hello-world

Just give it a title and description, then save and quit. After that, check out a local working copy (not inside any existing local copies of other packages; this is why I recommend keeping a separate folder in your workspace for OBS packages):

osc co home:<username>/hello-world -o my-hello-world

The easiest way to create a fork is to simply copy over everything from the branched project. Assuming that both are checked out into the same parent folder, the following commands should be enough to create the copy and commit it to your home repository:

$ cp hello-world/* my-hello-world/
$ cd my-hello-world/
$ osc add *
$ osc commit -m "Forking your package, can't stop me now!"

Once the package has finished building, you can direct other people to it by giving them your repository’s URL:

http://download.opensuse.org/repositories/home:/<username>/

From there, navigate to the appropriate openSUSE version and architecture, then click on your shiny new package to download and install it.

That pretty much covers the basics of using the build service to make changes and updates to existing packages. Feel free to go nuts hacking on other people’s packages, and always remember to have a lot of fun.

Solving the Queens Problem with Haskell

The eight queens puzzle is a classic problem in algorithm design because it showcases the power of backtracking and recursion. The premise is simple: find a way to place 8 queens on an 8×8 board such that none of them are attacking each other, which means that no two queens can share the same row, column, or diagonal.

Sounds simple enough, but how to implement it? The most basic solution would be to brute force it: try every possible configuration, stopping when a valid one is found. Not very efficient, but hey, at least it’s easy to understand.

As the title suggests, the solution I plan on implementing will be written in Haskell. So first, let’s get some boilerplate out of the way:

import System.Environment

type Queen = (Int,Int)

main :: IO ()
main = do
    args <- getArgs
    let n = case args of [] -> 8
                         (a:rgs) -> read a :: Int
    putStrLn $ show (solveQueens n)

Since we’re solving a problem that takes place on a chess board, we’ll define a custom datatype to represent a queen as a pair of integers, denoting her location as an (x,y) coordinate. Then, in order to make it possible to find a solution for any size board, we support providing a new value of n on the command line, defaulting to 8 if none is provided. After that we call solveQueens, which we haven’t written yet, and display its results.

Brute-Forcing It

So we need to write solveQueens, which should take some n and return a list of n queens. Because Haskell doesn’t support null values, we’ll wrap the result up in a Maybe monad, just in case we get some invalid n. In particular, we want to prevent any negative values (not possible), zero (non-existent), or one (which is vacuously satisfied).

Since Haskell is a functional language, we have to make sure that any data structure we plan to use is passed in as a parameter, but it’s bad design to require an extra parameter from the user just so we can have something to operate on. We also don’t want to check if n is valid more than once, and since we’re writing this in Haskell, it will almost certainly be recursive (spoiler: it will be). Hence, solveQueens will simply be the algorithm’s entry point and not the heavy lifter.

solveQueens :: Int -> Maybe [Queen]
solveQueens n
    | n < 2 = Nothing
    | otherwise = solveQueens' n []

Notice the very clever naming scheme.

Remember, the idea behind brute-forcing the solution is to try every possible combination, stopping once we’ve found one that works (we’re only interested in finding a solution, not necessarily all of them). We want our utility method solveQueens' to take an empty list and transform it into an answer, so assuming that our as-yet unwritten isValid method works as expected, we could write this:

solveQueens' :: Int -> [Queen] -> Maybe [Queen]
solveQueens' n stack
    | x < 1 = if isValid stack then Just stack else Nothing
    | otherwise = foldl loop Nothing [1..n]
    where x = n - length stack
          loop (Just s) y = Just s
          loop Nothing  y = solveQueens' n $ (x,y):stack

What we’re doing here is starting at the right-hand column, picking a value (row) for each one and then recursing on solveQueens' until the board is filled (remember, no two queens can share the same row, column, or diagonal). The decision to go by column instead of row is rather arbitrary, but the decision to go right-to-left is due to Haskell’s list append syntax. The prepend operator (“:”) is faster than the append operator (“++”), so we essentially iterate backwards, adding each new value to the front of the list.

Once we’ve gone off the left-hand side of the board (when x < 1), we know that one queen has been placed for each column. At that point, we return the current value if and only if it's a valid result; if not, then we return Nothing. Once a valid answer has been found, each iteration will simply pass it back up the stack, eventually handing it back to main.

There's just one piece missing: how do we tell if a configuration is valid? Well, we know that no two queens can a) share an x-value, b) share a y-value, or c) share a diagonal. Testing the x and y values is simply a direct comparison, but the diagonal requires a little trick. Two queens are sharing a diagonal if the distance between their y's is equal to the distance between their x's.

Here's the implementation:

isValid :: [Queen] -> Bool
isValid stack = foldl validate True pairs
    where pairs = [(s1,s2) | s1 <- stack, s2 <- stack, s1 /= s2]
          validate False _ = False
          validate True ((x1,y1), (x2,y2)) =
              x1 /= x2 && y1 /= y2 && (abs $ y2 - y1) /= (abs $ x2 - x1)

This code looks dense, but it's really quite simple. We first get a list of square-square pairs, taking care to make sure that we don't compare a square with itself. This list holds all of the comparisons we need to make. Since we're looking for failure conditions (sharing an x, y, or diagonal), we start out by assuming True, and if it turns out that a failure condition was met, we simply pass it back up the stack.

The last line is where the actual logic is. We can invert the failure conditions by using DeMorgan's Law, which means the result of this statement can be set directly; True to continue checking, False if an error was found. Hence, it should return True only if a) their x's are different, b) their y's are different, and c) they are not on a diagonal.

Let's see what result we get for 8, the default value of n:

Just [(1,4),(2,2),(3,7),(4,3),(5,6),(6,8),(7,5),(8,1)]

If we draw out an 8x8 board and mark each of these squares with a queen, we can see that this is indeed a correct solution. But how fast is it?

real    0m6.348s
user    0m6.324s
sys     0m0.020s

Yikes. But wait, we forgot to turn on full optimizations:

real    0m2.068s
user    0m2.043s
sys     0m0.023s

That's a huge improvement, but we can do better.

Backtracking

Believe it or not, the brute-force solution we just finished is already well on its way to being transformed into a backtracking one. Think of it as walking through a maze. When you hit a wall, you want to take a step back and then try a different direction. That's more or less what our brute-force algorithm does. When it finds an invalid configuration, it takes a step back (or several) and tries a different one, though it's still brute-force in the sense that it's designed to test every possible configuration until it finds a valid one.

In order to make our algorithm more efficient, we want to be able to recognize, as early as possible, when our current path is fruitless. We don't want to wait until we actually bump into the wall, since it's much more efficient to turn around the moment we see ourselves walking into a dead-end. What qualifies as a dead-end? Well, if we add a queen onto a square that causes it to be in conflict with one that's already in place, there's no need to wait until the board is filled before backing up.

Let's work backwards a little bit. In order to catch dead-ends as soon as possible, we need to check the validity of the current board as each queen is being placed, rather than waiting until the end. Knowing this, we can re-design our isValid method to take two parameters: the current board and the proposed placement for our new queen. By assuming that the existing board is conflict-free, we only need to make comparisons on the new addition, drastically reducing the number of operations needed.

-- Modified to take advantage of backtracking
isValid :: [Queen] -> Queen -> Bool
isValid stack (x2,y2) = foldl validate True stack
    where validate False _ = False
          validate True (x1,y1) =
              x1 /= x2 && y1 /= y2 && (abs $ y2 - y1) /= (abs $ x2 - x1)

This version is essentially the same, but a little bit shorter than our first one since we don't need to calculate which queens to compare.

solveQueens' also needs a slight modification:

-- Modified to take advantage of backtracking
solveQueens' :: Int -> [Queen] -> Maybe [Queen]
solveQueens' n stack
    | x < 1 = Just stack
    | otherwise = foldl loop Nothing [1..n]
    where x = n - length stack
          loop (Just s) y = Just s
          loop Nothing  y =
              if isValid stack (x,y)
                  then solveQueens' n $ (x,y):stack
                  else Nothing

The initial version of this method simply prepended each possible new value for (x,y) onto the list and recursed on it. Since we modified isValid, we want to prepend (x,y) to the list if and only if it won't cause any conflicts. Then, if we detect that the board is full, we can simply return our current configuration since we know that it's valid.

The results should end up being the same, so what we're really interested in now is the speed (don't forget to compile with optimizations):

real    0m0.006s
user    0m0.002s
sys     0m0.004s

That's more than 300x faster, a difference which grows exponentially as you start to increase the value of n. For example, with n = 9, the backtracking solution has virtually no change in running speed, but our original brute-force solution jumps up to 23 seconds.

Both solutions can be found here.

The algorithm could be further improved by finding all valid configurations and not just the first one. But I'll leave you to do that on your own.

Thinking Functionally

Functional programming is, rightly or wrongly, often seen as a lot harder than imperative or object-oriented programming. There are several possible reasons for this. There’s the obvious issue of education; most college classes teach Java and C++, imprinting the object-oriented mindset deeply into impressionable minds (“Concepts of Programming Languages” was the only class I took that taught functional concepts), and functional languages often work on a higher level of abstraction, appearing to be a lot more “math-y.”

To demonstrate the algorithmic transition that takes place going from an object-oriented/imperative style to functional, here’s a very simple example: printing out the elements of a list (functional languages excel in data traversal and manipulation).

Here’s our algorithm, described imperatively:

1. Print out an opening bracket
2. Initialize an index counter, starting at zero
3. Print out the current element
4. If there is another element after this one, print out a comma and a space
5. Increment the index counter
6. Repeat steps 3-5 until the counter goes past the end of the list

And a simple version in Java:

// imperative algorithm in Java
public void printList(java.util.List list) {
    System.out.print("[");

    int length = list.size();
    for (int i = 0; i<length; i++) {
        System.out.print(list.get(i));
        if (i < length-1)
            System.out.print(", ");
    }       

    System.out.println("]");
}

Java itself doesn’t support a functional style, so let’s switch over to Scala. Scala as a language provides support for both object-oriented/imperative and functional styles, so it provides a good transition.

Here’s the same basic algorithm, re-written in Scala.

// imperative algorithm in Scala
def printList(list:List[Any]) = {
  System.out.print("[")

  for (i <- 0 until list.size) {
    System.out.print(list(i))
    if (i < list.size-1)
      System.out.print(", ")
  }

  System.out.println("]")
}

Okay, we’ve migrated the algorithm over to Scala. Now what? How do we go about making this functional?

Well, as it turns out, the imperative version by itself is almost completely useless. The idea to demonstrate here is that programming in a new paradigm is similar to learning how to speak in a new natural language. Planning out everything you want to say in English and then translating it word-for-word is going to get you a lot of weird stares. To become good at it, you have to learn to think in the new language. Same goes for functional programming.

So, we need a new algorithm. And in the functional way of things, we’re going to write it using immutability and pattern matching.

One of the biggest hurdles to thinking functionally is that immutability (the idea that variables, once created, shouldn’t change) removes one of programming’s most useful tools, the for loop, since it relies heavily on updating an existing value. Instead we have recursion. Looping through a list changes from incrementing an index counter to calling the same function with a smaller list, namely everything minus the first element. We then use pattern matching to quickly deconstruct the list to see what it is we’re working with.

So, a basic functional algorithm might look something like this.

1. Print out the opening bracket
2. Print out the list’s first element, if any
3. If the list has more than one element, print out a comma and a space
4. Repeat steps 2-3 with the list minus its first element as long as elements remain
5. Print out the closing bracket

This kind of works, but isn’t quite there yet. Functional programming also has a strong emphasis on minimizing side effects, so to make things a little more meta, we’ll break this up into two algorithms: one which will calculate the contents of the list as a string, and one which will print the brackets and that resulting string.

What the hell am I talking about, you ask?

// functional algorithm in Scala
def printList(list:List[Any]) = {
  def listElements(xs:List[Any]):String = xs match {
    case x :: y :: z => x + ", " + listElements(y::z)
    case x :: y => x.toString
    case _ => ""
  }
  println("[" + listElements(list) + "]")
}

Notice the function within a function. printList() is a function that technically only has one line, which is the print statement on line 8. This does exactly what I described: prints the opening bracket plus the contents of the list plus the closing bracket. listElements() is an inner function that takes care of the task of turning a list of elements into a single string, and is the bulk of the algorithm’s complexity.

Knowing that we can define inner functions, we can narrow the problem down to translating a list into a string. This is the type of problem that functional programming is known for: turning one or more values into a single result. You’ll notice that the return keyword is nowhere to be found in this algorithm; that’s because functional methods must return a value, and so they automatically return the value of the last statement (in this case, whichever case statement was matched). Technically, printList() isn’t functional at all, but is instead a wrapper around the functional listElements() whose only purpose is to carry out the side-effect of printing to the screen.

Scala’s match keyword lets us do pattern matching on a variable. Think of it as a beefed-up switch statement, where we execute certain code based on some variable’s value. Since we’re working with lists, scala’s :: operator will tell the match statement to match against list elements. The last value may or may not be empty, so in general, x :: y matches x to the list’s first element and y to the rest of the list, if any. If the list is empty, this match will fail.

So to re-cap, there are two cases we’re interested in: when the list has at least two elements (so we know to print a comma), and when the list only has one (no comma needed).

The first case statement matches any list with at least two elements: the first element x, the second element y, and the rest of the list (if any) z. In this case, we want to print x, a comma, and then follow it up with the rest (the result of recursing listElements() on the rest of the list y::z).

The second case statement will match any list with at least one element. Note that order is important here: every list that has at least two elements will also have at least one element, so we only want to check this case if the first one fails. Since the first one failed, we know that there’s only one element (in other words, the rest of the list y will always be empty), so we return the string value of x and let the recursion bottom out.

The final case statement will only match if all of the other statements failed, which will only happen on an empty list. To avoid errors being thrown when printList() is called with an empty list, we let the program know to simply return an empty string.

This was only a basic primer, but hopefully it’ll give you a good starting point when beginning to work with functional languages like Scala.

Happy coding.

Adding Javadoc Search to GNOME 3

One of GNOME 3′s more interesting features is its built-in search provider. Press the Super key, start typing, and there are buttons at the bottom of the screen to open up that search term in the engine of your choice. My copy of GNOME 3 (installed via openSUSE) comes with Google and Wikipedia as the default options, which are both very useful. But as a programmer, this opens up the possibility for one of the most global, accessible, and usable documentation search engines ever. Lord knows I’ve wasted way too much of my programming time Ctrl+F’ing through Javadoc pages.

For those who haven’t yet used GNOME 3, here’s what I’m referring to:

Our goal is to add a Javadoc button to this list. On the GNOME Shell side of things, it’s really easy; the harder part is deciding where exactly to search.

I decided to go with using Kiwidoc, a useful website designed to make searching for Javadoc easier. This has several advantages: first, to my knowledge, the official Javadoc pages do not offer online search short of Ctrl+F; second, using Kiwidoc avoids the need to download the full Javadoc to your hard drive, which is required of most Javadoc search plugins. The only downside is, again only as far as I know, there is no way to add custom Javadoc pages to Kiwidoc, so anyone doing jEdit plugin development might be shit out of luck.

To add a new search provider, we’ll need to add a new search provider definition in /usr/share/gnome-shell/search_providers. Here’s what google.xml looks like:

<OpenSearchDescription xmlns="http://a9.com/-/spec/opensearch/1.1/">
<ShortName>Google</ShortName>
<Description>Google Search</Description>
<InputEncoding>UTF-8</InputEncoding>
<Image width="16" height="16">data:image/x-icon;base64,AAABAAEAEBAAAAEAGABoAwAAFgAAACgAAAAQAAAAIAAAAAEAGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADs9Pt8xetPtu9FsfFNtu%2BTzvb2%2B%2Fne4dFJeBw0egA%2FfAJAfAA8ewBBegAAAAD%2B%2FPtft98Mp%2BwWsfAVsvEbs%2FQeqvF8xO7%2F%2F%2F63yqkxdgM7gwE%2FggM%2BfQA%2BegBDeQDe7PIbotgQufcMufEPtfIPsvAbs%2FQvq%2Bfz%2Bf%2F%2B%2B%2FZKhR05hgBBhQI8hgBAgAI9ewD0%2B%2Fg3pswAtO8Cxf4Kw%2FsJvvYAqupKsNv%2B%2Fv7%2F%2FP5VkSU0iQA7jQA9hgBDgQU%2BfQH%2F%2Ff%2FQ6fM4sM4KsN8AteMCruIqqdbZ7PH8%2Fv%2Fg6Nc%2Fhg05kAA8jAM9iQI%2BhQA%2BgQDQu6b97uv%2F%2F%2F7V8Pqw3eiWz97q8%2Ff%2F%2F%2F%2F7%2FPptpkkqjQE4kwA7kAA5iwI8iAA8hQCOSSKdXjiyflbAkG7u2s%2F%2B%2F%2F39%2F%2F7r8utrqEYtjQE8lgA7kwA7kwA9jwA9igA9hACiWSekVRyeSgiYSBHx6N%2F%2B%2Fv7k7OFRmiYtlAA5lwI7lwI4lAA7kgI9jwE9iwI4iQCoVhWcTxCmb0K%2BooT8%2Fv%2F7%2F%2F%2FJ2r8fdwI1mwA3mQA3mgA8lAE8lAE4jwA9iwE%2BhwGfXifWvqz%2B%2Ff%2F58u%2Fev6Dt4tr%2B%2F%2F2ZuIUsggA7mgM6mAM3lgA5lgA6kQE%2FkwBChwHt4dv%2F%2F%2F728ei1bCi7VAC5XQ7kz7n%2F%2F%2F6bsZkgcB03lQA9lgM7kwA2iQktZToPK4r9%2F%2F%2F9%2F%2F%2FSqYK5UwDKZAS9WALIkFn%2B%2F%2F3%2F%2BP8oKccGGcIRJrERILYFEMwAAuEAAdX%2F%2Ff7%2F%2FP%2B%2BfDvGXQLIZgLEWgLOjlf7%2F%2F%2F%2F%2F%2F9QU90EAPQAAf8DAP0AAfMAAOUDAtr%2F%2F%2F%2F7%2B%2Fu2bCTIYwDPZgDBWQDSr4P%2F%2Fv%2F%2F%2FP5GRuABAPkAA%2FwBAfkDAPAAAesAAN%2F%2F%2B%2Fz%2F%2F%2F64g1C5VwDMYwK8Yg7y5tz8%2Fv%2FV1PYKDOcAAP0DAf4AAf0AAfYEAOwAAuAAAAD%2F%2FPvi28ymXyChTATRrIb8%2F%2F3v8fk6P8MAAdUCAvoAAP0CAP0AAfYAAO4AAACAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAQAA</Image>
<Url type="text/html" method="GET" template="http://www.google.com/search?q={searchTerms}"/>
</OpenSearchDescription>

The only parts we’ll need to change are the name, description, and search template string (not sure about the image, since it doesn’t show up with my theme; if I find out how the image works, then I’ll add how to give each provider a custom one). Here’s what my javadoc.xml looks like:

<OpenSearchDescription xmlns="http://a9.com/-/spec/opensearch/1.1/">
<ShortName>Javadoc</ShortName>
<Description>Javadoc Search</Description>
<InputEncoding>UTF-8</InputEncoding>
<Image width="16" height="16">data:image/x-icon;base64,AAABAAEAEBAAAAEAGABoAwAAFgAAACgAAAAQAAAAIAAAAAEAGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADs9Pt8xetPtu9FsfFNtu%2BTzvb2%2B%2Fne4dFJeBw0egA%2FfAJAfAA8ewBBegAAAAD%2B%2FPtft98Mp%2BwWsfAVsvEbs%2FQeqvF8xO7%2F%2F%2F63yqkxdgM7gwE%2FggM%2BfQA%2BegBDeQDe7PIbotgQufcMufEPtfIPsvAbs%2FQvq%2Bfz%2Bf%2F%2B%2B%2FZKhR05hgBBhQI8hgBAgAI9ewD0%2B%2Fg3pswAtO8Cxf4Kw%2FsJvvYAqupKsNv%2B%2Fv7%2F%2FP5VkSU0iQA7jQA9hgBDgQU%2BfQH%2F%2Ff%2FQ6fM4sM4KsN8AteMCruIqqdbZ7PH8%2Fv%2Fg6Nc%2Fhg05kAA8jAM9iQI%2BhQA%2BgQDQu6b97uv%2F%2F%2F7V8Pqw3eiWz97q8%2Ff%2F%2F%2F%2F7%2FPptpkkqjQE4kwA7kAA5iwI8iAA8hQCOSSKdXjiyflbAkG7u2s%2F%2B%2F%2F39%2F%2F7r8utrqEYtjQE8lgA7kwA7kwA9jwA9igA9hACiWSekVRyeSgiYSBHx6N%2F%2B%2Fv7k7OFRmiYtlAA5lwI7lwI4lAA7kgI9jwE9iwI4iQCoVhWcTxCmb0K%2BooT8%2Fv%2F7%2F%2F%2FJ2r8fdwI1mwA3mQA3mgA8lAE8lAE4jwA9iwE%2BhwGfXifWvqz%2B%2Ff%2F58u%2Fev6Dt4tr%2B%2F%2F2ZuIUsggA7mgM6mAM3lgA5lgA6kQE%2FkwBChwHt4dv%2F%2F%2F728ei1bCi7VAC5XQ7kz7n%2F%2F%2F6bsZkgcB03lQA9lgM7kwA2iQktZToPK4r9%2F%2F%2F9%2F%2F%2FSqYK5UwDKZAS9WALIkFn%2B%2F%2F3%2F%2BP8oKccGGcIRJrERILYFEMwAAuEAAdX%2F%2Ff7%2F%2FP%2B%2BfDvGXQLIZgLEWgLOjlf7%2F%2F%2F%2F%2F%2F9QU90EAPQAAf8DAP0AAfMAAOUDAtr%2F%2F%2F%2F7%2B%2Fu2bCTIYwDPZgDBWQDSr4P%2F%2Fv%2F%2F%2FP5GRuABAPkAA%2FwBAfkDAPAAAesAAN%2F%2F%2B%2Fz%2F%2F%2F64g1C5VwDMYwK8Yg7y5tz8%2Fv%2FV1PYKDOcAAP0DAf4AAf0AAfYEAOwAAuAAAAD%2F%2FPvi28ymXyChTATRrIb8%2F%2F3v8fk6P8MAAdUCAvoAAP0CAP0AAfYAAO4AAACAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAQAA</Image>
<Url type="text/html" method="GET" template="http://www.kiwidoc.com/java/s/p/findKeywords?k={searchTerms}"/>
</OpenSearchDescription>

Save it, then restart the shell with Alt+F2 and the command ‘r’, or log out and back in. Now we can use the Shell to search for Javadoc:

And here’s what it brings up:

This can obviously be extended to work with more than just Javadoc; the only potentially hard part is narrowing down what query string to use.

Have fun.

Why I Don’t Like E-book Readers

Sorry for the sensationalist headline; despite the title of this post, I don’t intend to spend the whole time explaining why e-book readers are evil and why you should never buy one. Instead, I see the popularity of the Amazon Kindle as hiding a potential danger that many people may be unaware of.

I’m going to start off by going on a slight tangent to talk a little bit about the idea of free software. The premise is simple: anyone should be able to view, modify, and share the source code for the programs they use. Why does this matter? Because, in theory, it prevents users of a piece of software from being held victim by its creators. It’s very much akin to being allowed to cook your own food. Without grocery stores that let us pick and choose the ingredients we want to eat, we’d have to eat at restaurants all the time and hope that whoever’s behind the counter will let us request changes to the menu.

Unfortunately, there are two big issues that the free software movement has overlooked. The first is that we live in a heavily capitalist society that loves specialization and corporate structure. There’s a stigma surrounding free and open source software in our society that seems to suggest that it is less secure than proprietary software. To this day, many voting machines run proprietary software. Not only is this grossly exploitable, but many Americans seem to think it is the best way to go. Why they’re wrong is a topic for another day, but the underlying point is that free software is often unwittingly painted in an unfavorable light, for reasons from security to compatibility issues.

The second issue is that software is inherently complex. From low-level memory management to application design to framework integration, even seasoned programmers have difficulty keeping track of it all. The consequence of this is that software users are, quite frankly, lazy and dumb. They don’t want to know how their software works, and part of me doesn’t blame them. It’s very satisfying to have a program work exactly as expected, and equally frustrating when something doesn’t work for reasons beyond your control.

The level of complexity that most software has attained is all intended to ultimately do one relatively simple thing: enable the use of computers. Many of our daily tasks have migrated to the digital world, from checking mail to listening to music to doing homework. As a result, much of this has been made more convenient, something our society pursues endlessly. What it also does is entirely remove our understanding of how we do these things, which used to be easy. This is where the danger lies, as any company developing widely-used proprietary software can easily pull the rug out from under our feet. Basic tasks can now be rendered helpless by decisions made by a profit-driven corporation.

Finally, we get to the topic of e-book readers; in particular, the Amazon Kindle which created and currently dominates the e-book market. The Kindle itself runs Linux, but its books are stored in a proprietary format designed by Amazon. This means that they have a huge amount of control over, get this, every book you own. To Amazon’s credit, they’ve done a decent job of opening up the platform with PDF support and conversion utilities (source: wikipedia), but the need for conversion utilities in the first place suggests that something is wrong.

Since I don’t actually own a Kindle, I can’t claim to know how their system works, and as I’ve already mentioned, Amazon seems to have done a decent job holding themselves back from all-out vendor lock-in. But my real fear is that Amazon will take a cut of every single book purchase. By creating the format, our capitalist society is all too happy to pour its money into their pockets for essentially no work, and the simple act of buying a book sends a cut of the profits to one company. Even if this isn’t the case now, it’s always a possibility should Amazon become desperate down the road.

The exact same thing happened with the iPhone App Store. Since Apple was the first on the scene with a proprietary format, they now dominate the market, and are all too happy to do so. If Apple had their way, they would receive a cut every time someone installed a new program on their computer, and their users wouldn’t care.

What both the App Store and Kindle have in common is that they’ve reached a critical mass; people will now use it simply because others use it, regardless of the quality of the software itself. This is unfortunately inevitable, since having a large user base is a great advantage for any software platform, but it’s one that’s often undeserved and gives the owner of the platform permission to let its quality degrade slowly over time. After several years of dominance, if Amazon wanted to add an additional fee to purchase books, existing customers would have no choice but to pay it.

Ultimately, what I don’t trust is torrents of money given to one company for an action as simple as buying a book. Consumers simply don’t care who creates their software and how it works; as long as it does, their money goes to the first one on the field. There is certainly some level of merit to the Kindle and the App Store, but consumers need to use some level of discretion when deciding why they choose the option that they do.

TL;DR – the level of control that Amazon Kindle and other platforms exert over basic day-to-day actions has the potential for corporate corruption and shouldn’t be encouraged to the level that it is today.

My Problem With Python

First, as a disclaimer, I do not hate Python. It is a great language for what it does, and obviously has a large following of very devout users. For a long time I myself was a little confused about why I shied away from it so much, but I think I’ve finally begun to grasp in words what it is that I don’t like about the language.

First, what does Python do right?

The Good

Python is clean. This is one of Python’s biggest selling points, and the motivator behind using indentation-based code blocks over the traditional brackets. It’s easy to look at a section of Python code and read it quickly without having to adjust to a different coding style you’re not used to seeing.

Python is easy to learn. A good REPL, descriptive error messages, and minimal boilerplate all help make Python a very easy language to pick up, even for novice programmers. It’s very often touted as the best language to start programming with.

Hundreds of different operations are supported. Relatively complex operations like reversing a string are easy in Python:

str[::-1]

Great documentation. python.org has hundreds of pages of documentation and API references. The world would be a better place if every language put this much effort into their docs.

The Not-So-Good

Now for the section that will generate the most hate. Agree or disagree, these are the reasons that I’m not the biggest Python fan.

With a couple exceptions, it does nothing new. Rather than introduce new ideas or ways of thinking, Python focuses solely on minimizing the effort it takes to access old paradigms, in some areas lagging badly behind. For example, lambda methods appear to be a poor imitation of anonymous functions, nowhere nearing the power of those found in Scala or Haskell, or even C# and Vala. Python is hailed as the savior of programming languages, yet does little to contribute towards the theory of what a programming language should be.

It’s used where it shouldn’t be. Python is great for a web-development language (after all, something needs to oust PHP), but Python begins to overstep its bounds when it’s used to develop large desktop applications. Small ones, great, but the trend of developing desktop apps with Python only stems support for languages that are designed specifically to run on the desktop. I would feel better about this if desktop apps written in Python were compiled before they shipped, but they’re generally not.

It’s too dynamic. You cannot declare a variable in Python, and you cannot specify what type a variable should be. This makes it less clear to someone reading your code what exactly something is. This is especially annoying when dealing with objects, since you can’t tell by looking at the top of a class what values it holds. Languages like Bash get away with being overly-dynamic by simplifying the type system; every variable in Bash is a string, so there’s no need to explicitly declare its type.

To build a little on the previous point, it’s not simple. I’m using Stuart Halloway’s definition of simple, which is simply “not compound.” Any variable in Python can be anything, and any function call can do or return anything, since much of the program executes in the global namespace and functions don’t define return types.

And finally, Python is not elegant. It is a good language for quickly hashing out ideas, but that’s exactly it: it’s designed to get stuff done quickly. And that’s it. There is nothing pure or organized about the language. Haskell is purely functional, Java purely object-oriented, and C purely procedural; by contrast, Python is a melting pot of ideas, but that’s not necessarily a good thing. By focusing on and building upon a single programming paradigm, Haskell, Java, and C all introduce new ways of thinking about problems, which is something Python does not do.

Conclusion

It seems that I will never understand the level of religious fervor held by Python proponents. To be fair, I am not a web developer at heart, and so perhaps I am speaking out of place. However, there is one thing I am proud to have. The next time I begin telling someone about a new project, and they respond with “why don’t you just use Python?”, I will at least have something to say.

Linux Application Development Part V: Designing Interfaces with Glade

This is the fifth entry in my series on Linux application development. For part 4, go here.

Before we get started, I want to state that this post is not a full introduction to GTK+ (which can be found here); instead, I’m going to jump straight into using an interface designer to create a simple text editor.

A Brief Overview

One way to write your application’s GUI is to code it by hand. Doing it this way works fine for simple interfaces, but when your program gets more complex, it becomes increasingly difficult to build and maintain. This is where an interface designer comes in. Glade is a program that lets you design your GUI by placing and configuring widgets visually and then saving it as an XML file, which your application can then import and display. Even for relatively simple interfaces, Glade is a great tool to learn and know.

This post will go over the process of designing a simple text editor interface using Glade and then writing a Python script to display it.

Let’s Get Started

First, open up Glade from Applications -> Programming -> Glade Interface Designer. You should be presented with a new window.

On the left-hand side, you have all of the available GTK+ widgets grouped by category. In the top-right is a pane that shows all added widgets so far, and underneath that is space to configure the selected widget. Finally, in the center is where you will actually build your GUI.

Every GUI starts with some top-level widget, usually a window. So let’s start by putting in a window:

If you click on a top-level element, it will automatically be added to the current workspace. You’ll notice that our window was given a default name of “window1″; since we’re only planning on having one window (for now, at least), let’s re-name it to simply be “window”.

Knowing the names of your widgets is important, because you’ll need them in order to access them from your code. In this first example, the only widget we’ll need to know is the top-level window, because show_all() will take care of displaying everything it contains. But when specifying widget actions, you’ll need to know their names as well.

Remember that our goal is to create a basic text editor. The idea is simple: a window with a menu bar on top and a large text area in the center. Since we want to show two widgets in one window, we’ll need to add a container widget that will itself hold two widgets. The top-level window will only hold one widget, so containers let us make better use of that space; you can design fairly complicated interfaces simply by nesting containers.

But which container to use? For this situation, a V-box (vertical box) will work best. Both the menu bar and text area should span the full width of the window, but we want to stack them vertically.

To add one, click on the Box widget under Containers. Then click inside our empty window to add it. A dialog will pop up asking how many items it should hold, with a default value of 3. Change this to 2, since we only need to add two things. Click Create to add it to the window. Note: the Box widget defaults to a vertical orientation; to add an H-box (horizontal box), you can change the Orientation underneath General properties.

Now locate the menu bar widget in the left panel (it’s listed under Containers); click on it, and then inside the top half of the box to add it there. Do the same with the text area (called “Text View” and listed under Control and Display) for the bottom half. Your window should now look something like this.

We’re almost done, but something’s not quite right. Notice in the screenshot how the text view widget seems to be pretty short; it’s currently just stacked up against the menu bar, not filling the empty window space. To fix this, click on it and change the Expand property (under Packing) from No to Yes.

All right, looking good! Now we just need a way to display it. Save this interface as “notepad.ui” and then open up a text editor and save the following as “notepad.py”:

#!/usr/bin/env python
import sys
from gi.repository import Gtk

# initialize GTK+
Gtk.init(sys.argv)

# create a GtkBuilder
builder = Gtk.Builder()
builder.add_from_file("notepad.ui")

# get and display the window
window = builder.get_object("window")
window.set_default_size(300, 200)
window.connect("destroy", Gtk.main_quit)
window.show_all()

# start the main loop
Gtk.main()

Make it executable, run it, and you should see something like this:

Looking good, even if it doesn’t really do much yet. Let’s work on adding a little bit more functionality; at the very least, File->Quit should exit the program.

Getting the menu items to do something requires connecting their signals to some callback function. If you’ll notice, we already connected the window’s “destroy” signal to the function Gtk.main_quit, which exits the GTK+ main loop and lets our script finish. Without connecting this signal, clicking on the window’s close button would have no effect.

When you click on a menu item, its “activate” signal is triggered. So to connect a menu item to its callback, we use the same syntax as we did for connecting the window’s destroy signal.

To make things easier, locate the widget corresponding to the “Quit” menu item in Glade and re-name it (use the top-right panel to expand the menu bar’s children). It should be named “imagemenuitem5″ or something similar; change its name to “menu_item_file_quit”. Then save it and add the following to notepad.py after window.show_all():

# connect File->Quit to Gtk.main_quit
menu_item_file_quit = builder.get_object("menu_item_file_quit")
menu_item_file_quit.connect("activate", Gtk.main_quit)

Then File->Quit should work correctly.

If you wanted to add more flexibility, you can connect these signals to a custom callback rather than send it directly to Gtk.main_quit. An alternative version of notepad.py could look like this:

#!/usr/bin/env python
import sys
from gi.repository import Gtk

# initialize GTK+
Gtk.init(sys.argv)

# quit callback method
def quit(source):
	print("Quitting...")
	Gtk.main_quit()

# create a GtkBuilder
builder = Gtk.Builder()
builder.add_from_file("notepad.ui")

# get the window
window = builder.get_object("window")
window.set_default_size(300, 200)
window.connect("destroy", quit)
window.show_all()

# connect File->Quit to quit()
menu_item_file_quit = builder.get_object("menu_item_file_quit")
menu_item_file_quit.connect("activate", quit)

# start the main loop
Gtk.main()

Now, when you close the window, the program will print “Quitting…” before actually exiting. This approach can be used to do things like ask the user if they want to save before exiting or to do other cleanup.

Exercise: To take this even further, try connecting the other menu items to their own callbacks and see what you can come up with. Try connecting Help->About to a method that shows a Gtk.MessageDialog to the user. If you’re feeling particularly adventurous, read up a little bit on the API for GIO and see if you can implement File->Open and File->Save.

Until next time.

Linux Application Development Part IV: GNOME, GTK+, and yet another Hello World

This is the fourth entry in my series on Linux application development. For part 3, go here.

As the title of this post suggests, we’re finally going to start digging into some real Linux application development by using GTK+ and GNOME. For those who are unsure, let me start by outlining the different parts of the Linux world.

Operating Systems, Desktop Environments, and Linux Distributions

The one thing that ties all Linux distributions together is, well, Linux. Technically, Linux is nothing more than the kernel, which is the core of the OS that handles fundamental operations such as I/O and process management. What’s relevant to us is that all of Linux shares two things: executable format and filesystem compatibility. This means that a program compiled on one version of Linux should in theory work on another, as they both share a common means of executing them. This is what separates Linux from other systems like BSD; they differ on a very fundamental level.

On top of the Linux kernel sits the desktop environment, of which GNOME and KDE are the most popular. They build on the kernel by providing a set of libraries, which are utilities to ease common tasks and enable more advanced ones. In order to run a GNOME application, the user must already have all of the GNOME libraries that the application intends to use. It is possible to install these libraries on a KDE-based system in order to run it, but it is usually preferable to choose a native application that can make use of the libraries already there, hence our focus for the time being is on writing applications for people running GNOME.

Lastly, we have the Linux distribution, which primarily serves as a method of, well, software distribution. The primary job of a distro is to settle on a suite of software (including the desktop environment) and then package it up in a consistent format that is easy for users to install. Thanks to package maintainers, it’s pretty rare that you’ll need to compile a program from source. If you want your application to be installed easily, then you’ll need to package up your program and make it available for as many distributions as you can.

Unless you’re developing drivers or other very low-end software, it’s unlikely that you’ll be working at the kernel level. Most development will be done at the desktop environment level, and it won’t be until you get to packaging up your finished product that you’ll have to decide which distros to support.

A little about GNOME

I chose GNOME as the focus of this post because 1) it’s more widely used than KDE, 2) I have more experience with it, and 3) the recent release of GNOME 3 means that anything written for it now will be supported for a long time to come.

Some of the history of GNOME and what the GNOME Project does can be found on their website, but what we’re interested in right now is a suite of useful, flexible libraries, which GNOME provides for us. In particular, what we’re most interested in is GTK+, GNOME’s library for creating graphical user interfaces.

For more information on the technical backend of GNOME, I highly recommend reading up on GLib and GObject, which are general-purpose abstraction libraries used throughout the entire platform. For this post, it’s not necessary to have in-depth knowledge of how they work, but they will be very useful to know as your applications become more advanced and integrated.

Setting up a Development Environment

If you are running either GNOME 3 or a recent version of Ubuntu, feel free to skip to “Learn Your Tools” and make sure that each of the listed programs is installed from your package manager. For everyone else (including myself), I created a SUSE Studio appliance that comes installed with all of the necessary tools to get started: download.

If you have a spare computer, feel free to grab the Live CD and install it from Applications -> System Tools -> Live Installer. Otherwise, I recommend grabbing the VMWare image and setting up a virtual machine in either VMWare or VirtualBox. To set it up, create a new virtual machine based on openSUSE Linux, up the base memory to 1024 MB, and select the downloaded .vmdk image as the existing hard disk. Start it up, grab yourself a drink as you wait for it to boot, and you should be good to go.

The system will automatically log you in as user “tux”. For administrative access, use the password “linux”.

Don’t worry if you get an error saying that GNOME 3 failed to load, especially if you’re using a virtual machine. The GNOME Shell requires hardware acceleration and rarely works in virtual environments, but all we need is the libraries, not the Shell interface. Fallback mode is more than good enough for our needs.

Learn Your Tools

Before getting too far, it’s a good idea to familiarize yourself a little bit with the available applications. Each one does something useful, so let’s see what there is. The first two are found in Applications -> Accessories, everything else is under Applications -> Programming.

GNOME Terminal – your basic terminal emulator. If you’re not familiar yet with how to use a terminal, I strongly recommend learning the basics.

gedit/Vim – text editor. Vim can be used either in a GUI (Applications -> Accessories -> Vi IMproved), or inside the terminal with the command “vim”. These are very useful for writing small programs, as well as editing config files. I highly recommend taking the time to learn Vim if you haven’t yet, but gedit is also extremely useful, and has a much smaller learning curve.

Anjuta – IDE. This is the official tool of the GNOME Project for creating new applications.

Glade – user interface designer.

Devhelp – developer’s documentation.

A text editor and terminal is all we’ll need for the first few examples.

Hello World

All right, it’s finally time to write a program. First, create a new folder to put all your projects in (I use ~/workspace), and in there create another one for hello world (mine’s named “hello-world”; if you can, try to avoid using spaces in your folder names). Then fire up gedit or Vim.

Tip: if using gedit, go to Edit -> Preferences -> Plugins and enable the plugin “Embedded Terminal”, as well as any other plugins you may find useful. Close that and go to View -> Bottom Panel to open up the terminal. View -> Side Panel will open up a file browser.

This is a basic hello world example using GTK+ and Python, which I have saved as hello-world.py:

#!/usr/bin/env python
from gi.repository import Gtk
Gtk.MessageDialog(None, 0, Gtk.MessageType.INFO, Gtk.ButtonsType.CLOSE, "Hello World").run()

Make it executable with chmod and then run it by invoking it directly.

Since this is an executable script, we start out with a hash-bang comment (“#!”) that tells the system which interpreter to use. /usr/bin/env is a program that lets us specify an interpreter without knowing its absolute path, which means that it will work as long as python is on our system PATH.

The second line uses GObject Introspection (PyGI) to import the Python bindings for GTK+. GTK+ is written in C, and introspection provides a way for other languages to interface with any library based on GObject, which includes GTK+.

The last line is where all the work is actually done, creating a new message dialog and then running it.

The Current State of GNOME Python

First, beware of any examples using PyGTK. As of the release of GTK+ 3, PyGTK is deprecated. It will work fine for GTK+ 2, but my focus here is on newer API’s and tools.

Unfortunately for us, since GTK+ 3 is so new, there is no good accurate source of PyGI documentation. This page provides some tips for translating the up-to-date C syntax to Python, as well as porting from PyGTK to PyGI, which should help when writing more advanced Python programs.

When searching for more examples, look for import statements that take modules from gi.repository. This is a good sign that the example is up-to-date with GNOME 3.

Use GNOME’s Resources

The GNOME Developer Center has many useful pages filled with documentation, guides, and more. In particular, I recommend checking out some of their demos. Everything on that page is up-to-date and includes some examples in Python that get quite a bit more advanced than hello world.

If you’re serious about learning to write Linux applications, the best thing you can do is to just dive in head first. Join some mailing lists, install Pidgin and head to the IRC channels, and don’t be afraid to ask questions.

Above all, have fun with it. Try to come up with an idea for an application that you’d like to see, then see if you can code up a small part of it. Want to design a new music player? Start by reading up on GStreamer, then try to create a program that will play a music file. Want to create a file downloader? Try using GIO to fetch the contents of a webpage. Not satisfied with your text editor? Writing a new Notepad in GTK+ is a great first project.

Or if you’re interested but don’t have the time, knowledge, or even motivation to start pursuing your own project, you could also just wait until the next post, because I’m just getting started. =)

An Aside on Program Design

When you get sick of programming, please take a look at the GNOME Human Interface Guidelines. They are slightly out of date, but the majority of the suggestions apply as equally to GNOME 3 as they do to GNOME 2; additional suggestions specific to the GNOME Shell are being collected here.

What the guidelines do is not only provide suggestions for how to make your program look good, but also how to make sure it integrates well with the rest of the GNOME environment, including maintaining interface consistency that lowers the learning curve for your user. A lot of what’s said is common sense, but all of it is good advice, and I strongly suggest you adhere to it whenever possible. One possible exception is the section discussing GConf; as of GNOME 3, I believe that GConf has been deprecated in favor of GSettings, so don’t be surprised if that gets removed when it’s finally updated.

Time to Wrap Up

This post was intended to not only show you how to write hello world with GTK+ and Python, but also to give you some background on what GNOME is and how to use it. Good desktop integration is what separates a good program from a great program, and I hope that everyone reading this strives for a great program.

Happy developing.