patrick dewane gathers wool

Strange Curry, Part 2

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!

Strange Curry

Just for fun (again, my definition of fun), I was working on a stack based evaluator for Polish notation. This notation differs from infix by moving operators to the front of their corresponding operands, such as '+ 4 7' as opposed to '4 + 7', or '+ 4 - 10 3' instead of '4 + (10 - 3)'. One wonderful feature of this notation is that it renders parenthesis completely useless, providing a cleaner syntax for evaluation (the same can be said of Reverse Polish notation, the yang to Polish notations yin). Evaluating expressions in Polish notation is simple, as demonstrated by this algorithm:

         1.                 2. 

           3.              4.

You can see how the binary operators need to support currying. Furthermore, you can see the need to be able to treat operators and operands as the same type as they share the token stack. Even further, you can see how a partially applied operator needs to be the same type as an un-applied operator as they share the operators stack. Some may argue the necessity of partially applied operators since in this example another operand is available on the token stack. But in the event we are evaluating an expression such as '+ 4 - 10 3', the second operand for the addition operator won't be available until '- 10 3' is evaluated.

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? We do so with some strange curry (and by not being a pedant about what constitutes state data).

Let's look at some code already. First, we can define an interface for our tokens (operands and operators) and a class for the operands:

public interface IToken
{ }

public class Operand<T> : IToken
{
    public T Value { get; private set; }
    public Operand(T Value)
    {
        this.Value = Value;
    }
} 

Now what about this strange curry I mentioned? Let's take a look at the BinaryOperator class and then I'll explain:

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 idea here is pretty simple. To construct a binary operator, you do so by providing the BinaryOperator class with a function of (T,T)->T. This function could add, subtract, multiply (any binary operation) as long as it takes 2 arguments a value of the same type.

A typical curry function does not amplify values and most certainly does not rewrite itself. This is reason I call this strange curry. The beauty in this design lies in the ability for the Apply function to use the curriedOp function transparently of whether or not it has not been applied or has been partially applied. That point is my primary reason for my design, and it should be evident with another glance at the curriedOp function. Once again, none of this would be possible without closures.

The caller of the Apply function is left with examining its return type to determine whether an operator or operand has been returned. To evaluate the expression '+ 4 7' we can do the following:

var lhs = new Operand<int>(4);
var rhs = new Operand<int>(7); 
var add = new BinaryOperator<int>((x, y) => x + y);
// result1 is an operator (Ly.4+y)
var result1 = (BinaryOperator<int>)add.Apply(lhs);
// result2 is an operand (11)
var result2 = (Operand<int>)result1.Apply(rhs); 
Console.WriteLine(result2.Value.ToString());

It's clear that I've created quite a lot of code just to add together two numbers. The benefit of what I've done can be realized when evaluating complex expressions in Polish notation, as we will see in my next post.

I find it interesting what happens when we blend functional programming concepts with languages like C#. We had to bend the fundamental concept of currying a bit to fit our needs, and in this case it has provided us with an elegant, although strange, solution.