Не так давно на 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);
}
}
... << RSDN@Home 1.2.0 alpha 4 rev. 1090>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Не так давно на RSDN отгремели дискуссии вроде этойАвтор: SmbdRsdn
Дата: 22.04.08
в которых демонстрировались примеры использования какбы-сопоставления-с-образцом в Java-синтаксисе. В ответ на резонный вопрос о том, что представляет из себя магический метод Match демонстрировалось загадочное лицо и рассуждения о том, что реализация тривиальна.
Напишите кто-нибудь квази-квази-паттерн-матчинг на С++, может тогда я пойму чем это отличается от свича с регулярными выражениями вместо кейсов...
Ведь чем-то точно отличается, но вот чем....
Здравствуйте, x-code, Вы писали:
XC>Здравствуйте, Klapaucius, Вы писали:
K>>Не так давно на RSDN отгремели дискуссии вроде этойАвтор: SmbdRsdn
Дата: 22.04.08
в которых демонстрировались примеры использования какбы-сопоставления-с-образцом в Java-синтаксисе. В ответ на резонный вопрос о том, что представляет из себя магический метод Match демонстрировалось загадочное лицо и рассуждения о том, что реализация тривиальна.
XC>Напишите кто-нибудь квази-квази-паттерн-матчинг на С++, может тогда я пойму чем это отличается от свича с регулярными выражениями вместо кейсов...
XC>Ведь чем-то точно отличается, но вот чем....
В паттерн матчинге можно проверять не только значения, но и типы значений и отдельные поля внутри значений и типы отдельный полей внтри значений. И при этом на связывать значения с переменными, если в этом нет необходимости
Для С++ есть
Prop, который потом развертывается в необходимый код на С++ (
разбор дерева ->
сгенерированй код)
Здравствуйте, x-code, Вы писали:
XC>Напишите кто-нибудь квази-квази-паттерн-матчинг на С++,
У меня точно не получится.
XC>может тогда я пойму чем это отличается от свича с регулярными выражениями вместо кейсов...
XC>Ведь чем-то точно отличается, но вот чем....
The Hatter opened his eyes very wide on hearing this; but all he said was “Why is a raven like a writing-desk?”
“Come, we shall have some fun now!” thought Alice. “I’m glad they’ve begun asking riddles—I believe I can guess that,” she added aloud.
“Do you mean that you think you can find out the answer to it?” said the March Hare.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll