YouTube: Vibop by NewBlue

I'm proud to announce that we launched a new YouTube.com/create partner, Vibop:

Vibop makes your videos shine with just a few clicks. Add an animated intro, a vintage filter, a cartoon look, a silent movie theme, and dozens of other effects. Brighten dark images and fix a shaky camera. Fun, fast, and easy, Vibop will take your memories to the next level!

Dart at BayPiggies

I gave a talk on Dart last night at BayPiggies. We had a great turn out, and the crowd was super interactive! Never underestimate a Python programmer's ability to question every aspect of a new programming language, especially one that uses curly braces and semicolons ;)

If you're interested, here are the slides.

Walking Skeletons and TODO Outlines

These days, applications are so complicated and contain so many layers that it's difficult to know where to start. Should you work bottom up or top down? How much should you work on one layer before starting to work on the next layer? How can you ensure that the layers work properly together? Building a walking skeleton and managing a TODO document in outline format are two techniques that work well together to conquer complex problems, even ones involving multiple layers. Best of all, you don’t have to worry about trying to get things right the first time or getting lost along the way.

A Walking Skeleton is a tiny implementation of the system that performs a small end-to-end function. It need not use the final architecture, but it should link together the main architectural components. The architecture and the functionality can then evolve in parallel. -- Alistair Cockburn

Building a walking skeleton is a great way to handle the complexity of dealing with multiple layers. Start with the simplest possible feature, and implement it top down. Ideally, the feature should force you to work your way all the way down the stack. The goal is to make sure the layers work together.

As you’re building the walking skeleton, you may think of many things that you need to add, test, or in general worry about. It's helpful to maintain a TODO document in outline format so that you can organize and plan your attack, especially when you’re working with multiple layers at the same time. Eventually, each TODO item can be transferred into a test, a piece of code, an issue in the bug tracking system, or perhaps just an email to someone else.

Once you’ve built a walking skeleton, should you go back to developing one layer at a time? For most applications where the cost of change is low, probably not. Actively building one layer at a time is frequently very inefficient. A more efficient approach is to focus on one feature at a time. Sketch out the feature using a set of TODOs and build it top-down, managing the TODOs as you go. If you focus on one feature at a time instead of one layer at a time, you won’t end up building a lot of code in different layers that never actually gets used. The time saved by only building what you need and only building it when you have all the information you need more than compensates for the refactoring time.

Thanks go to Chris Lopez for his help with this post.

Books: Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists

I just finished reading Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists. In short, I liked it. I wouldn't say I liked it as much as, say, Coders at Work, however, I'm glad I read it. What I liked most about it was that it contains biographies from really early computer science pioneers such as Ada Lovelace, John von Neumann, John Backus, and John McCarthy. I know computer history after 1970 really well, but this book contains a lot of stuff from before 1970.

I jotted down a few interesting tidbits while I was reading the book. However, since I read the Kindle version of the book, I only have percentages, not page numbers. Anyway, I hope you're as entertained by some of these as I was.

John Backus, who lead the team that created Fortran at IBM, flunked out of college [2%]. He had a metal plate installed in his head [3%]. He disliked calculus but liked algebra [3%] (just like me!). These days, Backus is a proponent of functional programming [7%].

John von Neumann, who helped establish the fundamentals of computer architecture, thought that creating a programming language (i.e. Fortran) was a waste of time since programming wasn't a big problem [4%].

Ada Lovelace, who was the first programmer (not to mention, a girl!), was a gambler, an alcoholic, and a cocaine addict. She died of cancer at the age of 36. She is credited with inventing loops and subroutines [5%].

Fortran only had globals. Algol, which is considered an ancestor of C, added locals, thus permitting recursion [6%].

McCarthy, who designed Lisp, was born in 1927 to Communist party activists. He had an Irish, Catholic father and a Lithuanian, Jewish mother [8%]. McCarthy is the reason Algol had recursion [11%]. (I didn't know that C got recursion because of Lisp.)

Alan Kay, who did pioneering work on object-oriented programming and helped create Smalltalk, got thrown out of school for protesting the Jewish quota [15%].

Edsger W. Dijkstra, who did influential work on a lot of early computer science problems such as concurrency, did very well in school and wanted to turn programming into a respectable discipline [21%].

Fred Brooks, who wrote "The Mythical Man-Month", wrote this about iterative development:

In "The Mythical Man-Month" I said build one and throw it away. But that isn't what I say anymore. Now I say, build a minimal thing--get it out in the field and start getting feedback, and then add function to it incrementally. The waterfall model of specify, build, test is just plain wrong for software. The interaction with the user is crucial to developing the specification. You have to develop the specification as you build and test.

Python: Shrapnel

After many years of hopeful expectation, IronPort (now part of Cisco) finally open sourced a bunch of stuff, most importantly Shrapnel, our proprietary version of stackless Python. Back when I worked at IronPort (2004-2006), I was dying for them to open source this stuff. The existing open source version of stackless Python at the time never had quite the same flavor or emphasis as Shrapnel, but these days gevent is very similar.

Anyway, congratulations to Sam Rushing, Mark Peek, etc., and thank you Cisco! By the way, there's a reference to me in the code ;)

Dart at g|egypt 2.0

I gave a talk on Dart at g|egypt 2.0. All I can say is, wow!

First of all, I wasn't even on the agenda. In fact, the room I was using wasn't really even labelled on the map--it took me several minutes to find it. It was a small room. 2 minutes before my talk was supposed to start, I only had 3 people in the audience. However, 10 minutes later, every seat was taken, and people were standing at the back and along the sides. The room was packed!

Since Dart is so new, we haven't spoken about it at very many places. I told the Egyptians that I was giving them a chance to become the best Dart programmers in the world because they were seeing the talk before most of the rest of the world had seen it. I almost got a standing ovation ;)

People were very excited about Dart and asked a ton of excellent questions. Even after my talk, I had to stand around for 2.5 hours answering more questions.

The comments on Google+ were very supportive:

Hady Allam said, "your DART session is one of the best sessions i have ever attended. Thank You +Shannon Behrens and hope to see you again in Egypt."

Abdurrahman Alraies said, "The dart session was the best surprise of the day. Thank you very much +Shannon Behrens and +Sebastian Trzcinski-Clément It says much about how important is Egypt to Google."

Saied Attala said, "really i have opened the comment box for 30 minutes and can't write every thing for you. i loved your Dart sessions and your sense of humor. i enjoyed talking with you and having pics with you."

Those comments were very touching to me. To all the Egyptians out there who went to my Dart talk, thank you for making me feel so special! I hope I get to come back to Egypt again!

After the trip, I accidentally ran into Lars Bak, the creator of Dart, in Zurich. That was very exciting for me!

If you're interested, here are the slides.

Thanks also to Saied Attala and Ayman Reda Bedair for the pictures and Seth Ladd for most of the slides.

YouTube for Your Business at g|egypt 2.0

I gave a talk called YouTube for Your Business at g|egypt 2.0.

The talk went very well. There were about 200 people in the audience (and almost 900 in total at the event), which is a great turnout for a YouTube API talk. People asked me questions for about an hour afterwards. I even created a video for the talk:



I was really worried that I would lose my voice during the talk. It's very crackly right now.

Since this is the first time I've visited the middle east, I'm suffering a little from culture shock. I forgot to remove a beer joke from one of my slides. It took me a few seconds to realize why people weren't laughing. What's really funny is that I don't even drink!

I was very amazed by a few things. There were a lot of women at the event. There are far more female programmers in Egypt then there are in the US, as far as I can tell. The next thing that surprised me was that almost everyone here uses Windows--even on the server side. That's certainly not the case in the San Francisco Bay Area. At all the companies I've worked at recently, people tended to use Apple laptops and Linux on the servers. The last thing that surprised me was how many people wanted to have their picture taken with me. For about two hours, I felt like a total rock star ;)

I have a talk on Dart tomorrow and a talk on Python the next day. Let's hope my voice holds up ;)

Thanks go to Mohamed Naguib for taking the picture.

Computer Science: The Travelling Salesman Problem

I was thinking about the Travelling Salesman problem this morning. I came up with an algorithm that permits a few nice optimizations. My guess is that Knuth probably already came up with this algorithm, formally analyzed it, and then came up with 15 others that were much better. Nonetheless, I figured I'd jot it down.

Warning: This is a rough draft of an algorithm. You shouldn't bother reading this if you want real rigor. I'm just writing it down to get it off my chest.

Rather than picking the first segment of the journey and working my way to the end, I want to pick a middle segment of the journey and work my way outwards recursively.

