Wednesday, February 2, 2011

Fib: The T-P Premise.

Guilherme Silveira wrote a lovely blog exploring the Transformation Priority Premise using the Fibonacci sequence. He posed a suite of tests similar to these:

@Test public void fibTest() throws Exception { assertEquals(0, of(0)); assertEquals(1, of(1)); assertEquals(1, of(2)); assertEquals(2, of(3)); assertEquals(3, of(4)); assertEquals(5, of(5)); assertEquals(8, of(6)); }

He found that the proposed list of transformations did not lead him to a good solution. At first he found that the transformations led him to a solution like this:

switch(n) { case 0: return 0; case 1: return 1; case 2: return 1; case 3: return 2; ... }

Obviously this is the wrong approach, but the priority list presented in my original article did not prevent it. So I’ve added the (case) transformation to the very bottom of the list. This means that using a switch/case or an ‘else if’ is always the last option to choose.

Guilherme went on to rightly ignore the switch/case solution to see if he could get a good solution for fib by following the other priorities. I suggest you read his blog to see how that turned out. Meanwhile, let’s try it here.

The first test leads us to use the ({}–>nil) and then the (nil->constant) transformations:

public class Fibonacci { public static int of(int n) { return 0; } }

The second test forces an (unconditional->if) transformation that we can refactor with a (constant->scalar). This coincidentally makes the third test pass which is always nice.

public static int of(int n) { if (n <=1) return n; return 1; }

The fourth tests is tricky. How can we transform that ‘1’ into something that maps 1->1, 2->1, and 3->2. We know that fib(n) = fib(n-1)+fib(n-2) so we could use recursion to solve the problem. That’s the (statement->recursion) transformation.

public static int of(int n) { if (n <=1) return n; return of(n-1) + of(n-2); }

This makes all the tests pass. Hallelujah! And look how simple that was! What a pretty sight.

Unfortunately there are three things wrong with this pretty solution. First, that algorithm has a horrific runtime complexity of something like O(n2) or worse. Secondly, the algorithm does not use tail-recursion, and so uses a lot of stack space. Thirdly, Java is not a great language for recursion anyway since the JVM simply can’t optimize tail recursion (yet).

It’s a great shame that such a simple expression has so many problems! There are ways to address that, but they are beyond the scope of this article. For now we’ll focus on the three problems mentioned above.

Let’s tackle them one at a time. Is there a transformation that will at least get us to tail recursion? Of course there is, but it was missing from my original list. So I’ve modified that list as follows:

  • ({}–>nil) no code at all->code that employs nil
  • (nil->constant)
  • (constant->constant+) a simple constant to a more complex constant
  • (constant->scalar) replacing a constant with a variable or an argument
  • (statement->statements) adding more unconditional statements.
  • (unconditional->if) splitting the execution path
  • (scalar->array)
  • (array->container)
  • (statement->tail-recursion)
  • (if->while)
  • (statement->recursion)
  • (expression->function) replacing an expression with a function or algorithm
  • (variable->assignment) replacing the value of a variable.
  • (case) adding a case (or else) to an existing switch or if

So tail recursion is preferred over arbitrary recursion.

Now, can we use tail recursion to tranform this?

public static int of(int n) { if (n <=1) return n; return 1; }

Of course we can. It’s not as pretty as the previous solution, but it captures the same semantics. And it’s not ugly by any means.

public class Fibonacci { public static int of(int n) { if (n <=1) return n; return of(0,1,n); }  private static int of(int a, int b, int n) { if (n == 0) return a; return of(b, a+b, n-1); } }

Of course we can clean this up by removing the redundant ‘if’.

public class Fibonacci { public static int of(int n) { return of(0,1,n); }  private static int of(int a, int b, int n) { if (n == 0) return a; return of(b, a+b, n-1); } }

But now, how do we deal with the fact that Java doesn’t do well with recursion? If we thought that n would always stay relatively small, we could just ignore it. But let’s assume that ‘n’ will be large; forcing us to unwind the recursion and replace it with iteration. This requires a (if->while) and a few (variable->assignment) transformations.

public class Fibonacci { public static int of(int n) { return of(0,1,n); }  private static int of(int a, int b, int n) { while (n != 0) { int s = a+b; a = b; b = s; n--; } return a; } }

