1) To give you an idea of what to expect at the final. The final will contain one exercise for each of the groups of topics (I, II etc.) described in this page.

2) To serve for you as preparation for the final: The exercises in this page are of the same level of difficulty, or slightly higher (and generally longer), than those which will be given in the final. So if you can solve well all of them you have a good chance of doing very well at the final. For several of these exercises, I wrote also the solution here. It is of course recommanded, for your maximum benefit, that you try to solve the exercise yourself and only afterwards look at my solution and compare it with yours.

- Catuscia Palamidessi

1. Consider the grammar for Types of mini ML:

Type ::= TVar |  Type -> Type  |  Type * Type

Show that this grammar is ambiguous by giving two derivation trees for each of the following type expressions:

• alpha -> beta -> gamma
• alpha -> beta * gamma
• alpha * beta * gamma
 
2. Modify the grammar of previous exercise so to obtain a non-ambiguous grammar, enforcing the following properties:
• -> is right associative
• *  has higher priority than  ->
• * is left associative
 
3. Exercise 2.6 in Sethi's book. Note: by "parse tree" Sethi means "derivation tree"

 

1. In C and C++ the concepts of  "expression" and "command" are often confused. For instance, --x  is an expression, in the sense that it returns a result, and also a command, in the sense that it changes the state of  x. Expression whose evaluation might affect the state are called "expressions with side effects", and require special care by the programmer as they cannot be regarded as "pure values". Consider for instance the following (incorrect) definition of the factorial function:

int  fact(int x) { if (x == 0) return 1;
                   else return  fact(--x) * x;
}

a) What is the result returned by the call  fact(3) ?
b) Would the definition be correct if we substitute the command   return fact(--x) * x;    with    { int y = x; return fact(--x) * y; }   ?

2. Exercise 4.2 in Sethi
3. Write a procedure which prints all the prime numbers from 2 to n, where n is a given positive integer. (Note: a number is prime if it cannot be divided by any number except for 1 and itself).

 

1. Consider the following sequence of declarations:

z : integer;
procedure p (x:integer) body

write a  body  for  p  so that the following piece of code

z := 1 ; p(z) ; write(z)

will have all different outcomes in case of pass by value, pass by reference, and pass by value-result.
 

2. Consider the following procedure declaration:

procedure p;
    begin
      x: integer;
      procedure q; x := x+1;
      procedure r; begin x: integer in x := 1; q ; write(x) end
    in
      x:= 2; r
    end

  What is the output produced by calling  p  in
  a) A language with static scope
  b) A language with dynamic scope
 

3. Consider the following procedure declaration in C:

void p() {int x; q = &x; *q = 1; }

where q is a global variable declared as pointer to int and initialized by  q = new int. What output can we expect to be produced by the following piece of code:  *q = 0 ; p() ; printf(*q) ; ?

IV. Exercises on types

1. For each of the following expressions, write its most general type
• fn f => fn g => fn x => f (g x)
• fn f => fn (x,y) => f x
• fn x => fn f => (x, (f x))
 
2. For each of the following  types, write a ML expression having such a type
• 'a -> 'b -> 'a * 'b
• 'a -> 'b -> 'a
• ('a * 'b) -> ('a -> 'c) -> ('c * 'b)
 
3. Define the datatype  'a stack  (stack of elements of the generic type  'a) with operations
• emptystack : 'a stack
• push : 'a * 'a stack  -> 'a stack
• pop : 'a stack  -> 'a stack
• top : 'a stack  -> 'a
• isemptystack : 'a stack  -> bool

Some of these operations can be implemented as constructors and the others as functions. Be careful about choosing the right set of constructors!

V.  Exercises on Functional Programming

1. Write in ML a function which takes in input an ordered list l (possibly with repetitions) and gives as result the list obtained from l  by eliminating all repeated elements.
2. Write in ML a function    maptree : ('a -> 'b) -> 'a btree -> 'b btree which, given a function f : 'a -> 'b, and a binary tree t : 'a btree, gives  as result the tree obtained from t  by replacing each node n  by  f(n).
3. Define the functions
• curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
• uncurry :  ('a -> 'b -> 'c) -> 'a * 'b -> 'c

curry takes a function f of two arguments paired (i.e. defined as f(x,y) = e) and gives back the equivalent curried function (i.e. the function  g such that  g x y = e). uncurry does the reverse, i.e. takes a function like  g and gives back  f.

VI.  Exercises on Logic Programming

1. Assume given a set of facts of the form  father(name1,name2).  Define a predicate   cousins(N1,N2)   which holds if   N1  and  N2  are cousins.
2. Define a predicate subset(S1,S2) which holds if  S1 is a subset of S2 (represented as lists).
3. Define a predicate disjoint(S1,S2) which holds if  S1 and  S2  are disjoint sets (represented as lists).
4. Datatypes can be represented in Prolog using constructors like in ML. For instance, binary trees can be represented by the terms

- emptybt   (empty tree)
- consbt( n, t1, t2)  (tree with root n, left subtree t1, and right subtree t2)

Define a predicate infix_visit(T, L) which holds if L is the list of nodes produced by the infix visit of the binary tree T.
 

5. Consider the Prolog program for the Type System of mini ML (Lecture 37). Modify the code so to treat the static environment R  as a stack instead than a list.

 
6. Consider the Prolog program for the Type System of mini ML. If we are only interested in doing type-checking, and we consider only the sublanguage without application, then we could translate easily this program into an ML program of the same length (more or less). However, the clause for functional application:

type(app(E1,E2),B,R) :- type(E1,A->B,R), type(E2,A,R).  /* application */

cannot be translated so easily in ML.  (It is possible, but it require to write a lot of additional code).  Try to explain why.
 

1. Consider the following class declarations in C++:

class C {
  private: int x;
  protected: int y;
  public: int z;
};

class C1: public C {
  private: int x1;
  public: int y1;
};

class C2: private C {
  private: int x2;
  public: int y2;
};

Assume that in   main  there is the following declaration:

C1 o1;

For each of the following expressions in  main, say whether they are allowed or not (they can be forbidden either because they violate the class definition or the protection  mechanism)

o1.x , o1.y , o1.z , o1.x1 , o1.y1 , o1.x2 , o1.y2
 

2. Consider the following template definition in C++:

template <class T> cell {
   private: T info;
   public: void set(T x){ info = x; }
              T get() { return info; }
};

Define the subclass coloured_cell by extending the class  cell  with:
- a field  colour, indicating the colour of the cell, represented as a character ("w" for white, "b" for black, "r" for red, etc.),
- the method  set_colour, which set the content of the field colour, and
- the method  get_colour,  which returns the content of the field  colour.
 
 Choosing the right signature, types and parameters is part of the exercise.

3. Exercise 7.1 in Sethi.

4. Exercise 7.3 in Sethi.