AI, machine learning and deep learning · Advanced

Meta-programs

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

Meta-programs in Prolog manipulate object-level clauses by treating logical constructs like ':-' as both predicates and functors, enabling the creation of meta-interpreters that simulate logical reasoning. These programs operate on two levels: the object-level where clauses are defined, and the meta-level where clauses are processed as data structures. The implementation often requires handling unification and substitution to support variables, moving from simple propositional simulation to full clause interpretation.

Intuition

Think of a meta-program as a program that treats other programs as data. In Prolog, the operator ':-' is dual-purpose: it defines rules on the object-level but acts as a functor representing a term on the meta-level. This allows a meta-interpreter to recursively break down goals, simulating logical deduction by checking if a goal matches a rule head, a conjunction, or an assumption. When variables are introduced, the interpreter must explicitly manage unification and substitution to handle the most general unifier (MGU), distinguishing meta-predicates (which take clauses as arguments) from higher-order predicates (which take predicates as arguments).

Key equations

Head:−Body
(1)

A clause represented as a term:-(Head,Body) in Prolog

derive(ifAssumptionsthenGoal)
(2)

A meta-predicate clause that derives a goal from assumptions

prove((Goal1,Goal2))
(3)

A clause in the meta-interpreter that handles conjunctions by proving Goal1 and Goal2

Derivation

  1. 1. Identify the dual nature of the ':-' operator, which serves as both a predicate for rule definition and a functor for term representation.
  2. 2. Define the meta-interpreter's recursive structure: check if the goal is an assumption, a conjunction, or matches a rule head.
  3. 3. Use the built-in 'clause(H,B)' predicate to unify the goal with the head of a clause in the database.
  4. 4. If the goal is a conjunction, recursively prove each conjunct separately.
  5. 5. For clauses with variables, incorporate unification and substitution mechanisms to handle the most general unifier (MGU).
  6. 6. Handle pragmatic issues by ordering clauses and using cuts to ensure built-in predicates like 'true' are processed before database queries.

Worked example

Problem

Explain why calling 'clause(true, B)' might cause issues in a meta-interpreter and how to fix it.

  1. 1. Recognize that 'true' is a built-in predicate in Prolog.
  2. 2. Understand that calling 'clause' with 'true' as the first argument can lead to interpreter problems because it is not a user-defined clause.
  3. 3. To fix this, reorder clauses in the meta-interpreter so that 'true' and conjunctions are handled explicitly before attempting to query the clause database.
  4. 4. Use cuts ('!') to ensure these built-in cases are processed efficiently and do not trigger unnecessary database lookups.

Answer The issue arises because 'true' is a built-in predicate, not a user-defined clause. The fix is to handle 'true' and conjunctions explicitly in the meta-interpreter's clauses, using cuts to prevent database queries for these cases.

Common mistakes

  • Confusing meta-predicates with higher-order predicates: meta-predicates take object-level clauses as arguments, while higher-order predicates take lower-order predicates.
  • Calling 'clause' with 'true' or conjunctions as the first argument can cause problems in some Prolog interpreters because these are built-in predicates.
  • Assuming 'setof' is more efficient than 'bagof': 'setof' is slightly less efficient because it sorts and removes duplicates.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

This is a text lesson: it has no animation code yet.

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.