Program Synthesis from Partial Traces

Margarida Ferreira, Victor Nicolet, Joey Dodds, Daniel Kroening · 2025

Read Program Synthesis from Partial Traces by Margarida Ferreira, Victor Nicolet, Joey Dodds, Daniel Kroening (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14480.txt.

Introduction

Margarida Ferreira, Victor Nicolet, Joey Dodds and Daniel Kroening present a method to synthesise programs from partial traces of their runs. The traces record only the calls that have side effects, yet the built program must mix those calls with pure functions and control flow. Uses include rebuilding an API script from call logs, with only positive examples given.

Their method generalises from the traces and uses cost measures to stop over-general fits, so no negative examples are needed. It joins optimising rewrites with syntax-guided synthesis, and the result is correct by construction: it can always replay the input traces. Tests on real-world benchmarks weighed how metric choice shapes program quality and speed.

Catalog record

CREATORMargarida Ferreira, Victor Nicolet, Joey Dodds, Daniel Kroening
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-14480

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Program Synthesis from Partial Traces Margarida Ferreira, Victor Nicolet, Joey Dodds, Daniel Kroening Abstract . We present the first technique to synthesize programs that compose side-effecting functions, pure functions, and control flow, from partial traces containing records of only the side-effecting functions. This technique can be applied to synthesize API composing scripts from logs of calls made to those APIs, or a script from traces of system calls made by a workload, for example. All of the provided traces are positive examples, meaning that they describe desired behavior. Our approach does not require negative examples. Instead, it generalizes over the examples and uses cost metrics to prevent over-generalization. Because the problem is too complex for traditional monolithic program synthesis techniques, we propose a new combination of optimizing rewrites and syntax-guided program synthesis. The resulting program is correct by construction, so its output will always be able to reproduce the input traces. We evaluate the quality of the programs synthesized when considering various optimization metrics and the synthesizer’s efficiency on real-world benchmarks. The results show that our approach can generate useful real-world programs. \acmBadgeR [https://www.acm.org/publications/policies/artifact-review-and-badging-current]images/artifacts_available_v1_1.png \acmBadgeR [https://www.acm.org/publications/policies/artifact-review-and-badging-current]images/artifacts_evaluated_functional_v1_1.png \acmBadgeR [https://www.acm.org/publications/policies/artifact-review-and-badging-current]images/artifacts_evaluated_reusable_v1_1.png DOI: 10.1145/3729316 Journal: PACMPL Volume: 9 PLDI 6 CCS: Theory of computation Automated reasoning CCS: Theory of computation Logic and verification † † cc-license: by-sa 1. Introduction Program synthesis is for lazy people. The promise of program synthesis is that a user writes a simple specification and gets a complex program. If specifications are complex to write or synthesis tools are hard to apply, users will prefer to write the program directly. The best specification is one they already have with no changes needed. Unfortunately (for synthesis tool writers), these specs often take the form of traces of external side effects. These traces may be sequences of messages exchanged between networked servers, logs of calls made to an Application Programming Interface (API), or traces of system calls made by a workload. Program synthesis from traces can be widely applied across different tasks; there are many instances of this approach in Programming-By-Demonstration (PBD) work ( Shin et al., 2018 ; Jeppu et al., 2020 ; Cypher et al., 1993 ; Gulwani et al., 2017 ) , but all of this work is either limited to pure functional examples, simple trace replay, or assumes no computation occurs between effects visible in traces. Real-world traces are an incomplete view of a task: function calls with no side effects may not be recorded. A program a = F (); b = h ( a ); return G ( b ) where only the calls to F and G are logged may produce traces F ()=0 :: G ( "id-0" )= true and F ()=42 :: G ( "id-42" )= false , with no occurrence of h . These hidden function calls not present in the traces are a significant challenge for trace-guided synthesis. In our example, the synthesizer infers from the data that there is a non-visible function that transforms 0 into "id-0" and 42 into "id-42" . These traces come from external recordings of program behavior. For example, the administrator of a cloud deployment might repeatedly follow a sequence of steps to create a data store and then attach an access policy to that data store. For convenience, they create a policy name by appending the string "policy" to an ID generated by the creation of the data store. The log of these actions kept on the cloud will contain the creation of the data store, the policy, and the connection between the two. It will not contain the hidden function where the administrator bases the role name on the store’s metadata. To help automate such repetitive tasks, we propose a new synthesis technique, Syren . Syren is the first approach to synthesize programs from partial traces. It can infer both control flow and non-trivial hidden pure function calls with no additional input from the user. We combine optimizing program rewrites of an initial trivial solution with calls to a syntax-guided synthesizer (SyGuS) with input-output examples as specifications. Synthesis from input-output examples, also known as Programming-By-Example (PBE), has a long history of research and enables the synthesis of nontrivial functions. In Syren , we rely on a PBE synthesizer to synthesize hidden functions without additional input from the user. These hidden functions, in turn, let us perform further computation so that the rewrites can expose more intricate relations between data. In example- and trace-based synthesis, we can assume the existence of a hidden target program , the program with the exact desired behavior. In the cloud administrator example above, the complete target program exists only in the administrator’s mind. We can describe the behavior of a program as the set of traces that result from its execution on any possible input. When the synthesis specification is a set of traces, there is a trivial solution to the synthesis problem—the program that exactly reproduces the input traces. This trivial solution, though correct by construction (in the sense that it satisfies the specification), is likely not the target program that the user desires. The user probably wants a program that generalizes the provided traces. For example, our cloud administrator does not want a program that can reproduce all of the data store names they have used in the past, they want a program that takes a data store name as a parameter, allowing them to provide important information like the name, while saving them many repetitive clicks on a web interface. The trivially correct program is a lower bound on the behavior of all possible correct programs because it produces the minimal set of traces to be considered correct. The target program, on the other hand, is an upper bound of the desired behaviors—it would provide us with all the possible traces that are considered correct, but behaviors not exhibited by the target are undesirable. Since we do not have access to the target program, we need another way to quantify as accurately as possible how close to the target behavior a program in the space is. In other words, we need a cost function to efficiently traverse the program space. Besides generalizing to traces beyond those observed (allowing more behavior), we considered readability when building Syren ’s cost functions. Like other synthesis works before us, we generally follow Occam’s razor principle and favor shorter programs to achieve both goals. We evaluate Syren using two different cost functions we built, but our approach is agnostic to the cost function; a user can write different cost functions for Syren if they choose to optimize for something else. For example, a user might specify that a specific input to a given method call must be generalized, that they want to minimize the syntactic statements in the program, or a combination of both. On the left, there is a set of input traces. These traces are used as input to the synthesizer. The synthesizer starts by writing an initial program using the traces. Then, the initial program is fed into a loop that optimizes for the user-defined metric. This loop uses a synthesis solver and a program rewriting engine, which entails the definition of program rewrites and a rewriting strategy.

Read the complete text