Design Patterns vs Algorithms

Posted by on Sep 9, 2010 in Design Patterns, RIA | 0 comments

How Come they Get Calculus and We Get Sticks and Arrows?
I’m still playing with Skip Lists: A Probabilistic Alternative to Balanced Trees by William Pugh. I have yet to work up an ActionScript 3.0 solution for both inserting new data into a skip list and deleting data from one—even though there’s lots of code that shows how to do it. It’s more fun to look at Pugh’s article with the pseudo-code that he provides to show how to insert/delete data in skip lists. Were I working to figure out a design pattern, I’d be looking at a bunch of association arrows, dashed line instantiation trails and diamond-tailed aggregation spears—just like poor old wound man.

Some of the key parts of Pugh’s article, along with lots of articles you see in professional programming journals have all of these cool formulas. If you’ve seen Flash Math Creativity: 2nd Ed by Keith Peters and some other folks, you’ve seen lots of formulas like the one’s in Pugh’s article although Flash Math Creativity tends to be more trigonometry and geometry than calculus—in any case they’re über cool.

So how do we calculate the efficiency of Design Patterns? The algorithm crowd gets all kinds of cool formulas from every nook and cranny of math—even statistics in some

cases. However, in going through The Gang of Four’s Design Patterns, there’s not a single formula that has that kind of proof.

Here’s What I’m Talking About…

In discussing how to work through the cost of running a skip list versus a balanced tree, Pugh offers the following formula:

C(0) = 0
C(k) = (1–p) (cost in situation b) + p (cost in situation c)

which he follows up with:

C(k) = (1–p) (1 + C(k)) + p (1 + C(k–1))
C(k) = 1/p + C(k–1)
C(k) = k/p

Eventualy he comes up with the total expected cost to climb out of a list of n elements as:

≤L(n)/p + 1/(1-p) which is O(log n)

In all of this, C(k) is the the expected cost —length— of a search path that climbs up k levels in an infinite list. So now Pugh can take his formula to the Balanced Tree makers, and say,

See, my formula proves that Skip Lists work as well as Balanced Trees and they take less effort.

So with formulas you can demonstrate mathematically and using math logic that a certain course of action is a reasonable one. So where do we start looking for formulas that can:

  • Help determine which pattern to use
  • Prove that a design pattern is a better choice over a non-design pattern

Why not start with OOP principles and see if they can help?

Liskov’s Substitution Principle and Related Formulas

In her 1994 paper with Jeannette Wing, Barbara Liskov proposed the following principle:

Let q(x) be a property provable about objects x of type T. Then q(y)should be true for objects y of type S where S is a subtype of T.

That’s something like what we need. However, it can be risky trying to write formulas when what you really need is a better understanding of the tools at hand (if indeed they can be called tools). For years in research sociology, I insisted on ethnographic studies because I didn’t trust survey data—what strangers say to other strangers that somebody writes down. Repeating the process thousands of times doesn’t exactly increase validity. It just makes it easier to do statistical analysis. The same is true with design patterns; writing a formula for the sake of writing formulas does not increase either understanding or validity.

The problem with ethnographic research, while rich contextually, is that it’s difficult to analyze. When you start seeing the same thing over and over again, you can be pretty sure you’re looking at a pattern of behavior. (Kids being trundled off to school at a certain age is a pattern observable in most societies.) With design patterns we’re in a lot better shape because the Gang of Four has done the work for us as far as identifying patterns. So, I guess we’re really not looking for formulas like Liskov used in her succinct description of her substitution principle.


The Other OOP Principles–How Did they Become Principles?

In going over the other OOP principles I didn’t find any more formulas that could be tested or proven with some kind of calculus. So how did the principles become principles? For the most part they were solutions to problems that were tested and found to work. Basically, it was an inductive process. If something worked (again and again), it was formulated into a principle. For example, the stricture that objects should be loosely coupled is based on the fact that if they’re not, when change is introduced or you attempt to reuse an object, it gets tangled up in dependencies to other objects. They tend to be simple principles based on successful use. No formula needs to be used to clarify or better formulate the principle.

How to Move Forward With Design Patterns

First of all, really get to know the principles behind both OOP and design patterns. They make up the context of the patterns in that they’ll help you ask the right questions about programming. The whole design pattern discussion is based on reasons for using design patterns, and if you don’t begin looking at the principles, your head will be in the wrong context. For example, a typical question for algorithms is,

Will this make my program run faster?

That’s not a good design pattern question because design patterns were not developed to make programs run faster. Algorithms do that. Design patterns were developed so that the process of creating programs (big complex ones) would go faster. The principles all help enhance the development process.

Every ActionScript 3.0 programmer should know from experience that the single constant in programs is they change constantly. The idea that you cook up a program in Flash or Flash Builder and dust off your hands and you’re finished with it is pure bunk! If you build an excellent program, you can go in and both re-use parts, change parts and update it for years before you have to tear the whole thing apart. That’s where design patterns come in.


Get Over MVC! One Size Does Not Fit All

Second, forget MVC. The Model View Controller was developed prior to the Design Pattern catalog to ensure loose coupling. That’s history, but now, 15 years on from the introduction of the Design Pattern catalog, too many developers stilluse MVC for every application where they need loose coupling—including wholly inappropriate applications that could be done better with one of the many new patterns. It’s like using ActionScript 1.0 for every application years after it was supplanted first by ActionScript 2.0 and then ActionScript 3.0.

Design Patterns are Not Easy, But One Day You’ll Get Them

Third, design patterns are important but not easy. As a reminder, (just in case you needed one), ActionScript 3.0 design patterns are difficult to learn and use. Once you get them, you’re truly in a different world. Chandima and I are still working to get them right, and we’ve been at it for a while. The intellectual challenge is unlike anything else in programming that I’ve encountered. That includes machine and assembly level programming. So, you have to be patient. There’s no magic bullet.

The importance of design patterns lies in complex programs that need regular (if not constant) updating. When I made my website, I was giddy over the fact that I used a design pattern (State) in the video portion of it. The rest, while given a great deal of thought to updating, was not done with a design pattern, and now that I have to re-do it, I’m going to have to start from scratch except for the video portion. On top of that, I dread the design portion (making it look good), but the site will include design patterns for both the ActionScript 3.0 and PHP portions. So that the next time I have to do some major re-modeling, the site will be able to handle the changes with aplomb.

Where Do We Go From Here?

We’ve been maintaining this blog for years now, and are now at a crossroads. Both Chandima and I have had other projects that we’ve had to take care of, and I’ve been doing more with both HTML5 and PHP design patterns. However, I have no intention of abandoning ActionScript 3.0—in fact quite the opposite. What I’d like to do is to move ahead with ways where ActionScript 3.0 design patterns are more accessible. In other words, I want to write more posts on this blog that are examples of using design patterns so that both the implementation and purpose are made clearer. The goal is to ease readers into design patterns and OOP as their natural way of programming. Your ideas and thoughts on this are crucial; so please comment on what you’d like and any other ideas you may have.