Abstract
Inductive Logic Programming (ILP) aims to learn logical rules from examples, but learning complex recursive programs remains a significant challenge. This paper introduces STEVIE, a system that automatically discovers higher-order abstractions—such as map, filter, and fold—by refactoring first-order logic programs. By treating abstraction discovery as an optimal compression problem, STEVIE enhances both the accuracy and efficiency of ILP systems while enabling cross-domain knowledge transfer.
Introduction
A major hurdle in ILP is the "Higher-Order Refactoring Problem": the difficulty of automatically identifying reusable patterns within existing code. While humans frequently use higher-order functions to simplify complex logic, ILP systems have traditionally relied on manual provision of these abstractions. STEVIE bridges this gap by automatically identifying these patterns, allowing the system to learn more effectively by searching a reduced space of higher-order templates rather than verbose first-order rules.
The STEVIE System
STEVIE operates in two primary stages:
- Abstraction Generation: The system generalizes first-order programs by replacing specific predicate symbols with higher-order variables, creating a library of potential templates.
- Optimal Compression: The selection of useful abstractions is formulated as a Constraint Optimization Problem (COP). Using Google's OR-tools CP-SAT solver, STEVIE identifies the subset of abstractions that maximizes the compression of the original program. To ensure quality, the system incorporates a complexity penalty that discourages the creation of overly generic or inefficient abstractions.
Experimental Results
The researchers evaluated STEVIE across 176 recursive program synthesis tasks and 35 transfer tasks spanning domains such as Chess, ASCII art, and robotics.
Performance and Efficiency
STEVIE demonstrated a significant performance boost, improving predictive accuracy by 27% compared to standard baselines. Furthermore, the system reduced learning times by 47% by enabling the generation of more concise solutions. On average, refactoring reduced program length from 8 literals to just 4.
Scalability and Transfer
A key strength of STEVIE is its ability to capture universal computational patterns. Abstractions discovered in one domain, such as string manipulation, were successfully reused to solve problems in entirely different domains like Chess. However, the system faces a scalability bottleneck; as program complexity increases, the refactoring time grows exponentially, particularly for programs exceeding 460 literals.
Conclusion and Future Work
STEVIE represents a significant step forward in automated program synthesis by demonstrating that higher-order abstractions can be discovered through optimal compression. Future work will focus on addressing scalability through parallelized solvers and refining type inference to further enhance the robustness of cross-domain knowledge transfer.
Summary updated