Tail Recursion
 

My Kid’s encounter with Iteration

I was teaching the addition of 2 numbers to my 5-year-old kid. The initial approach is to use fingers in the hand, so she could sum 2 numbers which add up to a maximum of 10. When it went beyond 10, she needed a placeholder (a variable in software terms). Now I taught her to have one of the numbers in mind so that she could just count the fingers for the second number. Again if the second number is bigger than 10, she was limited. When I started questioning about what her next approach will be, I was surprised by her answer. She came up with an iteration algorithm! The Idea is to use a counter (0n paper) for the number of times the set of 10 fingers were counted. This triggered my thoughts about iteration and recursion, hence this blog post.

 Iteration & Recursion

Recursion had been there in software for very long time. Recursion in software is derived from its mathematical formulations. Below are the rules of recursion.

  1. A simple base case (or cases)
  2. A set of rules that reduce all other cases toward the base case

If we can categorize each of the iteration into a form of simple base cases, then the iterative operation can be made recursive. In simple form: A function calls itself. A ‘Recursion’ is a special form of Iteration where no one knows the number of times the iteration will happen. Below is an example of recursion based Fibonacci series generator.

 
        public int Fibonacci(int n)
        {
            if (n == 0)
                return 0;
            else if (n == 1)
                return 1;
            else
                return (Fibonacci(n - 1) + Fibonacci(n - 2));
        }

 

 Stack Based Languages/Frameworks

Recursive logic in stack based languages/frameworks(example .net, Java)are limited by the amount of memory available. This is because these frameworks add the method name and the data(value types) to a top of the call stack for every call to a method. This is done to retain the data in the current method (in the stack) so that when the method returns, the data can be popped out the stack for usage.The data in the stack is not useful if they are not used after the method call.

 
public void PrintCallStack()
{
  var stackTrace = new StackTrace();           // get call stack
  var stackFrames = stackTrace.GetFrames();  // get method calls (frames) 
  foreach (StackFrame stackFrame in stackFrames)
  {
    Console.WriteLine(stackFrame.GetMethod().Name); 
  }
}

 

 Tail recursion (example)

A recursive method is called Tail recursive if the last line of the method calls itself. Since there are no other operations done after the recursive call, the stack data is useless. So the stack need not be built for each of the recursive calls. A compiler is said to be Tail recursive if it can identify the above scenario and replace the caller with called, and the current stack is reused. This is a huge performance optimization and you might never encounter Stack Overflow exception during recursion.

 
public int NonTailRecursiveFactorial(int n)
{
    if (n < 2)
        return 1;
    return n * Factorial(n - 1);
}
 
public int TailRecursiveFactorial(n, a)
 {
    if (n == 0) return a;
    return TailRecursiveFactorial(n - 1, n * a);
  }


Tail recursion is some times equivalent to Goto statements

public int factorial(int n, int a) 
{ 
beginning: 
if (n == 0) return a; 
else 
  { 
     a *= n; 
     n -= 1; 
     goto beginning; 
   } 
}

 

 By the way..

Generally Tail recursion (tail call optimization) is attributed to functional programming languages and unfortunately major programming languages like C# and Java does not support Tail Recursion. But this optimization is available in their sister frameworks F# and Scala. Also there are thoughts like Trampolines and Lambda expressions are far superior method to achieve results than other form of iterative programming. But i think that is a separate post altogether.

Contextual Friendship Framework
 

Recently one of my colleague,  Rahul Rathore and I were on a conversation on object-oriented techniques and we both agree that it has lots of inspiration from the real world. Below is the background of our conversation and what emerged out of that.

Background:

The object-oriented languages like C#, Java are more close to real world. We can mimic the real world behaviors in these languages easily. Scenarios are well captured because of their object-oriented abilities. Inheritance, polymorphism, and encapsulation are principles derived from the real world. In the real world, there are more concepts which are applicable to humans but are not well mimicked in the computer world. One of them is Friendship (between objects).

For better code re-usage, Object-oriented programming languages like C++ have a feature called Friend classes. A class in C++ allows access to all the private & protected members to its friend classes.

But in the real world, we share only a few things with our friends based on the context we are in. We have complete control over what we want to share with our friends and families. This is not the case with C++ friend classes; it shares all the private & protected members to its friends. This poses a threat to the object-oriented theory of encapsulation.

Because of this threat, advanced programming languages like C# and Java have completely removed friendship between objects. But friendship can significantly increase code re-usage and cohesion in objects than breaking them. We wanted to have friendship in C# and Java but still, follow other object-oriented principles.

We observe that C# is very easy to use and highly extendable. So we embraced C# and extended it with the custom module which will enable friendship between classes.

Contextual Friendship Framework:

The framework extends the Microsoft.Net framework to enable friendship among classes. This Friendship framework allows developers to add attributes to classes and its members to enable friendship. There are 2 attributes available.

  1. FriendOf – for classes
  2. AvailableToFriends – for members
  3. FriendOf attribute can be applied to a class whose private and protected members need to be made available to specific friend classes. It takes an array of .Net Types as a parameter. AvailableToFriends attribute can be applied to a class member to allow its access to specific friends only.

A Friend class can access a private/protected member of its friend class by using the ‘MakeFriendlyCall’ extension method exposed by the friendship framework. MakeFriendlyCall method is an extension method that internally uses .Net Reflection to reach to private and protected members. MakeFriendlyCall will allow making calls to private/protected members with AvailableToFriends attribute.

Friendship enables selective sharing of members with friend class based on the class definition. The module provides facility to decorate members of a class for granting access to its friend. Let’s understand this using the below example

 
    [FriendOf(typeof(World))]
    public class Hello
    {
        public string Name { get; private set; }
 
        public void HelloPub()
        {
            Console.WriteLine("Public Hello");
        }
 
        [AvailableToFriends(typeof(World))]
        private string PrivateMethodsAvlToFriends(string name)
        {
            Name = name;
            Console.WriteLine("Private Hello : " + Name);
            return Name;
        }
 
        private void PrivateMethod(string d)
        {
            Console.WriteLine("Private method" + d);
        }
    }
 

    public class World
    {
        private void DoSomething()
        {
            var h = new Hello();
            h.MakeFriendlyCall("PrivateMethodAvlToFriends", "John");
        }
    } 

Here we have 2 classes, Hello and World. The Hello class has two private methods “PrivateMethodsAvlToFriends” and “PrivateMethod”. PrivateMethodsAvlToFriends is decorated with AvailableToFriends attribute. Now the Friend class “World” can make a call to this private method. This can be done by using the ‘MakeFriendlyCall’ extension method exposed generically.

Class Diagram Of the dependencies:

FriendshipFramework

Alternative solutions:

  • Friend class in C++
  • C# has Friend Assemblies which allow all internals of a class visible to another assembly using InternalsVisibleTo attribute. This is more generic than the C++ friend class and does not allow selective access.

Comparison of C++ Friend class Vs Friendship Framework:

Criteria C++ Friend Class Friendship Framework
Security All members are available to friends Granular control over what is available to Friends
Encapsulation Breaks Encapsulation Enhances Encapsulation
Re-Usability Part of the C++ library, so re-usable Fully re-usable as the framework is shipped as a package.
Design Pattern Access Modifier Decorator pattern is used. Also, can be implemented using Access Modifier

Future scope:

We have enabled friendship between classes without breaking encapsulation and security. However, this design can be extended to objects of classes, which makes it closer to the real world. After all, we are not sharing our car with a friend all the times.

Also, the Friendship attributes ‘FriendOf’ and ‘AvailableToFriends’ can be converted to new access modifiers like Public, private, protected. This could be done using Roslyn which is a complier extension to .Net. The Friend framework is available in .Net, but can be implemented to Java framework as well.

 

 

A Developer is an Author
 

When I started this blog, I was skeptical if I can be an author. But what appeared more important to me is spreading knowledge, my thoughts So I continued blogging. After writing few articles what I realize is that writing a blog is not much different from my favorite profession (writing code).

Few similarities between coding and authoring.

  1. Both require deep knowledge of the subject (Domain)
  2. Both require good use of vocabulary
  3. Both require good organizing and formatting
  4. Both require analytic and logical skills
  5. Focus on the reader

If someone is a good writer, he/she can be a good programmer as well. I want to simply put it like this…

Programmer = Author + Technical Knowledge

Most of us(developers/testers)  are focused on attaining higher levels in Technology and unfortunately less in Authoring skills. This is because we think that there is a magical box (called compiler) which will convert our code to machine language and after that, there is no use of our code. This is not true!. When we write code, we are already an author, we are already creating an article/document/story.  And apart from the compiler, there are other readers for your code(Other developers and testers !).  And when they read, they expect to read it like an article. I know this is not a new concept, people like Robert C Martin,  Martin Fowler have spoken/wrote about this long time back. I am just re-emphasizing it from a different perspective.

Let us consider how a small snippet from the novel “A Stone for Danny Fisher” by Harold Robbins.

Harold Robbins

If you observe the paragraphs, each one has a unique purpose. Beautiful short paragraphs doing only one thing at a time (Single Responsibility). This makes it easy for the reader to understand the subject.

Learning: Single Responsibility

Also, observe that the order of paragraphs tells a story. The first paragraph sets the stage for the court, the second one describes the start of the court etc.

Learning: Order the methods in the order, they are being called. Tell the story of your code.

There are lots of quotations in the above snippet. They represent the words of the character. This helps the fast skimmer to skip the unnecessary things and just read the important words.

Learning: Characterize your code, give personality to your classes.

Observe that almost all the sentences are in active voice. They represent the voice of a person. It’s more assertive and stronger.

Learning: Method names should be assertive.

There are lots of similarities between good code and a good novel. We just need to read between the lines to understand them! Besides, each author is different and have their own style of writing and so will be the choices made by developers. These styles will have long-term implications on the success of the project.