Saturday, February 6, 2016

YAGNI and Building In-House Frameworks

YAGNI - Ya Ain’t Gonna Need It

Write only what you need. It’s a profound concept. Engineers can’t help but overbuild things. For some reason this is inherent to being an engineer. In physical engineering, overbuilding is mostly an issue of up-front cost in terms of extra time and material. In software, there is also a substantial ongoing expense. The maintenance cost of code is related to its total size (1).

Therefor, minimizing the size of the code-base is an important goal. Using standard abstractions like functions and classes can reduce the total codebase size. This isn’t the same as building a framework.

What is a Framework?

A framework is a module. At their heart, modules are about encapsulation. Modules have an external interface and internal implementation. Better modules have simpler interfaces and more-isolated implementations.

Frameworks are different from other modules because they are designed to be used across multiple applications. Frameworks must be the best possible modules. In order to work across multiple applications, a framework must have the simplest possible interface and the most isolated implementation. Frameworks should also have their own codebase and be packaged for easy reuse.

Why Do We Build Frameworks?

If YAGNI were the only value, we would never build frameworks. By the time we’ve built a solution to the required specs, we ship. End of story. That’s what YAGNI tells us to do. If we only followed YAGNI, our applications would include operating systems, drivers, database, compilers and every other part of our dev and runtime stack. In other words, each new application would be enormous and have a fraction of the capabilities we enjoy today.

I said above that the maintenance cost of code is related to its total size. When we measure the size of code in an app we do not include frameworks. This is for good reason. The complexity a module adds to an app is proportional to its interface size and leakiness of its implementation. Frameworks are the best of modules. Their leakiness is minimal and their interface refined. A framework with millions of source-tokens may only add a few thousand tokens worth of complexity to a project using it. 

Are In-house Frameworks Worthwhile?

Clearly using other people’s frameworks is a big win. You get 100x or more leverage in terms of complexity. You only have to maintain your application’s code base and you get all the framework’s capabilities for a very modest price. Building a framework in-house at first doesn’t seem like a good idea. The total code-size you have to maintain will increase when you take an application and factor it into an in-house framework plus the rest of the app.

We talked about how application code-size is properly measured, but we haven’t talked about how that value relates to maintenance. Maintenance costs are proportional to complexity, and complexity’s relationship to code-size is non-linear. If you double the code-size, you will more than double its complexity (2).

Realizing that code-complexity is non-linear in code-size reveals why it makes sense to write frameworks even if they only have one app using them. If the application’s code-size is N-tokens before we factor out the framework, and let's assume that we can cut the application code in half by factoring out the framework. There is always some overhead in writing a framework due to interface and abstraction code. We’ll assume that overhead is 10%.

After the split, both the framework and app will have (1.1 * N/2) tokens, or (1.1 * N) total. For simplicity, our final assumption is a complexity-to-size factor of O(N2):

  • Complexity before split: N2
  • Complexity after split: 0.6 * N2
    • App: (1.1 * N/2)2
    • Framework: (1.1 * N/2)2
    • Total: 2 * (1.1 / 2)2  * N2

That’s a 40% savings! Granted, I made the favorable assumptions, but clearly it is possible to have large savings. Further, you don’t have to limit yourself to making just one framework. There are diminishing returns, but in my experience I've still found improvements with over 10 in-house frameworks.

Once you have a good framework, it is possible to re-use it in other apps. Then the savings really start to compound. If we assume just two apps, using the example above, the complexity savings increase to 55%. You also get code-size savings as well - about 18%.

When to use 3rd Party Frameworks

Obviously you should use an existing framework, if one exists, instead of writing your own. Right? Well, when evaluating the merits of a 3rd-party framework, there are a lot of things to consider. 

Let's start with technical aspects:

  • Does it do what you need it to do?
  • Does it meet your performance goals?
  • Is the source open?
    • Can you look at the source code? No matter how good the documentation is, there are always questions it doesn’t answer. If the source is open, you can get definitive answers. If not, you will be flying blind.
  • Is it OpenSource?
    • Can you contribute improvements back to the project?
    • How clear are the maintainers about what sort of contributions are acceptable?
    • Can you fork the project? This is only a last resort, but it is nice to have as an option. If you expect to fork early, you will be mostly maintaining your own, in-house framework. The problem with this is it is a codebase no-one in your organization knows well. Seriously consider writing your own in-house framework from the start.
  • How difficult will it be to switch frameworks later? 
    • How much of your code will directly interact with the framework?
    • If you are picking a UI framework, most of your code will be tied to that framework. Changing frameworks later probably means rewriting the app from scratch.
    • If you are using an encryption framework, like, say, md5, only a line or two of your app will use it. Changing that framework later is usually trivial.

There are also important non-technical aspects to evaluate:

  • Momentum. Usually there are multiple options for the same type of framework. Eventually, some die out and some thrive. It’s a good idea to use a tool like Google-Trends to determine which projects are thriving and which are dieing. If a framework dies, you may need to fork it to maintain it, and then you are back to maintaining an in-house framework.
  • Direction. 3rd party frameworks evolve outside your control. It is important to not only assess the current technical merits of the framework, but also, where is the framework going? What values and goals does the controlling team have? What values and goals does their organization/funding have? If your use-case is not squarely in their target use-cases, seriously consider looking elsewhere.

When to Write an In-House Framework

There are two main questions to ask each time you consider building a framework:

  • Is it the best of modules?
    • Is the interface simple?
    • Will the implementation be well isolated and minimally leaky?
  • Is there a reasonable chance you’ll reuse the framework on other projects? YAGNI argues you should be cautions making assumptions here, but if you think there is a > 90% chance you’ll reuse it even once, this can be a big factor.

