The power and insanity of C++ templates

exhibit 12941b: analog literals


it is possible for this to compile as valid c++ code:

  assert( ( o-------------o
            |L             \
            | L             \
            |  L             \
            |   o-------------o
            |   !             !
            !   !             !
            o   |             !
             L  |             !
              L |             !
               L|             !
                o-------------o ).volume == ( o-------------o
                                              |             !
                                              !             !
                                              !             !
                                              o-------------o ).area * int(I-------------I) );

here's more: analog literals
still more: yep, they're turing complete

why, bjorne, why?

Dtrace

Up until very recently I had never heard of Dtrace.

Sun Microsystems, makers of brilliant software but not money, created Dtrace for their Solaris OS. It allows you to create probes and listen on a port where syscalls or other OS events are reported.

This is awesome and also ported over to Mac OS X. This set of one-liners gives a small example of what's possible. If you're on a mac or FreeBSD or Solaris (!) and looking for a good time try running a few of these.

And if you have Instruments installed, you can launch apps and monitor their calls, file I/O, memory leakage, etc...

For my own personal Rube Goldberg machine, I might write a Dtrace script which listens for whenever files of a certain type are opened, and pipe them to a script which automatically backs them up using some version control.

Or similarly, automating other tasks such as running make whenever code files are written.

I was excited to learn about and had never heard of Dtrace, so I thought I'd share, enjoy!

11 week Project Manager Manifesto

If you are taking a project course that lasts 11 weeks, and you are leading a group of 5-8 software engineers, congratulations, you are a project manager for CSE 403!

Read this post-mortem fresh from the source, the project manager on Robot Rock. Robot Rock is an open-source interactive music framework built in 11 weeks by 5 UW undergrads for CSE 403, a software engineering course.

Suggested reading:
The Pragmatic Programmer
How To Win Friends and Influence People

At the beginning

You are the one to set the tone. Work as hard as it takes to get the project off the ground, and demonstrate what your expectations are. The sooner you demonstrate that the project could be a success, the sooner you win the rest of the team's dedicated efforts, and you can't get far without that.

This is the time for experimentation--it will never get easier to test out different concepts!

For example, Robot Rock started with separate demos of drum sounds in a loop and a trivial non-functional UI. Mashing these together was a major milestone and morale boost, demonstrating the fact that all of our technologies can live and work together in the same environment in a doubtful time when we still struggled to set it all up.

It also provided a tangible way to demonstrate that a lot of the hard work was already done, and was useful for settling disputes through experimentation instead of abstract arguments (for example, when designing architecture based on the performance limitations of our libraries).

Establish regular meeting times during the week, and hold onto this inertia. Meeting often is the best thing your group can do.

Don't think of yourself as any sort of authority, think of yourself as the sniffable glue keeping your team happy and productive and it's up to you to figure out exactly how to make that happen! If you read Dune you know that as soon as you start giving orders, people stop acting autonomously, so don’t command, lead instead.

Testing

Write lots of tests in the beginning, but keep them fairly general/flexible since things will be fairly tumultuous at the start and tests will die quick and noisy deaths.

You need the tests for just two purposes: to verify and enlighten. Tests help maintain confidence and momentum, and allow you to breath easy knowing that you aren't breaking anything as you hurtle with breakneck speed through the rapid development which takes place after the design is settled. Of course, with all this code, you need a way to demonstrate what it all does. Tests are a great way to communicate to your team mates how to actually use the code you're writing.

Don't let tests prevent refactoring--accept that you will have to some tedious effort fixing them up. If you hate the thought of this, don't go hog wild writing tests for things likely to change, and write professional tests which don't have lots of repeated code.

Don't leave your tests broken.

Planning

Assembla is a hugely valuable tool. It integrates a ticket system, file hosting, milestone tracking, wiki, and repository with online code browsing.

Use the wiki to maintain your documentation and deliverables. Use the milestone tracking to organize and shuffle your tickets around in time.

As soon as you think of something that needs to be done, create a ticket for it.

Design

So, you're in 403, which means you're writing code for 11 weeks, then throwing it away, right? There's some truth to this, but if you write ugly code you can't use it to convince people to hire you. Often job postings require an example of code you've written to solve a non-trivial problem, and so this is your chance to shine to all future employers.

There are a lot of general things which constitute a good design, such as modularity, simplicity, modules which are decoupled, interfaces, etc.

This isn't really about bad design/good design though. You want a design which will make your high level goals natural to achieve.

