Blog - Title

The FP Switch Pattern (used to implement the World's Smallest RPN Processor)

The FP Switch Pattern (used to implement the World's Smallest RPN Processor)

  • Comments 0

[Blog Map]  This blog is inactive.  New blog: EricWhite.com/blog

You can implement common procedural constructs in the Functional Programming (FP) style. For instance, the FP tutorial showed how to loop using a ForEach extension method. We can do something similar to implement something analogous to the C# switch statement. To do this, we'll write an extension method that takes as parameters, 1) a delegate that returns an integer, and 2) an array of delegates (declared using the params keyword). The extension method indexes into the array using the integer, and calls the appropriate method in the array.

We can call this the FP Switch Pattern. When writing a program in the FP style, you could use this in a variety of contexts, but the cutest is a small RPN token processor. Here is the RPN token processor, including the code to exercise it, in its entirety.

// the following computes (5*2)-1

// the Token class is included in the listing at the bottom of this post

Token[] tkns = {
    new Token(5),
    new Token(2),
    new Token(TokenType.Multiply),
    new Token(1),
    new Token(TokenType.Subtract)
};

 

Stack<double> st = new Stack<double>();

 

// The RPN Token Processor

tkns.Switch(
    i => (int)i.Type,
    s => st.Push(s.Operand),
    s => st.Push(st.Pop() + st.Pop()),
    s => st.Push(-st.Pop() + st.Pop()),
    s => st.Push(st.Pop() * st.Pop()),
    s => st.Push(1/st.Pop() * st.Pop())
);

 

Console.WriteLine(st.Pop());

The Switch extension method is almost more interesting because of its signature than the body of the method. Because of the way that lambda expressions interact with the void keyword, we have to declare two extension methods, one for a switch where each delegate returns a type, and another for a switch where each delegate returns void:

public delegate void VoidFunc<T0>(T0 a0);

 

public static class MyExtension
{
    public static IEnumerable<TR> Switch<T0, TR>(
        this IEnumerable<T0>source,
        Func<T0, int>expr,
        params Func<T0, TR>[] funcArray)
    {
        foreach (T0 item in source)
            yield return funcArray[expr(item)](item);
    }

    public static void Switch<T0>(
        this IEnumerable<T0>source,
        Func<T0, int>expr,
        params VoidFunc<T0>[] funcArray)
    {
        foreach (T0 item in source)
            funcArray[expr(item)](item);
    }
}

Here is the program, in its entirety:

namespace MyProgram
{

    public delegate void VoidFunc<T0>(T0 a0);

 

    public static class MyExtension
    {
        public static IEnumerable<TR> Switch<T0, TR>(
            this IEnumerable<T0>source,
            Func<T0, int>expr,
            params Func<T0, TR>[] funcArray)
        {
            foreach (T0 item in source)
                yield return funcArray[expr(item)](item);
        }

 

        public static void Switch<T0>(
            this IEnumerable<T0>source,
            Func<T0, int>expr,
            params VoidFunc<T0>[] funcArray)
        {
            foreach (T0 item in source)
                funcArray[expr(item)](item);
        }
    }

 

    class Program
    {
        public enum TokenType
        {
            Operand,
            Add,
            Subtract,
            Multiply,
            Divide
        };

 

        public class Token {
            public TokenType Type;
            public double Operand;
            public Token(TokenType type)
            {
                this.Type = type;
            }
            public Token(double op)
            {
                this.Type = TokenType.Operand;
                this.Operand = op;
            }
        }

 

        static void Main(string[] args)
        {
            Token[] tkns = {
                new Token(5),
                new Token(2),
                new Token(TokenType.Multiply),
                new Token(1),
                new Token(TokenType.Subtract)
            };

 

            Stack<double> st = new Stack<double>();

 

            tkns.Switch(
                i => (int)i.Type,
                s => st.Push(s.Operand),
                s => st.Push(st.Pop() + st.Pop()),
                s => st.Push(-st.Pop() + st.Pop()),
                s => st.Push(st.Pop() * st.Pop()),
                s => st.Push(1/st.Pop() * st.Pop())
            );

 

            Console.WriteLine(st.Pop());
        }
    }
}

When you run this, it prints 9 to the console, as expected.

Leave a Comment
  • Please add 7 and 7 and type the answer here:
  • Post