If you haven’t written a line of code yet, should you even consider writing a framework yet? You should never write something unless you know for certain you will use it. Don’t build more than you immediately need for current requirements. In this, you should always follow YAGNI.

However, when looking at current requirements, it is reasonable to ask how you are going to meet them. As you do, you will be considering how to modularize your implementation. If you are doing an agile approach, this design work will happen in code as you go. If not, you may be doing some up-front design. Either way, there will be a point where you have modules.

As soon as you start to form modules, you should start thinking about if the modules make sense as a frameworks. If the answer is “yes” to both questions above, then package up the module immediately, put it in its own code-base, and declare it a framework. The sooner you do it, the sooner you can reap the simplification rewards. Once you do, keep following YAGNI. Continue to only add functionality as you need it.

Frameworks Clarify Thinking

Frameworks have another benefit beyond reducing complexity. Once you have isolated part of your code in a framework it takes on a life of its own. It has purpose beyond just serving the current app (though it should still be driven by that app's requirements ala YAGNI). A framework begs for clarity in its purpose. By drawing a line between your app and your framework you have to start thinking clearly about what belongs where. 

Don't expect to nail the framework's "purpose" in the first pass. Your framework will evolve as YAGNI drives it. Over time, though, clarity will emerge and you will have a new, powerful tool, codified in your framework, but also in your mental toolbox for solving and thinking about programming problems.

Writing Frameworks is Hard - and Worthwhile

I don't want to make this seem easy. Writing the best of all possible modules is hard! However, it is a learnable skill. You are only going to learn a skill be practicing it - a lot.

And what about YAGNI? Writing frameworks and YAGNI are not in conflict. You can write frameworks while observing YAGNI. After all, DHH, one of the strongest proponents of YAGNI, wrote Ruby on Rails.


  1. I measure codebase size in parse tokens rather than lines of code. Though still only an approximate measure, they are much better than LOC. They are the smallest meaningful unit in code. LOC measures several aspects of code which are ignored by the compiler including comments and whitespace.
  2. Codebase complexity can be understood in terms of graph-theory. Complexity comes from the number of possible interactions within the code. In the worst case, if you have N bits of code (tokens), you can have as many as N * (N - 1) or roughly N2 possible interactions. In practice the relationship between code-size and code-complexity is somewhere between O(Nk>1) < CodeComplexity(N) < O(N2).
    Modular design is all about reducing the number of interactions a chunk of code has with the rest of the code-base. This is how modules help reduce complexity.

Saturday, July 5, 2014

Amazingly Great Design Howto

Video or Blog

Originally, I created this content for a presentation. I then recorded a video, now on YouTube. This post is the third incarnation, the long-form blog. Please read on, or watch the 18 minute video if that's more to your liking.

Design Defined

de·sign (verb) \di-ˈzīn\
to plan something in your mind
Everything built or planned is designed. Putting forethought into something is designing. The difference isn't whether or not something is designed but rather how well designed it is — how much forethought was put into it.

Five Examples

ps vållö

All a watering can needs is a handle, a reservoir and a spout. Ikea manages to surprise and delight with this seemingly simple product. The proof is in the details.

more with less — Start with the handle. It is tapered so people with different sized hands can find a comfortable grip. Next, notice how it supports pouring. Its long tapered spout makes it easy to pour precisely. It even excels at the simple task of holding water. Being a single plastic mold it is unlikely to ever spring a leak. The lightweight plastic ensures that even with a small amount of water and a tapered base it is not very tippy. The design also minimizes production costs. It allowing Ikea to sell it for an amazing 99 cents and as a bonus, they stack.

emotional — Beyond function, it is beautiful. The lines are graceful. The shape is alluring. It makes you want to pick it up and feel it.


The goal of the Together iPad app from the World Wildlife Foundation is to increase awareness of endangered species and accept donations. The minimal requirements are a list of animals, their current status, and link to a donations webpage. Instead, they developed a deeply emotional experience.

compelling first impression — The app starts with a light, playful soundtrack. The screen then folds into an oragami panda. The music chreshendoes as we pans to a whole pack of pandas and the app's welcome screen. Tap "start" and the soundtrack morphs to a softer, pleasent background piece. Up until this point everything has been in black and white. A three second shuffling-card-slideshow of full-color animals transitions you into the app's home-screen.

beautiful, pervasive aesthetic — They brought a sense of elegance by integrating the origami theme. The theme is echoed at all levels of the app from the opening sequence to the sharing UI. Even the 3D globe appears to be made out of paper. The app's primary color palette is shades of grey. This makes the color portions of the app, such as the vividly colorful photos of the animals, stand out dramatically.

strategic — Charities often fail to clearly communicate why we should care. They are often too pushy, full of doom and gloom and ladened with guilt. This amazingly well designed app has none of those shortcomings. The majority of the app is about praising the majesty of the animals. It is inspiring and uplifting. It is anything but pushy. To even see the donation screen, you have to "unlock" the last animal ensuring the user is deeply engaged before asking for money.


invisible engineering — The Jawbone JAMBOX is an engineering triumph. It packs an amazing amount of sound in a tiny package, but it doesn't stop there. The packaging hides the speakers, and the box shape communicates a promise of simplicity. It is designed to run totally wireless. It has excellent battery life and uses bluetooth for audio. It's built-in microphone allows it to be used as a speakerphone. Though it targets wire-free use, the inclusion of a 3.5mm jack supports older devices and gives you an alternative when bluetooth doesn't work perfectly.

holistic excellence — This is a highly focused product. The goal is wireless, high-quality sound, simplicity and style. Individually these are goals any portable sound system might target, together with Jambox's flawless execution elevates the product to another level. It invites everyone to take off their headphones and share their music.


streamlined — The Balanced iPhone app by Jaidev Soin helps you track your daily goals with minimum distractions. Balance says completing your goals can be hard, your goal tracking app shouldn't be. Setup is accelerated by providing a catalog of common tasks reducing the number of taps required by over 90%. Logging when you complete a task is a single swipe gesture. Minimizing the most common and critical path makes the app effortless to use.

differentiated — Balance uses a unique set of fonts setting it apart from other apps, and the one fancy 3D transition manages to not be distracting and furthers its differentiation.


simple — The last example is the Nest thermostat. Targeting an industry that has been stagnant for decades, they reduced the number of controls to one dial. Even more amazing, the dial only does one thing: it sets the desired temperature. The display is minimal including only the current temperature, the desired temperature, a visual of their delta aligned with the dial and an estimate for how long the temperature change will take.

empathic — The elegance of the interface is a brilliant bit of design, but the true genius of Nest is what happens behind the scenes. It tracks every time you set the temperature and automatically learns your daily routine. It automatically programs itself and soon it starts adjusting the temperature for you according to your past preferences.

Extreme focus takes what used to be a heinously painful task of programming your thermostat and transforms it into an effortless and joyful interaction.

Amazingly Great Design Defined

a·maz·ing·ly great de·sign (noun) \əˈmeɪzɪŋl'ē grāt di-ˈzīn\
Design that exceeds expectations down to the last detail.

Three Pillars of Amazingly Great Design

Focus, details and tools are essential for amazingly great design. They can take a lifetime to master, but even a novice can make use of them immediately. With these basic ideas and a lifetime commitment to learning and improving their application, anyone can become a great designer.

First Pillar: Focus

"Focus is about saying no." - Steve Jobs

Time is your most valuable resource. Focus is the ultimate time management tool. Focus means learning how to use every moment of time for only the single most important thing you can do with it. Say 'no' to everything else.

customer archetype

The first thing to focus on is your customer. Instead of describing the average or most common customer, I recommend inventing a customer archetype. Your archetype describes a potentially real person. An archetype is like an average person, but there is difference. Your average customer may have 2.5 children. The archetype forces you to choose a real mom with, say, exactly 2 children. With that choice, you can achieve amazingly great design for moms with 2 children instead of merely good design for moms of 2 or 3.

use-story archetype

When the customer interacts with your product you are guiding them down a specific designed path. This path has a story. It has a beginning, middle and end. In the beginning the customer has a task they want to accomplish. They must decide to use your product and take action to begin their journey. In the middle they are working on the task. This is where they spend the most time with your product. By the end they have accomplished the task. They are rewarded not only by the desired result, but also some set of positive emotions. The very best stories have excellent beginnings, middles and endings. They are just the right length. You certainly don't want your story to be too long, but you also don't want it to be too short. Write down the archetypical story for your product, step by step, with storyboards. This is a single linear path through time. Think of it as a movie rather than an interactive product. Focus on this single story exclusively, and making it the best possible story it can be.

singular focus

This singular focus on one customer and one story ultimately leads to a better product. A highly focused product is easier to use. The product itself can communicate to the customer what it is for and how to use it. The product tells its own story. Another benefit of a highly focused product involves human perception. Our minds are tuned to notice things that stand out. Doing one and only one thing amazing is better than doing many things merely "good." An amazing product will be cherished and remembered. A merely good product will be quickly replaced and forgotten, even if it does more.

time = features * quality

In the end, Focus is the key to solving this equation. The time required to complete a project is proportional to the product's features and its quality. All too often people assume the feature-list is a hard requirement. If they have to meet a certain deadline, then quality has to be sacrificed. This decision always results in a mediocre product. Instead, if you want to make amazingly great products, then quality must be fixed a maximum. To meet a deadline, then, it is the feature list which must be culled. As you practice this methodology of extreme focus you'll find there are very few features which are requirements. As Jobs said, focus is about saying "no." To produce with maximum quality, keep saying "no" to features until the list is so short every last one of them can be implemented with excellence. The result will be a far better product.

Second Pillar: Details

"The details are not the details. They make the design." - Charles Eemes

The question then becomes, what details matter? This is a question which takes a lifetime to master. The first step is to learn how to broaden your scope. To inspire you, I'm going to cover four of the many types of details that might be important to consider when designing your product.


  • Where is the product used?
  • Is it loud or quiet, bright or dark?
  • Who is around?
  • What time of day will it be used?


Assuming the product is some sort of application or website:
  • Are all elements aligned exactly?
  • Is there adequate white-space to make the viewer comfortable?
  • What colors are used and are they used consistently?
  • Is the app perceived to be performant and immediately responsive?
  • Do the animations reduce distractions or are they themselves distracting?
  • Are the fonts legible? Do they invoke the right emotional response?
  • How are errors handled?

customer archetype

  • What is their day like?
  • Who are the important figures in their life?
  • What social groups do they belong to?
  • What are their hopes and desires?
  • What will the person be thinking just before they use the product? Just after? 
  • Will they be thinking about the product while not using it?
  • What do we want them to feel when they use the product?
  • How will our customer want to be perceived while using our product publicly?


  • How will the customer learn about the product?
  • Where will they first see it?
  • Where will they first "touch" it?
  • When is their first real engagement?
  • What is their daily engagement?
  • What is their last engagement?
  • How does the product reoccur in their thoughts after their last engagement?
  • What details will help to reengage the user with this or other products?

Third Pillar: Tools

"Nothing is original. Steal from anywhere that resonates with inspiration or fuels your imagination. Devour old films, new films, music, books, paintings, photographs, poems, dreams, random conversations, architecture, bridges, street signs, trees, clouds, bodies of water, light and shadows. Select only things to steal from that speak directly to your soul. If you do this, your work (and theft) will be authentic. Authenticity is invaluable; originality is non-existent. And don’t bother concealing your thievery - celebrate it if you feel like it." - Jim Jarmusch
The third and final pillar of great design is your idea toolbox. These are the tools and patterns you use to create the product and exceed expectations in the details. A designer's toolbox is constantly expanding and evolving. The best designers make a continual effort to improve it by all means available.


Keep a design notebook. As you start noticing good and bad design in the world, start taking notes. This helps you clarify your thinking on the design and gives you something concrete to come back to when you need it.


Develop a well-considered opinion. In order to be a great designer you need to learn to care deeply about great design. You need to be able to not only distinguish between good and bad design, but also articulate why it is so. Be prepared to offend people. If you don't, then you aren't pushing the envelope.


Constantly experiment with your tools. Free yourself of the constraints of your real projects and allow yourself to explore freely to discover great new possibilities.


Creativity is equal parts experimentation and inspiration. You need to constantly feed your brain new stimulus from the outside world. This includes trying out competitors products, but it also includes getting inspiration from completely different fields. Visit great works of art and architecture. Read voraciously, explore nature, take classes, go to conferences, read blogs and listen to podcasts.

Designer's Amnesia

In addition to the three pillars, I have one important word of caution. The processes of design and implementation unavoidably leads to the designer memorizing the design. Any design, good or bad, can become "intuitive" to anyone who memorizes it. One loses objectivity and empathy for new users the more one uses a product, and it's worse if you are the designer.

Keep the following questions in mind:
  • Is your focus the right one?
  • Are there failures in details you can no longer see because you've memorized them?
  • Is there a tool that obviously solves a problem better but you can no longer see it?
Explaining what you are working on to someone new is a good way to expose these shortcomings. It is even better to give them a prototype and watch them use it. Video the session and study it in detail for every little success and failure. Often you'll be slapping your forehead in minutes.

Impact of Amazingly Great Design

Many companies are committed to amazingly great design including Apple, Herman Miller, Blizzard, Jawbone, 53 and IKEA. Each of these companies have been successful largely because of their great design.


perceived value — Repeatedly exceeding expectations dramatically increases the customers perception of your product's value. You can charge more, customers will seek you out and you will stand out amongst the competition.

brand — Great design creates good will towards your brand. It is one of the most effective ways to show your customers you care about them. They will, in turn, begin to care about your brand and even come to love it.

actual value — Great design adds real, tangible value for the customer. Historically design has been considered window dressing - a frivolous veneer on the product which may sell 10% more. Thankfully, it is now clear that great design dramatically increases the value for the customer, and here's why.


time — Great design saves time. Just as time is the designers ultimate resource, it's also our customer's most important asset. All great design takes the customer's time into account and gives them the most bang-per-second.

reduced stress - Great design reduces stress and fatigue. Rough edges both literally and metaphorically wear us down and suck our energy. A poorly design product may get the job done, but we'll be emotionally and physically exhausted after using it. Instead, an amazingly designed product could actually energize, excite and slingshotting us to the next task of the day.

beauty and delight - Great design brings beauty and delight to our lives. Great design goes beyond the veneer of frivolous window dressing. Its beauty reaches deep inside the product and impacts us on many levels. It can inspire, sooth and bring joy. It can even impact us when we are not using the product. These positive emotions impact the bottom line for everyone. We are more productive under their influence and happier in life.

Zen of Amazingly Great Design

Each of the three pillars of great design is a never ending path towards mastery. We are constantly inventing and discovering new tools. There is always the next layer of details to consider, and a good designer is constantly refining their ability to separate the important from the unnecessary.

focus — Say "no" to everything but the most important features. Practice deep empathy with the customer to identify those essential features. Reduce the scope of the project until there is enough time to implement every aspect with excellence. Paradoxically, reducing a products features usually results in a better product.

details — Train your mind to be precise and attentive. Learn to see products from every angle and see every minute flaw. Discovering what details matter is equal parts science and experience gathered over a lifetime.

tools — As you progress you will learn thousands of tricks, patterns and solutions you can employ to implement your design. Each time you finish one design you'll have new and better ideas for the next one.

Overall, the key to becoming an amazingly great designer is to be aware of these pillars, follow your own passion and keep an open mind. Insight can come from the strangest places.

Further Reading

Sunday, December 15, 2013

Principle of Exposure and Transparency - POET

The Visibility Problem

We have a problem in programming. The majority of our work is invisible. It's invisible to the end user. It's invisible to us. We can only see ~50 lines at a time of the thousands and millions of lines of code in our programs. Imagine a miopic Leonardo da Vinci who could only focus on a square inch of canvas trying to paint the Mono Lisa or even the Sistine Chapel.

Most modern debuggers can only show a dozen variables and a stack trace. Generously, that represents no more than a few hundred bytes of memory. Our running programs are measured in megabytes if not gigabytes. In anything but the most trivial program, we can't see more than a small fraction of a percent of our paused runtime state. When our creation is actually running, we are blind.

Two Challenges of Programming

All difficulties in programming can be separated into two categories. There are the problems due to core computer-science limitations or limitations of our personal understanding. These are legitimate challenges which require real engineering, design and exploration. All other problems are due to a lack of understanding of what our creation is actually doing.

One way to measure a programmer's skill is how well they can simulate programs in their head. This can be measured concretely by how much code can they write without error without running or compiling. Mental program simulation is the only way we can mange the complete lack of visibility in running programs. The best programmers have developed an intuitive sense about running programs over years and decades.

Simulating programs in our head is a major part of modern programming. This is broken. The computer is infinitely better at running programs. There is a monumentous opportunity to improve programming by developing better tools for inspecting, exposing and making our running programs transparent.

The Principle of Exposure and Transparency (POET)

POET: All bugs are trivial once their cause is exposed; given enough runtime transparency, all bugs are trivial.

The vast majority of bugs only require a few lines to fix. Most of our debugging time is spent trying to understand bugs well enough to know what two lines to change. POET embodies this observation: All this wasted time can be reclaimed with better instruments for understanding our running programs.

Linus's Law

Given enough eyeballs, all bugs are shallow. - Eric Raymond, The Cathedral and the Bazaar

POET is a generalization of Linus's Law. Getting more people looking at the code - "enough eyeballs" - is one way to better expose the code's runtime properties. However, it is a very inefficient method. It is akin to saying "with enough miopic da Vincis, we can paint the whole Mono Lisa." While perhaps true, a better solution would be repair his vision so Leonardo can do it without assistance.


  1. Pay attention the next time you run your code. Why are you running it? What information are you attempting to gain? How much time does it take to gather this information? Be sure to include the time it takes you to context switch, type in commands, wait for the run to start and do whatever interaction it takes to bring the program to the required state. How might you gain that information quicker with better tools? LiveReload plugins for web-page development is one such example.
  2. When you are working on a bug or performance problem, note how much time you spend understanding the problem vs how many lines of code were changed in the final fix. If you could send that patch back in time, how much time would you have saved? Note the key insight along your discovery path led to the final solution. How could you have gotten that insight sooner? ( Spark Inspector was just that tool for us in a recent debug jam session for our iPad app. )

Wednesday, October 9, 2013

Bugs and Mutations

It took me hours to find this bug, and it turned out to be pretty surprising. I had good check-ins before and after the change. I was refactoring my code to make the rectangle class immutable. After the change text was no longer positioned correctly:

correct position

incorrect position

I changed one line in my text-layout code to be compatible with immutable rectangles:
- metrics.area.location = metrics.area.location.neg.add offset
+ metrics.area = rect metrics.area.location.neg.add(offset), metrics.area.size
I can tell you there were no bugs in the new immutable Rectangle class.

Can you spot the bug?

There is no bug. The new line is correct, and yet that's all I changed.

It turns out I originally had a bug due to a mutation I wasn't taking into account, but that mutation made the layout algorithm work. When I stopped mutating the rectangle object, the "bug" stopped making the algorithm work. The reason it took me hours to find this bug was the new code was "right", but the algorithm was wrong.

Here's what was actually wrong, in 3 code snippets (CoffeeScript):

1) The original code that worked but had an accidental mutation:
    updateTextLayout: ->
      offset = point()
      @area = @metricsList[0].area  # object assigned here
      for metrics in @metricsList
        metrics.area.location = metrics.area.location.neg.add offset  
          # gets mutated here the first time through the loop
        offset = offset.add 0, @fontSize
        @area = @area.union metrics.area
      @size = @area.size
2) Code with one line changed that seemed correct but didn't work:
    updateTextLayout: ->
      offset = point()
      @area = @metricsList[0].area
      for metrics in @metricsList
        metrics.area = rect metrics.area.location.neg.add(offset), metrics.area.size  
          # @area no longer gets mutated
        offset = offset.add 0, @fontSize
        @area = @area.union metrics.area
      @size = @area.size
3) Final working code:
    updateTextLayout: ->
      offset = point()
      @area = null  # FIX - don't capture the wrong value here
      for metrics in @metricsList
        metrics.area = rect metrics.area.location.neg.add(offset), metrics.area.size
        offset = offset.add 0, @fontSize
        @area = if @area then @area.union metrics.area else metrics.area    
          # FIX - capture the right value here
      @size = @area.size

Wednesday, September 11, 2013

Sashimi Coding

Sashimi is a Japanese delicacy consisting of very fresh raw meat or fish sliced into thin pieces. - Wikipedia
Sashimi-coding* is the art of slicing up code into the smallest possible parts. Sashimi-coding works best when used consistently across the entire application. It may seem painful at first, but once you get used to it, you'll wonder how you ever lived without it.

Sashimi-Functions are Tiny

Sashimi-functions are the smallest possible functions.

  • 10 lines max for dynamic languages (Javascript, Coffeescript, Ruby, Python)
  • 20 lines max for static languages (Java, C++, Objective-C)