For example, we knew at the start that it was critical for Robot Rock's music to feel very responsive and sensitive to user manipulations.

We also knew that we wanted the audio generation to have no influence over the rest of the design, in case we wanted to drastically change the way we generate the actual musical tones.

From these first principles, we could evaluate each potential design (everyone came up with a rough design as a homework assignment) and examine if it allowed for real time responsiveness, as well as decoupled abstract song data from the underlying generation. Once these requirements were met, we went on to examine other more general qualitative characteristics, such as separation of components and simplicity.

If we started with an arbitrary design goal, such as simplicity, we may have locked ourselves into a design where real time responsiveness was anything but natural, despite whatever other elegance is achieved. In other words, we would have picked A Good Design, but it'd be The Wrong Design.

Features

Build the simplest thing that meets the requirements.

If there's a feature you want to add, consult your users first. Make a prototype before investing the time in something which the user may not actually care about.

No optimization until feature complete, or later even.

Understand when code is good enough...I'm just parroting The Pragmatic Programmer at this point, so just read that instead.

Grow Experts

Assign each group member an area of ownership. It doesn't have to be something they are familiar with, just something they care the most about ideally. There should be no part of the project without an associated leader. Everyone can just refer to this person for questions, and it will deepen their understanding of the respective area. It also provides resume bullet points.

Not everyone will have the same knowledge level of the languages you use. It helps to have at least one person experienced with each language utilized, and they should oversee code reviews with the less experienced members, at least during the initial stages. It goes without saying that the instruction and learning are the crucial goals for these code reviews, never judgment.

Teamwork

I forget where I read this, but the difference between a team and a group is that a group all leaves a meeting at its deadline regardless of where things stand, whereas a team will stay as long as it takes to get things to a satisfactory point.

In practice this makes no sense. Sometimes people really do have to be somewhere at a certain time, and sometimes despite your best efforts, you have to force a less than ideal resolution. But the idea is not to leave things open and unresolved at the end of the day. Make some sort of plan for the next session, or if someone can stay and play cleanup, they should and earn the gratitude of the group. Make sure it's not the same person every week.

Get the entire group involved. If someone's quiet, explicitly invite them to weigh in with their position. Assign homework to the whole group to prepare a decision on items which affect the overall team course. Send around status updates during times when everyone's too busy on different areas to meet.

Code and documentation is communal. If any problem is found, it's your problem to fix, regardless of its origin. No drawing territorial boundary lines, if it's someone else's code, take it as an opportunity to learn about its inner workings.

When Conflict Occurs

Let everyone speak their minds, and focus on the ideas, not the person.

Try to be the first to find and acknowledge the weaknesses of your own idea, and the strengths of each opposing idea.

Find common ground. Find and point out things about ideas you disagree that are positive, and be sincere.

If the discussion drags on, put it to a group vote. Once the group decides, that's it, no revisiting the topic until taking action to make things work as they stand.

Think Big

Able developers seek worthy, difficult projects to grow their skills. Give yourselves a difficult and interesting project, so you'll attract hungry developers, and everyone will rise to meet the challenge.

Project Euler

I started working on Project Euler since I had some down time during spring break.

I started working yesterday evening and did some more problems this morning. I've solved the first 10 but still am not even halfway to completing 'Level 1.' The good news is that most of the problems don't take longer than 10 minutes to start to finish, especially when using Python. Generators, list slice assignments and list comprehensions made things like iterating Fibonacci sequences and computing prime numbers fast and easy.

What I've learned in each course this quarter

Networks:

Now that I've taken Networks, I believe I could describe, at some points in excruciating detail, everything that occurs when a user clicks 'Go' to load a webpage, to the page displaying on their screen.

This includes all the Operating System considerations, sockets, threading, buffering, packets/segments, error detection schemes, framing, Ethernet, DHCP, ARQ, NAT, STUN, TCP, IP, reliability, ordering, congestion control, routing, forwarding, heterogeneity of network topology, BGP; plus real-time application support, wireless protocol, and RFID thrown in just for fun.

Things we didn't learn about: DNS. But I can fill in most of the blanks on this one myself. And we didn't spend much time on application layer protocol such as HTTP, though we touched on SMTP some.

We covered so much in this class that my understanding of network principles didn't congeal until it was time to review for the final.

Algorithms:

We surveyed a suite of useful problems solved using Greedy algorithms, Divide and Conquer techniques, and Dynamic Programming. We also learned how to show that a problem is NP complete or prove that an algorithm is correct and/or efficient.

Key takeaways: the incredibly useful technique of dynamic programming to exploit redundant subproblems to solve a larger problem efficiently, and firm understanding of the definition of NP and NP-complete.

Technical Communication:

This class sharpened my understanding for and gave me practice with presenting technical information. Still, the one liner for this class remains:
Tell them what you're about to tell them, tell them, then tell them what you just told them.

9 hours of messing with iPhone SDK

The iPhone feels like a new frontier, at least for non-early adopters such as myself.

After learning about Walk Score, I was in a bit of disbelief that their application was not available on the iPhone. Their lookup simply requires a latitude and longitude, which the iPhone readily provides. I dreamed of running around while looking for an apartment and pressing a button on my phone to get its walk score.

So knowing nothing about Objective C, mobile development, XCode, or much else related to Apple development I set out to whip up a simple mashup of iPhone + Walk Score today and went at it for about 9 hours.

Unfortunately I haven't yet produced anything close to finished.

But I learned quite a bit.

For example, I learned that diving straight into the iPhone samples was a fruitless, frustrating process. The interface builder was not intuitive and I spent over an hour trying to add functionality to a button.

After downloading a 50-page tutorial on "Your First iPhone Application," I learned how rigorously the SDK enforces the Model-View-Controller principles, such that a simple Hello World app requires substantial scaffolding (50 pages worth!).

Additionally I got a taste of Objective C, a taste I have not yet acquired. It's more verbose than Java, yet is dynamically typed with difficult syntax and a reasonable number of dependency issues.

I learned that Objective C prefers a SAX style XML parsing.

I figured out how to send HTTP queries to Walk Score, parsed their XML response, and displayed a score for a fixed latitude and longitude.

After this I wondered if a browser based approach held more advantages. It would spare XML parsing and simply direct users to the search results page for their coordinates. This idea held appeal, since I would reuse the existing browser functionality, and some scores took time to calculate and would require a redirect anyway.

As my networks professor mused a couple of days ago, "Perhaps one of the best programmers I've met is also one of the laziest programmers I've met, he never does more than he has to for his code to get the job done. Maybe his laziness is what makes him so good." (He was relating it to the design decisions behind NAT)

After learning how to load web pages using an embedded browser, it came time to retrieve live GPS coordinates. Unfortunately, this is not as simple as a one-line API call. Using GPS is expensive battery-wise and is best done sparingly according the dev docs. For this reason a custom manager is required, which I was hooking up before deciding to call it a day and write this developer diary entry.

Perhaps later this week I will wrap up the GPS retrieval and integrate it into the iPhone app browser call. But I also learned it might not be worth it:
--Walk Score's heat maps show certain places, such as San Francisco, have near universal scores of 80-90 with only small pockets of lower quality. If the result is nearly uniform, is the experience of walking around with this app anything like I imagined?
--Apple has a certification program in place. Testing and verifying the app might be a costly endeavor, and it might not even find its way into the Apple store.
--Now that I learned some basics, I find myself less interested in this project versus what I could now begin working on.

All in all, a great experience. I'm still very excited to see what I can produce on this platform, even if I have to hold my nose to write Objective C...

Diving into "Dive Into Python"

Well I'm now five chapters deep in Dive Into Python, which is available completely for free as a PDF.

It's an older book, but still relevant for its unusual and fantastic approach of teaching a new language to experienced programmers. The approach seems so obvious, and yet it's difficult to come up with examples of other titles which follow the same approach.



Each chapter begins with a short code example which highlights the power of Python while performing non-trivial tasks such as outputting the language's own documentation or displaying directory listings with file metadata.

