Не так давно на RSDN отгремели дискуссии вроде этой

Автор: SmbdRsdn
Дата: 22.04.08

в которых демонстрировались примеры использования какбы-сопоставления-с-образцом в Java-синтаксисе. В ответ на резонный вопрос о том, что представляет из себя магический метод Match демонстрировалось загадочное лицо и рассуждения о том, что реализация тривиальна.
Не подумайте, что я решил заняться PM-троллингом — мне просто было интересно подумать, как можно реализовать что-то подобное и у меня реализация будет приведена. Сразу говорю, что это не велосипед с треугольными колесами и в форуме "исходники" ему не место — это фокус-иллюстрация. Реализация наивная и не претендует на практичность, также я отдаю себе отчет в том, что это строго говоря не PM — это квази PM.
Ничего подобного я здесь еще не видел, может кому-нибудь покажется интересным.

class Program
{
    public abstract class Expr{}

    public class Var : Expr
    {
        public Var(string name) { Name = name; }
        public string Name { get; private set; }
    }

    public class Const : Expr
    {
        public Const(int val) { Val = val; }
        public int Val { get; private set; }
    }

    public class Add : Expr
    {
        public Add(Expr le, Expr re) { LExpr = le; RExpr = re; }
        public Expr LExpr { get; private set; }
        public Expr RExpr { get; private set; }
    }

    public class Mul : Expr
    {
        public Mul(Expr le, Expr re) { LExpr = le; RExpr = re; }
        public Expr LExpr { get; private set; }
        public Expr RExpr { get; private set; }
    }

    public static string PrettyPrint(Expr e)
    {
        return e.Case((Const c) => c.Val.ToString())
                .Case((Var v) => v.Name)
                .Case((Add op) => string.Format("({0} + {1})", PrettyPrint(op.LExpr), PrettyPrint(op.RExpr)))
                .Case((Mul op) => string.Format("{0}*{1}", PrettyPrint(op.LExpr), PrettyPrint(op.RExpr)))
                .Result(); // если ни один из "паттернов" не будет сопоставлен будет выброшено исключение.
    }

    public static Expr ASTTransform(Expr e, Func<Expr, Expr> f)
    {
        return e.Case((Var v) => f(v))
                .Case((Const c) => f(c))
                .Case((Mul op) => f(new Mul(ASTTransform(f(op.LExpr), f), ASTTransform(f(op.RExpr), f))))
                .Case((Add op) => f(new Add(ASTTransform(f(op.LExpr), f), ASTTransform(f(op.RExpr), f))))
                .Result();
    }

    public static Expr Apply(Expr e, IDictionary<string, int> env)
    {
        return e.Case((Var v) => (Expr)new Const(env[v.Name])).Default(e);
    }

    public static Expr Simplify(Expr e)
    {
        return e.Case((Mul op) => op.LExpr.When((Const c) => c.Val == 1).Result(op.RExpr))
                .Case((Mul op) => op.RExpr.When((Const c) => c.Val == 1).Result(op.LExpr))
                .Case((Add op) => op.LExpr.When((Const c) => c.Val == 0).Result(op.RExpr))
                .Case((Add op) => op.RExpr.When((Const c) => c.Val == 0).Result(op.LExpr))
                .Default(e);
    }

    public static Expr ConstFold(Expr e)
    {
        return e.Case((Add op) => op.LExpr.With(op.RExpr)
                    .Case((Const a, Const b) => (Expr) new Const(a.Val + b.Val)).Default(op))
                .Case((Mul op) => op.LExpr.With(op.RExpr)
                    .Case((Const a, Const b) => (Expr) new Const(a.Val*b.Val)).Default(op))
                .Default(e);
    }

    static void Main()
    {
        var e = new Add(new Add(new Add(new Var("x"), new Const(0)),
                                new Mul(new Var("y"), new Const(1))), new Add(new Const(2), new Const(5)));
        
        Console.WriteLine("expression: {0}",PrettyPrint(e));

        Console.WriteLine("simplification: {0}",PrettyPrint(ASTTransform(e, Simplify)));

        Console.WriteLine("const. folding: {0}",PrettyPrint(ASTTransform(e, ConstFold)));

        var env = new Dictionary<string, int> {{"x", 7}, {"y", 9}};

        Console.WriteLine("application: {0}", PrettyPrint(ASTTransform(e, _ => Apply(_, env))));

        Console.WriteLine("result: {0}", PrettyPrint(ASTTransform(ASTTransform(e, _ => Apply(_, env)), ConstFold)));
    }
}