The Five Benefits of Sashimi-Functions

  1. Easier to understand
  2. Easier to test
  3. More reusable
  4. Self documenting
  5. Inheritance & monkey-patching friendly

Easier to Understand

A function which is twice as long is more than twice as hard to understand. Sashimi-functions are not just a little easier to understand, they are typically much easier to understand.

Easier to Test

Breaking a large function into sashimi-functions allows you to test simpler components in isolation before testing them together.

More Reusable

Slicing a function into many sashimi-functions opens up the possibility of reusing sub-parts of the original function.

Self Documenting

Comments in the middle of functions are a code-smell. Sashimi-functions eliminate the need for these comments. Split the function in two, and the comment becomes the name of the new function.

Inheritance & Monkey-Patching

In both cases, adding custom code must be done in whole-function units. Sashimi-functions make it easy to augment or replace only the code you care about.

Performance Cost?

There is one down-side. There may be a performance cost to sashimi-functions. In static languages the compiler can usually inline away any overhead, but in dynamic languages it depends a lot on how smart the runtime environment is. 

In almost all cases the large increase in developer productivity wins over the small decrease in performance. As always, avoid premature optimization and profile-first so you only optimize what needs optimizing.

* I heard the term Sashimi Coding first from Jason Thane who in turn heard it from Nathan McCoy.