These examples highlight the succinctness of the language while including a new language concept per chapter, effectively booting the reader into a frigid pond of fresh semi-obtuse language constructs ('Get thrown into freezing cold pond of python' doesn't have quite the same ring though).

The remainder of the chapter is always devoted simply to exposing the constructs and syntax of the example; both what and how it all works, line-by-line if necessary. Code samples are available from the website, and the chapter encourages a hands-on approach of running and modifying sample code.

At each chapter's conclusion, a checklist of concepts is presented and the semi-obtuse sample seen at its start reads as clearly as a language you've known all along.

It makes perfect sense that the best way to learn a language is by dissecting code beyond one's current reading level and then changing and authoring examples to reinforce it all. It's a bit strange that fewer books go as far as this one, but it's possible the "by Example" series follows a similar tack.

Dive Into Python's chief drawback is it's age--the book was written way back in 2003, the time of Python 2.3 (it's now the age of 2.6 and the dawn of 3.0). Still, this is a much more fun way to learn than reading, for example, Python in a Nutshell, as I was doing (it's more of a reference manual anyway, though more up to date).

Python Imaging Library

I've been diving into Python and trying to craft short little programs to improve my skillz.

One of the first Python extensions I made a move for was the Python Imaging Library. The PIL packs in an impressive amount of file format compatibility; loading and creating images could hardly be simpler.

For 90% of your typical use cases I'd say PIL does great, since loading saving and doing simple transformations on images is ridiculously simple. The PIL even supports drawing directly on images with polygons and other primitives. This is where my list of annoyances begins.

When you're drawing on an image, it seems only natural to desire transparency of shapes. Strangely, this is not possible. After some digging it seems the closest hack is to draw on a buffer image and then blend() or paste() with the original to achieve transparency. This is alright as long as the number of shapes are limited.

However, if you're trying to create multi-layered vector art, PIL isn't really up to the task.

In order to achieve the incremental layering of these shapes with true alpha values, I had to write my own pixel-by-pixel merge function, which was ridiculously slow. I'm sure there might have been a better way to do it but I found some of the documentation lacking, and on further investigation it's just literal comments from the source code, with few usage examples.







The above images took about a minute each to render, so there goes my plan to create a fun hill-climbing afternoon evolutionary image grinder. I might give this another stab with some Python OpenGL libraries.

Graphics class final project.

Well, I'm slowly but surely taking my tuition money back out of the department by snatching their various prize giveaways. Yesterday I received an Amazon gift certificate in my inbox from "The CSE Department" for qualifying in the regional ACM programming contest.

Today I took away a WALL-E 3-DISC Special Edition, an excellent and relevant reward for coming in second place in our graphics class' animation short festival. My graphics partner Robert and I built a strange little one-eyed Residents-style toaster creature which likes dancing and creating toast. Here's the full clip:




I'm also adding the original dancing clip below because unfortunately we didn't match up our video resolutions and it clipped out a lot of the detail. Here it is:


Dancing eye ball toaster from a f on Vimeo.

Last summer's big ol' DNS scare

An entertaining and well-written article about a crucial internet security flaw last summer:

Dan Kaminsky destroys, saves internet etc.

A scary reminder of how the entire web hinges on the security of e-mail of all things.

ACM Programming Contest

It was a lot of fun to compete in the ACM Pacific Northwest regional programming contest. We didn't qualify to go on to the finals but our school (University of Washington) swept the top three spots at our site (University of Oregon in Eugene) and my team snagged the second place spot at the site with 7/11 problems correctly solved.

It was an exciting finish too--we had only solved four problems with less than an hour to go in the five hour contest, and we got 3 correct submissions in the final 45 minutes to boost our standing to the top three.

I really enjoyed the contest, they challenged our problem solving and debugging skills and I especially enjoy working with the guys who were on my team. It was also a chance for people who didn't know me as well to discover the true extent of my nerd-dom as I missed an excellent party or two to travel to Eugene and write code instead. Carpe Diem.

Sweet they made an instructional video too!

I'm still really excited about the coverage Google Ad Planner is receiving.

Now that it's open to everyone, they made an instructional video specifically for my feature:



Ok so the visualization has an instructional video, does this mean it's difficult to use? Not necessarily, it's powerful since there are 4 axes of control and the video helps people realize the potential sitting right at their fingertips that they may not otherwise realize!

Once again you can check it out here.

Tech Crunch write up!

My summer internship product / feature was written up on Tech Crunch!

Google Ad Planner is now open to everyone:

Check out the sweet video demo then go check it out.

I worked on the bubble chart mentioned. There was a bit more to it then hooking up the Trendalyzer API. Scale and performance were big considerations as well as prototyping and researching different audience visualization concepts.

Here's a custom close-up of the feature at work:


I'll provide another link right here so you can jump right to it:
Google Ad Planner

The results are in

My group placed 3rd out of 21 teams in our school's ACM programming contest! We'll go on to represent the University of Washington at the regional tournament, along with the other two top teams from the UW.

The contest was to complete as many of 8 challenges as possible in 4 hours. Only three teams including ours completed 5 problems right, but we had the slowest time to do so. Some of the problems were actually kind of fun.

For example, this problem involved finding a specific kind of prime number variant named an "H-number semi-prime."

The regional tournament is on November 15 at the University of Oregon, can't wait!

(The rest of the problems/solutions are here.)