My Name Rhymes

DNA on Programming

2008-02-16T17:45:47Z

"Well, what we called a computer in 1977 was really a kind of electric abacus, but..."
"Oh, now, don't underestimate the abacus," said Reg. "In skilled hands it's a very sophisticated calculating device. Furthermore it requires no power, can be made with any materials you have to hand, and never goes bing in the middle of an important piece of work."
"So an electric one would be particularly pointless," said Richard.
"True enough," conceded Reg.
"There really wasn't a lot this machine could do that you couldn't do yourself in half the time with a lot less trouble," said Richard, "but it was, on the other hand, very good at being a slow and dim-witted pupil."
Reg looked at him quizzically.
"I had no idea they were in such short supply," he said. "I could hit a dozen of them with a bread roll from where I'm sitting."
"I'm sure. But look at it this way. What really is the point of trying to teach anything to anybody?"
This question seemed to provoke a murmur of sympathetic approval from up and down the table.
Richard continued, "What I mean is that if you really want to understand something, the best way is to try and explain it to someone else. That forces you to sort it out in your own mind. And the more slow and dim-witted your pupil, the more you have to break things down into more and more simple ideas. And that's really the essence of programming. By the time you've sorted out a complicated idea into little steps that even a stupid machine can deal with, you've certainly learned something about it yourself. The teacher usually learns more than the pupil. Isn't that true?"
"It would be hard to learn much less than my pupils," came a low growl from somewhere on the table, "without undergoing a pre-frontal lobotomy."
"So I used to spend days struggling to write essays on this 16K machine that would have taken a couple of hours on a typewriter, but what was fascinating to me was the process of trying to explain to the machine what it was I wanted it to do. I virtually wrote my own word processor in BASIC. A simple search and replace routine would take about three hours."
"I forget, did you ever get any essays done at all?"
"Well, not as such. No actual essays, but the reasons why not were absolutely fascinating. For instance, I discovered that..."
He broke off, laughing at himself.

-DNA

Functional Roman Numerals in Python

2008-01-12T17:52:00Z

Just as a quck note, I thought I'd post the cleanest python I could come up with to solve the roman numerals problem I discussed earlier. It tries to use a functional style while actually avoiding recursion. To do so, I wrote an iterative python unfold:

def unfold(f, x):
    res = []                       
    while 1:
        try:
            w, x = f(x)
            res.append(w)
        except TypeError:
            return res

And then the answer becomes:

numerals = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
    ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
    ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
    ("I", 1)]

def next(x):
    for n in numerals:
        if n[1] <= x: return (n[0], x-n[1])

def romanize(n):
    return "".join(unfold(next, n))

Compare to the haskell I posted before:

romanize = concat . unfoldr next
    where next 0 = Nothing
          next x = Just $ second (x-) $ head $ filter ((<=x) . snd) numerals
          numerals = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
                      ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
                      ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
                      ("I", 1)]

The "where" idiom allows you to group helper functions and constants underneath the main function, and the unimportance of function order means you can highlight the high-level logic. The haskell code is much shorter and tighter than the python.

Having powerful iterative functions like unfoldr in the standard library is another clear win for Haskell; it took me more lines to define unfold than it did to define both next() and romanize(). (By the by, some googling failed to turn up a previous python implementation of unfold(); I think this code gets a lot uglier without it. I also don't see any obvious way to do it with itertools.)

On the other hand, I find the simplicity of the python next() appealing, with its constructive instead of declarative approach. It's a less generic solution that's intuitively simpler (for me, still an imperative thinker).

You could match the haskell more exactly:

from itertools import ifilter

def second(f, (a, b)): return (a, f(b))

def next(x):
    return second(lambda a: x-a, ifilter(lambda (y, z): z <= x, numerals).next()

but the result is pretty ugly. The inability to compose functions compactly results in a lot of boilerplate, and in having to pick a lot of meaningless variable names that obscure what's going on. We could move the lambdas out of the call and give them names:

def next(x):
    subx = lambda a: x-a
    ltx = lambda (y, z): z <= x

    return second(subx, ifilter(ltx, numerals).next())

And it's a little better, but I think we're now pretty far from idiomatic python.

Conclusion

The python translation of the haskell isn't bad, but I do think it loses something. The unfold() trick works really well, and translates easily into an imperative, pythonic implementation; I'll look for ways to use it in the future. And, finally, I'm pretty jealous of Haskell's function combination abilities.

Updates

In the comments at reddit, nostrademons posts a nicer unfold function:

def unfold(f, x):
    while True:
        w, x = f(x)
        yield w

And Kay Schluehr prefers the iterative solution:

 numerals = (("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
("C", 100),("XC", 90),("L", 50),("XL", 40), ("X", 10), ("IX", 9), ("V", 5), 
("IV", 4), ("I", 1))

def romanize(n):
    roman = []
    for ltr, num in numerals:
        (k,n) = divmod(n, num)
        roman.append(ltr*k)
    return "".join(roman)

David Pollak contributes a Scala unfold and romanize at his blog.

Beautiful Code

2008-01-12T03:32:00Z

This bit of code for converting numbers into their Roman numeral equivalents was posted by geezusfreeek on reddit, and I found it so alarmingly pretty that I'm going to spend some time to break it down. This exercise is largely for my own edification, but perhaps somebody else will learn a bit along the way. Here's the code:

import List
import Control.Arrow

romanize = concat . unfoldr next
    where next 0 = Nothing
          next x = Just $ second (x-) $ head $ filter ((<=x) . snd) numerals
          numerals = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
                      ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
                      ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
                      ("I", 1)]

Starting from the inside out is usually the easiest method of understanding blocks like this, so we'll look first at the "numerals" list. It is, simply, a list of tuples matching Roman numerals to their value. Importantly, it's ordered from largest to smallest; we'll see why shortly.

The meat of this snippet comes in the "next" function:

next 0 = Nothing
next x = Just $ second (x-) $ head $ filter ((<=x) . snd) numerals

This function is going to return either Nothing (in the base case) or Just a tuple of type (String, Integer), where the string is the largest roman numeral that's smaller than x and the int is the difference between x and the value of that roman numeral.

The first thing we do is filter out the numerals larger than x; we can run some quick tests at the interactive console to see how this works:

Prelude> let numerals = [("M", 1000), ("CM", 900), ("D", 500)]
Prelude> filter ((<=900) . snd) numerals
[("CM",900),("D",500)]

We use head to grab the largest numeral we can squeeze into the current value:

Prelude> head $ filter ((<=900) . snd) numerals 
("CM",900)

Then we subtract the value of the roman numeral from the current value of x, in order to return the remainder to be operated on next:

Prelude> :m Control.Arrow
Prelude Control.Arrow> second (900-) $ head $ filter ((<=900) . snd) numerals
("CM",0)
Prelude Control.Arrow> second (915-) $ head $ filter ((<=915) . snd) numerals
("CM",15)

And, finally, we wrap it up in a Maybe monad, so that the main function can handle the base case transparently:

Prelude Control.Arrow> Just $ second (915-)  $ head $ 
    filter ((<=915) .  snd) numerals
Just ("CM",15)

And now we're getting pretty close! What we have is a function that returns either Nothing or a tuple containing a letter to add to our roman numeral and the next value to operate on. All we have left is the code to drive the operation:

romanize = concat . unfoldr next

The use of unfoldr helps explain why we've wrapped next up in Maybe; here's its type:

Prelude Control.Arrow> :m List
Prelude List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

So we'll take a function from b -> Maybe (a, b), a value of type b, and return a list of [a]. In our case, a = String and b = Integer.

All unfoldr does is call the function it's given as a first argument, which returns a tuple or Nothing. If it's a tuple, it appends its first element to a list and calls the same function with the second element. If it's Nothing, it returns the list it's built up to this point.

As we can see, that matches up perfectly with the "next" function we've already defined, and the unfoldr will build up a list of roman numeral strings:

Prelude> :m Control.Arrow List
Prelude Control.Arrow List> let numerals = [("X", 10), ("IX", 9), ("V", 5), 
("IV", 4), ("I", 1)]
Prelude Control.Arrow List> let next x = if x==0 then Nothing               
    else Just $ second (x-) $ head $ filter ((<=x) . snd) numerals
Prelude Control.Arrow List> unfoldr next 9
["IX"]
Prelude Control.Arrow List> unfoldr next 8
["V","I","I","I"]

(We had to mangle the definition of next a bit to fit into the interactive interpreter, but we haven't changed anything fundamental about it.)

Finally, all we have to do is concatenate the strings into our final result:

Prelude Control.Arrow List> (concat . unfoldr next) 8
"VIII"

Conclusion

Phew - that's an awful lot of information stuffed into a few pretty lines! I still have a hell of a time geting the types to match up so that I can write stuff like this, but that doesn't mean that I can't appreciate the beauty of how it all fits together. The original function presented here is tight in the very best sense of the word.

Iterating Over Database Results in C#

2007-12-17T01:13:00Z

At my job, we use what is essentially a custom C# ORM. Soon after I arrived, we adopted this idiom to pull a DB connection from the pool and run a query:

 class Something
{
    public int ourIdiom(long identifier)
    {
        using (DBConnection db = new DBConnection())
        {
            using (IDataReader rec = db.execQuery(@"
                SELECT some, rows
                FROM  Table1 t1, Table2 t2
                WHERE t1.t2id = t2.id
                AND   t1.id = ?",
                identifier))
            {
                while (rec.Read())
                    doSomething();
                return 1;
            }
        }
    }
}

Which is nice because it disposes of both the connection and the dataReader properly on failure, but ugly because it uses a whole bunch of boilerplate. Unfortunately, because doSomething() needs to execute inside both using statements, and we weren't using C# 2.0 until a few months ago, the only way to avoid the boilerplate would have been to pass in delegates.

This would have been just as ugly as keeping the boilerplate in the code, so we stuck with the using² idiom.

Since our switchover to 2.0 a few months ago, I've had an idea that I could make this idiom more concise and remove some boilerplate that I didn't get a chance to try until this week. Using 2.0's iterators, which seem awfully familiar from my python work, that can be reduced to:

class Something
{
    public int ourIdiom(long identifier)
    {
        foreach (IDataReader rec in new SQL().Query(@"
            SELECT some, rows
            FROM  Table1 t1, Table2 t2
            WHERE t1.t2id = t2.id
            AND   t1.id = ?",
            identifier))
        {
            doSomething();
        }
        return 1;
    }
}

With some fairly simple code:

public class SQL : 
    System.Collections.Generic.IEnumerable<IDataReader>
    {
        string m_sql;
        ArrayList m_sqlparams;

        public SQL()
        {
        }

        public SQL query(string sql, params object[] sqlparams)
        {
            m_sql = sql;
            m_sqlparams = new ArrayList(sqlparams);
            return this;
        }

        IEnumerator<IDataReader> IEnumerable<IDataReader>.GetEnumerator()
        {
            using (clsDBConnection db = new clsDBConnection(m_dbname))
            {
                using (IDataReader rec = db.execQuery(m_sql, m_sqlparams))
                {
                    while (rec.Read())
                        yield return rec;
                }
            }
        }

        //this is required because IEnumerable<> inherits IEnumerable. bleh.
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator() }
    }
}

This code should come in handy for more reasons than just its cleanliness. First off, if you ever need to change the idiom for accessing the DB, it's stored conveniently in one place.

Second, It makes a prepared SQL call into something like a thunk: a bit of code representing a future computation that can then be passed around to be performed later. An example:

void setUpQueries(nameId, addressId, custId)
{
    List<SQL> stringsWeNeed = new List(new object[]{
        new SQL().query("SELECT name FROM names WHERE id=?", nameId),
        new SQL().query("SELECT addy FROM addresses WHERE id=?", addressId),
        new SQL().query("SELECT zip FROM customers WHERE id=?", custId)});

    List<string> strings = getOurStrings(stringsWeNeed);

    mangleStrings(strings);
}

List<string> getOurStrings(List<SQL> queries)
{
    List<string> strings = new List<string>();
    foreach (SQL query in queries)
    {
        foreach (IDataReader rec in query)
            strings.Add(rec.GetString(0));
    }
    return strings;
}

While the example is silly, this property can be exploited to seperate declaration from execution, which I often find to be a useful pattern.

Though I am far from the first person to discover this simplification, I did figure it out on my own and I thought it was neat enough to share.

A quick disclaimer: the code here is modified from the original to remove some details, and is completely untested, and probably doesn't compile. You may, however, use it or distribute it as you see fit; it's licensed under the wtfpl.

UPDATE: added the while(rec.Read()), which I'd forgotten

Why Applications Suck (Part 1)

2007-08-24T01:50:00Z

Why do people outside of corporations overwhelmingly use webmail instead of email clients? Long before rich email clients like gmail were available, people have flocked to the internet email client - messaging has been the killer feature of the web for a long time now.

But why?

The answer is simple: Overwhelmingly, users do not want to install programs, and users do not want their data stored on their computer. In that order of importance.

Users Don't Want to Install Programs

Let's examine the process of getting a popular, free, email client like Thunderbird installed. To do so, imagine that we're instructing our kindly aunt Tilly how to install it.

Now Tilly is no old fogie, she's been using Microsoft Word at work for over a decade now, and she knows her way around msn.com. However, she just decided to strike out looking for a new job, and wants to finally use that personal email address that came with her cable internet. She's got us trapped on the phone, and "we know computers", so here's roughly what we'll tell her to do:

type google.com in the address bar
type in "thunderbird"; press enter
click on the first result
click on "Download Thunderbird"
click "OK"
choose a place to save it (Just use the desktop, Tilly!)
minimize the browser
hunt for the file named "Thunderbird"

And, ohmigod, we're not even close to done. She's still got to run the installer (3-4 clicks minimum), which involves selecting an installation directory (a what?), then open the program, open the tools -> accounts menu option, find the documentation for her service provider's email tools, copy them into the "add new account" wizard (another 3-4 clicks) where appropriate, remember her user name and password, and then download all the email she's had sitting there since she hasn't checked it ever.

Now, finally, she's ready to use her email client. It's just that easy!

Let's compare the process for getting her up and running with gmail:

type "gmail.com" in the address bar
click on "sign up for gmail"
fill out a form (a task she probably knows how to do)
click on "I accept. Create my account."

Now, Tilly may not be the most technological mind around, but she's also no dummy. I know which one I'd rather direct her to do.

Desktop application install is a problem.

Do We Even Want to Fix This?

Many web 2.0-savvy types will tell us that this isn't a big deal. In the future, all of our applications should be inside our browser, and to speak otherwise is heresy! The desktop is dead! Sure, Javascript + Json + the browser has limitations, but those restrictions are liberating! Get used to it, or perish!

Well, bah humbug. Here's what's good about the web: The easy posting, viewing, and navigating of documents described by URIs.

That's it.

Let me repeat it for clarity: The web, in your browser, is only really good at sending discrete data, displaying discrete documents and navigating in between them.

Phew.

The whole paradigm is absolutely superb at getting this job done. The system of hyperlinks, URIs, DNS, and HTTP over TCP/IP is the greatest achievement that computer programmers have achieved, a massive global effort that has managed to stay amazingly open and coherent. It "Just Works" enough to change the way information is distributed, businesses are run and even how society is structured.

Anything amenable to being represented as discrete visual documents has taken to the internet like a duck to water. Chief among them is email; check out the top 100 global Alexa websites and see how many "social networks" in how many languages are in the top 100. Sites displaying news (documents), photographs (documents), videos (strictly as documents), and information about software (documents) make up most of the rest.

What's left among those 100 is the elephant in the room; the Killer Internet Application: search. Even Microsoft's lame search engine finds its way into the top 100 because people will do whatever they need to in order to search the web; it's the only way to get an effective handle on the information in the Great Hyperlinked Mass. I believe it's the exception to my "web is only good at documents" theory that proves the rule.

Search Works, so Let's Put All our Apps On the Web

Since the web gained massive worldwide popularity in the mid-1990s, an enormous amount of effort has been spent on making the browser into an application development platform. The Great Mozilla Rewrite basically shut that browser down between 1998 and 2002 in order to make it an application platform. Microsoft developed activeX, Sun pushed Java applets as the solution, Adobe developed SVG, and Macromedia developed its Flash player.

Nowadays, Firefox is pushing <canvas>, Microsoft has released Silverlight, Macromedia has become Adobe, and Flash is the only one of the first generation technologies still breathing oxygen as a development platform.

Furthermore, with the invention of Google Gears, Joyent Slingshot, the aforementioned Silverlight, or Adobe Air, you might soon be able to (gasp) save files to the host computer! That's right, in 10 years we've almost gotten to the point where a program running in a browser can save a file on your hard drive and read it when you're offline.

The problem is that, fundamentally, a browser is still only good at one thing: documents. Its whole paradigm is set up that way. What does the "back button" mean when you're playing a game of asteroids? What does "home" mean while you're editing a photo? Does an address bar on an mp3 player need to be so in your face?

We Can Fix This

So, instead of shoehorning our applications inside of the browser window because it's convenient, let's do something radical: bring our "real software" applications into the modern age of the internet.

In the next article, we'll talk about how software installation came to suck so badly, with an eye towards how to go about bringing it up to the web era.