Tuesday, June 11, 2013

Riak and Monotable

The Imikimi Monotable project has been placed on indefinite hold. Unfortunately we don't have the manpower. It is an excellent solution to our back-end data-store needs, and probably for many others as well. However, it is still going to require a lot of work to bring to production-ready.

Instead, we are looking seriously at Riak for our back-end store. We hope to put all our Kimi-data and most of our Sql-data in two separate Riak clusters. Riak has several benefits that Monotable was designed to solve:
  1. no central server - every node is the same and any node can respond to any request
  2. scales easily by adding one node at a time 
  3. can configure replication levels on a per-bucket basis
  4. supports map-reduce
  5. can store binary data - up to 16 megabytes per record (this our requirement, not Riak's exact max size)

However, Riak has some down-sides:
  1. Riak's "eventually consistent" system only makes progress on a record's consistency when it is read. It is not clear that any progress is made if the record is never read after a write or consistency failure. This means the latest version of a record could go under-replicated indefinitely.
  2. Riak's scaling is limited by your initial "ring-size". My hazy understanding is we need to set our ring-size to 20x our max expected server-count.
  3. Riak has a lot of cross-talk between nodes. There is potentially an upper limit of 300 servers before performance degrades.
  4. Riak does not allow range-selects on the primary key
  5. The behavior and scalability of secondary indexes is not clear to me. Typically distributed hash tables can't do secondary indexes. Riak has secondary indexes, but there is probably a catch that we don't understand yet.
  6. I don't think Riak has "live" map-reduce. 
Monotable is designed to achieve all of the above goals and scale to very large sizes. However, we are a long ways from needing >300 servers. As long as Riak's indexes work reasonably well and we can do off-line map-reduce jobs without disrupting site performance, it should be good enough for us for now.

Monotable and Map-Reduce

Live map-reduce was not an original requirement for Monotable. However, it is a very powerful feature. It would bring Monotable from being a simple key-value store with basic range-selects to a system with powerful indexing and querying capabilities. It turns out the core of Monotable is well suited for it.

In an offline map-reduce, each chunk can be stream-processed by the mapper and fed into the reducer. Once a chunk has been reduced to a single output, the results of all chunks can be merged until a single overall result is output. If the reducer can write data back to Monotable, you can use this to generate secondary indexes. 

These indexes are more powerful than SQL indexes which have a 1-to-1 mapping between source and index records. With the reduce step we can arbitrarily choose to index at any level of reduction. In fact we can store the result of every reduction if we wish. This allows us to generate an index + aggregate hybrid. With this data structure we can compute the map-reduce result over any sub-range in O(ln n) time.

This much was already a possibility within the original Monotable requirements. Just take the Monotable core and add a standard map-reduce system over top. The question becomes how can we make it live-updating?

Acknowledgment: Live-Map-Reduce is not new. I believe CouchDB does this already. CouchDB, however, doesn't scale easily to large distributed clusters. 

Live-Updating Map-Reduce in Monotable

Anytime a source-record is changed, the off-line generated index will become out-of-date. Using normal map-reduce, we'd have to delete all the old data and re-run the map-reduce. Deleting a large range of records is fast in Monotable, but re-running the map-reduce will be slow. Since we are already storing the entire reduce-tree, couldn't we re-map the changed record and then update only the O(ln n) reduce steps which depend on it?

Structure Definitions

First, I need to briefly describe the structure of Monotable. The entire Monotable stores all records, sorted by key. Monotable is logically partitioned into "ranges" which are similar to separate "tables" in other stores. Each range is broken up into one or more 64 meg "chunks". Each chunk exclusively covers a sub-range of the overall Monotable. All records in Monotable with keys >= the chunk's start key and < it's end key are stored in that chunk.

To keep things simple, let's separate out map-reduce. Each range in Monotable can have zero or more mappers or reducers. A mapper takes each record and transforms it and then writes the results back into Monotable in a different range. Each reducer takes all records in one chunk and reduces them down to one record which is written, again, to a different range. In both cases, the new range can in turn have a mapper or reducer. 

To configure a standard map reduce, we would apply a mapper to our data-range which write records to another range we'll call the "index". The index-range would have a reducer which write records to a meta-index-range. This meta-index-range would in turn have the same reducer step to yet another meta-meta-index-range. This continues until the meta-meta-meta-*-index-range fits within one chunk.

Live Updating

Now that we have a sense of our data-structure, how do we keep it up to date? Due to the nature of distributed data, we can't afford to do it synchronously. Monotable guarantees atomic operations within a chunk, but provides no guarantees across chunk boundaries. 

When a record changes, the first step is to mark it's chunk as "dirty" with respect to all mappers and reducers applied to that chunk. Asynchronously, the master server for each chunk can later initiate the process of "cleaning" the chunk by updating all effected maps and reductions.

Unfortunately, simply re-applying the map or reduce step for the chunk doesn't work. The mapper may generate arbitrary output based on the record's data. If we naively insert the new value in the index we may be forgetting to remove the old value, which may be anywhere else in the index. We must have both the old and the new value so we can delete the old value before inserting the new one. Note that if the mapped old and mapped new values are identical, we can skip the rest of the update. 

Keeping the old value of a record adds complexities, particularly since we want to allow more than one active mapper or reducer. For every mapper/reducer we need to be able to access the version of every  changed records as they were the last time that mapper/reducer ran. 

A New Chunk Data Structure with Versioning

I believe the answer is similar to how CouchDB stores its entire database - as a continually appending log representation of a b-tree. This format keeps a complete revision history of all changes. Each mapper or reducer just needs to track the offset of the snapshot when it was last run. 

If we limit this to each individual chunk, then we avoid the main problem of CouchDB: it is painful to compact large databases. Since chunks are limited in size, we always have relatively small files which will be fast to compact. We have to be a bit careful when we compact chunks to ensure that we don't lose any of the snapshots that the map/reducers need. However, if they are kept up-to-date at roughly the same rate as our compaction schedule they should usually be fairly up-to-date and we only need to keep the most recent few snapshots. We just need a compaction algorithm that takes into account a list of snapshots that must be maintained after compaction.

Keep in mind that all this snapshotting and revision tracking is managed within one server. No synchronization needs to happen with other servers in the cluster. 

As a side-effect, Monotable gains a general snapshotting system. On a chunk-by-chunk bases we could establish any arbitrary history tracking plan up to tracking all history.


Now we know how on map/reduce step will stay up to date. The rest of the system falls out automatically. The mapper will dump its outputs into a separate range of Monotable which in turn will become "dirty" and trigger a reducer step. The reducer will write to yet another range triggering another reducer step. This will continue until the source range is reduced down to <= 1 chunk.

Chaining will add some latency to the system. Each step invokes an asynchronous delay between being marked "dirty" and the master-server for that chunk scheduling the map/reducer action. The good news is we are effectively working with a tree with very high branching factor. Pessimistically, given the minimum chunk size of 32megabytes and a large, 1k record size, we have a branching factor over 32,000. A two-level tree can address 1 billion records. Four levels can track 1 quadrillion records.

My other concern is how much work this might involves if there are random changes happening all over the source range all the time. Due to the asynchronous nature of the system, though, the answer is good. In the worse case, at the leaf level, there may be as many as one map operation per record change. This could be bad, but the mapper algorithm could be designed to run in time proportional to the number of changes. One change will only require a small amount of work to update.

As we chain "dirty" updates up the reduction tree, the story gets better. If several leaf nodes of one parent change at the same time, they will all mark their parent node as "dirty", but they won't each trigger a new reducer step. When the parent node's server schedulers the mapper step it will integrate all changes from its leaf nodes in one pass.


The result is quite elegant. Each individual record change would trigger approximately 'k' steps of work reading/writing only approximately 'k' records - where 'k' is the depth of the reduction tree <= log(n) / log(32000) - n == number of records in the source range. K is <= 2 for n <= 1,000,000,000 records, and K is <= 4 for n <= 1,000,000,000,000,000,000 records. If records are changing faster than the reduction steps can propagate up the tree, k will become smaller since updates up the tree can cover more than one child-node per update. K will approach 1 as the speed of record updates increases. The system gets more efficient as it becomes more loaded.

Thursday, January 31, 2013

Parsing JSON the Not-So-Hard Way With Ruby and Babel Bridge

Aaron Patterson recently posted this article on Parsing JSON the hard way using Racc. I think he did an excellent job explaining Racc. However, it was painful. Racc is an LALR(1) parser-generator similar to Yacc. While Yacc was fun to learn in school, it's also painful to use. LALR is hard to debug ("shift-reduce conflict" - !@#$% - if you know what I mean), and the parser generation steps are tedious to set up and maintain. There is a better way...

Enter Parsing Expression Grammars. I learned about PEGs from Treetop. Think of PEGs as greedy regular expressions with recursion. Being greedy, they don't try every possible pattern-match. This turns out to be a good thing; it makes them much easier to understand and debug. Adding recursive rule-matching to regular expressions makes PEGs approximately as expressive as LALR(1) parsers (though not identical). Treetop got me excited to work with parsers again, but sadly it still had some of the awkwardness of Yacc-style parser-generators. You have to build "treetop" files into ruby files before you can use them. There is yet an even better way...

Enter Babel Bridge (github). I wanted a PEG based parser-generator that allowed me to use 100% ruby with no extra build steps, so I built Babel Bridge. I've been evolving BB for over 2 years now. It is a powerful tool for building easy-to-understand parsers.

Here is how to write a JSON parser using the Babel Bridge gem. If you want to skip to the punch-line, here is the JSON parser source code.

Writing a JSON parser with Babel Bridge

First, install the babel_bridge gem:
gem install babel_bridge
With Babel Bridge you can create many different parsers and have many instances of each in one runtime. To define a new parser, create a class and inherit from BabelBridge::Parser.
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  # define the parser here
The main component for defining your parser is the "rule". A rule is a named pattern for matching strings of characters. The first parameter of the "rule" method is the name of the rule. The remaining parameters specify one or more patterns to match. For more detailed info, please see the readme.

There are five literal values that are allowed with JSON: string, number, true, false and null. Let's start by making rules for each of them. (Credit: I used Aaron Patterson's regular expressions he derived from
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  rule :value, any(:number, :string, :true, :false, :null)

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"
In addition to the five rules for the literals, I added two more lines of code. First, I added a general rule called :value. It matches any of the five literals. Babel-Bridge starts matching using the first rule you declare. That "root rule" must include everything you want to match. JsonParser will now match any of the JSON literals. Second, I added a "shell". It is a Babel-Bridge tool to help make parser-testing easier. Try running the above code and typing in some JSON literals at the prompts.

> "string literal"

Parse tree:
  ValueNode1 > StringNode1 > "\"string literal\""

> 123

Parse tree:
  ValueNode1 > NumberNode1 > "123"

> null

Parse tree:
  ValueNode1 > NullNode1 > "null"
We are halfway done. There are two more important patterns for JSON: objects (hashes) and arrays. Arrays consist of 0 or more :values, delimited by "," and wrapped in "[]". Objects consist of 0 or more :pairs, again delimited by "," and wrapped in "{}". Pairs consist of a :string, then a ":", then a :value.
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  rule :value, any(
    :object, :array, :number,
    :string, :true, :false, :null

  rule :array,  '[', many?(:value, ','), ']'
  rule :object, '{', many?(:pair,  ','), '}'

  rule :pair, :string, ':', :value

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"
You can try out the new rules:
> ["my string",123,true]

Parse tree:
  ValueNode1 > ArrayNode1
    ValueNode1 > StringNode1 > "\"my string\""
    ValueNode1 > NumberNode1 > "123"
    ValueNode1 > TrueNode1 > "true"

> {"my key":"my value"}

Parse tree:
  ValueNode1 > ObjectNode1
      StringNode1 > "\"my key\""
      ValueNode1 > StringNode1 > "\"my value\""
If JSON allowed literals to stand alone, we'd be done. Unfortunately JSON is a little more restrictive, so we have to add a new root-rule to ensure there is an array or object at the top-most level.

There is one other thing we need to add. Parsing-Expression-Grammars match every character or fail. Right now we are not handling white-space, so any white-space character in our string will cause our parsing to fail. BB makes this easy. Just call "ignore_whitespace" in your class declaration.

Below is the complete JSON parser. It should match any legal JSON and reject anything illegal. However, it just returns the parse-tree when it succeeds. In the next section we'll add the same functionality Aaron did in his blog post.
require "babel_bridge"

class JsonParser < BabelBridge::Parser

  rule :document, any(:object, :array)

  rule :array,  '[', many?(:value, ','), ']'
  rule :object, '{', many?(:pair,  ','), '}'

  rule :pair, :string, ':', :value

  rule :value, any(
    :object, :array, :number,
    :string, :true, :false, :null

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"

Adding Functionality to The Parse Tree

Every rule you define creates a node class. Every time an instance of that rule is parsed, an instance of that node class is created. With Babel-Bridge you can easily define methods on the parse-tree nodes for each rule you declare. When calling the rule method, just open up a do-block. The code inside the do-block is executed inside the class for that node.

Our goal now is to convert the resulting parse-tree from our JSON parser into the equivalent Ruby Hashes, Arrays and Strings etc. We are going to add an "evaluate" method to our nodes which returns the correct Ruby data-structures. For example, here is how we can add the evaluate method to our :null rule.
  rule :null, "null" do
    def evaluate; nil end
To evaluate the remaining JSON literals we can leverage the fact that Ruby's literals are nearly identical. In fact, "null" is the only one which is different. To avoid duplicating code (DRY!), I'm going to insert an extra rule called :ruby_compatible_literal. Calling to_s on a node just returns the source string that node matched. Using Ruby's "eval" method, we can evaluate that string and get the Ruby object back.
require "babel_bridge"
class JsonParser < BabelBridge::Parser

  rule :document, any(:object, :array)

  rule :array, '[', many?(:value, ','), ']'

  rule :object, '{', many?(:pair,  ','), '}'
  rule :pair, :string, ':', :value

  rule :value, any(:object, :array, 
    :ruby_compatible_literal, :null

  rule :ruby_compatible_literal, any(:number, 
    :string, :true, :false
  ) do
    def evaluate; eval(to_s); end

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null" do
    def evaluate; nil end
Next, let's add the evaluate method to array. When there are nested rules, you can access them by name. If that sub-rule can be matched more than once, it will return an array of the child nodes which were matched with that rule. Here, the #value method returns a :value nodes in matched in the array. We just need to convert that array to the #evaluated versions of each :value node.
  rule :array, '[', many?(:value, ','), ']' do
    def evaluate; value.collect {|v| v.evaluate}; end
Evaluating Objects takes two steps. The :pair rule returns a 2-element array of the form: [key, value]. Then the :object rule uses the Hash[] constructor for the final result.
  rule :object, '{', many?(:pair,  ','), '}' do
    def evaluate; Hash[ pair.collect {|p| p.evaluate } ] end

  rule :pair, :string, ':', :value do
    def evaluate; [ eval(string.to_s), value.evaluate ] end
Here is the full source-code for parsing JSON and generating Ruby data structures.
require "babel_bridge"

class JsonParser < BabelBridge::Parser

  rule :document, any(:object, :array)

  rule :array, '[', many?(:value, ','), ']' do
    def evaluate; value.collect {|v| v.evaluate} end

  rule :object, '{', many?(:pair,  ','), '}' do
    def evaluate; Hash[ pair.collect {|p| p.evaluate } ] end

  rule :pair, :string, ':', :value do
    def evaluate; [ eval(string.to_s), value.evaluate ] end

  rule :value, any(:object, :array, :ruby_compatible_literal, :null)

  rule :ruby_compatible_literal, any(:number, :string, :true, :false) do
    def evaluate; eval(to_s); end

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null" do
    def evaluate; nil end
source You'll notice that we didn't have to define evaluate on every node. Babel-Bridge has some intelligent defaults to help minimize code-size. Now run the code and enter some JSON values:
> [null]
 => [nil]

> {"my key":"my value"}
 => {"my key"=>"my value"}
Notice that the shell stopped printing our parse-tree. The shell looks for the "evaluate" method on the root node. If it exists, it prints out root_node.evaluate.inspect. You might also try inputing some illegal values. This shows off one of Babel-Bridge's powerful debugging tools - the parser-failure-info.
> [nil]
Parsing error at line 1 column 2 offset 1


Parse path at failure:

Expecting one of:
  "["                                                ArrayNode1
  "]"                                                ArrayNode1
  "false"                                            FalseNode1
  "null"                                             NullNode1
  "true"                                             TrueNode1
  "{"                                                ObjectNode1
  /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/ StringNode1
  /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/      NumberNode1
If you want to use your parser in real code, you probably won't want to use the shell. Here's how:
json_parser =

parse_tree = json_parser.parse "[null]"

if parse_tree
  ruby_data_structure = parse_tree.evaluate
  puts ruby_data_structure.inspect
  puts "ParsingError: " + json_parser.parser_failure_info
For further reading, you might be interested in my earlier blog post: How to Create a Turing Complete Programming Language in 40 Minutes (and 70 lines of code).