with string and number transformations commonly used in spreadsheets. Such transformations sit at a nice point on the complexity spectrum as a benchmark task; they are simpler than programs in general purpose languages, but still expressive enough for many common string transformation tasks.

The domain-specific language we use (shown in Figure \[fig:sheets\_dsl\]) is broadly similar to those of [@parisotto2017neuro] and [@ROBUSTFILL], but compared to these, our DSL is expanded in several ways that make the synthesis task more difficult: First, our DSL includes integers and integer arithmetic. Second, our DSL allows for arbitrarily nested expressions, rather than having a maximum size. Finally, and most importantly, our DSL removes the restriction of having [`Concat`]{} at the top-level, as is the case in previous works [@FLASHFILL; @ROBUSTFILL]. Without this constraint, version-space-based and dynamic-programming-based beam search approaches cannot exploit the prefix-output property to prune partial programs during search.

Our DSL allows for nesting and compositions of common string transformation functions. These functions include string concatenation ([`Concat`]{}) and other familiar string operations (see Supplementary Material for a full list). Integer functions include arithmetic, returning the index of the first occurrence of a substring within a string ([`Find`]{}), and string length. Finally, a few commonly 