A Program Model and Knowledge Base for Computer Aided Program Synthesis

Richard J. WoodAAAI 1980

Introduction

Originally presented at the inaugural AAAI conference in 1980, Richard J. Wood’s work on the Interactive Program Synthesizer (IPS) represents a foundational moment in the history of artificial intelligence and software engineering. During the era of "Good Old Fashioned AI" (GOFAI), Wood proposed a shift in how we view automated programming: moving away from simple compilers toward an active consultant model. In this paradigm, the computer acts as a collaborative partner that assists a human expert in bridging the gap between high-level conceptual requirements and low-level executable code.

The Problem: The Synthesis Gap

By 1980, the field of program synthesis—generating code automatically from specifications—faced a significant scaling problem. As software requirements grew in complexity, existing automated techniques struggled to manage the intricate relationships between different parts of a program.

Wood identified a fundamental disconnect in the software development lifecycle. On one side is the client (the domain expert), who understands the problem requirements but lacks the technical expertise to translate them into efficient code. On the other side is the consultant (the programmer), who possesses the technical knowledge but requires specific, often missing, details from the client to proceed. Wood’s IPS was designed to automate this consultant role, creating a system capable of assimilating information, querying the user for missing specifications, and maintaining a consistent internal model of the software design.

The IPS Architecture

The Interactive Program Synthesizer relies on two sophisticated components to manage the synthesis process: a dynamic Program Model and a structured Knowledge Base.

1. The Program Model (Semantic Network)

IPS represents the evolving program as a semantic network where nodes represent domain objects (e.g., a "screen") or operations (e.g., "clear"). The intelligence of the system lies in the links between these nodes, categorized into four distinct types:

  • User-Driven Links (*DEF and *REF): Definition and Refinement links represent explicit decisions made by the user.
  • System-Driven Links (*REP and *RED): Representation and Reduction links represent inferences made by the IPS based on its internal programming knowledge.

This distinction allows the system to track the origin of every design decision, a process known as justification tracking.

2. The Knowledge Base (Frame System)

To support these inferences, IPS utilizes a hierarchical frame system to store general programming knowledge. When a user provides a high-level description—for instance, describing a screen as a "40 by 86 byte array"—the system retrieves a "prototypical 2D array frame." This frame contains default information about indexing and storage, and it triggers specific queries to the user, such as asking whether the array size is fixed or dynamic.

Managing Consistency and Contradictions

A core strength of the IPS is its ability to handle "inimical" or contradictory states. Because the system tracks the justification for every assertion, it can resolve conflicts intelligently:

  • If a system-generated inference (*RED) causes a conflict with a new requirement, the system can automatically retract that inference and seek an alternative path.
  • If a user-defined decision (*REF) causes the conflict, the system identifies the contradiction and asks the user to restate their goal or modify their requirements.

This collaborative dialogue ensures that the program remains internally consistent throughout the design process.

Implementation and Case Study

While modern AI relies on massive datasets, IPS was evaluated through a specific architectural demonstration in the domain of assembly language programming for microprocessors. The authors tasked the system with building a software package to manage a video display buffer.

The system demonstrated its utility by transforming a simple English sentence—"The screen is thought of as a 40 by 86 byte array"—into a structured model. IPS identified the "screen" as an object, instantiated the corresponding array frame, and automatically prepared to handle complex operations like "clear the screen" by refining them into "store a blank in every position" using its internal reduction rules.

Conclusion and Legacy

Though the initial implementation was limited by the Natural Language Processing (NLP) capabilities of the time—requiring some hand-translation of English into model functions—the conceptual framework of IPS was ahead of its time. By emphasizing knowledge representation and the client-consultant paradigm, Wood’s work laid the groundwork for modern IDE features such as refactoring tools, automated linting, and contemporary AI-driven coding assistants. It remains a testament to the idea that programming is not merely about syntax, but about the structured management of knowledge and design intent.

Summary updated

BibTeX
@inproceedings{wood1980program,
  author = {Richard J. Wood},
  title = {{A Program Model and Knowledge Base for Computer Aided Program Synthesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure