Weekly exercises in INF3110
		 week 41 6-10.10.2008


Exercise 1
----------
Exercise 6.1 in Mitchell's book


Exercise 2
----------

a) Exercise 6.4 in Mitchell's book

b) Apply F to the identity function (fn x => x) and the following arguments: 0, 1, 2, 3. What is supposed to be the result? Why? Is F the factorial function? Explain.


Exercise 3
----------
Exercise 6.5 in Mitchell's book


Exercise 4
----------
Exercise 6.6 in Mitchell's book


Exercise 5
----------
Exercise 6.7 in Mitchell's book


Exercise 6
----------
Given the following general signature specifying a type t equipped with the value "zero" and operators "sum", "prod", "diff" and "quo":

signature ARITH = sig
  type t
  val zero: t
  val sum: t * t -> t
  val diff : t * t -> t
  val prod : t * t -> t
  val quo : t * t -> t
end;

Declare a structure "Real" matching signature ARITH, such that Real.t is the type "real" and the components "zero", "sum", etc, denote the corresponding operations on type "real".


Exercise 7
----------
There are two kinds of overloading of functions/operators:
- context-independent: overloading only done on parameters to function or type of operands for an operator;
- context-dependent: which operator to use depends also on the type of the result.
Hence, with context-independent overloading, the function to be called is solely based upon the type of the actual parameter. With context-dependent overloading, the function to be called may not be identified by the type of the parameters. The context must be taken into account to identify the function to be called. 

a) Consider the operator ++ (concatenation) to be overloaded, with types

Char x Char -> String
Char x String -> String
String x Char -> String
String x String -> String

Is this overloading context-independent or context-dependent? Have a look at the following examples:

c ++ s
(s ++ c) ++ c
s ++ (c ++ c)

where c is a Char variable and s is a String variable, and identify for each ++ what kind of concatenation it is.

b) Define in ML four infix operators ++ with the types specified in item a) (in the same order as they are defined). Define then the following four values:

val c1 = #"a";
val c2 = #"h";
val s1 = "bcd";
val s2 = "efg";

Before executing, guess what would be the result of the following:

c1 ++ c2;
s1 ++ c2;
c1 ++ s1;
s1 ++ s2;

Try it using sml and explain the result.


Exercise 8
----------
(NOTE: This exercise is about overloading in general, not in ML!)
Consider overloading to be defined for proper procedures (that is, not functions). 

a)Is it context-dependent or context-independent? 

b)Assume that the operator _/_ is overloaded, with types int * int -> int and int * int -> double. Assume further that we have an overloaded proper procedure "write", the argument of which may be either int or double.
Give examples of procedure calls where the procedure to be called cannot be defined uniquely.


Exercise 9
----------
Consider the following parametric function in C++ like syntax:

template <typename T>
T second(T x, T y) {return y}

It is parameterised by the type parameter T, and it returns the value of the second parameter. It is called in this way:

int i,j ;
second<int>(i,j)

The <int> is not really needed, as the compiler may infer that the type shall be int, but it is included here for clarity reasons. 

a) The body of the function does not really use any properties of the type T. Why is it so that C++ still has to generate different code for different actual types? 

b) Assume that we had the following version of "second":

template <class T>
T second(T *x, T *y) {return y}

Why would it be possible to use the same code for "second" for different actual classes for T?