A Theory of Equivalence-Preserving Program Embeddings
Authors: Logan Weber
Jesse Michel
Alex Renda
Saman Amarasinghe
Michael Carbin
Venue: Submitted to ICLR 2023 (2023)
Keywords: Programming Languages
Program Embeddings
Code
Big Code

Abstract: Program embeddings are used to solve tasks such as \textit{code clone detection} and \textit{semantic labeling}. Solutions to these \textit{semantic tasks} should be invariant to semantics-preserving program transformations. When a program embedding function satisfies this invariance, we call it an \textit{equivalence-preserving program embedding function}. We say a programming language can be \textit{tractably embedded} when we can construct an equivalence-preserving program embedding function that executes in polynomial time in program/input length and produces program embeddings that are proportional to the input length. Determining whether a programming language can be tractably embedded is the \textit{equivalence-preserving program embedding problem}. We formalize this problem and theoretically characterize when programming languages can be tractably embedded. To validate our theoretical results, we use the BERT-Tiny model to learn an equivalence-preserving program embedding function for a programming language that can be tractably embedded and show the model fails to construct an equivalence-preserving program embedding function for a similar language that is intractable to embed.


Under review as a conference paper at ICLR 2023
A THEORY OF EQUIVALENCC-PRESSRVVIS PROGRAM EMBEDDINGS
A Anonymous authors Paper under double-blind review
ABSTRACT
Program embeddings are used to solve lasks such as code clone delection and semanlic labeling. Solutions these semardic lasks should be invariant semantics-preservinn program transformations. When program embedding function satisfies this invariance, we call an equiuulence-preseevinng program embedding function. We say a programming langnage can be tractably em- bedded when we can construct an equivalence-preserving program embedding function that executes in polynomial time in program /input length and produces program embeddings that are proportional to the input length. Determining whether programming language can be tractably embedded is the problem and theoretically characterize when programming languages can be tractably embedded. To validate our theoretical resulls, we use the BERT- program embedding function
program embedding problem. We formalize this
Tiny model to learn qquivalence-preserviii for a programming language that can be tractably embedded and show the model fails to construct an equivalence-preservee function for a similar language that is intractable to embed.
program embedding
INTRODUCTION
Emerging rescarch demonstrates that powerful new techniques solve challenging program reasoning tasks, such as code clone detection and semantic labeling (Hu et al., 2017; Mou et al., 2016). At the core of many techniques lie program embeddings, fixed-size representations produced from program text that model a program property. For example, a program embedding may be vector of floating-point numbers that models a program's input-output behavior. A common and effective method for producing program embeddings is to use neural network (Yu et al., 2019; Ben-Nun et al., 2018). While the empirical results of these techniques have been demonstrated, there has been, to date, little theoretical understanding of the capabilities of program embedding techniques.
Semantic Tasks. A key first step towards understanding program embeddings is under- standing the tasks they are designed to solve. In this work, we focus on semantic tasks, tasks that depend only the input-output behavior of a program. Equivalently, the solution to semantic task is invariant to all semantics-preserving transformations on the input program.
A Theory of Equivalence- PreeencceePreeviing Program Embeddings. When a program embedding technique is invariant to cennannicc-preervinn transformations, two programs' embeddings are identical exactly when the programs are semantically equivalent. We call such a technique an gguiealence-preserving program embedding function. We say programming language can fractably embedded when we can construct an squivalence-presevvinn program embedding function that runs in time polynomial in program /input length and the embedding size is proportional to input length. The problem of determining whether a programming language can be tractably embedded is the equivalence- pereeeerccepprrrriiggg program embedding problem. To date, this problem has not been identified in the litcrature, and has been unknown under what conditions it can be solved. We provide the first theoretical characterization of this problem by proving necessary and sufficient conditions for when a programming language be tractably embedded.

---

Under review as a conference paper at ICLR 2023
Empirical Study. We apply theory to programming languages for modular addition and bitvector arithmetic (Bosselaers et al., 1994; Barrett et al., 1998). We prove the modular addition language can be tractably embedded, while the bitvector arithmetic language cannot. We find that a BERT-Timg -Tiy model can learn an suuivalence-preserviin embedding function for the modular addition language, but not the bitwise arithmetic language (Bhargava et al., 2021; Ture et al., 2019). We also validate that as the number of possible inputs increases for these languages, the model maintains 100% train and test accuracy for the modular addition language, but accuracy degrades quickly for the bitvector arithmetic language.
Our contributions are follows:
1. We define the prreseerin program embedding problem and identify applications of setivaleenc--reserviin program embeddings.
2. We prove necessary and sufficient conditions for when a programming language can be tractably embedded.
3. We hypothesize that programming languages that can be tractably embedded are easier learn than those that are intractable to embed and provide evidence with an empirical study of languages for modular addition and bitvector arithmetic.
We present definitions and results constituting the first steps in a theory of equivalence- preserving program embeddings. Building on these foundations, future work can better analyze existing programming languages, design new programming languages that can be tractably embedded, and develop principled approximations for programming languages that cannot be tractably embedded.
2 EQUIVALENCE-PRESEEVII PROGRAM EMBEDDINGS IN PRACTICE
Semantic lasks are those where only a program's 's input-oul put behavior must be modeled. We show how equivalence-presers program embeddings can solve these tasks and briefly explain how researchers solve them.
Code Clone Detection. Code clone detection is the task of identifying whether a pair of programs equivalent and is often used to find duplicate code in codebase or identify software vulnerabilities in programs (Hu et al., 2017). Given an program embedding function, one can solve this problem by embedding both programs and checking equivalence. Researchers produce program embeddings that solve this problem via neural networks (Yu al., 2019), execution of programs a fixed set of inputs (Hu et al., 2017), and locality-sensitive hashing of such executions (Pewny et al., 2015).
Semantic Labeling. In semantic labeling, the goal is label program having particular semantic property among a fixed-size collection of possible properties. Examples include determining the algorithm a program implements and identifying whether a program exhibits particular error. An equivalence- each program to its label, which identifies the program's functionality. Note that the labels come from a fixed set representing all program functionalities of interest. Rescarchers solve this problem using neural program embeddings (Mou et al., 2016; Ben-Nun al., 2018; Puri et al., 2021; Wang et al., 2018).
program embedding function maps
3 A THEORY OF EQUIVALENCE- PROGRAM EMBEDDINGS
In this section, formalize the equivalencee-reeerving program embedding problem and prove conditions under which it can be solved.
We define programming language P set of strings with additional structure. For one, deciding membership of programs a programming language is often decidable (e.g., by parsing and type checking), meaning one can enumerate all programs from shortest to
2

---

Under review as a conference paper at ICLR 2023
longest Furthermore, every programming language can be ascribed denotation function [:] that maps each program p to its meaning [p] - O as a mathematical function from imputs to outputs (Scott, 1977). We provide full definition in Appendix A.
We model embeddings as elements a finite set, from which a fixed-size bit-vector represen- tation can be recovered. A program embedding function is function e : P & that maps a program in P to an element of a finite set Σ. A program embedding is an clement e(p) produced by applying a program embedding function to a program p E P.
To define gqquivalence-preeeviing program embeddings, we need a nolion of program equiva- lence. Because programs denote mathematical functions, we define program equivalence in terms of functional equivalence. Programs p. q E P are functionally equivalent ([p] = [q]]
when for every imput æ E I, [p](2) [I]( where an equivalence relation defined over O
Definition 3.1. A program embedding function -> is equivalence-prresrnie if for every P. E P,
e(p) e(g)
[4]]-
(1)
In other words, program embeddings should be equivalent preciscly when the programs denote equivalent functions.
We say a programming language can be tractably embedded when there exists polynomial- time, equivalence-preserre
embedding function (in terms of program length [p] and input
bits log [Z] and the embedding size scales with log [Z]. The latter condition prevents encoding the entire input-output behavior of the program (see Corollary A.6).
Definition 3.2. A programming language P can be tractably embedded when:
1. One can construct an equivalence-preserving embedding function e such that, for all E P, the time complexity of e is polynomial in the length of the input pro- gram lp| and the minimum description length of the input space log [Z] (i.c., it runs in Oppoly(pp), log [Z])) time).
2. The length of the embedding's bit-level reprosentation |e(p)] is Ollog [Z] for all p P.
We are now ready to define the equivalence-preseving program embedding problem. Definition 3.3. The equivalence-preseee preserving program embedding problem is, given program- ming language, determine whether it can be tractably embedded.
While this problem sits at the core of many techniques to solve semantic tasks, it cannot always be solved. We can tractably embed a programming language when there are polynomially many semantic equivalence classes and an efficient canonicalization procedure. A semantic equivalence class for program p E P is the set {q [4] = [e]]] We define a canonicalizer e as function from programs to programs such that programs p, q E P canonicalize to the same program exactly when they are semantically equivalent. That is,
[4] + c(p) = c(q).
Theorem 3.1. A programming language P can be tractably embedded exactly when there are (ppoy((Z))) semantic equivalence classes and there is canonicalizer that runs in Oppoly(pp), logly((l),oo((]]))) time for every program p P.
Proof. =) By condition (2) of Definition 3.2, there are Olog [Z] bits in the embedding and therefore (ppoly([Z)) distinct semantic equivalence classes. An equivalence-ppeeervie embedding function gives decidable semantic equality, so we use Lemma A.3 to collect the shortest representative program for every semantic equivalence class. We then build a mapping from each program embedding to its corresponding canonical form, taking O(poly [Z]) space and having ((1) time lookup via perfect hashing. To canonicalize program p, embed
TTo enumerate programs, enumerate all strings the set of symbols for the language, then use the membership decision procedure to determine which strings to output.
2 Note that assuming decidable membership means our results exclude some complex languages such dependently typed ones, which only admit semidecidable membership.
3

---

Under review as a conference paper at ICLR 2023
it (in O(poly([p). log [Z]) time), then map it to the appropriate canonical form in constant time, and output the canonical form in O(pl)) time.
=) We build equivalence-pre preseerving program embedding function by rumning the canoni- calizer and then mapping from canonical forms to embeddings. By Lemma A.3, we collect the shortest representative programs from each semantic equivalence class into list. We then create a mapping from cach canonical form to a bitstring encoding of its index, giving O(1) lookup time, similarly to above. The program embedding function satisfies property (1) of Definition 3.2 because the canonicalizer runs in Oppoly(p)) log [Z)) time and mapping canonical form to its embedding takes constant time. satisfies property (2) since there are O(poly((Zi)) equivalence classes, meaning there are Ollog [I] bits in the embedding. I
program embedding problem is undecid- able in general, results preciscly describe the properties of programming languages for which the problem not only decidable, but also tractable. In Appendix A, we provide extended theory that describes the properties of programming languages for which the embedding merely exists or computable, which are both weaker guarantees than tractability.
Implications. While the equivalence-preseet
EMPIRICAL STUDY
Our theory demonstrates the conditions under which a programming language tractably embeddable. However, not all programming languages are tractably embeddable and yet many approaches apply a variety of techniques, including neural networks, to produce embeddings for programs from languages for which the equivalence-preservii problem is intractable. Thus, there a fundamental question: what is the observable difference between applying program embedding technique a tractably embeddable programming language versus one that is not?
embedding
In this section, construct and study the behavior of neural program embedding function applied to programs from two programming languages: one that can be tractably embedded, while the other cannot. Our results show that the test accuracy of our neural embedding function on the equivalence-preerry the input space size grows for the intractable language whereas performance remains at 100% for the tractable language.
program embedding problem degrades quickly as
4.1 A TRACTABLE PROGRAMMING LANGUAGE OF MODULAR ADDITION
We first consider a programming language with modular addition in a single variable. This is subset of modular arithmetic languages that arise in algorithms for computer algebra, cryptography, and error-correcting codes (Bosselaers et al., 1994; Giorgi et al., 2009; Hoeven et al., 2016). The grammar is:
= 0 x
The denotation function for terms in this language parameterized by the modulus n Z+:
[0] n [1] n = 1 [x|
Le + e|n ([e] + [e]x] mod n
where x an integer variable satisfying 0 S x < n.
Theorem 4.1. The modular addition language can be tractably embedded.
Proof. In Appendix B.1.
4.2 AN INTRACTABLE PROGRAMMING LANGUAGE OF BITVECTOR ARITHMETIC
We extend the tractable language from Section 4.1 to support a subset bitvector arithmetic, resulting in programming language that is intractable to embed. Bitvector arithmetic
4

---

Under review as a conference paper at ICLR 2023
languages used for the verification and synthesis of low-level code (Barrett al., 1998; Jha et al., 2010; Inala et al., 2016). The grammar for the subset we consider is:
= 0 x ele e & e ele el
with additional denotations for logical conjunction A, disjunction V, and negation -:
c]n ([e] n [c].)) mod n [e eln [[e]n v [c],) mod
[-]p- (-[elm) mod
where is integer variable satisfying 0 S < Theorem 4.2. I NP, the bitvector arithmetic language cannot be tractably embedded.
Proof. In Appendix 1.2.
4.3 METHODOLOGY
We use the BERT-Tiny architecture to learn a program embedding function by phrasing the embedding problem as supervised classification problem: given the syntax of program E P, predict its semantic equivalence class (Bhargava et al., 2021; Ture et al., 2019). When the network achieves 100% train and test accuracy, we say it has learned an equivalence- preserving program embedding function. See Appendix C.1 for details.
Because BERT- is feedforward model, it can perform fixed amount of computation. As we vary the input space size, both languages will reach point where the required amount of computation for an equivalence--reservinng program embedding function will exceed that available to the architecture. Thus, beyond some point, the network must approximate and we hypothesize that accuracy for the intractable language will diminish more quickly than for the tractable language.
4.3.1 VARYING INPUT SPACE SIZE
To vary the input space size, we first note that the tractable and intractable programming languages have denotations parametrie in the modulus n. Increasing n increases the number of values the variable x ranges over, meaning it increases the input space size [Z]. Consequently, increasing n increases the number of semantically distinct program denotations. For example, in the tractable language [x]] [1 + x]2, but [x]a * [ + 1 + x]a, and a result, there are more semantic equivalence classes modulo
4.3.2 UNIPYING SYNTAX
We first considered constructing the dataset by generating programs from the grammar of each programming language. However, using different grammars for the two languages introduces methodological concern: there are fewer operators in the tractable language than in the intractable language, so low accuracy could be explained by the need to learn embeddings for more operators.
To address this concern, we use the same program syntax for both the tractable and intractable language but interpret the two differently. For the tractable language, all unary operators in the intractable language are treated as no-ops and all binary operators are treated as addition. For example, x y is interpreted as a bitwise OR for the intractable language and as x + in the tractable language.
4.3.3 DATASET GENERATION
To generate a dataset, we sample 500,000 abstract syntax trees (ASTs) with fixed number of nodes, then select subset with balanced number of examples for each semantic equivalence class. For example, the expression (("0 + x) x) has 6 nodes. our empirical study, we ASTs with 11 nodes (see Appendix C.2 for justification).

---

Under review as a conference paper at ICLR 2023
100%
Packat
Train Accmnyy
Train Loss
10-2
50%
10-6.
100
200
300
100
200
300
Epoch
Epoch
100%
Test. Accuracy
Test Loss
50%
10-3
0%
0
100
200
300
0
100
200
300
Epach
Epach
Imput Spece Size
Figure Average loss and accuracy graphs for the tractable language. Shaded ar- show the minimum and maximum values across trials. Almost every configuration achieves 100% test accuracy in < 133 epochs, demonstrating that BERT-Tim can learn an suuivalence-preservvii program embedding function for the tractable language the input space sizes we evaluated on.
In the generated dataset, the label for a program is label corresponding a semantic equivalence class. We identify the semantic equivalence class by enumerating all inputs Zm, where is the modulus, and recording the outputs. See Appendix C.3 for details.
4.4 EXPERIMENTS
We sweep over imput space sizes in the set 2,, for both the tractable and intractable languages and train BERT-Tiny to learn an equivalence-preserving program embedding function. We chose this set of input space sizes because it forms sequence where the number of semantic equivalence classes monotonically increasing for both languages. See Appendix C.4 for details.
4.5 RESULTS
Figures 1 and present the losses and accuracies from training BERT-Tiny to learn an equivalence-preserving program embedding function for the tractable and intractable lan- guages, respectively. Figure 3 distills these results into plots showing average accuracy vs. input space size for both languages.
Tractable. Figure 1 shows BERT- learns ceevvalence-prseeevvin embedding func- tion for the tractable language at every input space size we evaluated on. That is, BERT-Tiny achieves 100% train and test accuracy every configuration, and morcover, the two track strongly throughout training.
Interestingly, [Σ] increases, the network learns equivalence-preserving embedding function in fewer epochs. For example, when [Z] = 2, the network requires ze 100 epochs to reach 100% test accuracy, but when [ = 11, it requires epochs.

---

Under review as a conference paper at ICLR 2023
100%
Train Accureey
100
75%
Trai Loss
50%
25%
090
200
400
600
200
400
600
Epoch
Epoch
10
60%6
Tost Accuracy
40%
2016
100
0%
0
200
400
600
200
400
600
Epoch
Epoch
6 108
Validation Accuacy
Validotion Loss
x 109
40%
x 109
10"
20%
100
0%
200
400
600
200
600
Epoch
Epoch
Input Spece Size
Figure 2: Average loss and accuracy graphs for the intractable language. Shaded areas show the minimum and maximum values across trials. After 600 epochs, no configuration achieves 100% train and test accuracy, demonstrating that BERT-Tiny unable to learn an equivalence--reservingg program embedding function for the intractable language the input space sizes we evaluated on.
Intractable. Figure shows BERT-Tiny was unable to learn an equivalence-presere program embedding function for the intractable language any input space size we evaluated on While some configurations with input space size [Z] < 4 achieve near-100% train accuracy, no configuration achieves greater than 55% test accuracy, and average test accuracy decreases monotonically in the input space size. For [ > 4, average train accuracy trends downward, reaching 65% at = 11.
For [Z] E {2, 4), we observe that the loss and accuracy begin to rapidly oscillate between nearly 100% and as low as 73%, while validation and test. remain relatively stable.
Analysis. Figure 3 shows the tractable language achieves 100% train and test accuracy all input space sizes we evaluated on, while test accuracy is never 100% for the intractable language and it trends downward as the input space size increases. Thus, expected, test accuracy deteriorates more quickly for the intractable language as we increase the input space size, compared to the tractable language.

---

Under review as a conference paper at ICLR 2023
100%
100%
Train Accurey
Test Accuracy
75%
80%
50%
60%
25%
10
2
Input Space Size
Input: Space Size
Language
Tractable
Intractable
Figure Average train and test accuracy vs. input space size for the tractable and intractable languages. We collect the accuracy for each trial at the epoch with the highest validation accuracy. These results show BERT-Tiny able learn an equivalence-preservie program embedding function for the tractable language at every imput space size evaluated on, while it was unable to learn an equivalence- preeeerviigeeeeinnggg program embedding function for the intractable language at any input space size evaluated on.
DISCUSSION
In this section, we identify opportunities for future work including relaxations of the setivalence-preerviing program embedding problem, program embeddings for modeling performance, and distance-preserving program embeddings.
5.1 APPROXIMATE EQUIVALENCE- CRIVALLENE--PRSEEVIING PROGRAM EMBEDDINGS
Our results show that even commonly used subsets of basic-block assembly code (Section 4.2) cannot be tractably embedded. We discuss approaches that approximate equivalence- preserving program embeddings by either approximating programming language semantics approximating equivalence preservation.
Subsetting the Language. A programming language that is intractable to embed may contain subset that can be tractably embedded, which case, we can restrict our consideration to this subset. For example, the modular addition programming language in Section 4.1 is a subset of the bitvector arithmetic programming language in Section 4.2; the former can be tractably embedded, while the latter cannot.
Approximating Semantics. When programming language cannot be tractably em- bedded, we may approximate its semantics. For example, the language of Turing machine descriptions that denote 1 if the Turing machine halts on all inputs and 0 otherwise is not computable and therefore not tractable to embed. we change the denotation function to be 1 if every input halts after fixed number of iterations and 0 otherwise, then there is putable, equivalence-preservie Similarly, programming language with unbounded loops is not tractably embeddable, we may approximate its semantics by modeling only a fixed number of iterations.
program embedding function for this programming language.
Almost Equivalence Preserving Program Embeddings. If we have a metric on relax equivalence preservation by enforcing that when two
denotations of programs, programs have equivalent embeddings, they are semantically similar (i.e., e(p) = e(g) + d([p]) <), and furthermore, is the embedding function with the smallest. image

---

Under review as a conference paper at ICLR 2023
among all other feasible embedding functions. 3 For example, programming language with rational constants in the unit interval [0, 1] has no equivalence-ppresrrinng program embedding function because there are infinitely many semantic equivalence classes. However, can build an almost. equivalence-preserve given program to index corresponding to the nearest of k uniformly spaced rationals between O and (inclusive). To use the original denotation, we can modify the specification to encode preferences for some programs (e.g., smaller constants) by defining a distribution over programs, then improving the approximation for more important programs.
with absolute error bounded by 1/2k-1. It maps
Probably Approximately Equivallnnce-rrssovve Program Embeddings. A prob- ably approzimately seciiaaenne--reeeevvin program embedding function maps similar programs to the same embedding with some probabilily. Locality- hashing can be used to satisfy this specification, because it guarantees that, for some c > 1, R > O, and proba- bilities P1. if d([p]. s R. then Pr(e(p) e(q)] 2 P1, and if d([p). Iq]) cR, then Pr(e(p) = =(g)) S P2. For example, Pewny et al. (2015) solve cross-architecture bug search (a form of code clone detection) using an embedding comprised of many input-output pairs that are compressed using locality-sensitive hashing, for faster comparisons.
5.2 DISTANCE-PRESERVING PROGRAM EMBEDDINGS
An even stronger condition than equivalence preservation is distance preservation (i.e., isometry). This corresponds to the desideratun that the embeddings of similar programs are close (Wang el al., 2020; Peng el al., 2021; Alon et al., 2019). Expressing this condition requires metric on denotations of programs and program embeddings. A distance- prreearci-rrsrrving program embedding function could be useful for variants of semantic code search, where the task is not only to find semantically identical programs, but also semantically similar programs.
5.3 MODELING NON-STANDARD SEMANTICS
One can model intensional behavior of a program (on its own or in addition to semantic behavior), such as its size, its control flow structure, or its execution cost. For example, embeddings that capture the performance of a program could be formalized by supplying a denotation function that, instead of modeling functional equivalence, counts the number of steps the program executes, averaged over all inputs. Such an embedding would distinguish between, for example, quicksort and bubblesort. One can interpret Mendis al. (2019) as building a program embedding function that models performance of basic block assembly code to predict throughput, a metric of performance.
CONCLUSIONS
In this paper, we develop the first steps towards theory of program embeddings by narrowing our focus to programming embeddings that are used in semantic tasks, tasks that depend only on the input-output behavior of the program. For such tasks, an ideal embedding technique is weeraalence-ppeeevvii two programs" embeddings are identical exactly when the programs are semantically equivalent.
Our results define the peepraaencce-eeervvin program embedding problem and provide both necessary and sufficient conditions for when a programming language can be tractably embedded. Our empirical study shows that neural networks are able to more accurately embed a tractable language than an intractable language.
Taken together, our work holds out the promisc of future, complete understanding of the fundamental tension between programming language expressivity and embeddability, along with new directions for the co-design of languages and embedding techniques.
3 This last condition is to prevent degenerate solutions where every program is mapped to a distinct embedding.
Floating-point numbers be seen as approximations of rationals in this sense.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. Code2vec: Learning distributed representations of code. In Principles of Programming Languages, 2019.
C.W. Barrett, D.L. Dill, and J.R. Levitt. A decision procedure for bit-vector arithmetic. In Design and Automation Conference, 1998.
Tal Ben-Nun, Alice Shoshana Jakobovits, and Torsten Hoefler. Neural code comprehension: A learnable representation of code semantics, In Neurol Information Processing Systems, 2018.
Prajjwal Bhargava, Aleksandr Droad, and Anna Rogers. Generalization in nli: Ways (not) to go beyond simple heuristics, 2021.
Anloon Bosselaers, René Govaerts, and Joos Vandewalle. Comparison of three modular reduction functions. In Advances in Cryptology, 1994.
Pascal Giorgi, Thomas Izard, and Arnaud Tisscrand. Comparison of modular arithmetic al- gorithms on gpus. In Conference on Paralled Compuling and High Performance Compuling, 2009.
Joris Van Der Hoeven, Grégoire Lecerf, and Guillaune Quintin. Modular simd arithmetic in mathemagix. Transactions on Mathematicall Software, 2016.
Yikun Hu, Yuanyuan Zhang, Juanru Li, and Dawu Gu. Binary code clone detection across architectures and compiling configurations. In International Conference on Program Comprehension, 2017.
Jeevana Priya Inala, Rohit Singh, and Armando Solar-Lezama. Synthesis of domain specific enf encoders for bit-vector solvers. In Theory and Applications of Satisfiability Testing, 2016.
Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. Oracle-guided component- based program synthesis. In International Conference on Software Engineering, 2010.
Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi. Learning and evaluating contextual embedding of source code. In International Conference on Machine Learning, 2020.
Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. In International Conference Machine Learning, 2019.
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks over tree structures for programmiin language processing. In Associalion for the Advancement of Artificial Intelligence, 2016.
Dinglan Peng, Shuxin Zheng, Yatao Li, Guolin Ke, Di Hc, and Tie- Yan Liu. How could neural networks understand programs? In International Conference on Machine Learning. 2021.
Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten Holz. Cross-architecture bug search in binary executables. In Symposium on Security and Privacy, 2015.
Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladmir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, et al. Project codenet: A large-scale ai for code dataset for learning a diversity of coding tasks. arXiv preprint XrXx:21105.12553 2021.
Dana Scott. Outline of a mathematical theory of computation. Kiberneticheskii Sbornik. Novaya Seriya, 1977.
10

---

Under review as a conference paper at ICLR 2023
Inlia Ture, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Well-read students learn better: The impact of student initialization on knowledge distillation. arXiv, 2019.
Ke Wang, Rishabh Singh, and Zhendong Su. Dynamic neural program embedding for program repair. International Conference on Learning Representations, 2018.
Yu Wang, Ke Wang, Fengjuan Gao, and Linzhang Wang. Learning semantic program embeddings with graph interval neural network. In Object- Oriented Programming, Systems, Languages, and Applications, 2020.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing. In Empirical Methods in Natural Language Processing: System Demonstrations, 2020.
Hao Yu, Wing Lam, Long Chen, Ge Li, Tao Xie, and Qianxiang Wang. Neural detection of semantic code clones via tree-based convolution. In International Conference on Program Comprehension, 2019.
11

---

Under review as a conference paper at ICLR 2023
A EXTENDED THEORY
We first provide a formal definition of programming language.
Definition A.I. A programminng language P (c) [+ is tuple of:
A language EC over an alphabet of symbols E
An enumeration order L()) NN L satislying the conditions of computable enumer--
ability (i.e., for every element E L, there exists a unique n E N such that Ln = p) and such that [.,1] S [ for all n E
denotation function I-] : C + (I + O) mapping programs to mathematical functions, where the input space is I and the output space O is also equipped with an equivalence relation decidable in O(log time.
For convenience, wrile P to mean p E L.
A.1 EXISTENCE
In this section, we give necessary and sufficient conditions for an equivalence-presorvvnn embedding function to exist.
Theorem A.1. An cerpalenco--reeervine embedding function exists for programming language p = (C, [-)),-I)) exactly when there are finitely many semantic equivalence classes.
Proof. +) The contrapositive is that every language with infinitely many semantic equivalence classes does not have equivalence-preservee embedding function. Suppose there were such an cnnivalennc-proserviin semantically distinct programs, two distinct programs must have the same embedding by the Contradiction.
embedding function into a set with n elements. Then, given n + 1
pigeonhole principle, so the embedding function is not equivalence--peserviie
-) We show that finitely many semantic equivalence classes implies the existence of equivalence-preervingg embedding function. Choose I-] as the embedding function. Since there are finitely many semantic equivalence classes, [C] is a finite set meaning is indeed an embedding, By definition, programs are functionally equivalent exactly when their denotations are equal, so this embedding preserves equivalences well.
The example below is programming language that cannot be embedded.
Example A.2. The programming language of integers (e.g., -100, 1, are all programs) has no embedding because each number forms its own semantic equivalence class and there infinitely many numbers. More generally, languages with infinite datatypes such as linked lists and binary trees have no embedding.
A.2 COMPUTARILITY
The embedding given by Theorem A.1 is not always useful because it may not be computable, so we need stronger condition ensure computability.
embedding function we develop in this section requires repre- sentative programs for each semantic equivalence class in a programming language. The following lemma provides a procedure to identify them.
The equivalence-presee
Lemma A.3. When a programming language p= (C, C(-), classes and semantic equality is decidable, there is algorithm that collects representative programs Pl.....P. for each semantic equivalence class in finite time.
[-I) has n semantic equivalence
Proof. We cnumerate through L, maintaining a set representatives for cach semantic equivalence class seen so far. For cach program p we encounter, we check [p] [r]] for all
$ $[C] is notation for the image of the programming langnage under the denotation function (i.e.
(Ipl p Z})
12

---

Under review as a conference paper at ICLR 2023
E R. If p is inequivalent to all such then it represents new semantic equivalence class, and we add p to R. Once [R] =n, n, we have a representative for each semantic equivalence class, terminate the procedure.
Now, we show the search for representatives terminates. Let C = ||e]- E [C]] be a partition of L into semantic equivalence classes. Each semantic equivalence class C C has a member L; E C that occurs before all other C' E C in the enumcration order and it does in finite time, by computable enumerability. The algorithı will terminate after encountering & representative from each class, so it will terminate after encountering the last representative in the enumeration order. That is, it will terminate after
CEC|
max
arg
arg min Ci i.[.,JE
iterations. This quantity is finite, because it the maximum of collection of finite values, so the algorithm terminates in fimite time.
Now, with the lemma above, we show decidable semantic equality the only additional property required to have necessary and sufficient conditions for programming language to be computably embedded.
Theorem A.4. There is computable, equivalence- language P exactly when there are finitely many semantic equivalence classes and somantic equality is decidable in P (for every p. E P. [p] [[q] is decidable).
embedding for programming
embedding e for P. By Theorem A.1, P must have finitely many semantic equivalence classes. Given programs P.q E P, we can decide semantic equality by checking e(p) = e(g). since is computable and equality of embeddings is computable.
Proof. =) Suppose we have a computable, equivalence-preserve
=) Suppose P has semantic equivalence classes and decidable semantic equality. By Lemma A.3, we can find representative programs Pr.....Pr in finite time. Then, we embed given program p by identifying the p; such that [p] = [p:]] (using decidable equality of programs), and setting the embedding e(p) to be
The following programming language can be embedded, but cannot be computably embedded.
Example A.5. Consider the programming language of Turing machine descriptions that denote 1 if the Turing machine halts on all inputs and 0 otherwise. There are only two semantic equivalence classes, so program embedding function exists. However, it is not computable because semantic equality is not decidable by a reduction from the Halting problem.
Corollary A.6. There is computable equivalence--reserving embedding for programming languages with finite input and output spaces.
Proof. Let P be a programming language with finite input and output spaces I, O. There are [Z] possible denotations of functions in P. Let Q be language of encodings of these functions (c.g., programs in Q could be sets of every input-output pair). Since the construction of Q computable and it satisfies the conditions of Theorem A.4, we can construct a computable squivalence-preseree
embedding. We can then embed a program in P by running on every input, recording outputs, to write a program in Q that we embed.
By Corollary A.6, bounded datatypes over bounded data such as all fixed-length lists of bounded integers have computable equivalence-preserve embedding functions.
13

---

Under review as a conference paper at ICLR 2023
B TRACTABILITY PROOFS
B.1 TRACTABLE PROGRAMMING LANGUAGE OF MODULAR ADDITION
Theorem 4.1 The programming language of modular addition is tractable. In particular, there are n² semantic equivalence classes.
Proof. Every expression in the language denoles an expression of the form kar c, where 0 < k < n and 0 S c < n, and each (k c) pair indexes into a distinct function signature. Thus, there are most n² semantic equivalence classes.
To show there are at least n² equiv classes, we show that each pair is unique. All of the equations below are mod n. When ka C1 kæ C2 where ei # c2, then e₁ C22 contradiction. Suppose k + c= k2z + where l & k2, then (k2 k1)æ = 0, but at r = 1, this mcans that h l2, contradiction. When 2 + C1 k2 C2 where 1 * k2 and e # C2. C2, but at r = 0, this means C₁ = C2, contradiction.
then (k2 - ka
Thus, there are precisely n² semantic equivalence classes. Evaluating the function at 0 and gives us the coefficients (k, c) and takes time linear in the program size and constant in the input space.
B.2 AN INTRACTABLE PROGRAMMING LANGUAGE MODULAR ADDITION AND BITWISE LOGIC
Theorem 4.2 P * NP, the programming language arithmetic and bitwise logic intractable.
Proof. Suppose we have a tractable embedding function e for P. We solve boolean satisfia- bility by encoding circuit a program p and outputting SAT if and only if e(p) # e(0). Therefore, we have a polynomial-time decision procedure for SAT, which is NP-complete, and P = NP. Contradiction.
C EXTENDED METHODOLOGY
C.1 LEARNING AN EMBEDDING FUNCTION
To learn an cettivaaeenc--reeevvvii embedding function, we train transformer neural network lo classify program text to a fixed set so that equivalent programs are mapped to the same element of that set.
Datasct size [D]
18000
Train set size
12000
Test set size
3000
Validation set size
3000
Number of epochs (tractable)
333
Number of epochs (intractable)
600
Learning rate 1)
1e-4
Batch size [73]
128
AST size
11
Number of AST Samples
500,000
Trials per configuration"
3
Model. Kanade et al. (2020) showed that the BERT (large) is capable of learning program embeddings that perform well across a nunber programming language processing tasks. Since our dataset is small when compared to the dataset size that BERT is trained on, we opt for a smaller model: BERT-Tiny (Bhargava et al., 2021: Ture et al., 2019). We use the BertForSequnneClssfii cation model from the transformers library (Wolf et al., 2020). We remove all dropout from the model. Table C.1 shows the hyperparameters for our setup.
14

