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.
Comments
- Anonymous
January 31, 2009
PingBack from http://www.anith.com/?p=4265