Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 40 ยท Data Structures and Parsing

Compound Terms and Structures

Learn how Prolog builds data from compound terms. Use functor/3, arg/3, =.., copy_term/2, pairs and operators, and build a binary search tree out of nested structures.

Prolog has no classes, records or objects. Everything is a term, and the only way to group data is the compound term: a name (the functor) followed by arguments in parentheses, like point(3, 4) or person(ann, 31, london). Because arguments can be any terms, including other compounds, you can build lists, trees, records and expressions out of this single idea.

This lesson shows how to design structures, take them apart and build them at run time with functor/3, arg/3 and =.., and ends with a binary search tree that you can run in a stand-in engine.

Terms, functors and arity

A compound term has a name and an arity, the number of arguments. point(3, 4) is point/2. Two terms with the same name but different arity are unrelated: point(3, 4) and point(3, 4, 5) can never unify.

PROLOG
?- functor(point(3, 4), Name, Arity).
Name = point,
Arity = 2.

?- arg(2, point(3, 4), Y).
Y = 4.

?- functor(T, point, 3).
T = point(_A, _B, _C).

functor/3 works in both directions: take a term apart, or build a skeleton with fresh variables. arg(N, Term, Arg) extracts or checks the N-th argument (counting from 1). Called with an unbound N, it enumerates all arguments on backtracking, which is a quick way to visit every child of a node.

Atoms and numbers are atomic terms with arity zero; functor(foo, N, A) gives N = foo, A = 0. The built-in tests atom/1, number/1, compound/1, var/1, nonvar/1, atomic/1 and callable/1 tell you what kind of term you hold.

Records as structures

A common style is one functor per kind of record, with a fixed argument order:

PROLOG
person(ann, 31, london).
person(bob, 45, paris).

name_of(person(Name, _, _), Name).
age_of(person(_, Age, _), Age).

Pattern matching in the head replaces getter functions. For a record with many fields, or when you need to add fields later, a list of Key-Value pairs (or an assoc, covered later) is easier to evolve:

PROLOG
?- Person = [name-ann, age-31, city-london], member(age-A, Person).
A = 31.

The binary operator - between a key and a value is just a convention: name-ann is the compound term -(name, ann). Library predicates such as pairs_keys_values/3, keysort/2 and list_to_assoc/2 all expect that shape.

Taking terms apart with =..

The "univ" operator =.. converts between a term and a list whose head is the functor:

PROLOG
?- point(3, 4) =.. L.
L = [point, 3, 4].

?- T =.. [area, circle, 5].
T = area(circle, 5).

?- foo =.. L.
L = [foo].

This is how Prolog programs inspect and construct terms generically. A typical use is calling a goal built at run time:

PROLOG
apply_to_all(_, []).
apply_to_all(Name, [X|Xs]) :-
    Goal =.. [Name, X],
    call(Goal),
    apply_to_all(Name, Xs).

SWI-Prolog's call/N adds the extra arguments for you (call(print_item, X)), so =.. is needed less often now, but it remains the tool for inspecting unknown terms, such as walking through an expression tree.

Sharing, copying and variables

Two occurrences of the same variable are one variable. If you want an independent version of a term, use copy_term/2, which renames all its variables:

PROLOG
?- copy_term(f(X, Y, X), C).
C = f(_A, _B, _A).

The copy keeps the sharing pattern (the first and third arguments are still the same variable) but is disconnected from the original. This is what happens to a clause each time it is used. term_variables(T, Vs) lists the distinct variables of a term in order of appearance.

Operators and notation

Many terms are written with operators for readability: X is 2 + 3 is really is(X, +(2, 3)). You can see the canonical form with write_canonical/1, and you can define your own operators with op/3:

PROLOG
:- op(700, xfx, ===>).

rule(a ===> b).

op(Priority, Type, Name) takes a priority (1 to 1200; higher binds looser) and a type: xfx (infix, non-associative), yfx (infix, left-associative), xfy (infix, right-associative), fy, fx (prefix), xf, yf (postfix). Operators only change how terms are read and printed, never what they mean, so use them sparingly, for example in domain-specific rule languages.

A binary search tree

A tree is a term with the shape t(Left, Value, Right) and the atom nil for the empty tree.

flowchart TD
  A["t( , 5, )"] --> B["t( , 3, )"]
  A --> C["t( , 8, )"]

The tree built by inserting 5, 3 and 8. Each node is a term; missing children are nil.

Insertion walks down the tree by comparing the new value with the node's value. In Prolog each case is one clause, selected by head unification and a comparison:

PROLOG
insert(nil, X, t(nil, X, nil)).
insert(t(L, V, R), X, t(L2, V, R)) :- X < V, insert(L, X, L2).
insert(t(L, V, R), X, t(L, V, R2)) :- X > V, insert(R, X, R2).
insert(t(L, V, R), X, t(L, V, R)) :- X =:= V.

inorder(nil, []).
inorder(t(L, V, R), Xs) :-
    inorder(L, As),
    inorder(R, Bs),
    append(As, [V|Bs], Xs).

The first clause says: inserting into an empty tree gives a one-node tree. The next two rebuild the node with one subtree replaced, and the last returns the tree unchanged when the value is already present. The comparison guards make the clauses mutually exclusive. Because nothing is modified in place, insert/3 returns a new tree that shares the untouched parts with the old one.

Python Binary search tree from nested terms (Python stand-in engine)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second query inserts a duplicate 3; the fourth clause leaves the tree unchanged, so inorder/2 returns a sorted list without it. The tree is also a data structure you can search: member_tree/2 would follow the same comparisons and find a value in a number of steps proportional to the tree's height.

Terms as code: functor, arg and univ in Python

The following stand-in shows what functor/3, arg/3 and =.. do to a term, using Python tuples for compounds.

Python functor, arg and univ (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Forgetting that arity is part of the name: point/2 and point/3 are different predicates and different terms.
  • Using a list when a fixed structure would do. Fixed person(Name, Age, City) records are faster to match and clearer to read.
  • Expecting to change a term in place. Terms are immutable; you build a new one (or, rarely, use the destructive setarg/3, which is undone on backtracking).
  • Writing T = point(X, Y) and then calling T.x. SWI-Prolog 7 dicts exist, but they are a separate feature.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does point(3, 4) =.. L give?

    Univ returns a list with the functor first, followed by the arguments.
  2. 2. What is the arity of person(ann, 31, london)?

    Arity is the number of arguments. Atoms like ann have arity 0.
  3. 3. In insert(t(L, V, R), X, t(L2, V, R)) :- X < V, insert(L, X, L2)., what is the role of X < V?

    The comparison makes the clauses mutually exclusive: smaller goes left, larger goes right.
  4. 4. Which call builds a fresh term with three unbound arguments named point?

    functor(T, Name, Arity) with T unbound creates a skeleton with fresh variables.

Summary

  • A compound term is a functor plus arguments; name and arity together identify it.
  • functor/3, arg/3 and =.. take terms apart and build them at run time; copy_term/2 renames variables.
  • Records are compound terms or Key-Value lists; trees are terms like t(Left, Value, Right).
  • Terms are immutable: operations return new terms that share unchanged parts.
  • Operators are notation only; op/3 changes how terms read and print.

Next: findall, bagof and setof