面向组合子的设计模式

小说君今天就开始搬砖了，先预备下心情，找篇老文修改修改发订阅号。

面向组合子（Combinator-Oriented），这个词的出处已经不可考，小说君随手google了下，可能源头就是ajoo在05年的连载系列。

需要声明的是，此组合子并非源于数理逻辑中的Combinator logic，而是Haskell中鼎鼎大名的PaserCombinator库。

对ParserCombinator没什么概念的同学，可以移步看看小说君之前的「21分钟学会写编译器」所实现的极简parser，或者「 用DSL实现更高效的AI制作流程 」所实现的略微有点复杂的行为树DSL parser。

熟读GoF的同学可能会疑惑，既然是「设计模式」，为什么23种模式中并没有听说过有一种叫「面向组合子」设计模式。

其实小说君也不知道「设计模式」的具体定义，不仅是「面向组合子」，像「生产者消费者」明明也是经典的设计「pattern」，为什么没有被归为「设计模式」？

这个问题就期待有高人能留言解答了，下面废话不多说，进入正文。

既然是讲设计模式，那我们自然是要从代码实例出发。

我们今天的业务情景是代码生成。

代码生成是生产流程中必不可少的一种解决问题方式，相信各位都不陌生，不过如果是在校学生接触一些生产性质的框架比较少的话，可能还需要学习一个。

抽象来说，代码生成就是嵌入于构建流程中的某一步骤，所做的工作就是拿一些元描述信息，生成代码，供后续构建流程使用。

小说君目前所接触过的代码生成的具体应用情景，有这样几种：

1. RPC相关的，数据打解包逻辑、Stub/Skeleton、组播等逻辑都可以借助工具自动生成。

2. 配表转代码的工作流中，序列化反序列化逻辑可以借助工具自动生成。

3. 策划配出来的可视化行为树转为代码，准确说是DSL编译器的代码生成器。

从这些情景可以看出这种需求的典型特征：性能好、便于上层调用。

具体来说，我们还是拿这种形式跟一些比较传统的形式做下对比：

• RPC打解包逻辑直接自动走函数 V.S. protobuf

• DSL转为C#代码的行为树 V.S. 运行时硬解DSL

• C#结构描述的配置 V.S. 一坨meta二进制+一坨data二进制

代码生成对比得出的优势相当明显。

来看看具体的业务情景。

在元数据中定义有这样一个方法：

List<ulong> GetValues(ulong key);

需求是，代码生成器要根据上面元数据中定义的方法，生成对应的代码框架：

List<ulong> GetValues(ulong key)
{
    // ...
}

现在假设不论是通过反射也好、parse也好，代码生成器将要拿到的实例结构定义是这样：

class MethodMeta
{    
    public string Name;
    public Type ReturnType;
    public List<ParaMeta> Params;
}

class ParaMeta
{    
    public string Name;
    public Type Type;
}

也就是说，代码生成器拿到的MethodMeta实例，描述的就是我们之前在元数据中定义的GetValues方法（包括方法名、返回值类型、所有参数的名字和类型）。

代码生成逻辑的最典型的写法就变成了这样：

void SerializeMethodMeta(StringBuilder sb, MethodMeta meta)
{
    SerializeType(sb, meta.ReturnType);

    sb.Write(" ");
    sb.Write(meta.Name);

    sb.Write("(");

    foreach (var pm in meta.Params)
    {
        SerializeParaMeta(sb, pm);
        if (pm != meta.Params[meta.Params.Length-1])
        {
            sb.Write(",");
        }
    }

    sb.Write("){//...}");
}

不仅有很多冗余代码，而且代码本身并没有直观地描述这个生成器的生成逻辑。

那接下来我们用面向组合子的方式解决这个问题。

首先我们定义一个概念，Coder，这里我们把它理解为一个函数，接收一个T描述结构作为参数，输出一个字符串。

Coder定义：

public interface ICoder<in T> 
{
    string Code(T meta);
}

这是所有Coder的基本表现形式，与之对应的，任何复杂的代码生成程序，其实本质都是通过一个抽象数据结构生成一个字符串。

基于ICoder，我们先 构造 最简单的Coder，也就是 「0」 和 「1」 ：

internal class ZeroCoder<T> : ICoder<T>
{
    private static ZeroCoder<T> instance;
    public static ZeroCoder<T> Instance
    {        
        get { return instance ?? (instance = new ZeroCoder<T>()); }
    }    
    public string Code(T meta)
    {        
        return "";
    }
}

internal class UnitCoder<T> : ICoder<T>
{
    readonly string output;
    public UnitCoder(string output)
    {
        this.output = output;
    }

    public string Code(T meta)
    {        
        return output;
    }
}

ZeroCoder：不论给什么作为输入，都返回空字符串。

UnitCoder：不论给什么作为输入，都返回一个固定的字符串。

只有这两个的话，似乎什么都不能做，我们需要一个最基本的可以让我们定制的Coder：

internal class BasicCoder<T> : ICoder<T> 
{
    private readonly Func<T, string> func;
    public BasicCoder(Func<T, string> func)
    {        
        this.func = func;
    }    
    public string Code(T meta)
    {        
        return func(meta);
    }
}

如此构造一个Coder：

