Introduction
In the field of Artificial Intelligence, a persistent challenge is enabling systems to learn from past successes to solve new, complex problems more efficiently. This 1991 paper explores derivational analogy—the process of reusing reasoning steps from previous solutions—specifically applied to the automation of UNIX shell script creation. The authors demonstrate that this approach can significantly reduce the computational cost of program synthesis.
The Challenge of Program Synthesis
Program synthesis, the automatic generation of code from high-level specifications, is traditionally a search-intensive task. A planner must navigate a vast space of rules and combinations to find a valid solution. While reusing past derivations (analogies) had shown promise in "toy" domains, this research investigates whether the approach scales to more realistic scenarios where the system must autonomously retrieve the correct analog from a large library. The central question is whether the overhead of searching for an analogy is offset by the time saved during the planning phase.
The APU System and Retrieval Heuristics
The researchers utilized a system called APU (Automated Program Understanding/Synthesis), which transforms formal specifications into UNIX shell scripts using a hierarchical planner. At the heart of APU is a Derivation History Library that stores the logical trees of previous solutions.
To identify relevant past solutions, the authors developed four key retrieval heuristics:
- Solution Structure ($H_1$): Matches high-level logic patterns.
- Systematicity ($H_2$): Employs an abstraction hierarchy to find similarities between different object types (e.g., files vs. processes).
- Syntactic Structure ($H_3$): Identifies specific keywords or recursive definitions.
- Argument Abstraction ($H_4$): Measures conceptual distance between objects.
The effectiveness of these heuristics is critical for minimizing "mismatches" and "inferior solutions."
As shown in the data, using the full suite of heuristics ("All") results in the highest retrieval score and the fewest inferior solutions, demonstrating near-human performance in selecting appropriate starting points for new problems.
Experimental Setup and Results
The authors evaluated APU using a custom benchmark of 45 unique UNIX-related problems. A library of 15 problems was used as the initial case base, with the remaining 30 serving as test cases.
The results confirm that derivational analogy provides a substantial performance boost. On average, the time required to synthesize a program was reduced by approximately 50%.
The bar chart illustrates that while the benefit varies by problem, the "With analogy" condition consistently outperforms the "Without analogy" baseline, particularly for more complex tasks. For instance, in Problem 5, the reduction in CPU time is dramatic.
Key Insights
- Abstraction as a Catalyst: By "climbing" an abstraction hierarchy, the system can apply the logic of a file-deletion script to a process-killing task, proving that exact matches are not necessary for successful analogy.
- Graceful Degradation: Even when the system selects a sub-optimal match, the performance penalty is minor compared to the massive gains achieved with a good match.
- Scalability: Retrieval time was found to grow linearly with library size, remaining a small fraction of the total synthesis time even as the library expanded.
Conclusion
This empirical assessment proves that derivational analogy is a viable and highly effective strategy for automating program synthesis in the UNIX domain. By leveraging a library of past reasoning steps and robust retrieval heuristics, systems like APU can achieve significant speedups, moving closer to the efficiency of human experts. Future work may involve refining the abstraction hierarchies to better reflect coding difficulty rather than just conceptual similarity.
Summary updated