Implementing Nested Functions in C#

If you program in more than one language, sometimes you want to use an idiom from one language in the other, where the idiom doesn't exist. So, you have to invent it for that language.

These days I write very short, well-named methods with behaviors spread over many classes. However, in the 1990s I programmed in Delphi (Object Pascal) and wrote much longer functions, sometimes using nested functions. Nested functions are functions defined within functions. They can be useful for compartmentalizing behavior that is invoked many times and at different places within a function. As well, they can be useful for naming a block of behavior within a function—even short functions.

Okay, that's a stretch. The truth is one day I was feeling creative and nostalgic, and I wanted to see if I could use nested functions in C#. What I came up with in C# so closely models nested functions that, for all intents and purposes, nested behaviors already exist for the language.

This article demonstrates how to implement nested functions for C#, and it might teach you a few things about C# in general. For the purposes of the demonstration, nested functions in C# have to behave like any other function to be useful. Therefore, they must have non-void return types, parameters, and recursion. The remaining sections demonstrate how you can effectively support all three of these elements. (Note: Some of the code isn't pretty, but it does work.)

Implementing Nested Functions Using Anonymous Delegates

To implement nested functions with parameters and return types, you need to know about delegates and another relatively new .NET capability, anonymous methods. Delegates and multicast delegates in C# (and .NET) add some additional safety nets and capabilities, but delegate really is just a fancy name for function pointer and event handler.

To begin, I picked a well-known behavior: calculating n! or n-factorial. The factorial algorithm takes a positive number n and returns 1*2*3*...n. For example, n! where n is 5 is 1*2*3*4*5 or 120. To map such a function by using a delegate signature, you can define a delegate that takes a long and returns a long, as follows:

public delegate long FactorialDelegate(long n);

The preceding defines a method signature, which permits you to define delegate instances that refer to methods matching this signature. The next thing you need to do is define an anonymous method inline where you define and initialize an instance of FactorialDelegate.

Defining an anonymous method

Think of anonymous methods as similar to C++ inline methods. The real difference is that anonymous methods are function headers with code blocks but without names. (Anonymous methods are used mostly as values that are assigned to events; that is, they are inline event handlers.)

To define an anonymous method, simply define a method whose header exactly matches the delegate signature but without the word delegate. Following on the previous code snippet, it would go like this:

public static long Factorial(long n)
{
   if (n < 1)
      throw new ArgumentOutOfRangeException(
         "n", "argument must be greater than 0");

   long result = 1;
   for (int i = 1; i <= n; i++)
      result *= i;
   return result;
}

To convert the function Factorial to an anonymous method, you remove everything from the header except the parameter list (long n), add the word delegate, and leave the method body in place. The result looks like this:

delegate (long n)
{
   if (n < 1)
      throw new ArgumentOutOfRangeException(
         "n", "argument must be greater than 0");

      long result = 1;
      for (int i = 1; i <= n; i++)
         result *= i;
      return result;
}

Now, to nest this anonymous method, you can delcare an instance of FactorialDelegate and assign it the anonymous method above, as follows:

FactorialDelegate Factorial = delegate(long n)
{
   if (n < 1)
      throw new ArgumentOutOfRangeException(
         "n", "argument must be greater than 0");

      long result = 1;
      for (int i = 1; i <= n; i++)
         result *= i;
      return result;
};

In fact, what you now have is a delegate instance that can be defined in an outer method—a defacto nested function—and can be invoked just like a function. Listing 1 shows the previously defined Factorial anonymous method instance nested in the Main function of a console application.

Listing 1: A Console Application Demonstrating Nested Functions

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Reflection;
using System.Text;

namespace NestedFunction
{
   class Program
   {
      public delegate long FactorialDelegate(long n);
      static void Main(string[] args)
      {
         // version 1
         FactorialDelegate Factorial = delegate(long n)
         {
            if (n < 1)
               throw new ArgumentOutOfRangeException(
                  "n", "argument must be greater than 0");

            long result = 1;
            for (int i = 1; i <= n; i++)
               result *= i;
            return result;
         };

         Console.WriteLine(Factorial {0} is {1}", 5, Factorial1(5));
         Console.ReadLine();
      }
   }
}

Implementing Recursion

Now, you have seen a defacto nested function, but what about recursion? Unfortunately, Factorial exists after it is defined. Hence, you cannot implement n! bu using recursion. The recursive version using the very first Factorial algorithm would look like this:

public static long Factorial(long n)
{
   return n > 1 ? n * Factorial(n - 1) : n;
}

My computer science professors might argue the implementation is not complete unless you can implement the entire idiom. (Of course, in business you would just do without recursion.) However, it is possible to implement recursion with nested functions. It isn't pretty, but it does work.

Listing 1 is a de facto nested function, but as I mentioned you cannot recurse by calling the variable Factorial. However, you can recurse by using reflection because even though the name Factorial doesn't exist in the anonymous method, the function does exist on the stack. Hence, all you need to do is pluck the Factorial method off the stack and call stack using reflection. Listing 2 demonstrates how you can implement nested functions using recursion.

Listing 2: A Nested, Recursive Function Using Reflection

FactorialDelegate Factorial = delegate(long n)
{
   if(n<1) throw new
      ArgumentOutOfRangeException(
      "n", "argument must be greater than 0");

   MethodBase method = new StackTrace().GetFrame(0).GetMethod();
   return n > 1 ? n * (long)method.Invoke(null,
      new object[] { n - 1 }) : n;
}

The first half of the nested function in Listing 2 is the same as in Listing 1. To recurse, you need to pluck the method object off the stack; it will always be the first method entry in the stack frame. Because you also know the signature long—anonymous(long n), you can reliably invoke the method by passing the correct argument type and casting the return type. (Told you it wasn't pretty.)

Broad and Expressive Language

Because language—whether speaking or programming—limits what you can conceive, I prefer to have as broad and expressive a language as possible, one that doesn't require me to use advanced idioms but makes them available. This is a tough balancing act for any language vendor to manage. In Microsoft's case, whether they actually support nested functions in C# or not is up to them. Of course, they already exist technically.

By using the demonstration in this article, you can implement nested functions. You won't need to use them often, but now you can if need be. For those who aren't old Pascal programmers or aren't interested in nested functions, notice that I threw in reflection, delegates, anonymous methods, how to get data off the callstack, recursion, and how to program by contract using exceptions.

About the Author

Paul Kimmel is the VB Today columnist for www.codeguru.com and has written several books on object-oriented programming, including Visual Basic .NET Power Coding (Addison-Wesley) and UML Demystified (McGraw-Hill/Osborne). He is the president and co-founder of the Greater Lansing Area Users Group for .NET (www.glugnet.org) and a Microsoft Visual Developer MVP.

Copyright © 2006 by Paul T. Kimmel. All Rights Reserved.



Comments

  • Interesting

    Posted by snareenactina on 11/12/2012 03:41am

    A lot has happened during last 20 years. It used to be that US was able to economically punish any European country, but during Iraq war it was absolutely toothless (unless you consider renaming french fries as a punishment) against France (backed by EU). slumber The theory section will highlight some of the problems facing Georgia in making the transition to a market based system and offer a brief outline of the state of its economy. organismal temario great balsey bheifeá

    Reply
  • Now available, an even slicker implimentation using System.Func

    Posted by jink on 08/25/2008 03:38pm

    In the latest C#, there are built-in generic delegates that can cover many circumstances...
    
        Func fact = delegate( long n ){ ...

    Reply
  • There is a much easier way to implement recursion

    Posted by Dinkwork on 10/31/2007 03:23pm

    Why not just define the delegate to take itself as an argument and then pass the delegate to itself.  I tried this and it works:
    
            internal delegate long FactorialDelegate( long n, FactorialDelegate x );
            static void Main( string[] args )
            {
                FactorialDelegate fact = delegate( long n, FactorialDelegate x )
                {
                    return ( n > 1 ? n * x( n - 1, x ) : n );
                };
    
                Console.WriteLine( "Factorial {0} is {1}", 5, fact( 5, fact ) );
                Console.WriteLine( "Done!" );
            }

    Reply
  • Nice but useless

    Posted by boudino on 11/03/2006 02:57am

    It is nice but useless, I think. Where is the benefit if you need to define the delegate outside the function anyway? I think lamba calculus from C# 3.0 is will be more suitable for this purpose.

    • Smallest function body possible...

      Posted by achristov on 11/14/2006 02:55am

      If this is a goal (and definitely it should be!) the aproach is realy excellent. The topic is too large to delve into details, however readability and code reuse are only two of the most important aspects of nested functions to be mentioned. I guess everybody would agree that Niclaus Wirth had given this methodology a good thought. So, I wouldn't call it 'useless'... And also, lambda-calculus is a new C# language feature, it may be the same as using delegates, only the form is different. So, it's a mather of 'taste', I'd say...

      Reply
    Reply
  • But what's the cost?

    Posted by davidhun on 10/18/2006 03:47pm

    True, this method does work, but at what cost?  I ran the code above but changed 5 to 25.
    
    The non-delegate way allocates 27k of ram and 369 instances (total, including .Net startup).  However, the delegate version allocates 365k of ram and 10,870 instances.
    
    True, for this small example, it might not be all that expensive, but in a larger context this is quite a bit of a performance cost.
    
    David

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • QA teams don't have time to test everything yet they can't afford to ship buggy code. Learn how Coverity can help organizations shrink their testing cycles and reduce regression risk by focusing their manual and automated testing based on the impact of change.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds