The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

1. ^(s) Assume given a set of facts of the form father(name1,name2) (name1 is the father of name2).
   1. Define a predicate brother(X,Y) which holds iff X and Y are brothers.
   2. Define a predicate cousin(X,Y) which holds iff X and Y are cousins.
   3. Define a predicate grandson(X,Y) which holds iff X is a grandson of Y.
   4. Define a predicate descendent(X,Y) which holds iff X is a descendent of Y.
   5. Consider the following genealogical tree:

         father(a,b).                   
         father(a,c).
         father(b,d).
         father(b,e).
         father(c,f).
      

      whose graphical representation is:

              a
             / \
            b   c
           / \  |
          d   e f
      

      Say which answers, and in which order, are generated by your definitions for the queries

       
         ?- brother(X,Y).
         ?- cousin(X,Y).
         ?- grandson(X,Y).
         ?- descendent(X,Y).
      

      Justify your answers by drawing the SLD-tree (akas Prolog search tree) for each query, at least schematically.
2. ^(s) Define a predicate reverse(L,K) which holds if and only if the list K is the reverse of the list L.
3. ^(s) Consider a representation of sets as lists. Define the following predicates:
   1. member(X,L), which holds iff the element X occurs in L.
   2. subset(L,K), which holds iff L is a subset of K.
   3. disjoint(L,K), which holds iff L and K are disjoint (i.e. they have no elements in common).
   4. union(L,K,M), which holds iff M is the union of L and K.
   5. intersection(L,K,M), which holds iff M is the intersection of L and K.
   6. difference(L,K,M), which holds iff M is the difference of L and K.
   Note that the solution to these exercises depends on the way you decide to represent sets. There are various possibilities:
   • lists with possible repetitions of the same element
   • lists without repetitions
   • (in case of lists of integers) ordered lists
   For each of these representation, give your solution to the above problems.
4. ^(s) Define a predicate length(L,N) which holds iff N is the length of the list L.
5. ^(s) Define a predicate occurrences(X,L,N) which holds iff the element X occurs N times in the list L.
6. ^(s) Define a predicate occurs(L,N,X) which holds iff X is the element occurring in position N of the list L.
7. ^(s) Define a predicate sumlist(L,N) which, given a list of integers L, returns the sum N of all the elements of L.
8. ^(s) Define a predicate add_up_list(L,K) which, given a list of integers L, returns a list of integers in which each element is the sum of all the elements in L up to the same position. Example:

      ?- add_up_list([1,2,3,4],K).
         K = [1,3,6,10];
         no
   

9. ^(s) Define a predicate quicksort(L,K) which, given a list of integers L, returns an ordered list K obtained from L with the method of quicksort.
10. ^(s) Define a predicate merge(L,K,M) which, given two ordered lists of integers L and K, returns an ordered list M containing all the elements of L and K.
11. ^(s) Consider a representation of binary trees as terms, as follows

       emptybt           the empty binary tree
       consbt(N,T1,T2)   the binary tree with root N and left and right subtrees T1 and T2
    

    1. Define a predicate preorder(T,L) which holds iff L is the list of nodes produced by the preorder traversal of the binary tree T.
    2. Define a predicate search_tree(L,T) which, given a list of integers L, returns a balanced search-tree T containing the elements of L.
12. ^(s) A directed graph can be represented in Prolog by listing the arcs among the nodes, as a set of facts (clauses with empty body). For instance, the clause

       arc(a,b).
    

    would represent the existence of an arc going from the node a to the node b.
    1. Define in Prolog a predicate path(X,Y) which holds iff there is an (acyclic) path from the node X to the node Y. Beware of loops: the graph may contain cycles, but your program should avoid looping on them.
    2. Enrich the previous program so to return not only the answer yes/no, but also, in case of success, the actual path represented as a list of nodes. Namely, define a predicate path(X,Y,P) which holds iff P is an (acyclic) path from the node X to the node Y. In case there is more than one acyclic path, the program should generate all of them.
    3. Consider the following graph:

          arc(a,b).
          arc(a,c).
          arc(b,c).
          arc(b,d).
          arc(c,d).
       

       What answers are given for the goal ?- path(a,d,P) by your solution to the last point? Justify your answer by drawing the SLD-tree (akas Prolog search tree), at least schematically.
13. Consider the following grammar for types of a subset of ML (mini ML):

       Type  ::= Tterm | Tterm -> Type
       Tterm ::= Tfact | Tterm * Tfact
       Tfact ::= Tvar | (Type)
       Tvar  ::= ' Name
    

    1. Define in Prolog a predicate parse(L) which holds iff L is a list of tokens representing a legal type expression, according to this grammar.
    2. Define a possible representation of the parse trees (abstract syntax trees) for the language generated by this grammar.
    3. Extend previous predicate with an additional argument T which represents the parse tree generated by parsing the list of tokens. Namely, define a predicate parser(L,T) which holds iff the list of tokens L can be derived by the previous grammar, and the term T represents the corresponding parse tree. Note: by "parse tree", here, we mean the abstract syntax tree.
14. Consider the following grammar for expressions of a subset of ML (mini ML):

       Exp ::= Ide                         (identifier)
             | (Exp Exp)                   (application)
             | fn Ide => Exp               (abstraction)
             | fn (Ide,Ide) => Exp         (abs. on pair)
             | (Exp,Exp)                   (pair)
    

    1. Define a possible representation of the parse trees (abstract syntax trees) for the language generated by this grammar.
    2. Define a predicate type(E,T) which holds iff the expression E has type T. You can assume that both E and T are represented as parse trees.