COMS 3997 · Neurosymbolic AI · Week 3

FlashFill

Automating String Processing in Spreadsheets Using Input-Output Examples

Sumit Gulwani · POPL 2011

Input	Output
Alan Turing	Turing, A.
Grace Hopper	Hopper, G.
Ada Lovelace	Lovelace, A.
Edsger Dijkstra	Dijkstra, E.

The user types the first output. The program fills in the green cells.

The problem

End users can show the task, not code it

Spreadsheet help forums are full of requests for one-off string reformatting: names, dates, phone numbers, addresses.

The person asking can give examples of what they want, but not a formula or a script.

Goal: learn the transformation from a few examples, fast enough to feel instant.

Input	Output
323-708-7700	323-708-7700
(425)-706-7709	425-706-7709
510.220.5586	510-220-5586
(206) 555 0133	206-555-0133

Three formats, one program: take the 1st, 2nd and 3rd run of digits and join them with “-”. The last row is filled in by the program.

FlashFill · Gulwani, POPL 2011

2

Why it's hard

One example fits many programs

“Alan Turing” → “Turing, A.”

Candidate program (all consistent with the example)	On “Grace Brewster Hopper”
Always output the constant “Turing, A.”	“Turing, A.”
Characters 5–10, then “, ”, character 0, “.”	“ Brews, G.”
Everything after the first space, then “, ”, first letter, “.”	“Brewster Hopper, G.”
The second word, then “, ”, first letter, “.”	“Brewster, G.”
The last word, then “, ”, first letter, “.”	“Hopper, G.” (intended)

FlashFill · Gulwani, POPL 2011

3

The one idea to remember

Don't pick a program. Keep all of them, then intersect.

A version-space algebra over a string DSL: exponentially many consistent programs, stored in a polynomial-size DAG. Each new example is an intersection. Ranking picks one at the end.

The language

A small DSL built for string edits

P := Switch((b1,e1), …, (bn,en))
e := Concatenate(f1, …, fn)
f := ConstStr(s)
   | SubStr(vi, p1, p2)
   | Loop(λw. e)
p := CPos(k) | Pos(r1, r2, c)
r := TokenSeq(T1, …, Tm)
b := ∨ of ∧ of Match(vi, r, k)

A program is a concatenation

Constant strings and substrings of the inputs, glued together.

Substrings are cut at positions

A fixed index CPos(k), or a context Pos(r1, r2, c). Regexes are just sequences of tokens.

Conditionals and loops on top

Switch chooses a trace by Match predicates. Loop repeats one for w = 1, 2, …

FlashFill · Gulwani, POPL 2011

5

Positions, part 1

Where do you cut? Fixed indices break

“Alan Turing”: cut at gap 5 copies “Turing”, correct

A

l

a

n

␣

T

u

r

i

n

g

0

1

2

3

4

5

6

7

8

9

10

11

“Ada Lovelace”: cut at gap 5 copies “ovelace”, wrong

A

d

a

␣

L

o

v

e

l

a

c

e

0

1

2

3

4

5

6

7

8

9

10

11

12

A position is a gap between characters, numbered from 0 up to the string's length.

SubStr(v1, p1, p2) copies whatever lies between two positions of input v1.

The simplest position is a number: CPos(5) means “gap 5”. It fits the first example, then cuts the second name mid-word.

What we mean is “the gap right after the space, where the letters start”. The next slide shows how to write that down.

FlashFill · Gulwani, POPL 2011

6

Positions, part 2

Describe a cut by what surrounds it

Token (a character class)	Matches
AlphaTok	a run of letters
NumTok	a run of digits
UpperTok, LowerTok	capitals, lower-case
WhiteSpaceTok	a run of spaces
StartTok, EndTok	start, end of the string
HyphenTok, CommaTok, …	one per punctuation mark

Pos(r1, r2, c)

The c-th gap where the text just before it matches r1 and the text just after it matches r2. r1 and r2 are sequences of tokens. c = 1 is the first such gap, and c = −1 is the last.

Pos(WhiteSpaceTok, AlphaTok, 1) is “after a space, before letters”: gap 5 in Alan Turing and gap 4 in Ada Lovelace. It's one description, and it's right for both.

c = 1 (gap 6)

c = −1 (gap 15)

G

r

a

c

e

␣

B

r

e

w

s

t

e

r

␣

H

o

p

e

r

On “Grace Brewster Hopper” two gaps have a space before and letters after: c = 1 gives “Brewster Hopper”, c = −1 gives “Hopper”. On “Alan Turing” both pick gap 5, so one example can't tell them apart.

FlashFill · Gulwani, POPL 2011 · Section 3

7

This is the construct that makes FlashFill generalize, so take your time. Tokens are character classes: AlphaTok matches one or more letters, NumTok one or more digits, and so on, with a special token for each punctuation character plus StartTok and EndTok. r1 and r2 are short sequences of tokens, and the empty sequence ε matches anything, for when one side doesn't matter. Pos(r1, r2, c) picks the c-th gap t where r1 matches some text ending at t and r2 matches some text starting at t. Negative c counts from the end. Walk the class through the grid: which gaps have whitespace on the left and letters on the right? Gaps 6 and 15. So c = 1 and c = -1 are different programs that agree on every two-word name. That sets up the ambiguity the version space has to keep, and that the ranking or another example has to resolve.

Version spaces

Keep the choices, not the programs

A version space is the set of all programs consistent with the examples so far. After one example it is enormous: too big to list, let alone test one by one. FlashFill's trick is to store it as independent choices.

Where “Turing” starts

CPos(5)
Pos(WhiteSpaceTok, AlphaTok, 1)
Pos(WhiteSpaceTok, AlphaTok, -1)

×

Where it ends

CPos(11)
CPos(-1)
Pos(AlphaTok, EndTok, 1)

=

9 programs SubStr(v1, start, end), stored as 3 + 3 entries

Real sets are far bigger, and the saving compounds at every level: token sets inside positions, positions inside substrings, substrings inside the concatenation. The algebra is the set of operations on these factored sets: intersect them, count them and run them, all without listing programs.

Mitchell 1982: version spaces for concept learning

→

Lau et al. 2000: version-space algebra for demonstration

→

FlashFill 2011: lifted to examples, with conditionals and loops

FlashFill · Gulwani, POPL 2011 · Sections 4.1 and 7

8

This is the conceptual pivot of the talk. The term comes from Tom Mitchell's "Generalization as search" (1982): in concept learning you keep the set of all hypotheses consistent with the data and shrink it as examples arrive. Lau, Domingos and Weld (ICML 2000) turned it into an algebra: build the version space of a complex function by composing the version spaces of its parts. FlashFill lifts that to programming by example. The picture: take just the "Turing" piece of the output. Using what we saw on the positions slides, there are several ways to say where it starts and several ways to say where it ends. Any start can pair with any end, so 3 × 3 = 9 SubStr programs. But you don't store 9 programs; you store the two lists of 3. That's the whole idea in miniature: a product of choices stored as a sum. The same factoring happens inside each Pos (sets of r1, r2 and c) and across the pieces of the output, which is the next slide. These three-item lists are illustrative; the real sets are larger.

From splits to a graph

Why a graph? Each path is one way to split the output

A program glues pieces together, but which pieces? “Turing, A.” could be one piece, or “Turing” + “, A.”, or “Turing” + “, ” + “A” + “.”, and so on. Put a node at each place the output could be cut, and an edge for each piece:

0

6

8

9

10

“Turing”

“, ”

“A”

“.”

“Turing, ”

“, A”

“A.”

“Turing, A”

“, A.”

“Turing, A.”

Any path from 0 to 10 spells the output: the green one is “Turing” + “, ” + “A” + “.”. Edges only go left to right and never loop back, so this is a directed acyclic graph (DAG). Drawn here: 5 nodes, 8 paths. The real one has a node at every character: 11 nodes, 55 edges, 512 paths.

FlashFill · Gulwani, POPL 2011 · Section 4.3

9

This slide answers "where did the DAG come from?" The output is built by Concatenate, gluing pieces, but the synthesizer doesn't know how the user's output was cut into pieces. Maybe "Turing, A." is one constant string; maybe it's four pieces. Trying every split separately would be exponential: a 10-character output has 2^9 = 512 ways to cut it. The paper's key observation (Section 4.3) is that there are only quadratically many pieces, one per substring: 55 here. So make a node for each cut point and an edge for each piece. Then every split is a path, and the 512 splits share just 55 edges. It's "directed" because edges go left to right, and "acyclic" because you can never return to an earlier position. For readability I've drawn only the cut points at word boundaries: 5 nodes and 8 paths instead of 11 nodes and 512.

GenerateStr · the version space for the whole output

Label each edge with every way to make its piece

“Turing”

“, ”

“A”

“.”

0

6

8

9

10

Same graph as the last slide (only the green path drawn). Each edge now carries a set: every atomic expression that produces its piece, a constant or a SubStr with sets of positions.

Edge 0 → 6, “Turing”

ConstStr(“Turing”), SubStr(v1, {CPos(5), Pos(WhiteSpaceTok, AlphaTok, 1), …}, {CPos(11), CPos(-1), Pos(AlphaTok, EndTok, 1), …})

Edge 8 → 9, “A”

