次の方法で共有


Statement Translation using Functional Programming in C#

I will demonstrate here how we can use the functional programming feature in C# to program something like a statement/expression translation. Basically, we will translate a statement tree into a function that we can call to run the program. I am not using Linq Expression as demonstrated in my previous blog. Instead, I will show how to use functional programming.

The expression list we support is a very small subset of a real programming language, the definition in detail is:

int an integer constant
variable variable reference
plus expression + expression
multiply expression * expression

The classes are:

     // base class for the expression node
     abstract class Expression
     {
     }
  
     // defines a constant integer
     class Int : Expression
     {
         public Int(int i)
         {
             Value = i;
         }
  
         public int Value { get; set; }
     }
  
     // defines a variable reference
     class Variable : Expression
     {
         public Variable(string name)
         {
             Name = name;
         }
  
         public string Name { get; set; }
     }
  
     // defines a plus expression
     class Plus : Expression
     {
         public Plus(Expression left, Expression right)
         {
             Left = left;
             Right = right;
         }
  
         public Expression Left { get; set; }
         public Expression Right { get; set; }
     }
  
     // defines a multiplication expression
     class Multiply : Expression
     {
         public Multiply(Expression left, Expression right)
         {
             Left = left;
             Right = right;
         }
  
         public Expression Left { get; set; }
         public Expression Right { get; set; }
     }

Our supported statements are just a very small subset of the whole programming language. It contains, an assignment, if, while, skip, and a sequence of statements. The definition in detail is:

Assignment variable := expression
if if (expression) then statement else statement
while while (expression) then statement
seq statement, statement
skip does nothing, e.g. could be used with the else statement.

The classes that represent our statements:

     abstract class Statement
     {
     }
  
     class Skip : Statement
     {
     }
  
     class Seq : Statement
     {
         public Seq(Statement s1, Statement s2)
         {
             S1 = s1;
             S2 = s2;
         }
  
         public Statement S1 { get; set; }
         public Statement S2 { get; set; }
     }
  
     class Assign : Statement
     {
         public Assign(string variable, Expression expression)
         {
             Variable = variable;
             Expression = expression;
         }
  
         public string Variable { get; set; }
         public Expression Expression { get; set; }
     }
  
     class If : Statement
     {
         public If(Expression condition, Statement @then)
             : this(condition, @then, new Skip())
         {
         }
  
         public If(Expression condition, Statement @then, Statement @else)
         {
             Condition = condition;
             Then = @then;
             Else = @else;
         }
  
         public Expression Condition { get; set; }
         public Statement Then { get; set; }
         public Statement Else { get; set; }
     }
  
     class While : Statement
     {
         public While(Expression condition, Statement body)
         {
             Condition = condition;
             Body = body;
         }
  
         public Expression Condition { get; set; }
         public Statement Body { get; set; }
     }

After we defined our language, we can just use it to construct our program, or use a help of a scanner/parser. What we care here is just to translate both expressions and statements nodes.

The way we are going to access our variables is through a heap. Our heap is a function that takes a variable name as a string and returns an integer (I assume we deal only with integer types)

heap := var => int

We will translate an expression into a function that takes a heap (heap function) and returns an integer value. For example, the addition expression will use the heap to return the result of the sum.

expression := heap => int

Statement will get translated into a function that takes a heap and returns another heap. For example, the assignment statements, will take the current heap and return a new heap that contains the new variable.

statement := heap => heap

The HeapFunc is declared as a delegate:

         delegate int HeapFunc(string variable);

The code for expression translation is simple and straight forward:

         // returns a function that takes a heap and returns an integer
         Func<HeapFunc, int> TranslateExpression(Expression e)
         {
             if (e == null)
                 throw new ArgumentNullException("Expression cannot be null");
  
             if (e is Int)
             {
                 // whatever the heap is, return the value
                 return (h => ((Int)e).Value);
             }
             else if (e is Variable)
             {
                 // use the heap to lookup the variable name
                 return (h => h(((Variable)e).Name));
             }
             else if (e is Plus)
             {
                 // translate the left expression into a function
                 var f1 = TranslateExpression(((Plus)e).Left);
                 // translate the right exression into a function
                 var f2 = TranslateExpression(((Plus)e).Right);
                 // run the functions on the given heap to get integers and sum them
                 return (h => f1(h) + f2(h));
             }
             else if (e is Multiply)
             {
                 // similar to the plus expression
                 var f1 = TranslateExpression(((Multiply)e).Left);
                 var f2 = TranslateExpression(((Multiply)e).Right);
                 return (h => f1(h) * f2(h));
             }
             else
             {
                 throw new NotSupportedException("Not supported expression.");
             }
         }

The code for statement translation is shown next:

         // returns a function that takes a heap and returns a heap.
         Func<HeapFunc, HeapFunc> TranslateStatement(Statement s)
         {
             if (s == null)
                 throw new ArgumentNullException("Expression cannot be null");
  
             if (s is Skip)
             {
                 // just return the same heap
                 return (h => h);
             }
             else if (s is Assign)
             {
                 Assign assign = (Assign)s;
                 // translate the expression
                 var f = TranslateExpression(assign.Expression);
                 // the resulted heap will check if the variable is the one responsible for
                 // if so return the result of the expression, else use the previous heap to look up.
                 return (h) => (var => var == assign.Variable ? f(h) : h(var));
             }
             else if (s is Seq)
             {
                 Seq seq = (Seq)s;
                 // translate the first statement
                 var f1 = TranslateStatement(seq.S1);
                 // translate the second statement
                 var f2 = TranslateStatement(seq.S2);
                 // apply the first translation on the heap, which will return a new heap
                 // that will be applied to the second translation.
                 return (h) => f2(f1(h));
             }
             else if (s is If)
             {
                 If @if = (If)s;
                 // translate the condition expression
                 var fcond = TranslateExpression(@if.Condition);
                 // translate the then statement
                 var fthen = TranslateStatement(@if.Then);
                 // translate the else statement
                 var felse = TranslateStatement(@if.Else);
                 // apply the heap to the condition function. If the value is not zero, use
                 // the heap returned by applying fthen, otherwise use the heap returned by 
                 // applying felse.
                 return (h) => (fcond(h) != 0 ? fthen(h) : felse(h));
             }
             else if (s is While)
             {
                 While @while = (While)s;
                 // translate the condition expression
                 var fcond = TranslateExpression(@while.Condition);
                 // translate the body statement
                 var fbody = TranslateStatement(@while.Body);
                 // apply the body multiple times then return the final heap.
                 return (h) => {
                     while (fcond(h) != 0)
                     {
                         h = fbody(h);
                     }
                     return h;
                 };
             }
             else
             {
                 throw new NotSupportedException("Statement not supported.");
             }
         }

Sample:

I wrote a simple example to show how we can translate a simple program into a functional code. My example returns the sum of numbers between 0 and 10.

         // this is our initial heap. our heap is empty, so calling this function 
         // sould just fail because we have no variable
         int InitialHeapFun(string variable)
         {
             throw new Exception("cannot find variable '" + variable + "'");
         }
  
         void Run()
         {
             // sum := 0
             // i := 10
             // while (i)
             //  sum := sum + i
             //  i := i - 1
             // end
             Statement myProgram = new Seq(
                 new Assign("sum", new Int(0)),
                 new Seq(
                     new Assign("i", new Int(10)),
                     new While(new Variable("i"),
                         new Seq(
                             new Assign("sum", new Plus(new Variable("sum"), new Variable("i"))),
                             new Assign("i", new Plus(new Variable("i"), new Int(-1)))
                         )
                     )
                 )
             );
  
             // translate the program into (heap=>heap)
             var f = TranslateStatement(myProgram);
             // run the program using our initial heap
             var heap = f(InitialHeapFun);
  
             // print the sum value. this outputs 55
             Console.WriteLine(heap("sum"));
         }

There are a lot of other cool examples that would benefit from this method of translation. For example, we could translate an XML file that contains different actions. The result function will run much faster using just function calls. You can think of it as an XML compiler.

The code is attached for your convenience.

Program.cs

Comments