## 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.

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.

2. I have read your blog its very attractive and impressive. I like it your blog.

Java Online Training Java EE Online Training Java EE Online Training Java 8 online training Core Java 8 online training

Java Online Training from India Java Online Training from India Core Java Training Online Core Java Training Online Java Training InstitutesJava Training Institutes

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

4. هل تبغون شركة مكافحة حشرات ماهرة اليكم الكمال

افضل شركة مكافحة حشرات بالدمام
ولديها افضل المبيدات الحشرية فهى ارخص شركة رش مبيدات بالدمام

وتقوم بمكافحة جميع انواع الحشرات فهى امهر شركة مكافحة النمل الابيض بالدمام

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

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

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

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

6. كهربائى بالمدينة المنورة - الصيانة السريعة – 0508353932

كهربائى بالمدينة المنورة للقيام بجميع اعمال الكهرباء والصيانة المنزلية او بالشركات والمؤسسات والشركات لان مؤسسة الصيانة السريعة حريصة على راحة عملائها فقررناالعمل على راحتكم ابناء المدينة المنورة

مهندس كهرباء بالمدينة المنورة
كهربائى بالمدينة المنورة
فنى كهربائى بالمدينة المنورة
كهربائى منازل بالمدينة المنورة
فنى كهربائى منازل بالمدينة المنورة
معلم كهربائى بالمدينة المنورة
فنى كهرباء بالمدينة المنورة
http://alcyana.com/%D9%83%D9%87%D8%B1%D8%A8%D8%A7%D8%A6%D9%89-%D8%A8%D8%A7%D9%84%D9%85%D8%AF%D9%8A%D9%86%D8%A9-%D8%A7%D9%84%D9%85%D9%86%D9%88%D8%B1%D8%A9/

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

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

8. فرسان المثالى افضل شركة مكافحة حشرات بالقطيف0506070763
مع فرسان المثالى افضل
شركة مكافحة حشرات بالقطيف

لا داعى للقلق بعد الان فى ستخلصك من جميع انواع الحشرات

شركة رش مبيدات بالقطيف
شركة مكافحة النمل الابيض بالقطيف

9. ابها

فرسان افضل
شركة تنظيف بابها

بما تتميز به من مميزات عديدة فالان تقدم خدمات التنظيف ومنها

شركة تنظيف فلل بابها
شركة تنظيف شقق بابها
شركة تنظيف مجالس بابها

شركة تنظيف مساجد بابها
شركة تنظيف موكيت بابها
وتفوم فرسان ايضا بمكافحة الحشرات لانها ارخص
شركة مكافحة حشرات بابها
شركة رش مبيدات بابها
شركة مكافحة النمل الابيض بابها
فلا تترددوا اتصلوا بنا الان

10. شركة مكافحة حشرات بالطائف الايمان كلين 0500096306
شركة مكافحة حشرات بالطائف قادره على القيام باعمال المكافحة والقضاء على اى نوع من الحشرات بالاعتماد على احدث الالات والماكينات التى تقوم بالوصول الى اصعب الاماكن التى من الممكن ان يتواجد بيها الحشرات
شركة رش مبيدات بالطائف
شركة مكافحة النمل الابيض بالطائف

شركة مكافحة الفئران بالطائف
مكافحة الفئران بالطائف

11. شركة مكافحة حشرات بمكة نور مكة 0555705619

نور مكة شركة مكافحة حشرات بمكة نقوم بالقضاء على كافة انواع الحشرات بافضل المبيدات الآمنة على الصحة فمؤسسة بيت العز افضل شركة رش مبيدات بمكة

هل تعانى من وجود الحشرات ؟ هل ياتى عليك فتره وتزداد كميه الحشرات المتواجده فى المكان ؟ فالان مع بيت العز كافضل شركة مكافحه حشرات بمكة انت الان تمتلك اكبر الشركات التى تعمل فى خدمات المكافحه والتخلص من اى نوع من الحشرات نهائيا

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

