Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

semantic equivalence

Semantic equivalence is a relationship between two or more programs, code snippets, or formal expressions indicating that they exhibit identical execution behavior and produce the same outputs for every valid input, regardless of differences in their syntax or internal implementation. In computer science and software engineering, two pieces of code are semantically equivalent if their observable state changes, return values, and side effects are completely indistinguishable under all valid operating conditions. Because formally proving exact semantic equivalence across arbitrary programs is computationally undecidable due to fundamental limits of computation such as the halting problem, practical systems often assess or approximate it using formal verification, static analysis, or execution over representative test suites. The concept is fundamental to compiler optimization, program refactoring, automated code generation, and software verification, where transformations must preserve the functional meaning and runtime semantics of the original program while changing its structure.

1 item

Natural Language to Code Translation with Execution

Natural Language to Code Translation with Execution

Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, Sida I. Wang

OrganizationsCarnegie Mellon UniversityMetaToyota Technological Institute at ChicagoUniversity of Washington

Why you should read this

Proposes an execution-based minimum Bayes risk decoding framework that boosts code generation accuracy by executing sampled candidate programs on test inputs to select the solution with the highest semantic consensus.

Generative models of code, pretrained on large corpora of programs, have shown great success in translating natural language to code (Chen et al., 2021; Austin et al., 2021; Li et al., 2022, inter alia). While these models do not explicitly incorporate program semantics (i.e., execution results) during training, they are able to generate correct solutions for many problems. However, choosing a single correct program from a generated set for each problem remains challenging. In this work, we introduce execution result–based minimum Bayes risk decoding (MBR-EXEC) for program selection and show that it improves the few-shot performance of pretrained code models on natural-language-to-code tasks. We select output programs from a generated candidate set by marginalizing over program implementations that share the same semantics. Because exact equivalence is intractable, we execute each program on a small number of test inputs to approximate semantic equivalence. Across datasets, execution or simulated execution significantly outperforms the methods that do not involve program semantics. We find that MBR-EXEC consistently improves over all execution-unaware selection methods, suggesting it as an effective approach for natural language to code translation.

Added

2026-09-26