Contents

1. Definitions
2. Building a Tiny Prolog in Python
   1. Variables
   2. Predicates
   3. Goals
   4. Lists
   5. Environment
   6. Unification
   7. Resolution
3. References
   1. Artifacts

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

TLDR; This tutorial is an implementation of a toy prolog interpreter in Python. It is based on an earlier implementation here that has since disappeared.

Definitions

For this post, we use the following terms:

• A fact is a statement that is unconditionally true. For example, man(adam). asserts that Adam is a man.
• A rule is a conditional statement that defines when something holds. For example, father(P, C) :- man(P), parent(P, C). states that P is a father of C if P is a man and P is a parent of C.
• A query (or goal sequence) is a question posed to the system, asking for values of variables that make a statement true. For example, ?- father(X, Y). asks for all pairs (X, Y) that satisfy the relation.
• A variable is a placeholder for an unknown value. During execution, variables can be bound to constants or other variables.
• A constant is a literal value such as a number or string (e.g., "adam", 42).
• A predicate is a named relation, such as man/1 or parent/2. Applying a predicate to arguments produces a goal.
• A goal (or predicate term) is an instance of a predicate applied to arguments, such as man(adam). Prolog execution is the process of trying to satisfy goals.
• A clause is a definition consisting of a head and a body. The head is a goal, and the body is a sequence of subgoals that must hold for the head to be true.
• An environment is a mapping from variables to values (or other variables) that records substitutions created during unification.
• Unification is the process of making two terms equal by finding consistent bindings for variables. For example, unifying X with "adam" binds X to "adam".
• Dereferencing means following variable bindings in the environment until reaching either a concrete value or an unbound variable.
• Resolution is the inference mechanism of Prolog: repeatedly trying to satisfy goals by unifying them with predicate definitions and recursively solving subgoals.
• Backtracking is the process of undoing variable bindings and trying alternative clauses when a goal cannot be satisfied.

Building a Tiny Prolog in Python

This implementation is based on an earlier implementation in Python2 here. The effort here is to update it for Python3, and to serve as a reference for future. The explanations are partial, and will be completed at a later point.

Prolog is a language designed around first-order predicate logic ¹. Instead of writing explicit algorithms, you declare facts and rules, and Prolog automatically searches for values that satisfy them. For example:

man(adam).
parent(adam, cain).
father(P, C) :- man(P), parent(P, C).

means that Adam is a man, Adam is the parent of Cain, and anyone who is both a man and a parent is a father. We will next build a very small Prolog engine in Python. Note that our implementation is very simple, and does not implement advanced concepts such as CUT or the WAM virtual machine. We next start with implementing the basic prolog concepts in Python.

Variables

In Prolog, variables stand for unknown values that the system will try to assign during computation. For example, one may query for man(X), and the X is represented by Var.

Using it

Predicates

A predicate represents a relation, such as man(X) or parent(X,Y). A predicate has a name and may have definitions (facts or rules). We model this using the Pred class.

Due to limitations of adapting Prolog semantics to Python’s semantics, we need to declare a predicate before we can attach any definitions to it. This is how we can delcare a predicate

Goals

A goal is a predicate applied to arguments, e.g., man(adam) or parent(X,Y). Goals can also be used to define clauses by associating them with other goals. The essential idea is that given a predicate goal, the prolog interpreter tries to find the subgoals that when solved, will make the current goal succeed. We will see this later in unify().

Note: Here, we represent clauses with <<. That is,

man('adam') << ()

This is how we define a goal. We leave the testing until we have defined Cons.

Lists

Prolog programs often use list-like structures. Here we represent them with a Lisp-style Cons cell.

Let us test it out

We update our Var with ** to stand in for list construction by appending a term to the beginning of the list That is, cons(term, list) same as : in other languages.

Let us test it out

The helper to_list converts Python sequences into this linked-list form.

Let us test the complete functionality.

Environment

Prolog variables don’t store values directly. Instead, an environment keeps track of bindings. Each variable may be associated with a term and the environment where it was bound. This allows variables to reference other variables until eventually grounded.

Let us test the complete functionality.

Unification

The heart of Prolog is unification, which tries to make two terms equal by binding variables as necessary. The unify function handles different cases: variable-variable, variable-term, and term-term.

Resolution

Finally, we need to solve queries. Resolution works by trying to match goals against predicate definitions, applying unification, and recursively resolving subgoals. Python’s generators make it natural to model Prolog’s backtracking search.

We also define a CallbackEnv to allow us to to make simple function calls.

We also define a convenience method query that resovles the goals.

variables, which allow us to define Vars

and predicates, which allow us to define predicates

Now, let us test all these out. We first define a few variables and predicates, which are needed to ensure that we can add clauses to predicates.

Next, we construct a simple library. Let us define our predicates.

Predicates for writing.

A few more predicates for list operations.

Let us try writing a merge sort.

Let us test it out.

A few more tests. First membership.

Appending to a list

Reversing a list

Takeout

Subset

A few more predicates. We also define our digits.

Using definite clause grammars.

Another way to use query.

References

Artifacts

The runnable Python source for this notebook is available here.