12. شركة مكافحة حشرات بالطائف الدانة كلين 0508554570 - 0508554217
مكافحة الحشرات بالطائف تقدمها لكم الدانة كلين فاذا كنت تعانى فى بيتك او منزلك اوفلتنك من الحشرات المزعجة التى تسبب قلق وخوف لرعب ممن يتواجد فى المنزل فاذا كنت تريد التخلص من الحشرات فشركة رش مبيدات بالطائف تقدم لك كل خدمتها برش المبيدات للقضاء نهائيا على الحشرات
شركات مكافحة الحشرات فى الطائف
شركة مكافحة الحشرات بالطائف
مكافحة الحشرات بالطائف
شركة رش حشرات بالطائف
شركة رش مبيدات بالطائف
شركة مكافحة النمل الاسود بالطائف
شركة مكافحة النمل الابيض بالطائف
شركة مكافحة الفئران بالطائف
شركة مكافحة الصراصير بالطائف
شركة مكافحة البق بالطائف
شلركة مكافحة بق الفراش بالطائف
شركة مكافحة العتة بالطائف

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

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

15. شركة تنظيف فلل بالرياض Perfect cleaning and cleaning of the villa's rooms and the use of a vacuum cleaner to remove dust and soil.شركة تنظيف بالرياض The beauty and cleanliness of the place gives the use of steam cleaning machines that remove stains accurately and quickly and are used to clean canes and boards.
شركة تنظيف بالخرج Carpets, carpets and ceramics. If you are unable to execute these tips from شركة تنظيف منازل بالخرج .
شركة مكافحة الحمام بالرياض We provide you with a range of tips that prevent the nesting of the bathroom on the surface of your home you clean the surface and balconies from the remnants of the grain and clean it from waste and used furniture
شركة تنظيف منازل بالمدينة المنورة We have the ability to make your home an oasis of cleanliness and beauty. We have a dedicated team to clean every part of your home, but we are keen to provide important tips to keep your house clean for as long as possible. شركة تنظيف بالمدينة المنورة Use a vacuum cleaner to get rid of accumulated dust on a daily basis. Cleaning the glass home facades provides a perfect look for the home Provide you with a great service in cleaning your house if you can not do this hard work and effort شركة نقل عفش بالمدينة المنورة .
شركة تنظيف بينبع Provide you with a distinctive service in all types of private cleaning Carpet carpet cleaning using the steam cleaning machine makes it clean and fully sterile.
شركة نقل اثاث بينبع It is an ideal choice to carry out your home furniture without any effort or hardship. But if you want to do it yourself, arrange the clothing bags for your family so that you can remove the tires and wooden rooms easily. Transportation. Many things you can do .
شركة تنظيف منازل بمكة It is the best choice for you to clean the perfect parts of your home - Carpet cleaning and carpeting the best types of steam cleaning machines or sent to Cleaning and cleaning of beds and boards and putting mattresses on them to prevent the accumulation of dust and stains on them You must use high quality detergents to ensure high quality cleaning of all the items and parts of your home You need a daily cleaning of the kitchen and bathrooms to give a recovery and confidence in the cleanliness of the whole house شركة تنظيف خزانات بمكة Able to clean your home without bothering you or get tired at great cheap prices.

16. Due to the level of quality provided by our company Al-Safa Company in Al-Ahsa شركة تنظيف بالاحساء of cleaning and cleaning services of air conditioning and sewage and insect control on all household services that we do,شركة تنظيف مكيفات بالاحساء and taking our prices suitable for all segments of society, has become the best and most important company in the field of cleaning. شركة تنظيف خزانات بالاحساء In order to maintain our success and progress, the company strives to continue along the same lines, through continuous development and the constant pursuit of following all that is best for the masters of customers. شركة مكافحة حشرات بالاحساء So, never hesitate our dear customer to contact us if you want daily, weekly or monthly cleaning for your home, your garden or your company, شركة تسليك مجارى بالاحساء or even want any kind of cleaning services, we will promptly meet your request with perfect quality and low cost .
شركة الصفرات لكشف التسربات بالرياض
شركة الصفرات للتنظيف بالرياض
شركة الصفرات لتنظيف الخزانات بالرياض
https://www.al-safaa.com/

17. شركة تنظيف بالمدينة المنورة Is one of the best companies currently located in Al Madinah Al Munawwarah, Saudi Arabia. Since the company started its activities more than twenty years ago, it has endeavored to develop all its services and made sure to provide the best service at the highest level of quality in cleaning and disinfection at the lowest prices possible. The company believes that the company's employment is a mirror that reflects the efficiency of the company that boasts of it. The worker must be confident and credible to provide the customer with everything he can provide. JAL cleaning and sterilization found in شركة تنظيف منازل بالمدينة المنورة .
شركة نقل اثاث بالمدينة المنورة Providing customers with transportation services of furniture and furniture and storage of furniture using the latest methods and methods and modern techniques and trained workers and freight cars specially equipped to transport furniture and clothes to anywhere inside or outside Medina, customers often need a city to transfer furniture to move furniture from their offices or homes Or their companies to new places but are afraid of their loss of damage or loss, but our company guarantees its customers to complete the transfer process safely and safely without being exposed to any piece of fracture or loss as the company provides a service to lift and download furniture using a hydraulic winch The only available within شركة نقل عفش بالمدينة المنورة .
شركة تنظيف بينبع The company's services include all kinds of services needed by customers such as house cleaning services, apartments, cleaning services for ground and upper water tanks, cleaning of palaces and cleaning services for hotels, residential complexes, mosques, parks, facilities and others. Types of Services The main governmental and private bodies cooperated with the cleaning company in Yanbu. Our company has provided them with the most complete image that has impressed them and increased their confidence in the skill and efficiency of our company and its employees. P safe and effective when providing various cleaning services such detergents, but inside there is no شركة تنظيف منازل بينبع .
شركة نقل اثاث بينبع Is one of the largest furniture transport companies in the city of Yanbu, which is known for providing services at the highest level and the company always offers offers and discounts and wonderful offers on the cost of services and this is what surprises customers and make them always put them the only choice for them, we have a professional team of carpenters who oversee the distinguished operations Dismantling and installing furniture and repair and maintenance of any fractures, as the company has workers polishing furniture and wooden furniture with effective polishes to remove the dirt from the layers of paint and make the furniture bright shiny like new, after the completion of cleaning the workers of evil Of furniture with materials encapsulates the strength and durability to protect the furniture from the external shocks or natural factors such materials are available only from within شركة نقل عفش بينبع
https://fajr-sate3.com/

