Post 3: Expression Evaluator - The Expression Class and Evaluation

The Expression Class is a n-ary tree representation of a given S-Expression.

In its simplest form, the class would look something like:

public class Expression
{
    protected Expression m_Parent = null;
    public virtual Expression Parent { get { return m_Parent; } }

    protected List<Expression> m_Children = new List<Expression>();
    public virtual List<Expression> Children { get { return m_Children; } }

    protected string m_TokenValue = String.Empty;
    public string TokenValue { get { return m_TokenValue; } }

    ... other housekeeping properties ...

At this point in the evaluation cycle, we have simply created a different representation of the S-Expression.

We actually perform the evaluation of each node by recursively evaluating each of the children and merging their results. The obvious questions here are:

• How exactly do we merge the results?
• How do we evaluate the children?

It would also be important to discuss the issue of the type of the result.

Let's go back to a simple S-Expression

(+ 1 2 3 4)

The Expression tree generated would be:

• Root (1 Child)
  • >> (5 Children)
    • "+" (0 Children)
    • "1" (0 Children)
    • "2" (0 Children)
    • "3" (0 Children)
    • "4" (0 Children)

In order to apply meaning to the expression, we define the convention that the first child represents some operation which has to be performed on all its siblings in order, which when applied, results in the value associated with the first child. Further, we define that the value of a node is the value of the first child.

In our example case, we define that the value of the Root node is the value of the anonymous ">>" node, which in turn is the value of the "+" node, which in turn is the value resulting from applying the "+" function on "1", "2", "3" and "4".

We notice that we have now answered the first question "How do we merge the results".

To answer the second question, let's take a closer look at the Evaluate function of the Expression class, shown here in its simplified form:

public Expression Evaluate()
{
    switch (this.Children.Count)
    {
        case 0:
            /* atomic value */
            {
                switch (this.Token)
                {
                    case E_TOKEN.SExprStart:
                        break;

                    case E_TOKEN.ValidName:
                    case E_TOKEN.Text:
                    case E_TOKEN.ValidNumber:
                    case E_TOKEN.SingleQuotedText:
                    case E_TOKEN.DoubleQuotedText:
                        {
                            this.SetValue(this.TokenValue);
                        }
                        break;

                    default:
                        {
                            throw new EvaluatorException(this, "Evaluate Error: Unknown Token!");
                        }
                }

                return _this;
            }

        case 1:
            /* s-expr or root node */
            {
                return this.SetValue(this.Children[0].Evaluate());
            }

        default:
            /* function call */
            {
                // apply first child to the remaining children
                return this.SetValue(Apply(this.Children[0], this.Children.Skip(1).ToList()));
            }
    }
}

We can see the straightforward processing of the Root and Atom cases. The default case deals with the situation where the first child needs to be "applied" on the other children. Apply is the most elaborate function in this project, but it's quite simple really. If all we did was addition, this is what Apply() would look like:

private static Expression Apply(Expression Functor, List<Expression> Arguments)
{
    string strFunc = Functor.TokenValue;

    switch (strFunc.ToLower())
    {
        #region SUM/CONCAT
        case "+":
        case "add":
        case "sum":
            {
                try
                {
                    return Functor.SetValue(Arguments.Aggregate(0.0d, (result, x) => result += x.Evaluate().ValueAsNumber);
                }
                catch
                { }

                return Functor.SetNil();
            }
        #endregion

    }
}

The lambda expressions and List extension functions in C# make writing the processor sections a breeze. It's easy to see how the first child's value (the Functor argument to Apply)  is set to the sum of the other children (the Arguments argument to Apply).

We are only left with one major issue to discuss - that of the value type.