DidaWiki

This is an summary of the lesson given on March 23rd.

We represent the functional semantics of skeletons with higher order functions. We use Ocaml for the examples (see the Ocaml online manual for the syntax).

Assuming that data streams are represented with Ocaml lists (just for the moment), a farm skeleton may be defined as follows:

let rec farm f x = 
  match (x) with 
  [] -> []
| listHead::listTail -> (f listHead)::(farm f listTail);;

Entering the farm definition in the Ocaml interpreter we get, as an answer, the type of the farm:

val farm : ('a -> 'b) -> 'a list -> 'b list = <fun>

that is a function taking a function from type 'a to type 'b and a list of values of type 'a and returning a list of items of type 'b When applying the farm to a function computing the square of integers, we get a function from integer streams to integer streams:

# let sq x = x * x;;
val sq : int -> int = <fun>
# farm sq;;
- : int list -> int list = <fun>
# 

and applying this function to a list of integers, we get the list of squares:

# (farm sq) [1;2;3;4;5];;
- : int list = [1; 4; 9; 16; 25]
# 

Suppose we also use lists to represent arrays. The map skeleton can be modelled through the List.map function, available as primitive in Ocaml and having the obvious type:

# List.map;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# 

Therefore we can look at the type of skeleton composition. As an example, a farm having a map worker computing sq on all the elements of the matrix (which is actually a vector represented as a list, in our simple assumption) has type:

# farm (List.map sq);;
- : int list list -> int list list = <fun>
# 

and in fact, giving the composite skeleton a stream (a list, in our assumption) of arrays (vectors represented as a stream, in our assumptions), we get the correct result: all items of the stream are processed in such a way all the subitems of the arrays are squared.

# let array1 = [1;2];;
val array1 : int list = [1; 2]
# let array2 = [3,4];;
val array2 : (int * int) list = [(3, 4)]
# let stream = [array1;array2];;
Error: This expression has type (int * int) list
       but an expression was expected of type int list
# let array2 = [3;4];;
val array2 : int list = [3; 4]
# let stream = [array1;array2];;
val stream : int list list = [[1; 2]; [3; 4]]
# farm (List.map sq) stream;;
- : int list list = [[1; 4]; [9; 16]]
#