💻 computer science

Inferring the Shape of Data Frames in R Programs using Abstract Interpretation

This paper presents a novel static analysis based on abstract interpretation that infers the shape of data frames in R programs by tracking column names and dimensions, demonstrating its soundness and practical utility in analyzing thousands of real-world scripts to detect potential invalid data accesses.

Original authors: Oliver Gerstl, Florian Sihler, Matthias Tichy

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oliver Gerstl, Florian Sihler, Matthias Tichy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef working in a very chaotic kitchen. In this kitchen, the ingredients (your data) are stored in large, magical trays called Data Frames. These trays are the heart of your cooking (data analysis).

The problem with this kitchen is that it's run by a language called R, which is incredibly flexible but also a bit forgetful. You can add ingredients, remove them, or rearrange them on the fly. But because the kitchen is so dynamic, there's no automatic way to know exactly what's in a tray at any given moment without actually cooking the whole meal and seeing what happens.

This leads to a common disaster: You reach into a tray to grab a specific spice (a column of data), but because you removed it earlier in the recipe, the spice isn't there. The kitchen explodes (the program crashes), and you have to start over.

The Solution: A "Magic Menu" (Abstract Interpretation)

The authors of this paper, Oliver Gerstl, Florian Sihler, and Matthias Tichy, built a new tool that acts like a super-accurate, predictive menu for your kitchen. They call this tool Abstract Interpretation.

Instead of waiting for the kitchen to explode to find out what's missing, this tool reads your recipe (the code) and predicts the shape of every tray before you start cooking.

Here is how their "Magic Menu" works, broken down simply:

1. The Three Rules of the Tray

To understand a tray, the tool tracks three specific things:

The Labels (Column Names): What are the names of the ingredients in the tray? (e.g., "Age," "Score," "ID").
The Width (Number of Columns): How many different types of ingredients are there?
The Height (Number of Rows): How many individual portions are in the tray?

2. The "Safety Net" (Soundness)

The most important rule of this tool is that it is safe. It never guesses that a tray has fewer ingredients than it actually does.

The Analogy: Imagine the tool is a cautious librarian. If it's not 100% sure if a book is on the shelf, it assumes the shelf is empty. It would rather tell you, "I don't know what's here," than say, "There is a book here," when there actually isn't one.
Why this matters: In their tests, the tool never gave a false sense of security. If it said a column existed, it was guaranteed to exist. If it said it might not exist, it was being careful.

3. Tracking the Changes

The tool follows every step of the recipe.

Creating a Tray: When you make a new tray, the tool knows exactly what labels you put on it.
Filtering: If you throw away all rows where "Age" is under 20, the tool knows the tray gets shorter (fewer rows), but the labels stay the same.
Adding/Removing: If you add a new column called "Level," the tool updates the width. If you delete the "Score" column, the tool marks "Score" as gone.

The "Aha!" Moment:
In the paper's example, the tool noticed a subtle mistake in a recipe. The chef removed the "Score" column in step 12, but then tried to grab the "Score" column in step 14 to print the average. The tool flagged this before the code ran, saying, "Hey, you can't grab 'Score' here; you threw it away three steps ago!"

What They Found (The Results)

The team tested this tool on a massive amount of real-world recipes (33,314 R scripts from researchers).

The Success Rate: For about 42% of the tray operations, the tool could tell them exactly what the tray looked like (e.g., "This tray has exactly 3 columns: ID, Age, and Level").
The "Perfect" Guess: For about 0.9% of operations, it knew the exact number of rows and columns, not just a range.
With Better Ingredients: If the tool was allowed to look at the actual data files the recipes were trying to read (which isn't always possible in a static analysis), the success rate jumped to 58.7% for concrete shapes and 4.2% for exact shapes.
Finding Bugs: The tool found 40 real-world scripts that had potential mistakes where researchers were trying to grab columns that didn't exist.

Why This Matters

Most tools for checking code are like spell-checkers; they look for typos. This tool is like a logic-checker for data. It helps researchers (who often aren't professional software engineers) avoid subtle bugs where their data gets lost or misshapen during complex analysis.

The tool is also fast. It takes less than a second to analyze a typical script, meaning it could be used while a researcher is writing their code to warn them of mistakes in real-time.

Summary

The paper presents a new way to look at R code that predicts the "shape" of data tables without running the code. It uses a "safety-first" approach to ensure it never lies about what data exists. By doing this, it helps researchers catch errors where they accidentally try to use data that has already been deleted or transformed, making data analysis more reliable and less prone to crashing.

Technical Summary: Inferring the Shape of Data Frames in R Programs using Abstract Interpretation

Problem Statement

Data frames are the fundamental data structure for statistical computing and data analysis in R. However, R is a dynamic language that lacks static guarantees regarding the "shape" of data frames (i.e., column names, number of columns, and number of rows). This dynamism makes it difficult to reason about data frame structures at specific points in a program, leading to subtle runtime errors such as accessing non-existent columns or out-of-bounds rows. Existing static analysis tools for data science either focus on general properties without considering shape and size, or they are limited to Python (specifically the pandas library) and have not been evaluated on real-world code. Furthermore, current R-specific tools like lintr rely on syntactic patterns and do not account for data flow or control flow, while flowR provides data flow analysis but lacks mechanisms to infer data shape.

Methodology

The authors propose a novel static analysis based on abstract interpretation to infer the shape of data frames in R programs. The approach involves defining an abstract domain, mapping concrete operations to abstract operations, and defining abstract semantics to track shape properties through program execution.

1. Abstract Domain Definition

The authors define the data frame shape domain ( $\mathcal{DF}^\#$ ) as a partially reduced product domain consisting of three sub-domains:

Column Names ( $\mathcal{N}^\#$ ): Modeled using a set range domain. A data frame's column names are represented by a pair $(A, B)$ , where $A$ is the set of column names that must exist (minimum set) and $B$ is the set of column names that may exist (maximum set).
Number of Columns ( $\mathcal{C}^\#$ ) and Rows ( $\mathcal{R}^\#$ ): Modeled using a positive interval domain $[a, b]$ , where $a$ is the lower bound and $b$ is the upper bound (potentially infinite).

To improve precision, the authors introduce a reduction function ( $\rho_{\mathcal{DF}}$ ) that refines the product domain. If the inferred number of columns (from the interval domain) matches the size of the minimum column name set, the maximum set is reduced to match the minimum set. Conversely, if the column count interval is constrained, the column name sets are refined accordingly.

2. Abstract Semantics and Operation Mapping

The analysis identifies the 20 most commonly used data frame functions in R (e.g., data.frame, read.csv, filter, mutate, select) and maps them to abstract operations.

Creation: Functions like data.frame and read.csv map to a create operation, initializing the column name sets and row/column intervals based on arguments.
Transformation:
- filter maps to filterRows, which soundly over-approximates the row count (potentially reducing the lower bound to 0) while preserving column names.
- mutate maps to mutateCols, which adds new column names to the maximum set and potentially increases the column count interval.
- select (or subset) maps to subsetCols, intersecting the current column name sets with the selected columns and adjusting the column count interval.
Access: Column and row accesses (via $, [, or [[) are mapped to accessCols and accessRows. The analysis checks if the accessed name or index falls within the inferred abstract shape.

The analysis is implemented as a visitor on the Control Flow Graph (CFG) generated by flowR, a static data flow analyzer for R. It performs fixpoint iteration with delayed widening at loop heads to ensure termination. For data frames read from external files (e.g., CSV), the analysis attempts to extract concrete shape information from the file headers and content if the files are locally available.

Key Contributions

Formal Definition: A formal definition of an abstract domain for data frame shapes using a partially reduced product of set ranges and intervals.
Implementation: A companion implementation based on flowR that includes a linter rule to report invalid data frame accesses (e.g., accessing a column that has been removed by a preceding select operation).
Evaluation on Real-World Code: The first approach to analyze data frame shapes in R evaluated on a large dataset of real-world scripts, moving beyond proof-of-concept evaluations on synthetic code.

Results

The authors evaluated the approach on two datasets:

Correctness Evaluation (78 Scripts):
- The analysis successfully identified 72% of actual data frame variables.
- Soundness: The analysis never under-approximated the actual shape (i.e., it never claimed a column existed when it did not, or a row count was lower than reality).
- Precision: 8% of detected data frames had exact shape matches. 92% were over-approximations (mostly top or infinite bounds), which is expected for dynamic filtering operations where the exact row count depends on runtime values.
Effectiveness Evaluation (33,314 Scripts):
- Constraint Inference: The analysis inferred concrete (non-top) shape constraints for 42.1% of data frame operations and exact shapes for 0.9%.
- Impact of Data Availability: When all datasets read by the scripts were available locally, these figures improved to 58.7% (concrete) and 4.2% (exact).
- Error Detection: The analysis identified 40 scripts containing potential invalid data frame accesses (e.g., accessing a column removed by a previous operation). While many reported issues were false positives due to unsupported edge cases (e.g., placeholders in pipes), the 40 scripts represent potential real-world bugs.
- Performance: The average total runtime per script was 826 ms (median 456 ms), with the shape inference step taking an average of 163 ms. This performance is considered sufficient for interactive use.

Significance and Claims

The paper claims to provide empirical evidence that the shape of data frames can be soundly inferred in real-world R programs using abstract interpretation. The significance lies in:

Static Guarantees: Offering a way to reason about data frame shapes in a dynamic language, potentially preventing runtime errors before execution.
Practical Utility: Demonstrating that the analysis can be applied at scale to real-world research code, identifying concrete shape constraints for a significant portion of operations.
Foundation for Future Tools: The inferred shapes can serve as static contracts for data science code, supporting tasks such as precondition derivation for external inputs, optimization of data transformations, and more precise content analysis.

The authors remain modest regarding the precision of row count inference (often over-approximated due to filtering) and acknowledge limitations in handling user-defined functions and certain dynamic features, framing these as opportunities for future work.