SISP/1: An Interactive System Able to Synthesize Functions from Examples

Jean-Pierre Jouannaud, Gérard D. Guiho, Jean-Pierre Treuil

Published in the late 1970s, SISP/1 represents a foundational milestone in Program Synthesis—the field dedicated to enabling computers to generate their own source code. While modern approaches often leverage Large Language Models (LLMs), SISP/1 utilized a structured, algebraic framework to infer recursive LISP functions from input-output examples.

The Challenge of Automatic Programming

In the 1970s, "Automatic Programming from Examples" was a burgeoning area of research. The contemporary state-of-the-art, a system called THESYS, suffered from several rigid limitations:

  • Fragility: It required perfectly curated examples that explicitly included the base case (stop condition) of the recursion.
  • Simplicity: It was restricted to a single iterative level of recursion.
  • Monolithic Nature: It lacked the ability to decompose complex problems into manageable sub-tasks.

SISP/1 was designed to overcome these hurdles through an interactive "dialogue" between the system and a user (the "Professor"), allowing it to discover recursive structures and base cases even from incomplete initial data.

Methodology: Lattices and Interaction

SISP/1 operates by analyzing the relationship between an input list and its transformed output. Its methodology rests on three pillars:

  1. Segmentation Patterns and Lattice Construction: The system decomposes strings into prefixes, cores, and suffixes. It then builds a directed graph—a segmentation lattice—where nodes represent data types and edges represent LISP primitives like CAR, CDR, and CONC. The system searches for a functional path through this lattice to transform the input into the desired output.
A segmentation lattice representing functional mappings between input and output components.
  1. Interactive Sub-problem Generation: If a direct mapping cannot be found, SISP/1 generates a simpler partial problem. It prompts the user for an example of this sub-task, solves it, and integrates the result back into the primary function.
  2. Recursive Inference: Rather than relying on fixed-point theorems, SISP/1 identifies recurrence relations within the lattice structure to determine where a function should call itself.

Key Results and Insights

The system was evaluated on classic LISP list manipulation tasks, such as reversing lists, returning every other element (HALF), and complex string repetitions.

  • Automatic Stop-Condition Discovery: One of SISP/1's most significant breakthroughs was its ability to infer base cases (e.g., if x is NIL then NIL) by analyzing sufficiently long examples, rather than requiring them to be explicitly provided.
  • Synthesis of REVERSE: SISP/1 successfully synthesized the REVERSE function using only a single example: ((A B C D) -> (D C B A)). Previous systems required a sequence of examples starting from the empty list.
A synthesized recursive LISP function with an automatically inferred stop condition.
  • Handling Deep Recursion: The system successfully generated a complex string repetition function ((P Q R S) -> (P P Q P Q R P Q R S)) that earlier systems like THESYS could not handle.

Limitations and Legacy

Despite its successes, the authors noted several constraints. The system was sensitive to the order of examples provided by the "Professor" and was limited to structural transformations on lists of atoms, lacking the ability to handle nested structures or logic predicates (like GREATERP).

However, the vision of SISP/1—using a "knowledge database" of previously solved sub-problems—foreshadowed modern library-based synthesis and remains a core concept in the evolution of automated programming.

Summary updated

BibTeX
@inproceedings{jouannaud1977sisp,
  author = {Jean-Pierre Jouannaud and Gérard D. Guiho and Jean-Pierre Treuil},
  title = {{SISP/1: An Interactive System Able to Synthesize Functions from Examples}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure