Binding Lambdas when they are closures

Question

Hi,

I am considering prototyping a system that would require remoting lambda expressions across remoting boundaries. It would be extremely useful if Expression<T> exposed the capability to "bind" itself to its surrounding environment and get the intermediate tree.

Example:

string lastName = "ANDERSON";
Expression<Func<RecordName, bool>> lastNameFilter = rn => rn.LastName == lastName;

A lot of compiler magic happens here, obviously. But at some point, what I would really like to do is call lastNameFilter.Bind() which would output some intermediate format that would say, resolves all the references to local variables into values. (the node that contains the ref to lastName would become "ANDERSON")

I would not be done at point and would to transform some intermediate format in that is serializable that does not have any reflection objects directly.

Anyways thought I would throw this out there.

Nick Schrock
CareEvolution

 

Answer 1

Nicholas -

 

What you describe is actually a generally useful thing to do for Expression Trees.  We refer to it internally as "Funcletization" - though the name leaves something to be desired.  Linq to SQL does something similar down in it's guts - turning sub-expression-trees which do not depend on any of the parameters into Constant nodes.

 

You can implement this yourself by:

1) Writing a visitor over the Expression Tree which recreates the tree at each node.

2) Specializing this to check at each node whether the subtree depends on any of the parameters, and if not - call .Compile on it and replace the sub tree with a Constant node with the value returned from calling the delegate returned from .Compile()

 

I've been meaning to post some sample code that does this - but maybe you can beat me to it :-)

 

Thanks,

Luke Hoban

Visual C# Compiler Program Manager

Answer 2

Thanks a bunch. The terminology you defined + Reflector allowed me to yank the Funcletizer from the dlinq internals and massage it to be generally applicable. As you say, its a generally useful capability so i'll post it.

Code Snippet

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq.Expressions;

public static class Funcletizer
{
    public static Expression Funcletize( Expression expression )
    {
        return new Localizer( LocalMapper.MapLocals( expression ) ).Localize( expression );
    }

    private class Localizer : ExpressionVisitor
    {
        internal Localizer( HashSet<Expression> localExpressionSet )
        {
            _localExpressionSet = localExpressionSet;
        }

        internal Expression Localize( Expression expression )
        {
            return Visit( expression );
        }

        internal override Expression Visit( Expression exp )
        {
            if ( exp == null ) return null;
            if ( IsLocalExpression( exp ) )
            {
                return MakeFunclet( exp );
            }
            return base.Visit( exp );
        }

        private bool IsLocalExpression( Expression exp )
        {
            return _localExpressionSet.Contains( exp );
        }

        private Expression MakeFunclet( Expression e )
        {
            Expression expression = e;
            if ( expression.Type.IsValueType )
            {
                expression = Expression.Convert( expression, typeof( object ) );
            }
            return Expression.Funclet( FuncletizeExpression( expression ), e.Type );
        }

        private static Funclet FuncletizeExpression( Expression expression )
        {
            return Expression.Lambda<Funclet>( expression, new ParameterExpression[ 0 ] ).Compile();
        }

        private HashSet<Expression> _localExpressionSet;
    }

    private class LocalMapper : ExpressionVisitor
    {
        public static HashSet<Expression> MapLocals( Expression expression )
        {
            LocalMapper mapper = new LocalMapper();
            return new HashSet<Expression>( mapper.MapLocalsCore( expression ).Keys );
        }

        private LocalMapper()
        {
            // Empty
        }

        private Dictionary<Expression, bool> MapLocalsCore( Expression expression )
        {
            _locals = new Dictionary<Expression, bool>();
            _isRemote = false;
            Visit( expression );
            return _locals;
        }

        internal override Expression Visit( Expression expression )
        {
            if ( expression == null )
            {
                return null;
            }
            bool isRemote = _isRemote;
            switch ( expression.NodeType )
            {
                case ExpressionType.Constant:
                case ExpressionType.Funclet:
                    break;

                default:
                    _isRemote = false;
                    base.Visit( expression );
                    if ( ( !_isRemote && ( expression.NodeType != ExpressionType.Lambda ) ) && ( expression.NodeType != ExpressionType.Quote ) )
                    {
                        _locals[ expression ] = true;
                    }
                    break;
            }
            _isRemote |= isRemote;
            return expression;
        }

