A language for describing concepts as programs

Claude Sammut, Brian CohenLecture Notes in Computer Science 1980 · DOI

In the late 1970s, the field of Artificial Intelligence was grappling with a fundamental question: How can a machine not only recognize a pattern but also understand it deeply enough to recreate it? This paper, presented at a 1979 symposium in Sydney, offers a fascinating look at an early attempt to bridge the gap between pattern recognition and functional programming.

TL;DR

This paper introduces a logic-based language where "concepts" (like a binary number or the maximum value in a list) are defined as executable programs. By using a sophisticated backtracking and queuing system, the authors demonstrate how a system can move beyond mere recognition to construct new objects that satisfy learned logical constraints.

What Problem Does This Paper Address?

In 1979, "structural description languages" were primarily used for pattern recognition—telling a computer how to identify a specific object. However, these were often one-way streets. If you taught a computer what a "box" looked like, it couldn't necessarily use that knowledge to "build" a box or use the concept of a box in a broader task.

The authors, Sammut and Cohen, identified a gap: the need for a language that treats a concept description as a program. They wanted a system where a learning algorithm (like Cohen’s CONFUCIUS) could output a logical function that serves two purposes:

  1. Recognition: Does object $X$ fit concept $Y$?
  2. Generation: Create an object $X$ that satisfies the requirements of concept $Y$.

Methods

The authors developed a compiler/interpreter based on a form of predicate logic. The language includes several key technical features:

  • Recursive Definitions: Unlike many description languages of the era, this language treats concepts as recursive functions. For example, a "binary number" is defined recursively as a head (another number) and a tail (a digit).
  • Quantified Variables: It supports existential quantifiers ($\exists x$). To handle the "infinite search space" problem usually associated with quantifiers, the system attempts to construct the variable rather than searching for it.
  • Goal-Directed Queuing System: Execution is managed by two queues:
  • Ready Queue: Stores new goals (logical expressions) to be attempted.
  • Conflict Queue: If two goals conflict (e.g., one goal sets $x=0$ and another requires $x=1$), the system suspends the current path and moves the offending goals here.
  • Backtracking: When a conflict is found, the system "undoes" previous assignments and tries alternative branches of the logic, similar to the execution model of PROLOG.

Datasets

As was common in 1979 AI research, the paper does not use large-scale modern datasets. Instead, it utilizes illustrative toy domains to prove the logic:

  • Binary Strings: Defining the concept of a "number" as a sequence of 1s and 0s.
  • Integer Lists: Defining the concept of a "maximum" value within a list.
  • Physical Objects: Describing a "box" via property/value pairs (shape: cube, colour: red).
  • Arithmetic: Defining the concept of a "sum" ($x + y = z$).

Key Insights and Ideas

  • Equality as Assignment: One of the most powerful "aha" moments in the paper is the treatment of the equals sign. If a variable is already defined, = acts as a boolean test. If the variable is undefined, = acts as an assignment. This allows the same code to be used for both checking and creating data.
  • The "Reverse" of Learning: The authors argue that execution is simply the reverse of the learning process. Learning goes from instances $\rightarrow$ description, while execution goes from description $\rightarrow$ instance.
  • Goal-Directed Programming: By telling the system what to do (the goal) rather than how to do it (the procedure), the interpreter gains the flexibility to solve problems in ways the programmer might not have explicitly mapped out.

Key Results

The paper provides a qualitative proof-of-concept for Automatic Program Synthesis.

  • Recursive Success: The system successfully parses and generates recursive structures like binary strings.
  • Logic over Procedure: The authors demonstrate that even if the logical statements are written in an "inefficient" order, the backtracking and queuing system can eventually find the correct solution (though they admit this affects performance).
  • Extensibility: They show that once a concept like sum is learned, it can be used as a primitive in more complex concepts, effectively allowing the language to "grow" its own library of functions.

Limitations and Future Work

  • Efficiency: The authors acknowledge that while the logic of a program might be order-independent, the efficiency of the interpreter is highly dependent on the order of expressions—a problem that still plagues logic programming today.
  • Tabula Rasa Start: The system starts with zero knowledge (not even basic integers). While this proves the power of the language, it makes the initial "bootstrapping" phase of learning very difficult.
  • Physical Integration: The paper concludes by suggesting that these generated "objects" could eventually describe robot movements, allowing a high-level concept (like "move the block") to be translated into real-world mechanical actions.

This summary is based on the 1979 paper "A Language for Describing Concepts as Programs" from the University of New South Wales.

Summary updated

BibTeX
@inproceedings{sammut1980language,
  author = {Claude Sammut and Brian Cohen},
  title = {{A language for describing concepts as programs}},
  booktitle = {Lecture Notes in Computer Science},
  year = {1980},
  doi = {10.1007/3-540-09745-7\_8},
}
Figure