Sketch/FlashFill合成

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

认识程序合成

你不需要背出油盐酱醋的精确克数，只要对主厨说“我想要一碗带溏心蛋的面”，他就能把整道菜做出来。传统编程就像你事无巨细地指挥主厨：“先放油，再放葱，三分钟后加水……”程序合成则把指挥权交给系统：你描述“要什么”，系统自动写出“怎么做”。

从技术上说，程序合成（Program Synthesis）是在一个由合法程序构成的空间里，自动寻找满足用户意图的程序。用户的意图可以是输入输出示例、自然语言描述、形式化规约，或者一张不完整的草图。Sketch 和 FlashFill 是这个领域最有名的两个代表：前者面向通用代码补全，后者面向表格文本变换。

用一个公式可以概括合成问题的核心：

Sketch 像酒店后厨的大师傅：先写一个粗略流程，然后让助手补齐细节。FlashFill 则像街边小摊老板：看一眼客人比划的样例，马上做出同样风格的小吃。它们共享同一个目标——从“模糊的需求”走向“确定的程序”。

Sketch核心原理

Sketch 的灵感来自“先画草图，再请人完善”。主厨写菜谱时，会留下“加少许____”这样的空格；Sketch 把这些空格称为占位符（Hole），通常用 ?? 表示。用户给出一个不完整的程序骨架，合成器负责把每个洞填上具体表达式。

这个“填洞”过程不能乱来。Sketch 使用语法引导搜索（Syntax-Guided Synthesis，SyGuS）：先定义一组允许出现的语法，比如只能使用加、减、乘和常量，再枚举候选填充方案。把候选填进草图后，验证器会检查它是否满足全部约束。

验证失败时，最漂亮的一招出现了：CEGIS（Counterexample-Guided Inductive Synthesis，反例引导的归纳合成）。验证器不是简单地说“不行”，而是返回一个反例，比如“输入为 3 时你输出了 7，但期望是 8”。合成器把反例加入示例集，重新搜索，直到没有反例或超时。整个过程可以写成：

这个流程像主厨反复试菜：先按暂定菜谱做一道，试菜员尝出“太咸”，他就在下一版减少盐量。CEGIS 的价值在于，每次失败都会带来一条新信息，让搜索越来越有方向。

FlashFill原理

FlashFill 是一道更家常的菜：在 Excel 里，用户手动示范“John Smith → J. Smith”，再按一下回车，整列都能自动生成类似缩写。它不要求用户写代码，只要求提供输入输出示例，因此也叫“编程通过示例”（Programming by Example，PBE）。

为什么机器能“照葫芦画瓢”？因为 FlashFill 为字符串变换设计了一个专属 DSL。这个领域特定语言限制了食材种类，让搜索不必漫无目的。常见的表达式语法是：

有了 DSL，FlashFill 会枚举所有候选表达式，再用示例过滤。最后它按“长度短、常量少、结构简单”的规则给候选打分，把最像人类手写的表达式排在前面。这正是主厨从三碗成品中猜出统一做法：先限定可用调料，再挑最简单说得通的版本。

关键算法

主厨手里有很多半成品：切好的葱花、调好的酱汁、煮到七分的面条。程序合成器也一样，擅长把已经验证过的子表达式拼接成更大的表达式。版本空间代数（Version Space Algebra）就是一套高效管理“候选集合”的方法。

普通初学者可能会把每个候选程序单独存起来，但程序空间会爆炸。版本空间代数的聪明之处在于：用集合的交、并、笛卡尔积运算来表示一大片候选，而不必逐个列出。例如，当已知左边候选集合 S1 和右边候选集合 S2 后，拼接表达式的集合可以写成：

在实际合成中，系统还会做一致性检验：如果一个表达式在某些示例上失败，就把它从版本空间里剔除；如果两个候选相互冲突，就保留更符合多数示例的一方。这就像主厨面对两个客人的口味矛盾，选择一套能同时满足最多人的固定流程。

性能与优化

菜谱越复杂，厨房要尝试的组合就越多。程序合成最怕的是搜索空间爆炸：明明只有几十种基本操作，组合起来却像天文数字。Sketch 和 FlashFill 都在拼命“省火省时”。

第一招是剪枝：遇到一个子表达式在某条示例上已经失败，就整棵剪掉，不再尝试它的各种上层组合。第二招是缓存复用：同一个字符串片段可能被多个候选用到，与其反复计算，不如把结果缓存起来，像提前批量切好的菜。第三招是多列协同合成：电子表格里常常同时需要改姓名、日期、金额，合成器让多列共享中间变换，一起逼近最终格式。

