More about Terms

The Anonymous variable

• 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

• 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

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
       

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

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

Tutorial

1. 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 unbound variables, attempt to unify them using the = predicate, otherwise my_unify must fail. Answer
2. Create an example where the lack of "occurs check" in unification causes a problem. Answer
3. 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

• 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.

• 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

• If all arguments are bound then sum must check that the first two add to the third.
• If the first two arguments are bound 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 bound, then sum must perform the subtraction and bind the variable appropriately.
• Otherwise sum must fail.
• prod should perform similarly for multiplication and division.

Lists

• 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.

• 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.

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

• 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

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

• Example : insert

  insert(Element,List,InsertedList):-
      my_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).
   

%-------------------------------------------------------------
%----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]):-
    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).
%-------------------------------------------------------------
 

Tutorial

1. 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
2. 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

• 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).
   

• 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).
   

• 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.

• 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

1. 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]

2. Write a program that generates a sequence of new atoms.