var paramCoder = "{0} {1}".Basic<ParaMeta>(m => TypeToString(m.Type), m => m.Name);

这个Coder的输入是一个ParaMeta，输出是我们需求的函数signature的一部分。

如此一来，通过给paramCoder传不同的、具体的ParaMeta实例，这个Coder就跟真的Coder一样coding出了不同的代码。

这三种Coder，构成了组合子体系中的 「单位」。 我们还需要想办法将这些单位组合起来，形成 「组合子」 。

需求中，MethodMeta的Params是一个List，因此我们需要一个输入是List<ParaMeta>的Coder。

这种Coder实际上是通过一定的重复规则将独立的Coder组合起来：

internal class RepeatedCoder<T> : ICoder<IEnumerable<T>>
{    
    private readonly ICoder<T> coder;    
    private readonly string seperator;    
    private readonly Func<T, bool> predicate;    
    public RepeatedCoder(ICoder<T> coder, string seperator, Func<T, bool> predicate)
    {        
        this.coder = coder;        
        this.seperator = seperator;        
        this.predicate = predicate;
    }    
    public string Code(IEnumerable<T> meta)
    {        
        bool first = true;        
        return meta.Where(m => predicate(m)).Select(coder.Code).Aggregate("", (val, cur) =>
        {            
            if (first)
            {
                first = false;                
                return val + cur;
            }            
            return val + seperator + cur;
        });
    }
}

然后，一行代码，就组合出了我们需要的、能Code出signature参数表部分的Coder：

var paramsCoder = paramCoder.Many(",");

不过，Repeated只能做同构的组合，更多情况下，我们需要的是异步组合。

比如说 「(ulong key)」 ，其实是 「 ( 」、paramsCoder、 「 ) 」三个Coder组合出来的Coder。

其中， 「 ( 」、 「 ) 」都是UnitCoder。

因此，我们需要定义一种可以组合异构Coder的组合子：

internal class SequenceCoder<T> : ICoder<T> 
{
    readonly Func<T, string>[] binders;    
    public SequenceCoder(params Func<T, string>[] binders)
    {        
        this.binders = binders;
    }    
    public string Code(T meta)
    {        
        return string.Join("", binders.Select(binder => binder(meta)));
    }
}

定义两个方便使用的扩展方法：

public static ICoder<T> WithPostfix<T>(this ICoder<T> coder, string postfix) 
    where T : class
{
    var coderPostfix = new UnitCoder<T>(postfix);
    return new SequenceCoder<T>(coder.Code, coderPostfix.Code);
}
public static ICoder<T> WithPrefix<T>(this ICoder<T> coder, string prefix) 
    where T : class
{
    var coderPrefix = new UnitCoder<T>(prefix);
    return new SequenceCoder<T>(coderPrefix.Code, coder.Code);
}

为了更声明式地写代码，我们甚至还能这样：

public static ICoder<T> Bracket<T>(this ICoder<T> coder) 
    where T : class
{
    return coder.WithPostfix(")").WithPrefix("(");
}

然后我们就可以这样组合Coder了：

var paramsCoder2 = paramsCoder.Bracket();

paramsCoder2现在是一个输入为IEnumerable<ParaMeta>的Coder。

用类似的方法，我们还能写出一个输入为Type的Coder，一个输入为string的Coder（也就是UnitCoder）。

然后，用异步组合的方式，将这三个组合为一个输入为MethodMeta的Coder。

这其实相当于一种lift，看下函数定义：

public static ICoder<T> Combine<T, T1>(this ICoder<T> coder, ICoder<T1> coder2, Func<T, T1> selector)
{
    return new SequenceCoder<T>(coder.Code, meta => coder2.Code(selector(meta)));
}

这种Combine是对上述组合方式的简化，我们假设先定义好一个输入为MethodMeta的Coder，然后用Combie去 「 吞并 」 一个输入为IEnumerable<ParaMeta>的Coder，最终自然还是一个输入为MethodMeta的Coder。

组合一下：

var coder = "{0} ".Basic<MethodMeta>(m=>TypeToString(m.ReturnType))
                  .Combine(paramsCoder2, m=>m.Params)
                  .WithPostfix("{//...}");

大功告成。

现在的coder，只要每次给一个MethodMeta实例，就会自动输出我们需求中提的代码形式。

写到这里，也许有同学会疑惑，ZeroCoder的意义是什么？

由于篇幅原因，小说君没有把TypeToString也展开写成一个Coder。

如果写的话，因为泛型类型需要特殊处理，就需要引入充当条件判断角色的组合子——条件判断通过，则正常表现为子Coder；条件判断不通过，表现为ZeroCoder。

本文的示例代码，由于篇幅原因都做了简化，详细地实现可以参考小说君在github上面的代码示例。

由于现在文章中仍然没法加外链，有兴趣的同学可以后台发消息 「 组合子 」拿到github链接。

需要注意的是，面向组合子的设计模式只提供了一种思路，这种pattern本身坑也很多，比如由于嵌套过多lambda导致的调试困难通病、写起来并不比常规方法优雅太多等等。

不过，用不同的思路解决问题，不正是编程的初心吗？

个人订阅号：gamedev101「说给开发游戏的你」，聊聊服务端，聊聊游戏开发。