An Automatic Algorithm Designer: An Initial Implementation

Elaine Kant, Allen NewellAAAI 1983

Introduction

In their 1983 seminal work, Elaine Kant and Allen Newell proposed an automated system designed to emulate the cognitive processes of human programmers. Moving away from rigid, rule-heavy transformation systems, their approach integrated data-flow representations with a simulated "mental imagery" space. This allowed the system to design algorithms through successive refinement, symbolic execution, and trial-and-error, mirroring the "protocol analysis" observed in human experts.

The Problem of Automated Synthesis

Early 1980s automated program synthesis faced a dichotomy. Transformation-based systems were often brittle, requiring an exhaustive library of specific rules for every coding nuance. Conversely, formal derivation systems demanded complete, formal specifications—a requirement rarely met in real-world human problem-solving.

Kant and Newell observed that human designers do not rely solely on formal logic. Instead, they sketch ideas, perform mental simulations with concrete examples, and leverage domain-specific intuition (e.g., geometry) to discover algorithmic steps. The authors' implementation sought to bridge this gap by mimicking these human-centric heuristics.

Methodology: Dual Problem Spaces

The system operates across two interconnected "problem spaces":

  1. The Algorithm Space (DFS): Algorithms are represented as data-flow configurations. Rather than traditional code, the system utilizes "components"—such as generate, test, and memory—interconnected via "ports" and "links." These components are represented as frames containing metadata about their function and relationships.
Figure 1: Frame representation of a 'TEST-1' component instance, illustrating the slots for ports and assertions.
  1. The Task-Domain Space: This space handles domain-specific objects, such as points and polygons in computational geometry. Modeled after "imagery simulation," it serves as a symbolic whiteboard where the system can "visualize" the problem. Assertions within this space link algorithmic logic to geometric predicates.
Figure 3: Representation of 'ASSERTION-2', showing a geometric predicate (ON-SIDE) used to define the logic of a test component.

Key Techniques

  • Successive Refinement: Design begins with a high-level "kernel schema" (a solution plan) that is gradually detailed.
  • Symbolic and Test-Case Execution: The system employs abstract symbols to detect general logic errors. When stuck, it generates concrete "test cases" (e.g., specific coordinates) to pinpoint failures.
  • Production System (OPS5): The control structure uses a set of production rules and means-ends analysis to select operators based on the current state-goal disparity.

Evaluation and Task Domains

The system was evaluated using specific tasks rather than modern large-scale datasets:

  • The Subset Test: Finding points on one side of the X-axis.
  • The Convex Hull Problem: Finding the smallest convex polygon enclosing a set of points. This served as a benchmark for "discovery" and complex domain reasoning.

Key Insights

  • Human-Centric Architecture: Parallelizing human reasoning makes the system more flexible and robust than purely formal approaches.
  • The Role of Discovery: By providing a dedicated "imagery" space, the system can "recognize" accidental alignments of facts, facilitating algorithmic discovery.
  • General Operators: The system favors a small set of general-purpose operators (e.g., add-component) over thousands of specific coding rules.
  • Tolerance for Inconsistency: The designer allows for temporary "type mismatches" or errors, assuming they will be resolved during execution phases.

Results and Limitations

The system successfully designed the "subset test" algorithm through 190 production-rule applications, demonstrating a viable integration of frame-based knowledge and OPS5 control structures. It effectively linked abstract logic with domain-specific predicates.

However, several limitations remain. The "mental imagery" model relied on analytic geometry rather than full array-based simulation. Furthermore, the system designs the algorithm (data-flow logic) but does not yet generate executable code in languages like Lisp. Scaling to complex problems like the Convex Hull remains the ultimate test for the system's ability to handle knowledge transfer and genuine discovery.

Summary updated

BibTeX
@inproceedings{kant1983automatic,
  author = {Elaine Kant and Allen Newell},
  title = {{An Automatic Algorithm Designer: An Initial Implementation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}

Loading related content...

Figure