---

Under review as a conference paper at ICLR 2023
Training. We train the model on standard cross-entropy loss using the Adam optimizer with a learning rate of le-4. We shuffle the dataset D before each epoch, and we use a batch size of 128. For the tractable language, train for 333 epochs. For the intractable language, this is not long enough to converge on all configurations, so we train for 600 epochs.
System. We run all Transformer experiments tractable language, each configuration takes about 20 minutes. For the intractable language, each configuration takes about 2 hours.
NVIDIA Tesla V100 GPU. For the
C.2 CHOICE OF AST SIZE
Since want a fixed program length (meaning fixed AST size), want to show a fixed AST size does not obscure the relationship between the imput space size and the number of semantic equivalence classes. Figure 7 shows that, for both languages, the relationship between input space size and number of semantic equivalence classes is preserved as we vary the AST size. In particular, this means if we included all AST sizes less than given bound, we would have the same relationship between the input space size and the number of semantic equivalence classes. Thus, choosing fixed AST size of 11 docs not threaten our results in this regard.
C.3 DATASET GENERATION
We first generate all ASTs of size 11 (Appendix C.3.2) and label them, then extract. balanced subset (Appendix C.3.1).
For the tractable language, we generate datasets with 15000 examples each, and we use an 80/20 train /eet split. For the intractable language, not all runs achieve 100% test accuracy, so we generate a validation set as well. That is, we generate datascts with 18000 examples each, and constraint in data generation, we generate a different dataset for each input space size and language.
60/20/20 20 train train//estt validation split. Note that due to the balanced-class
C.3.1 BALANCED DATASET GENERATION
The distribution of equivalence classes in random sample of generated ASTs is far from uniform. The equivalence classes for functions Az. O, Ar. 1, and Ax. are represented disproportionately often (sx 17%, 7%, and x 7%, respectively, at various moduli m 4) and long tail of infrequently occurring classes
If considered all ASTs, we might find enough examples for most classes build balanced dataset, but at larger AST sizes, the set of all ASTs is quite large. For example, at size 11, there are 22,240,092 ASTs. Enumerating this set and determining the equivalence class of each would take prohibitively long. So we need to balance the number of classes e we pick for the dataset and the mumber of examples per class x the following equation is satisfied: C- x = (D).
Figure plots equivalence classcs, ordered by frequency, on the x axis and the number of expressions in an equivalence class on the axis. Navigating the balance of e and x amounts to finding a rectangle in this plot with area [D]. If we wanted to, for example, have 2 examples per class (the brown line in the plot), can see that increasing the number of samples allows us to include more equivalence classes. Note that the strategy of finding rectangles means may underrepresent the true number of classes at given modulus.
For each dataset we generate, we use the shortest rectangle with at least examples per class. That is, we want many classes as possible, but we want at least 6 examples per class (4 for training, for test, and for validation).
To generate the final dataset, sample 500,000 ASTs and find rectangle satisfying the constraints above. Figure 5 shows that using 500,000 AST samples across all input space sizes provides datasets with distributions of semantic equivalence classes that match the
15

