ToLinqExpressionVisitor

Aug 25, 2008 at 8:21 PM
Just for the fun of it, a visitor to convert an expression tree to a LINQ expression tree. A LINQ expression tree is compilable into a delegate but its also usuable with DLINQ (as DLINQ requires expression trees instead of delegates)

Simple usage:

         var l_s = "2*x ^ 4 + 5*x ^ 3 + 3*x ^ 2 + 2*x + 1";
         var l_t = Tokenizer.Tokenize(l_s).Parse();
         var l_ex = ToLinqExpressionVisitor.GetExpression(
            l_t,
            "x");

         var l_d = l_ex.Compile();
         var l_r = l_d(3.14);



//////

using System;
using System.Collections.Generic;
using System.Linq;
using SymbolicDifferentiation.AST;
using SymbolicDifferentiation.Tokens;

namespace SymbolicDifferentiation.Visitors
{
   using SLE = System.Linq.Expressions;

   public class ToLinqExpressionVisitor : IExpressionVisitor
   {
      static readonly Dictionary<Token, Func<SLE.Expression, SLE.Expression, SLE.Expression>> s_token_handlers =
         new Dictionary<Token, Func<SLE.Expression, SLE.Expression, SLE.Expression>>();

      static ToLinqExpressionVisitor()
      {
         s_token_handlers[TokenBuilder.Symbol("+")] = (l, r) => SLE.Expression.Add(l, r);
         s_token_handlers[TokenBuilder.Symbol("-")] = (l, r) => SLE.Expression.Subtract(l, r);
         s_token_handlers[TokenBuilder.Symbol("*")] = (l, r) => SLE.Expression.Multiply(l, r);
         s_token_handlers[TokenBuilder.Symbol("/")] = (l, r) => SLE.Expression.Divide(l, r);
         s_token_handlers[TokenBuilder.Symbol("^")] = (l, r) => SLE.Expression.Power(l, r);
      }

      readonly Stack<SLE.Expression> m_stack = new Stack<SLE.Expression>();
      readonly Dictionary<string, SLE.ParameterExpression> m_args;

      public ToLinqExpressionVisitor(IEnumerable<SLE.ParameterExpression> args)
      {
         m_args = args.ToDictionary(
            x => x.Name);
      }

      public static SLE.Expression GetExpression(
         Type delegateType,
         Expression exr,
         params string[] args)
      {
         var l_args = args
            .Select(
               x => SLE.Expression.Parameter(
                       typeof (double),
                       x))
            .ToArray();

         var l_vis = new ToLinqExpressionVisitor(l_args);

         exr.Accept(l_vis);
         return SLE.Expression.Lambda(
            delegateType,
            l_vis.m_stack.Pop(),
            l_args);
      }

      public static SLE.Expression<Func<double, double>> GetExpression(
         Expression exr,
         string arg0)
      {
         return (SLE.Expression<Func<double, double>>)GetExpression(
            typeof(Func<double, double>),
            exr,
            arg0);
      }

      public void Visit(BinaryExpression expression)
      {
         expression.Left.Accept(this);
         expression.Right.Accept(this);

         var l_right = m_stack.Pop();
         var l_left = m_stack.Pop();

         m_stack.Push(s_token_handlers[expression.Operator](
            l_left,
            l_right));
      }

      public void Visit(Expression expression)
      {
         if(expression.IsNumber)
         {
            m_stack.Push(SLE.Expression.Constant(expression.Value.Value, typeof(double)));
         }
         else
         {
            m_stack.Push(m_args[(string)expression.Value.Value]);
         }
      }
   }
}

Coordinator
Aug 26, 2008 at 8:18 AM
Very nice :)

I'd be happy to check it in. This is exactly the kind of contribution I'm looking for. Cool stuff.

Do you have unit tests for it?

Aug 26, 2008 at 9:03 AM
Thanks,

unit tests definitely fixable but I don't have them right where I am now.

If you are interested in parsing I think you should take a look at FParsec, it's an F# project but it's very nice. I wrote up a bit on using FParsec (and F#) to write a simple expression parser.

http://martenrange.spaces.live.com/blog/cns!58ED096273EF8D4!172.entry

I'm not saying that  you should go F# for this project or anything. FParsec is just an awesome piece of work that anyone interested in parsing should look at IMO.
Coordinator
Aug 26, 2008 at 11:30 PM
Thanks :)
I'll definitely look into it.
I'm impatiently waiting for the F# CTP that is fully supported by Visual Studio.