Given a list of distances (or times, or costs, or whatever) between cities, sort the list from shortest distance to longest distance regardless of which cities are involved. Now, loop over this list and use each element of the list as a middle segment of your journey. This gives us a list of "first steps" (or rather, first middle steps). Looping over the list from shortest distance to longest distance is an important optimization because it increases the likelihood that we'll find an optimal path early, allowing us to skip over a lot of potential paths later.

Also sort the list of distances so that for each city, we have a list of other cities in ascending distance order. By sorting all of the city pairs in order of (first city, distance), you can use one sort for all of the pairs.

Now, here comes the recursion. We have a bunch of middle parts of the journey. Use recursion to extend the journey either by adding to the beginning of the journey or by adding to the end of the journey. Keep recursing until you have a complete path or a partial path that is already longer than the best path seen so far. Now, we can either extend the journey at the beginning or at the end. Recursively try extending the journey by either adding to the beginning or the end. However, do it in order so that you try adding the shorter distances first. There's an implicit merge sort going on in this algorithm. This, again, is an optimization to allow you to skip work later.

While we were recursing, we had a function that took two things, a middle chunk of the journey and a set of cities not yet visited. Apply memoization so that anytime we get the same parameters, we return the same answer (by using a cache, of course). This is an important optimization.

Last of all, using the above algorithm, we'll quickly come up with the first complete path that has a decently minimal distance. Keep track of this as the best complete path seen so far. Anytime we are recursing and we come up with a partial path that is longer than the best complete path seen so far, we can stop recursing, give up, and try something else. This is an important optimization to save work "at the leaves of the tree".

I can't even wrap my head around the big O of this algorithm. I suspect it's one of those cases where you use words like "amortized cost".

This algorithm does have a weakness. If every distance between cities is exactly the same, it'll try every possibility. Similarly, if every distance between cities is exactly the same except one pair of cities which has a longer distance, it'll still try every possibility. I'm not sure of the degree to which the memoization fixes this problem. It'd be good to extend the algorithm somehow to recognize this situation and short circuit, i.e. automatically throw out paths of duplicate length.

Math: Factoring Numbers

I was thinking this morning about factoring numbers. I wonder if it might sometimes be helpful to use real numbers to gain an interesting perspective in order to solve certain problems involving integer numbers (i.e. number theory problems). For instance, I was thinking about factoring large numbers.

For every natural number, C, (that isn't equal to 0 or 1), there are an infinite number of pairs of positive, real numbers A and B for which A * B = C. For instance, 6 = 1.0 * 6.0 = 2.4 * 2.5 = 2.0 * 3.0 = ... I wonder if playing around with pairs of real numbers like (2.4, 2.5) can lead you to pairs of integer numbers like (2, 3).

Imagine all the pairs (A, B) for which A * B = C. Let's create a way to graph all such pairs in a funny sort of way. Let's pick a bunch of A's going from 0 to C. For each different A, we can calculate B via C / A. Let's consider the parts of A and B that are to the right of the decimal point to see if one pair, (A, B) can lead us to another pair (A', B') which are integers (i.e. have only zeros to the right of the decimal point). In fact, let's see if we can come up with a numerical analysis approach where we use estimations to hunt down (A', B').

To do this, let's create a funny sort of three dimensional graph. Here's the pseudo code (assuming we're trying to factor some number, c):

for step in range (1, LARGE_NUM_OF_STEPS + 1):
    a = (step / LARGE_NUM_OF_STEPS) * c
    b = c / a
    x = a - int(a)  # x and y will always be in the range [0, 1).
    y = b - int(b)
    z = floor(a)
    draw_point(x, y, z)

If you use a very large number for LARGE_NUM_OF_STEPS, you'll create a funny looking 3D graph. Any place where x = 0 and y = 0, you'll have a pair of integers (a, b) that multiply to equal c.

Naturally, this is an extremely expensive way to factor numbers. However, I'll bet you'd learn a lot about factoring numbers by looking at this graph. In fact, I'm guessing that looking at this graph will lead you to a numerical-analysis-style approximation algorithm for honing in on valid integer pairs (a, b) where a * b = c.

Humans are fairly good at visualizing things in 3D, but it'd be really cool to extend this graph to four dimensions (perhaps using time as the fourth dimension). The fourth dimension would be used for various values of C, from 0 to infinity. I really think that looking at such a graph would help with fast number factoring.

Updated: Fixed a couple of errors pointed out by BMeph.