PaperlayerView exact revision on arXiv

Source-linked AI summary

SWIM: Synthesizing What I Mean

Mukund Raghothaman, Yi Wei, Youssef Hamadi

arXiv:1511.08497v2cs.SE

TL;DR

Programmers need help finding APIs and writing their usage code within large software libraries. SWIM maps natural-language queries to APIs and synthesizes snippets from open-source usage patterns, achieving relevant top-ranked results on its benchmark while retaining scope limitations.

  • Problem

    Programmers using large libraries must discover both which APIs solve a task and how to use them idiomatically.

  • Method

    SWIM uses Bing clickthrough data to map English queries to APIs, then synthesizes C# snippets from structured call sequences mined from open-source projects.

  • Results

    70% of 30 common C# API-related queries had a relevant first snippet, and every query had a relevant snippet in the top 10.

  • Takeaways & Limitations

    Structured call sequences provide an empirical representation of API usage that can support code-snippet synthesis and other applications such as code anomaly detection.

  • Takeaways & Limitations

    SWIM can produce incomplete snippets when a selected starting type does not reveal other objects needed to complete the task.

Abstract

from arXiv · show

Modern programming frameworks come with large libraries, with diverse applications such as for matching regular expressions, parsing XML files and sending email. Programmers often use search engines such as Google and Bing to learn about existing APIs. In this paper, we describe SWIM, a tool which suggests code snippets given API-related natural language queries such as "generate md5 hash code". We translate user queries into the APIs of interest using clickthrough data from the Bing search engine. Then, based on patterns learned from open-source code repositories, we synthesize idiomatic code describing the use of these APIs. We introduce \emph{structured call sequences} to capture API-usage patterns. Structured call sequences are a generalized form of method call sequences, with if-branches and while-loops to represent conditional and repeated API usage patterns, and are simple to extract and amenable to synthesis. We evaluated SWIM with 30 common C# API-related queries received by Bing. For 70% of the queries, the first suggested snippet was a relevant solution, and a relevant solution was present in the top 10 results for all benchmarked queries. The online portion of the workflow is also very responsive, at an average of 1.5 seconds per snippet.

1. INTRODUCTION

SWIM automates discovery of API-related C# code from natural-language queries by mapping queries to APIs and synthesizing snippets from learned usage patterns. Its evaluation found relevant results for common Bing queries, with responsive generation.

  • Motivation: SWIM accepts English API-related queries and outputs C# snippets intended to implement the described task.Examples include matching regular expressions and reading text files.
  • Approach: The natural language to API mapper suggests framework fields or methods from English queries using a model learned from Bing clickthrough data.The model estimates Pr(t | Q), connecting query words with APIs appearing in clicked programming pages.
  • Design rationale: SWIM deliberately leaves detailed API contracts and data-flow information to synthesis rather than requiring the natural-language mapper to learn them.This allows clickthrough pages that mention APIs without code snippets to remain useful and assumes key APIs make the rest of a task relatively predictable.
  • Approach: The synthesizer combines suggested APIs into valid, readable snippets by selecting object construction, API actions, control flow, and variable names.It relies on structured call sequences extracted from open-source projects and indexed for retrieval and ranking.
  • Evaluation: 70% of benchmark queries received a relevant first snippet, while every query had a relevant snippet among the top 10 generated solutions.The evaluation used 30 common API-related queries, with 88% of variable names judged appropriate and an average response time of about 1.5 seconds per snippet.
  • Contributions: The paper contributes query-to-API mapping, structured call-sequence extraction, snippet synthesis, and the SWIM prototype.Experiments reported relevant snippets for frequently asked API-related queries.

2.1 Motivation

The paper motivates structured call sequences with common API-usage patterns involving object creation, calls, field accesses, and control flow. These patterns capture idiomatic usage while remaining suitable for extraction and synthesis.

  • 2.1 Motivation: Regular-expression matching illustrates conditional API usage: Match.Groups is accessed only when Match.Success is true.The pattern combines Regex.Match(string) with an if condition around the Groups access.
  • 2.1 Motivation: Text-file reading illustrates sequential resource usage: StreamReader is created, read to the end, and closed afterward.Closing the reader releases associated system resources after I/O completes.
  • 2.1 Motivation: Structured call sequences represent object creation, method invocation, field access, and if or while control-flow blocks.They express more complex usage patterns than construction techniques or fixed method sequences alone.
  • 2.1 Motivation: When grouped by syntactic equality, frequently occurring structured call sequences are intended to describe idiomatic API usage.The paper emphasizes that these patterns remain easy to extract and readily synthesized into code snippets.

2.2 Formal definition

