Constructing a Static Program Slicer for R Programs
Creators: name: Sihler, Florian
Publisher: name: Universität Ulm
Year: 2023
Subjects: subject: Data-Flow
subject: Dataflow
subject: DDC 004 / Data processing &amp; computer science
subject: R (Computer program language)
subject: Data flow computing
subject: Programmverstehen
subject: Programmanalyse
subject: R (Programm)
subject: Program Slicing

description: In this master thesis we describe the construction of a backward program slicer for the R programming language. Given a variable at a specific point in the program, a so-called "slicing criterion", the slicer returns the subset of the program that might affect the value of the variable. CONTEXT: Programmers spend a huge part of their time trying to understand code, which led to the development of various tools to support them. For example, linters and program slicers, that analyze the program to identify potential problems or answer questions regarding its variables. However, the R programming language enjoys only a small set of existing tools. OBJECTIVE: Without any existing program slicer for the R programming language, we propose flowR, a static analyzer and program slicer for R programs. It supports, among others, assignments, loops, and function calls. Alongside flowR, we 1) identify the commonly used language constructs, 2) propose a new algorithm for the dataflow analysis of R programs, 3) evaluate flowR on a set of real-world programs, and 4) present an overview of the syntax and semantics of R. METHOD: To identify the most common language constructs we count their usage in the source code of R packages and R scripts published in the area of social science and compare the results. Next, we explain the five-step architecture of flowR, focusing on the dataflow analysis due to the amount of effort required. Moreover, we relate each part of the explanation to its corresponding implementation (https://github.com/Code-Inspect/flowr/releases/tag/v1.0.0). Afterward, we evaluate the theoretical capabilities of flowR and measure the required processing time as well as the achieved reduction in the size of the program slice using all possible slicing points in a set of real-world R files. For the overview of R's syntax and semantics, we use the R language definition and the related literature. LIMITATIONS: The capabilities of our program slicer are limited to a subset of what is possible in the R programming language mainly due to the limited scope of this master's thesis. Furthermore, there exists no formal specification of R and most semantics are defined implicitly. Therefore, every claim we present is inherently based on our understanding of the language. RESULTS: We find that R scripts are on average more than twice as long as the code in packages. Furthermore, scripts contain on average more assignments, loops, and function calls, but fewer if-constructs for branching. For the return value of functions, most definitions do not rely on an explicit exit point with 'return'. Instead, they implicitly return the result of the last expression they evaluate. We formulate slicing as a reachability problem on the dataflow graph of the program, including everything that can be reached from the slicing criterion. Our algorithm to construct this graph relies on the AST of the input program. Essentially, it works as a fold, with the inner nodes merging the dataflow of its children while keeping track of all active definitions. We find, that the AST produced by the R interpreter is unsuitable for our subsequent dataflow analysis and therefore normalize the AST prior. Our evaluation shows, that flowR requires on average roughly 3.83s for a single slice, although the time is influenced by outliers (median: 358ms) and around 99.35% of the time can be re-used when slicing for multiple variables in the same program. Additionally, we find that the average slice can reduce the number of characters in the program by 85.66%.