Last time I demonstrated a way to curry a function that involved amplifying types. I called it "strange curry" because the way I implemented partial function application did not involve a curry helper function and it involved re-writing a curried function when partially applied. I'm trying to show how functional programming techniques can be applied in non-functional languages, without a purely functional approach. This is also evident with my quasi-monadic type system; Operand<T> is an amplified type and the curried binary operators act as binding mechanisms.
My real goal in this (short) series is to show that there is no harm in taking programming techniques (even those with deep academic) roots and altering them to fit your needs. At the same time, though, we have to be careful to avoid the "everything looks like a nail" mentality when we use the functional programming hammer. I decided to use a form of currying in my polish notation evaluator because it provided me with an elegant solution, not because I had to partially apply functions. You have to have a full understanding of the problem at hand before picking a tool for the job.
So how did partial function application help me with my polish notation evaluator? To quote my last post:
Keeping state data for an operator is something I want to avoid. This notion gives rise to the idea that when an operator is partially applied, it will be a different instance then the same operator when un-applied. So how do you avoid keeping state data while maintaining the fact that an operator has been partially applied?
After reading that a few times, I felt partial function application was the best way to tackle that problem. Let's see how it worked out for me.
Recall from last time, the Operand and BinaryOperator classes:
public interface IToken
{ }
public class Operand<T> : IToken
{
public T Value { get; private set; }
public Operand(T Value)
{
this.Value = Value;
}
}
public class BinaryOperator<T> : IToken
{
private Func<T, T, T> binaryOp;
private Func<Operand<T>, Func<T, T, T>, IToken> curriedOp = (x, f) =>
{
return new BinaryOperator<T>(f)
{
curriedOp = (y, op) =>
{
return new Operand<T>(f(x.Value, y.Value));
}
};
};
public BinaryOperator(Func<T, T, T> BinaryOp)
{
binaryOp = BinaryOp;
}
public IToken Apply(Operand<T> Value)
{
return curriedOp(Value, binaryOp);
}
}
The benefit in using this strange curry in a polish notation evaluator may not be obvious, but the proposed evaluation algorithm from my last post demonstrates the benefits. When an operator is found on the token stack, it is pushed onto the operator stack. When an operand is found on the token stack, an operator is popped from the operator stack. The operand is then applied to the operator and the result (an operator or operand) is then pushed onto the token stack. This process then repeats until the token stack is empty. The simplicity of this algorithm comes from being able to partially apply operators and ignore the result until a more convenient time. The evaluator does not have to wait for two operands to be able to apply an operator, courtesy of strange curry. Let's take a look at the evaluator:
public static Operand<int> Evaluate(Stack<IToken> Tokens)
{
IToken token = null;
var operators = new Stack<BinaryOperator<int>>();
while (Tokens.Count > 0)
{
token = Tokens.Pop();
if (token is BinaryOperator<int>)
{
operators.Push((BinaryOperator<int>)token);
}
else if (token is Operand<int>)
{
if (operators.Count == 0)
{
break;
}
var op = operators.Pop();
var res = op.Apply((Operand<int>)token);
Tokens.Push(res);
}
}
if (token == null || operators.Count != 0 || Tokens.Count != 0)
{
throw new Exception("Invalid format.");
}
return (Operand<int>)token;
}
A token stack needs to be passed to the evaluator, so envision the following equation tokenized and pushed onto a stack in reverse order:
"- * / 15 - 7 + 1 1 3 + 2 + 1 1"
The majority of the evaluator code is self explanatory, so a line-by-line dissection is probably not needed. What we should pay attention to though is the way operands are applied to operators:
var op = operators.Pop();
var res = op.Apply((Operand<int>)token);
Tokens.Push(res);
When an operand is found, an operator is popped from the operators stack, and the operand is applied to the operator. The result of the application is either an operand (the result of the binary operation) or another operator, a partially applied operator in this case. We're not concerned with what the actual result is, so the result is placed back onto the token stack to be examined later. I don't know about you, but I like it!