Structured call sequences model object creation, API actions, and conditional or repeated usage patterns in a restricted C# language.

  • Language subset: SWIM’s modeled C# subset excludes generic types, anonymous classes, first-class functions, downcasts, and exceptions.The paper attributes this restriction to the computational difficulty of synthesis with generics and first-class functions.
  • Actions: Actions represent method invocations or field reads and writes, while constructors are represented as static methods named new with the constructed type as return type.Static members can be invoked without an object, and action return or field types are recorded.
  • Structured call sequences: Structured call sequences begin with object creation and combine method calls, field accesses, unknown usage, sequences, conditionals, and loops.They describe permissible API usage patterns rather than arbitrary program behavior.
  • Control flow: Structured call sequences support if-branches and while-loops to represent conditional and repeated API usage.The formal grammar also includes unknown for object usage through methods with unknown bodies.
  • Scope boundary: The formalism omits some C# constructs, including for-loops and do while-loops, although SWIM handles them operationally.The stated language limitation also excludes generic types and first-class functions.

2.3 Extracting structured call sequences

SWIM extracts structured call sequences by traversing method-level syntax trees, translating object lifetimes and control flow into API actions, and simplifying the result before synthesis.

  • Extraction target: SWIM extracts one structured call sequence for each non-aliased local variable of a framework type by traversing its method-body AST.The extraction operates on individual methods and uses Roslyn to parse source files and resolve bindings.
  • Action extraction: Assignments resolving to framework members become creation actions, while method calls and field accesses become corresponding API actions.Field reads and writes are represented as get and set actions.
  • Control flow: Sequential statements are concatenated, and if-statements and while-loops are recursively converted into structured control-flow sequences.Each branch and loop component is extracted from the corresponding syntax-tree statements.
  • Unknown usage: When a tracked variable is passed to another method, SWIM inserts unknown to represent usage it cannot model directly.This preserves the fact of external use without inferring the called method’s internal behavior.
  • Simplification: SWIM simplifies extracted sequences with rewrite rules, such as removing an empty conditional branch and retaining the nonempty branch.The resulting sequence is more compact before later code generation.
  • Limitation: The extraction is conservative because it does not perform inter-procedural analysis or account for aliased variables.The authors defer more sophisticated extraction techniques to future work.

2.4 Synthesis from structured call sequences

SWIM synthesizes snippets by translating structured call sequences into C# while recursively constructing prerequisite objects, supplying arguments, generating conditions, and choosing descriptive variable names.

  • Core synthesis: The synthesis procedure converts creations, actions, sequences, conditionals, and loops in a structured call sequence into corresponding C# statements.Boolean expressions are synthesized for control-flow conditions before emitting if or while constructs.
  • Object creation: For instance-based creation, SWIM recursively synthesizes a prerequisite object containing the tracer method, then merges that code with the target object’s usage.This handles dependencies such as constructing Regex before invoking Regex.Match.
  • Object creation: Recursive object construction may not terminate, so SWIM can impose a predetermined depth and use default(U).method() as a fallback.The authors report not observing nontermination in practice.
  • Method arguments: SWIM supplies default values for method arguments, using null for reference types and zero for value types.More involved argument-generation schemes are omitted because they require substantially greater computational resources.
  • Boolean expressions: SWIM converts non-void methods and field accesses into equality tests against default values when synthesizing boolean conditions.This generally produces non-standard code but usually preserves useful field guidance for programmers.
  • Limitation: Meaningful boolean conditions require semantic knowledge that SWIM’s simple default-value procedure does not model.The paper illustrates this limitation with alternative conversions of IEnumerator.MoveNext() results.
  • Variable names: Descriptive variable names are chosen from corpus-derived name-frequency lists, subject to forbidden identifiers and reserved C# keywords.Examples include regex for Regex objects and match for Regex.Match results.

3. MAPPING USER QUERIES TO STRUCTURED CALL SEQUENCES

SWIM maps natural-language programming queries to likely C# APIs using clickthrough data, then retrieves structured call sequences whose API patterns guide code synthesis.

  • Query-to-API mapping: SWIM models the probability Pr(t | Q) that API t appears in a solution snippet for query Q.The model ranks APIs likely to solve the task described by the query.
  • Query-to-API mapping: Clickthrough pairs connect programming queries with API names extracted from code fragments on clicked pages.Fragments are identified in HTML tags such as <pre>, <code>, and <p>, then parsed with Roslyn.
  • Query-to-API mapping: Query expansion decomposes Pr(t | Q) into word-level API probabilities weighted by normalized query-term probabilities.Pr(t | qi) links an API to a query word, while Pr(qi | Q) provides normalization based on query-term frequency.
  • Query-to-API mapping: An EM-trained word-alignment model estimates connections between individual query words and API elements.EM initializes Pr(t | q) and iteratively updates probabilities to maximize the likelihood of the training data.
  • Retrieving structured call sequences: The synthesizer represents ranked API probabilities and structured call sequences as vectors, then uses cosine similarity to rank candidate sequences.Each structured call sequence vector marks its APIs, and the ranked sequences are passed to synthesis.

4. EVALUATION

SWIM was evaluated on 30 API-related C# queries using GitHub-derived usage patterns and Bing clickthrough data. It produced relevant snippets frequently, selected meaningful variable names in most cases, and averaged 1.5 seconds per snippet, while examples exposed incompleteness and API-selection errors.

  • 4.2 Evaluation setup: SWIM was evaluated on 30 frequently asked API-related queries covering simple and involved API usages.The evaluation used 25,000 GitHub projects, 15 days of Bing clickthrough data, and structured call sequences extracted for common .NET types.
  • 4.2.1 Snippet relevance: 70% of benchmark queries had a relevant first generated snippet, and every query had a relevant snippet in the top 10.The FRank metric measures the rank of the first relevant generated solution.
  • 4.2.1 Snippet relevance: 65% of the top 5 snippets and 54% of the top 10 snippets were relevant on average.These metrics assess the relevance of the presented ranked lists, which can contain multiple valid implementations for vague queries.
  • 4.2.2 Variable name choices: 88% of synthesized variable names were meaningful on average, with better names for specific tasks than for general tasks.Names were selected according to their appearance frequency in GitHub repositories; specific tasks have more concentrated name distributions.
  • 4.2.3 Responsiveness: The synthesizer required an average of 1.5 seconds to produce each solution snippet.Measurements used a 3.6GHz desktop workstation with 16 GB of RAM, and the prototype was not optimized.
  • 4.3 Examples of synthesized snippets: Starting synthesis from ProcessStartInfo can yield an incomplete “launch process” snippet that omits starting and terminating the process.The synthesizer stops when generated statements for ProcessStartInfo do not depend on other objects, without knowing that the user query remains incompletely implemented.

5. RELATED WORK

Related work addresses code assistance, free-form query retrieval, type inhabitation, and typestate-aware completion. SWIM differs by mapping free-form queries with search clickthrough data and synthesizing multi-statement snippets offline from structured call sequences.

  • Snippet synthesis as type inhabitation: Type-inhabitation tools such as Prospector and CodeHint synthesize expressions around target types, but richer type systems can make inhabitation intractable.These techniques also require developers to know relevant API type names in advance.
  • Typestate-aware code completion: Existing programmer-assistance work includes n-gram and method-call-sequence models, but these face parameter sensitivity and limitations expressing certain API idioms.Some usage patterns depend on loops, return values, or structures that finite-state-machine approaches cannot express naturally.
  • Typestate-aware code completion: SWIM avoids merging call sequences from different files, instead grouping syntactically equal sequences and suggesting multiple snippets.This design addresses the difficulty of combining distinct method call sequences into one suggested sequence.
  • Related representations: Structured call sequences model the lifetime of a single object, unlike groums, which represent data flows among multiple objects.Because SWIM synthesizes snippets from scratch rather than filling holes, it uses the simpler structured-call-sequence model.
  • Answering free-form queries: Natural-language querying reduces the need for prior knowledge of framework type names such as ProcessStartInfo or XmlTextReader.This is a central distinction between SWIM’s problem setting and much existing snippet-synthesis work.
  • Answering free-form queries: SNIFF retrieves source files annotated with API-documentation text, whereas SWIM uses search-engine clickthrough data to map queries to APIs.SWIM extracts structured call sequences offline, enabling an average response time of 1.5 seconds per synthesized snippet in its unoptimized implementation.
  • Answering free-form queries: anyCode synthesizes single-API expressions from free-form queries, while SWIM can synthesize multi-statement snippets with control flow.anyCode uses string matching, WordNet, and parse-tree information to construct expressions.
  • Answering free-form queries: SmartSynth can generate larger snippets, but it requires longer descriptions and focuses on a predefined API set.Both systems learn mappings from natural-language descriptions to APIs, but their query and API-scope assumptions differ.

6. CONCLUSION

SWIM synthesizes API-related C# snippets by mapping natural-language queries to APIs with Bing clickthrough data and mining structured call sequences from open-source projects. The authors identify structured call sequences as a reusable artifact, while noting future work needed to broaden API disambiguation and usage-pattern coverage.

  • 6. CONCLUSION: SWIM maps natural-language queries to APIs using Bing clickthrough data and synthesizes snippets from structured call sequences mined from open-source C# projects.The workflow combines query-to-API mapping with learned API-usage patterns.
  • 6. CONCLUSION: Structured call sequences are presented as a fundamental empirical artifact of API design with potential applications including code anomaly detection.The paper frames these sequences as useful beyond snippet synthesis.
  • 6. CONCLUSION: Future work includes better NLP for distinguishing similar APIs, improved extraction and exception handling, and joint probability models for incomplete snippets.These directions target API ambiguity, broader idiom expressiveness, and incomplete generated code.
Loading 1511.08497v2…