18. The task of moving a catcher needs to rely on شركة نقل عفش بالمدينة المنورة It is specialized and has a long history in this field, helping it to carry out the task of transporting the baggage without causing any problems. Among the precautions taken by the company during transport of the luggage are the following: High-quality packaging materials to ensure that no problems are encountered during transport, the luggage is loaded into the car very carefully so as not to be subject to any problems during transportation. The luggage is re-connected to the place where it is transported and the packaging that is placed on the pallet is removed. During transportation. , All the transferred items are written to make sure that there is no defect in the piece, therefore you will ensure the transfer of the baggage without being exposed to any problems during transportation, شركة نقل اثاث بالمدينة المنورة .
Is characterized by شركة تنظيف بالمدينة المنورة With the experience and efficiency in the task of cleaning, as it uses the best equipment and the latest in addition to many aspects that focus on them to ensure that the cleaning is done to the fullest, and the most important things that you find in the fast service company and nowhere else find the following: It depends on the best detergents that can eliminate stains and smears, follow a certain system in the cleaning task; for this reason it ensures that it reaches the best results, depends on the latest methods such as steam cleaning method which proved its efficiency in the cleaning work, During which to eliminate all germs and The bacteria that are present in the place and maintain the health of the present, possess the best specialized perfumes that you can only find شركة نظافة بالمدينة المنورة.
that شركة تخزين اثاث بالمدينة المنورة It can store any quantity of furniture even if it is huge. This is because the company owns large warehouses divided into many sections. It packs and puts furniture in cars and is transported to the stores equipped with the highest level and has the latest means of monitoring. شركة تخزين عفش بالمدينة المنورة You will get satisfactory results without having to pay a lot of money in return
Be aware شركة تنظيف بينبع Cleaning works require the latest equipment for cleaning and the best detergents. This is what it provides to its customers. Therefore, it ensures the results. The company can clean any place, Will t D have شركة نظافة بينبع Discounts and offers can not be found elsewhere
The task of moving furniture from one place to another can not be done by anything, but it must rely on a specialized company such as شركة نقل اثاث بينبع ، As it will provide you with assurance that the furniture transfer works will be done well and will not be exposed any piece of the pieces to any problems during the transfer of furniture. In addition, it will carry out a comprehensive inspection of all parts before and before the transfer. The best packaging tools are used in this task. you only have to communicate with شركة نقل عفش بينبع .
https://www.zeenclean.com/

19. Welcome to the official website of our company to clean apartments, houses, villas and shops in Saudi Arabia This is because we are the best home services company at the moment and by the testimony of our valued customers, the workers who work in the company have a very high experience in the field of cleaning in general, as well as we will give you cleanliness of the highest quality and the lowest prices with the testimony of customers, our goal is to satisfy our customers to the highest degree possible and thanks to God always First of all, thanks to the workers and technicians, we were able to satisfy all the customers who contracted with the company and contacted them, because we specialize in cleaning, sewerage and transport of luggage just contact us and you will notice that your house as if it is completely new from the intensity of cleanliness.
شركة الصفرات للتنظيف بالرياض
شركة الصفرات لتنظيف الخزانات بالرياض
شركة الصفرات لمكافحة الحشرات بالرياض
شركة الصفرات لنقل الاثاث بالرياض
شركة الصفرات لكشف التسربات بالرياض
شركة تنظيف بالمدينة المنورة
شركة تنظيف بينبع

20. Al-Najah Company is one of the most distinctive things about Al-Ahsa cleaner company. Cleanliness of furniture, and some individuals are responsible for the operation of devices, whether pumping devices or suction, and there is a team responsible for the process of sterilization air conditioners , Our team is considered one of the best teams because of its vast experience over many years in this field, skill and high efficiency, and fast and perfect performance. The nature of the work of the team and what may be seen when carrying out its mission, and we have a team of women to be at the service of our valued customers so as not to worry about the entry of the team of men to come home in the presence of women and housewives.
شركة تنظيف بالاحساء
شركة تنظيف مكيفات بالاحساء
شركة تسليك مجارى بالاحساء
شركة مكافحة حشرات بالاحساء
https://www.a-lnagah.com

21. House cleaning company in Hail represents the best and ideal solution for specialized and distinctive cleaning of all pieces of furniture and house rooms no matter the number of floors of the house and the number of rooms, where we work through a team trained on modern methods of cleaning using the latest steam cleaning machines that give outstanding results in cleaning sofas, boards, carpets and rugs It is also used to clean curtains and furnishings.Ceramic floors, chimneys and hoods are cleaned from hard fat stains and rust stains safely and completely.We also provide marble polishing services by providing the latest Italian marble polishing machines with the best types of detergents Its excellent cleaning and disinfecting houses cleaning company examples in Hail is the best choice and cheaper.
شركة تنظيف بحائل
شركة تنظيف فرش بحائل
شركة تنظيف مجالس بحائل
شركة تنظيف سجاد بحائل
شركة تنظيف منازل بحائل
شركة رش مبيدات بحائل
https://www.raya-hail.com