More about Terms

The Anonymous variable

The single underscore variable is called the anonymous variable. It is used when the value of the variable is not cared about.

Example : Anonymous variable

lecturer(olivier,ai).
lecturer(john,pascal).
lecturer(geoff,ai).
lecturer(john,programming).
lecturer(nizam,networks).
lecturer(peter,graphics).
lecturer(geoff,projects).
lecturer(olivier,ppl).
lecturer(john,graphics).

--------------------------------------------------------
?- lecturer(Anyone,_).
yes
Anyone = olivier    ? ;
yes
Anyone = john        ? ;
yes ...

Classifying terms

It is often useful to determine the nature of a term, especially of an instantiated variable.

var(X) checks for unbound variables.
nonvar(X) checks for non-unbound variables
atom(X) checks for atoms
integer(X) checks for integers
atomic(X) checks for integers or atoms.

Unification and instantiation

Unification is the operation that compares two expressions, and, if possible, instantiates (or binds) variables in the expressions so that the two expressions become identical. Before instantiation a variable is unbound, but once instantiated the variable is completely replaced by the term it has been instantiated to.

In unifications, the instantiation of variables is as general as possible, to create a common instance of the two expressions. For example, p(X,a,Z) and p(A,B,B). The most common instance is p(X,a,a), but p(a,a,a) is also a common instance. The rules for unification are :

Functions/predicates unify if their functors/predicate symbols and arities are identical, and their arguments unify.
Variables unify with any term not containing that variable. The variable is instantiated to that term. (The check for the variable in the term is called the occur check, and is not implemented by most Prologs for efficiency reasons. This causes problems in examples such as p(X,X) with p(Y,f(Y)).)

Unification is used between query predicates and clause heads.

The = predicate determines if two expressions are unifiable, and \= the converse.

Example

?- p(a,X,f(Y)) = p(Z,Z,f(b)).
yes
X = a
Y = b
Z = a

Note that the following is not allowed, and will not work. The reason is that it is second order logic.

?-lecturer(geoff,ai) = Job(geoff,ai).
yes
Job = lecturer

== and \==

Check for identical and non-identical expressions.
Distinct variables are not identical, but unified ones are.
Compare these against = and \=

Tutorial

Write a set of clauses with head predicate symbol my_unify, which take two arguments. If the arguments are both atoms, both integers or both variables, attempt to unify them using the = predicate, otherwise my_unify must fail. Answer
Create an example where the lack of "occurs check" in unification causes a problem. Answer
Integers may be represented by functions in Prolog. Zero is represented by 0, one by s(0), two by s(s(0)), etc. Write Prolog clauses to add, subtract, multiply and divide numbers in this representation. For example
```
?- add(s(0),s(s(0)),X).
yes
X = s(s(s(0)))
     
```
Answer

Arithmetic

Evaluation is caused by the is predicate

The RHS of is may contain any of the arithmetic operators +, -, *, /, mod.
The RHS is evaluated, and the result unified with the LHS.
The RHS must be evaluable, i.e., no unbound variables.
Example
```
?- X is 2+3+4.
yes
X = 9
     
```
Note that this is an implementation of an infinite number of clauses.

The arithmetic predicates < > >= =< can be used to compare evaluable arithmetic expressions.

Example: To find the greatest common divisor of X and Y algorithm: If X and Y are equal, then that is the GCD, else find the GCD of the smaller of X and Y, and the absolute of their difference.
```
gcd(X,X,X).

gcd(X,Y,GCD):-
    X < Y,
    Difference is Y - X,
    gcd(X,Difference,GCD).

gcd(X,Y,GCD):-
    gcd(Y,X,GCD).
 
```

Tutorial

Write clauses for sum and prod. sum takes three arguments, the first two being operands, the last being the sum of the first two.

If all arguments are integers then sum must check that the first two add to the third.
If the first two arguments are integers and the last a variable, sum must add the first two and bind the result to the third.
If either of the first two are variables, and the other two are integers, then sum must perform the subtraction and bind the variable appropriately.
Otherwise sum must fail.
prod should perform similarly for multiplication and division.

Answer

Lists

Lists as functions using dot notation.

Lists are a function of two arguments with . as the functor. The first argument is the head and the second argument is the tail of the list.
The head may be anything, the tail must be a list. This means that the elements of a list need not be homogeneous, and can be anything, even lists.
The innermost function has an empty list as its tail. The empty list is written []
This notation is acceptable in Prolog, but is very cumbersome.

List notation, with head and tail

The | functor and [] brackets are an alternative to the dot notation.
[<head>{,<more head>}[|<tail list>]] - i.e. any number of head elements, optionally followed by a | and a tail list, all enclosed in []
This corresponds to a list of the head elements, concatenated to the tail list.

String notation for lists.

Strings of "characters in double quotes" are lists of integers, the integers being the ASCII values of the characters.

Examples of lists, and queries on lists.

Example

numbers([1,2,3,4]).
sentence(the,[cat,sat|[on,the,mat]]).

-----------------------------------------------------------
?- numbers([X|Y]).
yes
X = 1
Y = [2,3,4]

?- numbers([1,Y|Z]).
yes
Y = 2
Z = [3,4]

?- sentence(the,[Noun|Rest]).
yes
Noun = cat
Rest = [sat,on,the,mat]

?- "ABCDEFG" = .(First,.(Second.[Third,Fourth|Rest]))
yes
First = 65,
Second = 66,
Third = 67,
Fourth = 68,
Rest = [69,70,71]

Example : length

my_length([],0).

