Systems, methods, and computer-executable instructions for synthesizing programs using a prefix of an output. A specification of a task to synthesize a program in a domain specific language (DSL) is received. The specification includes an input and a corresponding prefix of the output. Programs for the task are synthesized. The synthesizing includes generating sub-goals based on the specification. Each of the synthesized programs include a solved subset of sub-goals and each sub-goal includes a symbol in the DSL. The symbol is transformed based on the DSL. The sub-goals are solved based on the transforming of the symbol using the input and the corresponding prefix of the output to generate the synthesized programs. The prefix of the output matches a prefix of an output from each of the plurality of synthesized programs.