RSynth

RSynth is a small program-synthesis framework for data-wrangling programs in R. It learns an R program that transforms an input dataframe into a desired output dataframe by searching over a context-free grammar, evaluating candidates in R (via Rserve), and optionally pruning or prioritizing the search with simple specs and heuristics.

The code is organized as a staged assignment:

• Core AST, CFG, interpreter, and synthesis scaffolding are in rsync/src/edu/umich/rsyn/base.
• pa0: call the R interpreter to execute a fixed R program in rsync/src/edu/umich/rsyn/pa0.
• pa1: top-down worklist search in rsync/src/edu/umich/rsyn/pa1.
• pa2: search with pruning using simple Z3 specs in rsync/src/edu/umich/rsyn/pa2.
• pa3: priority-queue search with a custom cost heuristic in rsync/src/edu/umich/rsyn/pa3.

Key Components

• CFG-driven search space: rsync/src/edu/umich/rsyn/base/CFG.java, rsync/src/edu/umich/rsyn/base/Production.java
• AST representation and expansion: rsync/src/edu/umich/rsyn/base/AST.java, rsync/src/edu/umich/rsyn/base/ASTNode.java
• R evaluation via Rserve: rsync/src/edu/umich/rsyn/base/Interpreter.java
• Synthesis scaffolds: rsync/src/edu/umich/rsyn/base/Synthesizer.java, rsync/src/edu/umich/rsyn/pa1/Synthesizer1.java, rsync/src/edu/umich/rsyn/pa2/Synthesizer2.java, rsync/src/edu/umich/rsyn/pa3/Synthesizer3.java
• Example tests and drivers: rsync/src/edu/umich/rsyn/pa0/Test1.java, rsync/src/edu/umich/rsyn/pa1/SampleTest.java

Requirements

• Java 8
• Maven
• R with packages: tidyr, dplyr
• Rserve
• Z3 Java bindings (included under rsync/z3)

Setup

From the rsync directory:

1. Start Rserve

make rserve

2. Install the Z3 Java binding into your local Maven repo

make z3

Build and Run

All tasks are defined in rsync/Makefile. Examples:

• pa0 interpreter test

make Test1

• pa1 synthesis search

make Test2

• pa2 synthesis with pruning (uses Z3)

make Test4

• pa3 heuristic search

make Test8

How It Works (High Level)

1. Define a grammar (CFG) of allowed dataframe transformations.
2. Enumerate candidate programs as ASTs.
3. Execute candidates in R via Rserve and compare outputs to the target.
4. Optionally prune partial programs with Z3 specs or prioritize them with a heuristic.

Notes

• Rserve is launched by rsync/server.r. If Rserve is not running, the Java interpreter will fail to connect.
• For Z3-based tasks, the Z3 native library must be discoverable. The Makefile sets LD_LIBRARY_PATH for you in the relevant targets.

Project Files

• Maven config: rsync/pom.xml
• Build/run targets: rsync/Makefile
• Rserve entry point: rsync/server.r