        internal override Expression VisitParameter( ParameterExpression p )
        {
            _isRemote = true;
            return p;
        }

        private bool _isRemote;
        private Dictionary<Expression, bool> _locals;
    }
}

// taken pretty much directly from the internals of System.Linq.Data.SqlClient
internal abstract class ExpressionVisitor
{
    internal virtual Expression Visit( Expression exp )
    {
        if ( exp == null )
        {
            return exp;
        }
        switch ( exp.NodeType )
        {
            case ExpressionType.Add:
            case ExpressionType.AddChecked:
            case ExpressionType.And:
            case ExpressionType.AndAlso:
            case ExpressionType.ArrayIndex:
            case ExpressionType.Coalesce:
            case ExpressionType.Divide:
            case ExpressionType.Equal:
            case ExpressionType.ExclusiveOr:
            case ExpressionType.GreaterThan:
            case ExpressionType.GreaterThanOrEqual:
            case ExpressionType.LeftShift:
            case ExpressionType.LessThan:
            case ExpressionType.LessThanOrEqual:
            case ExpressionType.Modulo:
            case ExpressionType.Multiply:
            case ExpressionType.MultiplyChecked:
            case ExpressionType.NotEqual:
            case ExpressionType.Or:
            case ExpressionType.OrElse:
            case ExpressionType.RightShift:
            case ExpressionType.Subtract:
            case ExpressionType.SubtractChecked:
                return VisitBinary( (BinaryExpression) exp );

            case ExpressionType.ArrayLength:
            //case ExpressionType.Cast:
            case ExpressionType.Convert:
            case ExpressionType.ConvertChecked:
            case ExpressionType.Negate:
            case ExpressionType.NegateChecked:
            case ExpressionType.Not:
            case ExpressionType.Quote:
            case ExpressionType.TypeAs:
                return VisitUnary( (UnaryExpression) exp );

            case ExpressionType.Call:
                //case ExpressionType.CallVirtual:
                return VisitMethodCall( (MethodCallExpression) exp );

            case ExpressionType.Conditional:
                return VisitConditional( (ConditionalExpression) exp );

            case ExpressionType.Constant:
                return VisitConstant( (ConstantExpression) exp );

            case ExpressionType.Funclet:
                return VisitFunclet( (FuncletExpression) exp );

            case ExpressionType.Invoke:
                return VisitInvocation( (InvocationExpression) exp );

            case ExpressionType.Lambda:
                return VisitLambda( (LambdaExpression) exp );

            //case ExpressionType.Lift:
            //case ExpressionType.LiftEqual:
            //case ExpressionType.LiftFalse:
            //case ExpressionType.LiftNotEqual:
            //case ExpressionType.LiftTrue:
            //    return VisitLift( (LiftExpression) exp );

            case ExpressionType.ListInit:
                return VisitListInit( (ListInitExpression) exp );

            case ExpressionType.MemberAccess:
                return VisitMemberAccess( (MemberExpression) exp );

            case ExpressionType.MemberInit:
                return VisitMemberInit( (MemberInitExpression) exp );

            case ExpressionType.New:
                return VisitNew( (NewExpression) exp );

            case ExpressionType.NewArrayInit:
            case ExpressionType.NewArrayBounds:
                return VisitNewArray( (NewArrayExpression) exp );

            case ExpressionType.Parameter:
                return VisitParameter( (ParameterExpression) exp );

            case ExpressionType.TypeIs:
                return VisitTypeIs( (TypeBinaryExpression) exp );
        }
        throw new InvalidOperationException();
    }

    internal virtual Expression VisitBinary( BinaryExpression b )
    {
        Expression left = Visit( b.Left );
        Expression right = Visit( b.Right );
        if ( ( left == b.Left ) && ( right == b.Right ) )
        {
            return b;
        }
        return Expression.MakeBinary( b.NodeType, left, right, b.IsLiftedToNull, b.Method );
    }

