Lists are a convenient and concise way of representing knowledge that might otherwise need several clauses, one for each fact. PROLOG has special syntax to create and handle lists. Recursion is used to handle the loop needed to process the elements.

Lists


  • simple list syntax

  • rather than have separate facts such as rainbow(red). rainbow(green). rainbow(blue). and so on, a list of colours of the rainbow could be represented as:
     rainbow([red, green, blue, indigo, violet]).
  • so rainbow has one argument placed within the () ; it is a single list of colours, the list items are encloded in [].

  • the basic syntax of the list is this:
     listname([element1, element2, element3, ..., elementN]).
  • notice that [] represents the empty list, a proper list but with no elements.

  • [Head|Tail] query

  • PROLOG can treat a list as being made up from a head and a tail, written like this [Head|Tail].
  • The vertical bar : | has a special meaning when used in a list, it divides a list into a single first item called the Head and then the Tail which is the remainder of the list after the head has been removed. Notice that the Head is an element but the Tail is a list.
  • This query:
    • [X|T] = [a,b,c,d,e,f].
  • produces the result:
    • done.
    • [X|T] = [a,b,c,d,e,f]
    • X = a
    • T = [b,c,d,e,f]
    • yes
  • So the query means: what item would X be and what list would T be if the list [a,b,c,d,e,f]. was divided up as head and tail?
  • Try the query: [X|T] = [a].



  • query to get first colour in the rainbow list
      rainbow([Colour1|Tail]).
  • Colour is a variable for one item, but Tail is a variable for a list



  • basic syntax of query
      listname([Element|List_tail]).

  • membership (recursive rule pair)

  • this is a recursive rule that allows a query to check if a given item is a member of a list (NB code in SCHOLAR is wrong)
  • To use membership, you should create a knowledge base with these two rules:
      member(X, [X|Tail]).
      member(X,[Head|Tail]) :- member(X,Tail).
  1. a fact
    • an item X is a member of the list if it is the first element of the list,
    • eg member(one, [one|[two, three, four, five]]) where X would be the element one and Tail would be the list [two, three, four, five]
  2. a recursive rule
    • item X is a member of a list (which is made up of a head element and a tail list), if item X is a member of the Tail (which is a list)
    • eg member(two, [one |[ two, three, four, five]]) if member(two , [ two, three, four, five]). and this will match fact 1.
    • member(five, [one, two, three, four, five]). would require several recursive loops ending with member(five, [five,[]]). matching fact 1 where X is five and T is the empty list.

SQA style exercise

  • SQA question A

  • Here is the representation of some EU countries
    • list [spain, italy, france, belgium].
  • (a) What would be the result of the following queries?
    • (i) ?member(brazil, [spain, italy, france, belgium]). (1 mark)
  • this is easy! when any prolog query fails, the result is ...
  • (ii) ?member(X, [spain, italy, france, belgium]). (2 marks)
  • this is a little more work! there is more than one solution, remember what JLog does when you click retry? ...
  • (b) Explain how Prolog would use both parts of the membership rule to solve the query:
    • ?member(belgium, [spain, italy, france, belgium]). (5 marks)
  • this is harder! you have to show how the two clauses of the recursive membership rule work together, every time clause 2 is used a new subgoal must be solved, the list gets shorter as the Head is removed. You don't need to do a full trace. Describe what clause Prolog is trying to match, what the result is and what the next step is, you should also detail the changes to the list.

  • SQA question B

  • A language translation system stores the words of each sentence as a Prolog list, for example: [a, dance, in, the, dark, every, monday].
  • (a) List membership is defined using two clauses. The first clause is the fact member(X, [X|Tail]). The second clause is a rule.
    • (i) Write the second clause required to define list membership. (2 marks)
  • You need to remember the two clauses of the membership rule, the second clause is the one about the Head and the Tail, it is the recursive part.
  • (ii) The following query could be used by the system to check whether the word “dance” is present in a sentence:
    • ?member(blue, [a, dance, in, the, dark, every, monday]).
  • Describe how Prolog would evaluate this query. (3 marks)
  • You don't need to write out a complete trace, this is like part b of question A above.


PROLOG recursion


  • Recursion is needed for list membership and also for inheritance as shown in semantic nets and frames.


concatentation

>
  • (concatentation is the joining of two lists; you don't need to know this construct though it is covered in SCHOLAR)
  • rules for concatenation
    % concat(List1, List2, Concat_List1_List2):
    % Concat_List1_List2 is the concatenation of List1 & List2
 
      concat([], List2, List2).
 
      concat([Item | Tail1], List2, [Item | Concat_Tail1_List2]) :-
                                                                concat(Tail1, List2, Concat_Tail1_List2).
  • concat([], List2, List2). is a fact not a rule, it will evaluate to true when a query is looking for a match such as concat([], [one, two], [one, two]).
  • the second part is a rule, it means


Summary

  • >


links


return to Knowledge representation (cAH)



This page has been edited 1 times. The last modification was made by - deborahkennedy deborahkennedy on May 29, 2012 7:11 am