ConstStr(“A”), SubStr(v1, {CPos(0), Pos(StartTok, AlphaTok, 1), …}, {CPos(1), …})

Choose a path, then one expression per edge: that is one program.

FlashFill · Gulwani, POPL 2011

10

FlashFill · Gulwani, POPL 2011 · Section 4.1

11

Version-space algebra: the operations

Lift the DSL from programs to sets of programs

A set of programs, and what it means

SubStr(vi, P, P') means
  every SubStr(vi, p, p'), p∈P, p'∈P'
Pos(R1, R2, C) means
  every Pos(r1, r2, c), r1∈R1, r2∈R2, c∈C
Dag(nodes, s, t, edges, W) means
  every Concatenate(f1, …, fn) along a
  path s→t, with each fi ∈ W(edge i)

Intersect, rule by rule

SubStr(vi,P1,P2) ∩ SubStr(vi,P1',P2')
= SubStr(vi, P1∩P1', P2∩P2')
Pos(R1,R2,C) ∩ Pos(R1',R2',C')
= Pos(R1∩R1', R2∩R2', C∩C')
ConstStr(s) ∩ ConstStr(s) = ConstStr(s)
Dag1 ∩ Dag2 = Dag on node pairs, labels ∩
anything else = ∅

Two more operations work on the sets directly: Size counts the programs without listing them (next slide), and Evaluate runs all of them on a new input, highlighting any cell where they disagree.

So a new example costs one intersection over these sets. FlashFill never enumerates programs, not even to check them.

This is the technical heart of the paper. A version space is the set of all hypotheses consistent with the examples seen so far, an idea from Mitchell's "Generalization as search" (1982). Lau, Domingos and Weld (ICML 2000) made it an algebra: build version spaces for complex functions by composing version spaces for their parts. In its own words, FlashFill shows "how the concepts of version-space algebra can be lifted to the PBE setting." Left card: the DSL is re-read so that every constructor takes sets of arguments, and a set-expression means every program you get by choosing one element from each set. Right card: intersection works structurally, constructor by constructor, and never lists programs. DAGs intersect like automata: nodes become pairs, and each edge label is the intersection of the two label sets. I've simplified the notation; the paper also has rules for Loop, CPos and TokenSeq (all pointwise), and Intersect returns ∅ when the constructors don't match. The paper compares the structure to BDDs, which represent huge sets of states succinctly and operate on them directly. (Source: Figures 3 and 4, and Section 5.1 for evaluation.)

Why the version space stays small

Options add up in memory but multiply in programs

One more option costs one more stored entry, but multiplies the number of programs. Here's the running example, with 3 options per list as on slide 8:

Level	What is stored	Stored entries	Programs represented
One piece: “Turing”	3 starts, 3 ends, 1 constant	3 + 3 + 1 = 7	3 × 3 + 1 = 10
One split: “Turing” + “, ” + “A” + “.”	one such set per piece (“, ” and “.” can only be constants)	7 + 1 + 7 + 1 = 16	10 × 1 × 10 × 1 = 100
Every split of “Turing, A.”	one set per DAG edge, shared by every path	55 edge sets	the sum over all 512 paths of each path's product

Counting, intersecting and running the set all work on the stored entries: multiply along a path, add across paths. No program is ever listed.

FlashFill · Gulwani, POPL 2011 · Sections 4.1–4.3

12

Walk the table top to bottom; each row builds on the one above. Row 1: the "Turing" piece. As on slide 8, there are 3 ways to say where it starts and 3 ways to say where it ends, plus the option of just typing the constant "Turing". FlashFill stores those 7 things. Any start can pair with any end, so they stand for 3 × 3 = 9 SubStr programs, plus the constant: 10. Row 2: one way of splitting the output, "Turing" + ", " + "A" + ".". Each piece gets its own set. The comma-space and the period don't appear in the input, so they can only be constants: 1 option each. "A" works like "Turing": 10 options. Storage adds up to 16 entries, but the programs multiply: 10 × 1 × 10 × 1 = 100, because you choose independently for each piece. Row 3: every split at once. That's the DAG from slides 9 and 10: 55 edges, each with its own set, and 512 paths through them. The paths share edges, so storage is just the 55 sets, while the number of programs is the sum over all paths of that path's product. The punchline: the Size function (Fig. 5 in the paper) computes this count directly from the stored sets, multiplying along paths and adding across them with dynamic programming, and intersection and evaluation also work on the stored sets. The 3-per-list numbers are illustrative; real sets are larger, which only makes the gap bigger. Section 4.2 adds one more saving: tokens that match exactly the same places in the input are merged into one, so the sets stay small to begin with (the paper's example lists several ways to extract "706" from "425-706-7709").

More examples

A second example intersects the DAGs

Example	Where the surname starts	Where it ends
Alan Turing	CPos(5), Pos(WhiteSpaceTok, AlphaTok, 1), Pos(WhiteSpaceTok, AlphaTok, -1), …	CPos(11), CPos(-1), Pos(AlphaTok, EndTok, 1), …
Grace Hopper	CPos(6), Pos(WhiteSpaceTok, AlphaTok, 1), Pos(WhiteSpaceTok, AlphaTok, -1), …	CPos(12), CPos(-1), Pos(AlphaTok, EndTok, 1), …
Both (∩)	Pos(WhiteSpaceTok, AlphaTok, 1), Pos(WhiteSpaceTok, AlphaTok, -1), …	CPos(-1), Pos(AlphaTok, EndTok, 1), …

Constants and fixed indices drop out. The “first space” and “last space” rules both survive: they only disagree on names like “Grace Brewster Hopper”. A third example, or the ranking, has to settle it.

FlashFill · Gulwani, POPL 2011

13

Beyond one trace

When the intersection is empty: Switch and Loop

Switch

GeneratePartition greedily merges examples whose DAGs still intersect. GenerateBoolClassifier then learns Match predicates that tell the groups apart.

“Hopper, Grace” → “Hopper, G.”
“Alan Turing” → “Turing, A.”
Switch((Match(v1, CommaTok), e1),
(¬Match(v1, CommaTok), e2))

Loop

Adjacent DAG pieces that are the same expression, differing only in an integer, get unified. That integer becomes the loop variable w.

“Alan Mathison Turing” → “AMT”
Loop(λw. Concatenate(
SubStr2(v1, UpperTok, w)))

FlashFill · Gulwani, POPL 2011

14

Ranking

Many programs survive; Occam's razor picks one

Simpler	Than	Why (from the paper)
SubStr	ConstStr, Concatenate	output constants rarely occur in the input; a long match is likely one extraction
Pos(r1, r2, c)	CPos(k)	constant offsets get less preference
Fewer arguments	More arguments	for Concatenate and TokenSeq
StartTok, EndTok	Other tokens	extraction from start or end is common
Larger character class	Smaller one	favor generality

User types one output

→

Top-ranked program fills the column

→

User fixes a wrong cell

→

The fix is a new example: intersect again

FlashFill · Gulwani, POPL 2011 · Section 5.3

15

Evaluation

What the experiments show

100+

problem instances, from online help forums and the Excel product team

<0.1 s

average synthesis time, with up to 10 examples of up to 100 characters

≤ 4

interactive rounds in any scenario (2–3 typical); at most 10 examples

No task expressible in the DSL where it failed to converge on the right program.

The failures were outside the DSL: semantic tasks like turning a date into a weekday.

FlashFill · Gulwani, POPL 2011 · Section 6.2

16

Champion · the case for a best paper award

Why this paper matters beyond its benchmark

It proved synthesis can ship

Within two years it was Flash Fill in Excel 2013: program synthesis behind a single keystroke, used by people who have never written code.

It is a recipe, not a trick

Sets of programs, intersection and ranking work for any DSL. FlashMeta/PROSE (2015) turned exactly this into a framework for building synthesizers.

What I'd build on it

Keep the version space for its guarantees, but learn the ranking and the noise handling from data. That is the gap RobustFill and later neurosymbolic work go after.

Conceded up front: the DSL and ranking are hand-engineered

It only generalizes as far as its designer anticipated, and every failure in Section 6.2 is outside the DSL. That doesn't sink it: the contribution is the algorithm (represent, intersect, rank), and PROSE showed that algorithm transfers to other DSLs.

FlashFill · Gulwani, POPL 2011

17

Critic · Reviewer 2, recommends reject

Claims the evidence does not yet support

Concern	An experiment that would test it
The DSL does the generalizing	Run on tasks just outside the DSL, such as date arithmetic. Does it fail loudly, or return a wrong program?
The ranking is hand-tuned	Swap in a uniform or learned ranker and count how many extra examples each task needs.
Noise handling is a heuristic	Section 5.2 only flags a lone example that breaks classification. Corrupt 1, 2, 3 examples and measure recovery. (RobustFill's opening.)
Benchmarks come from forums	Collect tasks from real spreadsheet usage and compare the distribution of task types.

The one experiment that would change my score: Run FlashFill on string tasks collected independently of the author, and report how often it silently returns a wrong program.

FlashFill · Gulwani, POPL 2011

18

Discussion

What would we have to believe?

1

FlashFill generalizes from one or two examples. Is that reasoning, or is the DSL's prior doing all the work?

2

RobustFill learns the search instead. What does a neural model gain over a version space, and what does it give up?

3

An LLM can handle most of these tasks today. Which part of FlashFill's contribution still matters?