А вот реализация:

[Serializable]
public class PatternMatchingException : Exception
{
    public PatternMatchingException() { }
    public PatternMatchingException(string message) : base(message) { }
    public PatternMatchingException(string message, Exception inner) : base(message, inner) { }
    protected PatternMatchingException(
      System.Runtime.Serialization.SerializationInfo info,
      System.Runtime.Serialization.StreamingContext context)
        : base(info, context) { }
}

public class Pair<T1, T2>
{
    public Pair(T1 first, T2 second)
    {
        First = first;
        Second = second;
    }

    public T1 First { get; private set; }
    public T2 Second { get; private set; }
}

public static class PM
{
    public static Pair<T1, T2> With<T1, T2>(this T1 f, T2 s)
    {
        return new Pair<T1, T2>(f, s);
    }

    public class Res<T, RT>
    {
        public T Variant { get; set; }
        public RT Value { get; set; }
        public bool Matched { get; set; }
    }

    public class Res<RT>
    {
        public RT Value { get; set; }
        public bool Matched { get; set; }
    }

    public class Res
    {
        public bool Matched { get; set; }
    }

    public static Res<T, RT> Case<T, RT, VT>(this Res<T, RT> result, Func<VT, RT> pattern)
        where VT : T
    {
        if (!result.Matched && (result.Variant is VT))
        {
            return new Res<T, RT> { Variant = result.Variant, Value = pattern((VT)result.Variant), Matched = true };
        }

        return result;
    }

    public static Res<T, RT> Case<T, RT, VT>(this Res<T, RT> result, Func<VT, Res<RT>> pattern)
        where VT : T
    {
        if (!result.Matched && (result.Variant is VT))
        {
            var pr = pattern((VT) result.Variant);
            if(pr.Matched) return new Res<T, RT> { Variant = result.Variant, Value = pr.Value, Matched = true };
        }

        return result;
    }

    public static Res<T, RT> Case<T, RT, VT>(this T var, Func<VT, Res<RT>> pattern)
        where VT : T
    {
        if (var is VT)
        {
            var pr = pattern((VT)var);
            if (pr.Matched) return new Res<T, RT> { Variant = var, Value = pr.Value, Matched = true };
        }

        return new Res<T, RT> {Variant = var, Value = default(RT), Matched = false};
    }

    public static Res When<T, U>(this T var, Func<U, bool> pred)
        where U : T
    {
        if(var is U)
        {
            if(pred((U)var))
            {
                return new Res{Matched = true};
            }
        }

        return new Res{Matched = false};
    }

    public static Res<T> Result<T>(this Res result, T value)
    {
        return new Res<T>{Value = value, Matched = result.Matched};
    }

    public static Res<Func<T>> Result<T>(this Res result, Func<T> value)
    {
        return new Res<Func<T>> { Value = value, Matched = result.Matched };
    }

    public static Res<T, RT> Case<T, RT, VT>(this T variant, Func<VT, RT> pattern)
        where VT : T
    {
        if (variant is VT)
        {
            return new Res<T, RT> { Variant = variant, Value = pattern((VT)variant), Matched = true };
        }

        return new Res<T, RT>{Variant = variant, Value = default(RT), Matched = false};
    }

    public static Res<Pair<T1, T2>, RT> Case<T1, T2, RT, V1, V2>(this Pair<T1, T2> variants, Func<V1, V2, RT> pattern)
        where V1 : T1
        where V2 : T2
    {
        if ((variants.First is V1) && (variants.Second is V2))
        {
            return new Res<Pair<T1, T2>, RT> { Variant = variants, Value = pattern((V1)variants.First,(V2)variants.Second), Matched = true };
        }

        return new Res<Pair<T1, T2>, RT> { Variant = variants, Value = default(RT), Matched = false };
    }

    public static RT Result<T, RT>(this Res<T, RT> result)
    {
        if (!result.Matched) throw new PatternMatchingException();
        return result.Value;
    }

    public static RT Default<T, RT>(this Res<T, RT> result, RT defaultVal)
    {
        return result.Matched ? result.Value : defaultVal;
    }

    public static RT Default<T, RT>(this Res<T, RT> result, Func<RT> f)
    {
        return result.Matched ? result.Value : f();
    }

    public static RT Default<T, RT>(this Res<T, RT> result, Func<T, RT> f)
    {
        return result.Matched ? result.Value : f(result.Variant);
    }
}