Automatic Goal-Directed Program Transformation

Stephen FickasAAAI 1980

Introduction

In the late 1970s and early 1980s, the field of software engineering explored "Transformational Implementation" (TI) as a method to bridge the gap between high-level specifications and efficient executable code. The vision was to allow developers to write specifications in a high-level language like GIST and then apply a series of formal, correctness-preserving transformations to produce optimized LISP code. However, a significant bottleneck emerged: the manual effort required to prepare code for these transformations. Stephen Fickas’s 1980 work introduces "The Jitterer," a prototype system designed to automate the tedious, low-level code manipulations—termed "jittering"—that often stall the development process.

The Problem: The Bottleneck of Manual Jittering

While the goal of TI was to focus on high-level architectural decisions, developers found themselves bogged down by syntactic minutiae. To apply a "conceptual" transformation, such as merging two loops or shifting a data structure, the program state had to exactly match the transformation's formal preconditions.

In practice, the code rarely matched these requirements perfectly. Developers spent the majority of their time performing "jittering"—trivial but necessary adjustments like commuting adjacent statements, unfolding nested blocks, or renaming variables—simply to get the code into a state where the intended optimization could be applied. This manual "massaging" of code was not only time-consuming and error-prone but also distracted the developer from the primary task of system design.

The Jitterer: System Architecture and Methodology

Fickas proposed an automated Jittering System to bridge the gap between the current program state and the requirements of a high-level transformation. The system architecture utilizes a goal-directed approach to planning, consisting of several key components:

The Differencer

When a user attempts to apply a transformation that fails due to mismatched preconditions, the Differencer compares the current code to the required "goal" state. It produces a formal description of these discrepancies using a specialized goal language known as GL1.

Strategies and Tactics

The system employs a hierarchical planning approach to resolve the differences identified by the Differencer.

  • Strategies: These represent high-level plans to solve specific categories of differences, such as "change-predicate."
  • Tactics: These are the specific sequences of low-level actions, such as "embed" or "extract," used to achieve the strategy's goal.

Backward Chaining and Heuristic Scheduling

The Jitterer works backward from the desired goal state, searching through a library of low-level transformations to find a valid path back to the current program state. To manage the potentially vast search space, a Heuristic Scheduler prioritizes goals based on specific metrics:

  • Path Length: Shorter sequences of transformations are preferred to minimize complexity.
  • Conflict with High-Level Motivation: The system avoids steps that undo the user's broader objectives. For example, if the user is attempting to eliminate loops, the Jitterer will not suggest a path that introduces new ones.
  • Side Effects: The scheduler prefers "clean" transformations that do not unnecessarily disrupt the surrounding code structure.

Key Insights and Contributions

The paper’s primary contribution is the formal taxonomy of transformations, distinguishing between conceptual changes (design decisions) and jittering (syntactic preparation). By identifying jittering as a distinct, automatable class of activity, Fickas provided a roadmap for reducing the manual overhead of formal software development.

Furthermore, the system demonstrates the power of Goal-Directed Search. Rather than applying rules at random, the system uses the specific failures of a desired transformation as a concrete target, turning a general search problem into a focused planning problem. Finally, the work highlights the importance of User Intent as a heuristic, suggesting that automated tools must remain cognizant of the developer's high-level goals to remain useful.

Implementation and Results

The Jitterer was implemented as a prototype using the Hearsay-III knowledge representation language, operating on GIST specifications and LISP-based transformations. While the paper does not provide modern quantitative benchmarks, it successfully demonstrated that program differences could be formally described to trigger automated planning. The system proved that a combination of backward chaining and heuristic scheduling could successfully discover the sequences of low-level transformations that humans previously had to perform manually.

Limitations and Future Directions

As a preliminary system, the Jitterer faced several challenges. The author noted that a simple STRIPS-like approach to solving multiple sub-goals could be inefficient or fail in complex scenarios. Additionally, there was the issue of "acceptable" solutions; the system might find a technically valid sequence of transformations that a human developer would find unreadable or "ugly." Fickas suggested that future iterations should incorporate more interactive guidance, allowing users to provide feedback on the aesthetic or structural quality of the proposed code changes.

Summary updated

BibTeX
@inproceedings{fickas1980automatic,
  author = {Stephen Fickas},
  title = {{Automatic Goal-Directed Program Transformation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}

Loading related content...

Figure