The list of priorities prevents this from being the direct outcome of TDD because it prefers the recursive solution. So my list of proposed priorities will necessarily create Java programs that are recursive, and therefore less than optimal for the language.

That makes me think that the priority list is language specific. In Java, for example, we might move (if->while) and (variable->assignment) above (statement->tail-recursion) so that iteration is always preferred above recursion, and assignment is preferred above parameter passing.

This makes sense because Java is not a functional language, and strongly resists a functional style. So any bias towards functional style will lead to suboptimal implementations.

If the priority list is language specific, is it also application specific? Do different problem domains require different priority lists? I strongly doubt this. We are working at a level of detail so far below the problem domain that it is hard for me to see how different problems would require different solution styles.

What about teams? Will teams tweak the priority list to match their styles? I hope not; but I have to say that I think this is not improbable.

I think what this shows us is that the transformations and their priorities are a way to encode a particular programming style. So long as we have different languages and styles, we’ll likely need different transformations and priorities.

On the other hand, if we compare the Java list with the Clojure list (say), the difference is subtle. The recursive transformations would move slightly lower in the list relative to the iterative and assignment transformations. The effect is, of course, profound, but the difference in the lists is actually relatively small. All the other transformations seem to hold their positions.

So the good news is that, although there may be different styles based on language type, the vast majority of the low level coding decisions remain similar irrespective of those styles.

24 comments:

  1. Very good and useful review. Thanks for sharing with useful tips here. Nowadays it becomes easy to compare home insurance quotes by zip code and get the cheapest home insurance policy.

    ReplyDelete
  2. Thanks for giving such a wonderful article. This post is very well written and also well formatted..................
    R12 SCM Online Training

    ReplyDelete
  3. مكافحة حشرات بمكة - عبيرمكة - 0508034442

    مكافحة حشرات بمكة خدمة تقدمها لكم شركة مكافحة حشرات بمكة يبحث كثير من الناس عن طرق مختلفة وكثيرة للتخلص من الحشرات المزعجة والمقززة


    مكافحة حشرات بمكة
    شركة رش حشرات بمكة
    شركة رش مبيدات بمكة
    شركة مكافحة النمل الاسود بمكة
    شركة مكافحة النمل الابيض بمكة
    شركة مكافحة الفئران بمكة
    شركة مكافحة الصراصير بمكة
    شركة مكافحة البق بمكة
    شركة مكافحة العتة بمكة

    شركات مكافحة الحشرات فى مكة


    http://abeermakah.com/%D9%85%D9%83%D8%A7%D9%81%D8%AD%D8%A9-%D8%AD%D8%B4%D8%B1%D8%A7%D8%AA-%D8%A8%D9%85%D9%83%D8%A9/

    ReplyDelete
  4. شركة تنظيف بالاحساء 0552744429 السفير المثالى


    شركة تنظيف بالاحساءتنظيف كل جزء من أجزاء هذا المنزل فيمكنها أن تقوم بتنظيف الأرضيات والستائر والسجاد وتنظيف النجف أيضا فهي
    شركة نظافة بالاحساء كبيره وتعمل في هذا المجال منذ سنين طويلة وبالتالي فإنها لديها الخبرة الكبيرة جدا في هذا المجال التي جعلتها من أحسن الشركات في مجال التنظيف فهي
    شركة تنظيف منازل بالاحساء

    http://almthaly-dammam.com/%D8%B4%D8%B1%D9%83%D8%A9-%D8%AA%D9%86%D8%B8%D9%8A%D9%81-%D8%A8%D8%A7%D9%84%D8%A7%D8%AD%D8%B3%D8%A7%D8%A1/

    ReplyDelete

  5. It’s very informative and useful option for the daily online readers. Thumbs up for you!
    college paper writing service reviews

    ReplyDelete
  6. موقع برامج سات يقدم العديد من البرامج والالعاب العربية بروابط مباشرة جديدة مثل برنامج موبي كورة و العييد والعديد من البرامج والالعاب العالمية مثل جوجل كروم وبرامج اخري مثل تحميل لعبة ببجي للكمبيوتروكمان لعبة ميدل

    ReplyDelete
  7. Hi, I'm James Harrison a 23-year-old student (TUM) who enjoys social card games, watching sport and going to the movies. So now I'm working as SEO, SEA, SMM freelancer. I'm very experienced in copywriting, especially of related to essay writing services.
    Visit my site:
    CLICK HERE
    CLICK HERE
    CLICK HERE

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. التنظيف بالبخار: مزايا وأخطاء يجب تجنبها
    افضل شركة تنظيف بالبخار بجدة
    التنظيف بالبخار يستغرق وقتًا شركة تنظيف كنب بالبخار بجدة ، ولكنه يسمح لك بتعقيم المنزل وتعقيمه تمامًا. اكتشف فوائد التنظيف بالبخار وما هي الأخطاء التي يجب تجنبها
    شركة تنظيف سجاد بالبخار بجدة

    واحدة من أكثر الطرق فعالية للحفاظ على نظافة المنزل شركة مكافحة البق بجدة ، دون استخدام المواد الكيميائية ، هي استخدام الأجهزة لتنظيف البخار. من خلال هذا النظام ، من الممكن عدم تنظيف المنزل شركة مكافحة العتة بجدة ، ولكن أيضًا تطهير الأسطح ، وإزالة الأوساخ والشحوم ، دون الحاجة إلى استخدام منتجات إضافية. لهذا السبب ، يحظى التنظيف بالبخار بتقدير كبير شركة نظافة رابغ من قبل مرضى الحساسية ، أو من قبل العائلات التي لديها أطفال صغار.
    شركة مكافحة النمل الابيض بجدة

    تتضمن تقنية التنظيف المنزلي هذه استخدام شركة تنظيف مكيفات بجدة مياه بسيطة ، وبعد ذلك بمجرد الوصول إلى نقطة الغليان ، بفضل آلة معينة ، تسمح بطرد الغليان وتعقيم البخار عن طريق تنظيف الغرف المختلفة في المنزل.
    افضل شركات مكافحة الحشرات فى جدة

    ReplyDelete
  11. مزايا هذه الطريقة عديدة ، ومع ذلك شركة مكافحة حشرات برابغ ، يجب عليك أيضًا الانتباه جيدًا أثناء هذه العملية ، حيث لا يمكن تنظيف أي ركن من المنزل بالبخار ، خاصة في ظروف معينة. دعونا نرى ما هي شركة تنظيف خزانات برابغ مزايا وعيوب هذا النظام وما هي الأخطاء التي يجب تجنبها!

    مزايا التنظيف بالبخار
    شركة مكافحة حشرات بخليص

    تنظيف المنزل بالبخار هو طريقة بسيطة وفعالة لتعقيم المنزل. شركة تنظيف خزانات بخليص تختلف مزايا هذه الطريقة ، في الواقع ، باستخدام منظف بالبخار ، من الممكن:
    شركة تنظيف بخليص

    القضاء على الجراثيم والبكتيريا والعث دون استخدام المواد الكيميائية ؛
    الحفاظ على المنزل طازجًا ونظيفًا وعطرًا ؛
    القضاء على الشحوم والأوساخ شركة تنظيف بعسفان بدون منتجات أكالة
    تنظيف ألعاب الأطفال والمعدات الطبية (مثل آلة الأيروسول) وطاولة التغيير شركة تنظيف خزانات بعسفان دون خطر التلوث بالمنتجات الضارة بالطفل ؛
    شركة مكافحة حشرات بعسفان

    ReplyDelete
  12. ديها احترافية كبيرة جدا في تأدية خدمة تسليك المجاري، حيث إنها تعتمد على خبرتها في استخدام المواد الحديثة، والأدوات المتطورة التي تساهم في إنجاز العمل بشكل مميز، وفي وقت قليل، بالإضافة إلى ذلك نحن نقوم باستخدام لكم المواد الأمنة لعملية تسليك مجاري الحمامات، حتى لا نعرض عميلنا الفاضل إلي أي مشكلة من خلال استخدامنا للمواد المميزة، كما نوفر لكم مجموعة من الاحتياطات، والنصائح التي تتبعونها عند ظهور هذه المشكلة لديكم، لكي نقلل من الأضرار التي تحدث لأفراد الأسرة، و نوفر لهم الاطمئنان، ويمكنكم التواصل معنا عبر شركتنا.
    شركة تسليك مجاري بالدمام
    شركة تسليك مجاري بالقطيف
    شركة اللواء للخدمات المنزليه

    ReplyDelete