---

Under review as a conference paper at ICLR 2023
samples 200
Samples 1000
Samplss 10000
samples J0000
samples 1000000
num chasss =5
101
10
101
10
500
1000
1500
2000
2500
Equly Class Isoited by trequency)
Figure Scmantic oquivalence classes sorted by the number of expressions in the equivalence class.
Table 1: Number of semantic cquivalence classes in dataset generated at each input space size
Input Space Size
3
4
7
11
# Tractable Classes
9
16
22
26
26
Intractable Classes
27
53
834
2143
3000
distributions of classes encountered during sampling. Table shows the number of semantic equivalence classes at each input space size the final dataset.
C.3.2 AST GENERATION
We define AST size as the number of nodes in an AST. We generate ASTs of fixed size exhaustively by dynamic programming. Every generated program is valid (syntactically and semantically). Our code also caches enunerated expressions of each expression size. To generate an AST size n, at the end execution, all ASTs of size to n are stored the cache and each unique expression of size is generated preciscly once.
The base case is a constant or variable integration. For an AST of size n, the algorithm generates all ASTs of size binary operation the algorithm sets the left and right children to every possible AST pair coming from the partition of objects. Figure provides the algoirthm described above in Python syntax.
and feeds each the unary not function. Similarly, for every
C.4 CHOICE INPUT SPACE SIZE
The relationship between the input space size and the number of semantic equivalence classes for the tractable language, meaning we could choose any increasing sequence of imput space sizes to answer the relation between the imput space size and the number of semantic equivalence classes in the intractable language is complicated. In particular, it is not monotonic, but there
research question for the tractable language. However,
16

---

Under review as a conference paper at ICLR 2023
500,000 samples
(Tractable False)
(Tractable
1000
12020
Nam Se Cisse Friil Dalast
2500
2000
1500
1000
10
Modulis
Noduks
1, 1,000,000 samples
(Trectable Fabe)
(frectable False)
17500
3000
15000
Num Sa Clases Infiral Datsee
2300
2000
10000
Num Clases
3500
1000
3000
Moduks
10,000,000 samples
(Tractable False)
(Tractable False)
17500
3000
Num Exconteend
Num Be Clasuos Final Dansse
12500
2000
10000
7500
3000
5000
10
2
10
Modulus
Moduks
Figure 5: Comparison of the number of semantic equivalence classes encountered during sampling vs. the number of semantic equivalence classes included in the final dataset. We make this comparison for sample sizes 500,000, million, and 10 million ASTs, and we find that using 500,000 samples gives the number of encountered classes that matches most closely with the number of classes the final dataset.
17

---

Under review as a conference paper at ICLR 2023
def coum_ast(size) int) -> 1ist [Expr]: if size == 1: return [i for i in CONSTS] + [Var ("x")]
Unary trees trees = (N) for in enum_ast (size 1)]
Binary trees for r1nge size 1): for binop in BINOPS:
for left in enum_ast(i):
for right in enum_ast (size i 1):
trees. (pponn right))
return trees
Figure 6: The data generalion algorithm to enumerate ASTs of fixed size without caching,
exist monotone subsequences. Figure 7 shows the relationship for both languages. For our empirical study, we identify {2, 3, 4, 5, 7, [1} as sequence that provides a monotonically increasing number of semantic equivalence classes for both languages.
18

---

Under review as a conference paper at ICLR 2023
Expressible Equivalence Classes for Tractable Semantics
AST size
AST
# Equiv clases in Sample 100000 Expes
AST size
AST s/ze
AST
10
Modulus
Expressible Equivalence Classes for Intractable Semantics
AST size
AST size
3500
AST si0
3000
AST size
Sample 1000000
AST size 8
2500
AST size 9
AST size
1000
500
10
Modulus
Figure 7: Number of semantic equivalence classes encountered in 100,000 AST samples vs. input space size. We plot this relationship for the tractable language Section 4.1 (Top) and the intractable language in Section 4.2 (Bottom) and for AST sizes from 1 through 11. (Top) For the tractable language, we only see new semantic equivalence classes at odd AST sizes, since every operator binary. At each AST size, size, the number of semantic equivalence classes increases monotonically until platcaning. (Bottom) For the intractable language, do not input space size and the number of semantic equivalence classes, for any AST size. However, we do that the relative relationship across input space sizes preserved vary the AST size.
increase the input space
monotonie relationship between the
19


Reviews:
[{"review_id": "pnPwn-IEoH", "reviewer": "Reviewer_M5Qy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper defines equivalence-preserving program embedding, a constraint that requires the learned program embeddings to be equivalent if the corresponding programs have the same input-output behavior. It provides the conditions specifying when a programming language can be represented into embeddings that preserve the equivalence. It then provides empirical evidence showing that programming languages that satisfy the conditions can be more accurately embedded.", "summary_of_the_review": "My main concern is the practical implication of the proposed theory. Ideally, equivalence-preserving program embedding makes sense if it remains invariant against program transformations. For example, code clone detection requires the model to understand that various classes of transformations on program syntax do not change their input-output behavior. Therefore, it makes more sense to characterize what transformations can be tractably embedded. However, the authors characterize it from the language perspective. Most of the programming languages that existing applications consider are intractable, i.e., assembly code or even undecidable, as pointed out by the authors.\n\nTherefore, it is not unclear how the theory of equivalence-preserving embeddings could help solve existing semantic code modeling tasks. ", "strength_and_weaknesses": "Strength:\n+ Describes an important property of program embeddings: they should remain invariant to semantic-preserving transformations.\n+ First theoretical definition of equivalence-preserving program embedding problem. The paper provides formal conditions under which the programming languages can be tractably embedded.\n\nWeaknesses: \n\n- The empirical study is not convincing by only evaluating BERT-Tiny. Numerous neural architectures have been used to model programs, e.g., large language models, graph neural networks, etc. Can the proposed theory help explain some of the successes of one architecture over others? Can the theory guide how to develop new models to learn program representations? \n\n- The practical implication of this paper is unclear. While the authors describe two applications (Section 2), these applications often deal with common programming languages that are intractable, e.g., code clones across binary code for vulnerability detection. Can the proposed theory help explain if the same code modeling task for some languages is strictly easier than the others? The theory can be more practically useful if it can be extended to quantify the intractability level so the resulting embeddings' error can be bounded or compared. \n\n- Figure 1: unclear why certain input sizes have their accuracy going down, even though they have reached 100% in the earlier epochs. \n\n- There is no discussion on why larger input space sizes need a smaller number of epochs to converge on the tractable language, which contradicts the observation that losses increase monotonically with input space sizes on the intractable language.\n- Extensive results and discussions are put in the Appendix, costing great effort in going back and forth. \n\n- The paper uses code clone detection and semantic labeling to motivate their theory, but the theory focuses on characterizing language tractability. Can the theory extend to cross-language clone detection, e.g., one language is tractable, but the other language is not?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6g96r5LRTFd", "reviewer": "Reviewer_Pnio", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to provide a theory to analyze the semantic equivalence of programming languages. This is the classical equivalence problem and in general undecidable. This paper additionally imposes some assumptions and studies when the equivalence can be efficiently decided, defined as tractably embedded in this paper. The authors also conduct an empirical study, aiming to show that BERT-Tiny can learn languages with tractably embedded semantics but not intractably embedded semantics.", "summary_of_the_review": "This paper presents a theory to study the semantic equivalence of programming languages. However, the theory is ad hoc and the evaluation is inconclusive. This paper is not ready for acceptance yet.", "strength_and_weaknesses": "**Strength**\n\nAnalyzing the hardness of equivalence decidability can be an interesting perspective to understand the learning capacity of neural network models, especially for programming language tasks.\n\n**Weakness**\n1. The theory is ad hoc:\nThe (semantic) equivalence problem is a classical problem and has been studied for decades for different formal systems, for example, automata, regular expressions, and pushdown systems. They are often at least PSPACE-hard. These are naturally encountered formal systems. In this paper, the authors impose assumptions like the (denotational) semantics is from a finite set, the input space is finite. Those assumptions in general do not hold.\n\n2. The techniques are elementary:\nThe techniques used to develop the theory are elementary. With the finiteness and some efficient procedure assumptions, the proofs are usually direct manipulations of definitions and assumptions. It does not seem that there are useful theoretical or mathematical techniques.\n\n3. The evaluation is rough:\nThe evaluations are on two toy languages defined in this paper, and the input space size is at most 11. It is conceivable that modular addition is easier than bitvector arithmetic to learn because the latter is a direct extension of the former. It is inconclusive to understand model's capacity to learn the semantics just based on this toy evaluation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "154Y8MzPwS0", "reviewer": "Reviewer_3JjL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a theoretical background on how to incorporate code semantics into code embedding.  They argue that when two programs behave identically on a given input, they are semantically equivalent, and their representation in the embedded space should capture such properties. They demonstrate their theoretical foundation across two tasks.  ", "summary_of_the_review": "The paper presents some interesting and important ideas. However, there is a large gap between the idea and practicality and generalizability.  It is not clear to me how the proposed idea of tractable embedding can be applied to real-world problems. ", "strength_and_weaknesses": "(+) Code semantics is an important program property, and proposing a theoretical framework to incorporate semantics to embedding is important. \n\n(+) The theoretical foundation is good.\n\n(-) The demonstration is shown on small tiny problems. \n\n(-) I am not sure any general-purpose language can be tractably embedded. It is not clear how such a definition can be extended to such languages.\n\n(-) If the intention is to use tractable embedding to domain-specific language, I would encourage the authors to show some convincing scenarios.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0PGO1XDduu0", "reviewer": "Reviewer_c7mJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed a new notion of equivalence-preserving program embedding, proved a simple arithmetic language has an equivalence-preserving embedding, and experimentally demonstrated that having the embedding is crucial to learn an embedding of programs.\n", "summary_of_the_review": "The paper addresses a critical aim to apply machine learning techniques to programming language tasks. The proposed notion of equivalence-preserving program embedding is novel. However, as described above as a weakness, its practicality is a big concern because of its theoretical strictness. Research given in Section 5.1 would enhance the work much more.", "strength_and_weaknesses": "Strengths:\n\n+ The notion of equivalence-preserving program embedding is new, theoretically formulated, and proven to be satisfied by a simple arithmetic language and unsatisfied by a bit-vector language.\n\n+ The usefulness of equivalence-preserving program embedding is experimentally demonstrated.\n\n+ The documentation is well written and easy to follow.\n\nWeaknesses:\n\n- Little languages have equivalence-preserving program embedding functions. Theoretically, a tractably embeddable language (i.e., one with an equivalence-preserving embedding function) has a means to determine the equivalence of two programs. It means that no Turing-complete language is tractably embeddable. Furthermore, although recognizing the limitation of an approach is crucial in general, even the simple bit-vector language does not have such a function. Therefore, I am concerned about the practicality of the proposed approach in its current status. Considering the strictness of equivalence-preserving program embedding, I am not surprised that a machine learning model can learn an embedding for a tractably embeddable language even when the same model cannot learn an embedding for a language that is not tractably embeddable.\n\n- As a minor point, the theory of the paper seems to assume the input space ($I$) is finite, but, in general, one can consider programs with an infinite input space (like list-processing programs).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject