CP2003 - Answer to tutorial 13

Prolog and Functional Programming

1. Define the relations predecessor, grandparent and grandchild using the parent relation.

   predecessor

    
       predecessor(X, Z):- 
               parent(X, Z).
   
       predecessor(X, Z):-
               parent(X, Y),
               predecessor(Y, Z).
   

   grandparent

       grandparent(X, Z):-
               parent(X, Y),
               parent(Y, Z).
   

   grandchild

       grandchild(X, Z):-
               parent(Y, X),
               parent(Z, Y).
   

   
   

   ---

   
   
2. Translate the following statements into Prolog rules: (a) two people are relatives if one is a predecessor of the other, (b) two people are relatives if they have a common predecessor, (c) two people are relatives if they have a common successor.

   (a)

       relatives(X, Y):-
               predecessor(X, Y).
   
       relatives(X, Y):-
               predecessor(Y, X).
   

   (b)

       relatives(X, Y):-
               predecessor(Z, X),
               predecessor(Z, Y).
   

   (c)

       relatives(X, Y):-
               predecessor(X, Z),
               predecessor(Y, Z).
   

   
   

   ---

   
   
3. Define the relation

    
        conc(L2, L2, L3)
   

   so that L1 and L2 are two lists and L3 is their concatenation. For example:

   ?- conc([a,b,c], [1,2,3,e], List). L = [a,b,c,1,2,3,e]

       conc([], List, List).
       conc([X | Tail], L2, [X | BigTail]):-
           conc(Tail, L2, BigTail).
   

   
   

   ---

   
   
4. Define the relation

        del(X, L1, L2)
   

   so that X is an atom and deleting X from list L1 gives list L2. For example:

   ?- del(a, [a,b,a,a], L).
   
   L = [b,a,a];
   
   L = [a,b,a];
   
   L = [a,b,a];
   
   no
   

        del(X, [X | Tail], Tail).
        del(X, [Y | Tail], [Y | ShortTail]):-
              del(X, Tail, ShortTail).
   

   
   

   ---

   
   
5. Explain the terms first-order function and high-order function.

   A function whose parameters and results are all nonfunctional is called is called a first-order function.

   A function that has a functional parameter or result is called a higher-order function.
   

   ---

   
   
6. Discuss efficieny/inefficiency of functional programming language.
   Functional languages have a reputation for inefficiency. There are several apparent reasons why this might be so:
   • Since functions are first-class values, local data must be allocated on the heap, and deallocated automatically by the implementation. This is in order to avoid dangling references.
   • Lazy evaluation implies that every time a function argument is used, and every time a component is selected from a composite value, it must be checked in case it turns out to be an unevaluated expression. Such checks are unnecessary in languages with eager evaluation (including all imperative languages).
   • The preferred functional programming style uses many intermediate composite values.

   The following arguments indicate that things are not quite what they seem.

   • Heap management techniques are improving rapidly, and allocating all data on the heap is not real inefficient.
   • Early implementations of lazy evaluation were expensive. Recent ones are much less so. Moreover, optimizing compilers can generate improved code in many cases. For example, if a function is shown to be strict (a call to a function can be evaluated only if its argument can be evaluated), then its argument can safely be evaluated eagerly.
   • Intermediate composite values can often be eliminated by program transformation, and the transformation involved are easy enough to be done by optimizing compilers.

   
   

   ---