BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Qirun Zhang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Recently, Li et al. [2022] presented a dynamic Dyck-reachability algorithm for bidirected graphs. The basic idea is based on updating edge weights in a data structure called the merged graph $G_m$. As noted in Krishna et al. [2023], the edge deletion procedure described in the algorithm of Li et al. [2022] cannot properly update the weights in the presence of cycles in $G_m$. This note discusses the cycle case and the time complexity.
Type inference for dynamic programming languages such as Python is an important yet challenging task. Static type inference techniques can precisely infer variables with enough static constraints but are unable to handle variables with dynamic features. Deep learning (DL) based approaches are feature-agnostic, but they cannot guarantee the correctness of the predicted types. Their performance significantly depends on the quality of the training data (i.e., DL models perform poorly on some common types that rarely appear in the training dataset). It is interesting to note that the static and DL-based approaches offer complementary benefits. Unfortunately, to our knowledge, precise type inference based on both static inference and neural predictions has not been exploited and remains an open challenge. In particular, it is hard to integrate DL models into the framework of rule-based static approaches. This paper fills the gap and proposes a hybrid type inference approach named HiTyper based on both static inference and deep learning. Specifically, our key insight is to record type dependencies among variables in each function and encode the dependency information in type dependency graphs (TDGs). Based on TDGs, we can easily integrate type inference rules in the nodes to conduct static inference and type rejection rules to inspect the correctness of neural predictions. HiTyper iteratively conducts static inference and DL-based prediction until the TDG is fully inferred. Experiments on two benchmark datasets show that HiTyper outperforms state-of-the-art DL models by exactly matching 10% more human annotations. HiTyper also achieves an increase of more than 30% on inferring rare types. Considering only the static part of HiTyper, it infers 2x ~ 3x more types than existing static type inference tools.
Inclusion-based (i.e., Andersen-style) points-to analysis is a fundamental static analysis problem. The seminal work of Andersen gave a worst-case cubic $O(n^3)$ time points-to analysis algorithm for C, where $n$ is proportional to the number of program variables. An algorithm is truly subcubic if it runs in $O(n^{3-δ})$ time for some $δ> 0$. Despite decades of extensive effort on improving points-to analysis, the cubic bound remains unbeaten. The best combinatorial analysis algorithms have a "slightly subcubic" $O(n^3 / \text{log } n)$ complexity. It is an interesting open problem whether points-to analysis can be solved in truly subcubic time. In this paper, we prove that a truly subcubic $O(n^{3-δ})$ time combinatorial algorithm for inclusion-based points-to analysis is unlikely: a truly subcubic combinatorial points-to analysis algorithm implies a truly subcubic combinatorial algorithm for Boolean Matrix Multiplication (BMM). BMM is a well-studied problem, and no truly subcubic combinatorial BMM algorithm has been known. The fastest combinatorial BMM algorithms run in time $O(n^3/ \text{log}^4 n)$. Our result includes a simplified proof of the BMM-hardness of Dyck-reachability. The reduction is interesting in its own right. First, it is slightly stronger than the existing BMM-hardness results because our reduction only requires one type of parenthesis in Dyck-reachability ($D_1$-reachability). Second, we formally attribute the "cubic bottleneck" to the need to solve $D_1$-reachability, which captures the semantics of pointer references/dereferences. This new perspective enables a more general reduction that applies to programs with arbitrary pointer statements types. Last, our reduction based on $D_1$-reachability shows that demand-driven points-to analysis is as hard as the exhaustive counterpart.