my_length([_|Tail],Length):-
    my_length(Tail,TailLength),
    Length is TailLength + 1.

Three interpretations

What is the length of L
Does L have this length
What Ls have this length

Example : member
```
my_member(Element,[Element|_]).

my_member(Element,[_|Tail]):-
    my_member(Element,Tail).
 
```
Three interpretations
- Is E and element of L
- What are the elements of L
- What lists have E as an element (a dangerous interpretation with an infinite number of answers)
Example : append
```
my_append([],List,List).

my_append([Head|Tail],List,[Head|TailList]):-
    my_append(Tail,List,TailList).

     
```
Five interpretations
- What is L1 appended to L2
- What must be appended to L1 to get L
- What must be prepended to L2 to get L
- What two lists append to form L
- What two lists append to form another list (infinite number of answers).

Example : select

list_select(Element,[Element|Tail],Tail).

list_select(Element,[Another|Tail],[Another|SelectedTail]):-
    list_select(Element,Tail,SelectedTail).

Example : insert

insert(Element,List,InsertedList):-
    list_select(Element,InsertedList,List).

Example : sublist

sublist(Sublist,List):-
    append(_,Back,List),
    append(Sublist,_,Back).

Example : permutation

permutation([],[]).

permutation([Head|Tail],PermutedList):-
    permutation(Tail,PermutedTail),
    insert(Head,PermutedTail,PermutedList).

An Application: Counting user words

%-------------------------------------------------------------
%----Counts the number of words in some text, and how often
%----each occurs.
%----A list of the form [word(Word,Count), ...] is returned.
count_words(Words):-
%----Read the first word
    read_word(Word),
%----Build the list of words
    count_words(Word,[],Words).
%-------------------------------------------------------------
%----Adds words to a list until exit is reached
%----At exit return the current list
count_words(exit,Words,Words).

%----Otherwise add the word too the list.
count_words(Word,OldWords,Words):-
%----Add the word in the list
    add_word(Word,OldWords,NewWords),
%----Get another word
    read_word(NextWord),
%----Loop
    count_words(NextWord,NewWords,Words).
%-------------------------------------------------------------
%----Adds a word to a list.
%----If the first word in the list already, increment the
%----count
add_word(Word,OldWords,[word(Word,NewCount)|OtherWords]):-
    list_select(word(Word,OldCount),OldWords,OtherWords),
    NewCount is OldCount + 1.

%----If not the first word, then move on down the list
add_word(Word,OldWords,[word(Word,1)|OldWords]).
%-------------------------------------------------------------
%----Read a word from stdin
read_word(Word):-
%----Prompt user
    write('Enter word : '),
    read(Word).
%-------------------------------------------------------------
%----Standard select code
%----Built in Eclipse, so call it something weird
list_select(E,[E|T],T).

list_select(E,[H|T],[H|TT]):-
    list_select(E,T,TT).
%-------------------------------------------------------------

Tutorial

Write clauses for mega_append, which has a list of lists as its first argument and their concatenation (all appended) as the second argument. Answer
Write a program to solve the Towers of Hanoi problem. Your program must generate a list of functions of the form move(FromPeg,ToPeg), returned in the last argument of hanoi(FromPeg,ToPeg,SparePeg,NumberOfDisks,ListOfMoves). Answer

Manipulating Expressions

functor(Term,Functor,Arity)

With the Term instantiated, this is used to find/check the functor and arity of a term.
With the Term uninstantiated and the Functor and Arity instantiated, this is used to build Terms with new variables as arguments.

Example

copy(OldTerm,NewTerm):-
    functor(OldTerm,Functor,Arity),
    functor(NewTerm,Functor,Arity).

arg(Position,Term,Argument)

Always used with the Position and Term instantiated to find/check the Positionth argument of the Term.

Example

write_each_argument(Term):-
    functor(Term,_,Arity),
    write_Nth_argument(Term,1,Arity).

write_Nth_argument(Term,N,Arity):-
    N =< Arity,
    arg(N,Term,Argument),
    write(Argument),
    nl,
    N1 is N + 1,
    write_Nth_argument(Term,N1,Arity).

write_Nth_argument(_,Arity,Arity).

Term =.. List (univ)

Succeeds if the head of List unifies with the functor of the Term, and the tail elements of List unify with the arguments of Term.
If the Term is an atom, the List is a single element list.

Example

?-  f(a,S,d) =.. L.
yes
S = S
L = [f,a,S,d]
 Example
?-  F =.. [f,a,S,d].
yes
S = S
F = f(a,S,d)
 Example
?-  f(a,S,d) =.. [f,a,S,d].
yes
S = S
?-  A =.. S.
no

Example

write_each_argument(Term):-
    Term =.. [_|Arguments],
    write_arguments(Arguments).

write_arguments([]).

write_arguments([Argument|RestOfArguments]):-
    write(Argument),
    nl,
    write_arguments(RestOfArguments).

Useful for building structures and goals. See under call in meta-programming section.

name(Atom,List)

Converts between the Atom and the List of the ASCII values of the characters of the Atom.

Example

concatenate_atoms(Atom1,Atom2,Result):-
    name(Atom1,List1),
    name(Atom2,List2),
    append(List1,List2,ResultList),
    name(Result,ResultList).

Tutorial

Write a program that flattens an expression into a list of atoms, using the =.. predicate, for example:
```
?- flatten(p(X,f(a,b),g(g(g(a)))),Flat).

yes
Flat = [p, X, f, a, b, g, g, g, a]
```
Write a program that generates a sequence of new atoms.