    internal virtual MemberBinding VisitBinding( MemberBinding binding )
    {
        switch ( binding.BindingType )
        {
            case MemberBindingType.Assignment:
                return VisitMemberAssignment( (MemberAssignment) binding );

            case MemberBindingType.MemberBinding:
                return VisitMemberMemberBinding( (MemberMemberBinding) binding );

            case MemberBindingType.ListBinding:
                return VisitMemberListBinding( (MemberListBinding) binding );
        }
        throw new InvalidOperationException();
    }

    internal virtual IEnumerable<MemberBinding> VisitBindingList( ReadOnlyCollection<MemberBinding> original )
    {
        List<MemberBinding> list = null;
        int num = 0;
        int capacity = original.Count;
        while ( num < capacity )
        {
            MemberBinding item = VisitBinding( original[ num ] );
            if ( list != null )
            {
                list.Add( item );
            }
            else if ( item != original[ num ] )
            {
                list = new List<MemberBinding>( capacity );
                for ( int i = 0; i < num; i++ )
                {
                    list.Add( original[ i ] );
                }
                list.Add( item );
            }
            num++;
        }
        if ( list != null )
        {
            return list;
        }
        return original;
    }

    internal virtual Expression VisitConditional( ConditionalExpression c )
    {
        Expression test = Visit( c.Test );
        Expression ifTrue = Visit( c.IfTrue );
        Expression ifFalse = Visit( c.IfFalse );
        if ( ( ( test == c.Test ) && ( ifTrue == c.IfTrue ) ) && ( ifFalse == c.IfFalse ) )
        {
            return c;
        }
        return Expression.Condition( test, ifTrue, ifFalse );
    }

    internal virtual Expression VisitConstant( ConstantExpression c )
    {
        return c;
    }

    internal virtual ReadOnlyCollection<Expression> VisitExpressionList( ReadOnlyCollection<Expression> original )
    {
        List<Expression> list = null;
        int num = 0;
        int capacity = original.Count;
        while ( num < capacity )
        {
            Expression item = Visit( original[ num ] );
            if ( list != null )
            {
                list.Add( item );
            }
            else if ( item != original[ num ] )
            {
                list = new List<Expression>( capacity );
                for ( int i = 0; i < num; i++ )
                {
                    list.Add( original[ i ] );
                }
                list.Add( item );
            }
            num++;
        }
        if ( list != null )
        {
            return list.AsReadOnly();
        }
        return original;
    }

    internal virtual Expression VisitFunclet( FuncletExpression f )
    {
        return f;
    }

    internal virtual Expression VisitInvocation( InvocationExpression iv )
    {
        IEnumerable<Expression> arguments = VisitExpressionList( iv.Arguments );
        Expression expression = Visit( iv.Expression );
        if ( ( arguments == iv.Arguments ) && ( expression == iv.Expression ) )
        {
            return iv;
        }
        return Expression.Invoke( expression, arguments );
    }

    internal virtual Expression VisitLambda( LambdaExpression lambda )
    {
        Expression body = Visit( lambda.Body );
        if ( body != lambda.Body )
        {
            return Expression.Lambda( lambda.Type, body, lambda.Parameters );
        }
        return lambda;
    }

    //internal virtual Expression VisitLift( LiftExpression lift )
    //{
    //    Expression expression = Visit( lift.Expression );
    //    ReadOnlyCollection<Expression> arguments = VisitExpressionList( lift.Arguments );
    //    if ( ( expression == lift.Expression ) && ( arguments == lift.Arguments ) )
    //    {
    //        return lift;
    //    }
    //    return Expression.MakeLift( lift.NodeType, expression, lift.Parameters, arguments );
    //}

    internal virtual Expression VisitListInit( ListInitExpression init )
    {
        NewExpression newExpression = VisitNew( init.NewExpression );
        IEnumerable<Expression> initializers = VisitExpressionList( init.Expressions );
        if ( ( newExpression == init.NewExpression ) && ( initializers == init.Expressions ) )
        {
            return init;
        }
        return Expression.ListInit( newExpression, initializers );
    }

    internal virtual Expression VisitMemberAccess( MemberExpression m )
    {
        Expression expression = Visit( m.Expression );
        if ( expression != m.Expression )
        {
            return Expression.MakeMemberAccess( expression, m.Member );
        }
        return m;
    }

    internal virtual MemberAssignment VisitMemberAssignment( MemberAssignment assignment )
    {
        Expression expression = Visit( assignment.Expression );
        if ( expression != assignment.Expression )
        {
            return Expression.Bind( assignment.Member, expression );
        }
        return assignment;
    }

    internal virtual Expression VisitMemberInit( MemberInitExpression init )
    {
        NewExpression newExpression = VisitNew( init.NewExpression );
        IEnumerable<MemberBinding> bindings = VisitBindingList( init.Bindings );
        if ( ( newExpression == init.NewExpression ) && ( bindings == init.Bindings ) )
        {
            return init;
        }
        return Expression.MemberInit( newExpression, bindings );
    }

    internal virtual MemberListBinding VisitMemberListBinding( MemberListBinding binding )
    {
        IEnumerable<Expression> initializers = VisitExpressionList( binding.Expressions );
        if ( initializers != binding.Expressions )
        {
            return Expression.ListBind( binding.Member, initializers );
        }
        return binding;
    }

    internal virtual MemberMemberBinding VisitMemberMemberBinding( MemberMemberBinding binding )
    {
        IEnumerable<MemberBinding> bindings = VisitBindingList( binding.Bindings );
        if ( bindings != binding.Bindings )
        {
            return Expression.MemberBind( binding.Member, bindings );
        }
        return binding;
    }

    internal virtual Expression VisitMethodCall( MethodCallExpression m )
    {
        Expression instance = Visit( m.Object );
        IEnumerable<Expression> arguments = VisitExpressionList( m.Arguments );
        if ( ( instance == m.Object ) && ( arguments == m.Arguments ) )
        {
            return m;
        }
        return Expression.MakeCall( m.NodeType, instance, m.Method, arguments );
    }

    internal virtual NewExpression VisitNew( NewExpression nex )
    {
        IEnumerable<Expression> arguments = VisitExpressionList( nex.Arguments );
        if ( arguments != nex.Arguments )
        {
            return Expression.New( nex.Constructor, arguments );
        }
        return nex;
    }

    internal virtual Expression VisitNewArray( NewArrayExpression na )
    {
        IEnumerable<Expression> initializers = VisitExpressionList( na.Expressions );
        if ( initializers == na.Expressions )
        {
            return na;
        }
        if ( na.NodeType == ExpressionType.NewArrayInit )
        {
            return Expression.NewArrayInit( na.Type.GetElementType(), initializers );
        }
        return Expression.NewArrayBounds( na.Type.GetElementType(), initializers );
    }

    internal virtual Expression VisitParameter( ParameterExpression p )
    {
        return p;
    }

    internal virtual Expression VisitTypeIs( TypeBinaryExpression b )
    {
        Expression expression = Visit( b.Expression );
        if ( expression != b.Expression )
        {
            return Expression.TypeIs( expression, b.TypeOperand );
        }
        return b;
    }

    internal virtual Expression VisitUnary( UnaryExpression u )
    {
        Expression operand = Visit( u.Operand );
        if ( operand != u.Operand )
        {
            return Expression.MakeUnary( u.NodeType, operand, u.Type, u.Method );
        }
        return u;
    }
}

Answer 3

Hi

 

These are very cool things indeed, but as Nicholas said - Funcletizating the expression is only half way to serializing it...

 

So is there a known/standard way to serialize an Funcletizatized expression ?

 

Answer 4

Hi Nicholas,

I have tried pasting your code above into my project as I need to do much the same thing as you describe here. However, I am getting exceptions as ExpressionType.Funclet is not a recognised type. Can you please advise what I need to do to fix this compilation error?

Thanks,

Grahame