搜索代价可以粗略表示成：

剪枝和缓存还能继续互相配合：缓存让剪枝判断更快，剪枝让缓存里存的东西更少。主厨的灶台也讲究“顺手”：把最常用的高汤提前备好，把不合适的配方直接扔掉，整个后厨才能高效运转。

应用与场景

Sketch 和 FlashFill 不只活在论文里，它们已经悄悄出现在你每天使用的工具中。最典型的是表格数据处理：几万行地址需要统一成“省-市-区”格式，手写公式又长又容易错；用 FlashFill 风格的工具，只要手动改两行示例，系统就能生成一整列转换规则。

代码自动化也是重头戏。工程师写排序函数时，可以只画出整体框架，把实现细节留成洞，交给 Sketch 类工具补全。数据清洗管道同样受益：ETL 流程里常见的日期格式转换、手机号脱敏、姓名拆分，都能靠“示例即规则”快速生成，而不是写一堆 if else。

教学场景同样有趣：学生输入“3 → 9、4 → 16”，可以让系统自动合成一个平方函数，帮助理解抽象逻辑。对 AI 从业者来说，这些应用意味着一个共同趋势：把“写代码”变成“描述代码”，而程序合成就是这套自动化的核心引擎。

挑战与前瞻

主厨也会遇到难题：客人只给三个例子，却要求覆盖一百种口味。程序合成目前最大的挑战，是如何处理复杂约束与海量搜索之间的矛盾。规格越复杂，验证越慢；示例太少，又容易学到过度拟合的错误程序。

可解释性同样棘手。系统给出一个能通过所有示例的表达式，但用户往往想问“为什么是这个而不是另一个”。如果合成器能提供简单的排名理由，比如“这个表达式最短、用到的常量最少”，信任感会大大增强。数据隐私也值得关注，因为合成过程常接触敏感表格数据，直接在本地端侧完成合成，会是一大趋势。

与大模型结合是新的希望：大模型擅长理解自然语言和生成候选代码，Sketch/FlashFill 擅长用验证器保证正确性。两者结合，就像主厨先用经验快速设计菜式，再让试菜员系统把关。未来的程序合成，会离“只表达意图，不关心实现”的梦想越来越近。

AI 应用场景

Python 演示

# coding: utf-8"""A mini Sketch-style synthesizer:learn arithmetic expression from input-output examples.""" def evaluate(expr, x):    if isinstance(expr, int):        return expr    if expr == 'x':        return x    left, op, right = expr    if op == '+':        return evaluate(left, x) + evaluate(right, x)    if op == '-':        return evaluate(left, x) - evaluate(right, x)    if op == '*':        return evaluate(left, x) * evaluate(right, x)    raise ValueError('unknown expression') def size(expr):    if isinstance(expr, int) or expr == 'x':        return 1    return 1 + size(expr[0]) + size(expr[2]) def to_string(expr):    if isinstance(expr, int):        return str(expr)    if expr == 'x':        return 'x'    return '(' + to_string(expr[0]) + expr[1] + to_string(expr[2]) + ')' def synthesize(examples, max_size=5):    exprs = ['x'] + list(range(0, 10))    for d in range(2, max_size + 1):        base = list(exprs)        for left in base:            for op in ['+', '-', '*']:                for right in base:                    e = (left, op, right)                    if size(e) == d:                        exprs.append(e)    valid = []    for expr in exprs:        if all(evaluate(expr, x) == y for x, y in examples):            valid.append(expr)    valid.sort(key=lambda e: (size(e), to_string(e)))    return valid[0] if valid else None if __name__ == '__main__':    examples = [(2, 5), (3, 10), (4, 17)]    expr = synthesize(examples)    if expr is not None:        print('synthesized:', to_string(expr))        for x, y in examples:            print('f(%d) = %d' % (x, evaluate(expr, x)))    else:        print('no expression found')

1. exprs = ['x'] + list(range(0, 10))初始原料：输入变量和常量 0 到 9。
2. if size(e) == d:只保留指定复杂度的候选表达式，防止无限膨胀。
3. if all(evaluate(expr, x) == y for x, y in examples):用全部示例验证候选，不满足就淘汰。
4. valid.sort(key=lambda e: (size(e), to_string(e)))按“更短、更直观”排名，类似 FlashFill 的排序偏好。
5. print('synthesized:', to_string(expr))输出最终合成出的表达式。

常见误区

面试题