A Language for Function Signature Representations

Kyle RichardsonarXiv 2018 · arXiv

Introduction

The field of Natural Language Processing (NLP) has seen a surge in "text-to-code" models designed to translate natural language docstrings into functional code. However, a significant bottleneck remains: the "code" side of these pairs often consists of ad-hoc strings representing function signatures (e.g., math.max(a, b)). These representations lack formal semantic definitions, making it difficult to perform high-level reasoning, such as determining structural equivalence across languages or querying databases for specific functional patterns. This paper introduces a unified domain-specific language (DSL) and a systematic mapping to first-order logic (FOL) to provide a rigorous framework for function signatures.

Formalization Framework

The proposed formalization involves a two-step process to move from informal signatures to mathematical constraints. First, a unified syntax is defined to capture essential components—language identifiers, namespaces, classes, function names, and typed parameters—standardizing representations across disparate languages like Java and Python.

Second, these normalized signatures are translated into First-Order Logic. By employing a set of domain-specific predicates (e.g., type(v, r), param(x, f, i), in_namespace(f, n)), signatures are expanded into logical formulas. This transformation allows signatures to be treated as mathematical constraints rather than mere text labels.

Normalization and logical expansion of a Java function signature.

Applications and Key Insights

By treating signatures as logical constraints, the framework enables "intensional reasoning"—the ability to reason about abstract relationships between concepts, such as class hierarchies, across different programming ecosystems.

One of the most powerful applications is polyglot translation. Because the underlying logic is unified, a single natural language description can be mapped to equivalent signatures in multiple languages simultaneously. This identifies functional equivalences that are often obscured by syntax, such as recognizing that Clojure's bit-shift-left performs the same operation as Java's shiftLeft.

Cross-language translation of a natural language query into Haskell, Java, and Clojure.

Furthermore, this formalization facilitates structural querying. Developers can use logical queries to search for functions matching specific structural patterns across vast library ecosystems, regardless of the original programming language.

Conclusion and Future Work

This theoretical framework provides a "Rosetta Stone" for software signatures, moving beyond simple string matching toward semantic understanding. While the current predicate set is a robust starting point, future work will focus on extending the domain model to include complex concepts like inheritance and exception handling. Integrating these logical representations into machine learning models and developer tools promises to significantly improve the efficiency of code retrieval and automated program synthesis.

Summary updated

BibTeX
@misc{richardson2018language,
  author = {Kyle Richardson},
  title = {{A Language for Function Signature Representations}},
  year = {2018},
  eprint = {1804.00987},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.00987},
}
Figure