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 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]]
# 

This is a little bit ambiguous due to the usage of lists to represent both streams and arrays. Ocaml provides arrays as primitive types actually. Arrays are denoted similarly to lists using particular brackets:

# [|1;2|];;
- : int array = [|1; 2|]
# 

As for lists, a map working on arrays is pre-defined:

# Array.map;;
- : ('a -> 'b) -> 'a array -> 'b array = <fun>
# 

Therefore we can re-write the farm of map example as follows:

# let rec farm f x = 
  match (x) with 
  [] -> []
| listHead::listTail -> (f listHead)::(farm f listTail);;
      val farm : ('a -> 'b) -> 'a list -> 'b list = <fun>
# let sq x = x * x;; 
val sq : int -> int = <fun>
# let worker = Array.map sq;;
val worker : int array -> int array = <fun>
# let main = farm worker;;
val main : int array list -> int array list = <fun>
# let array1 = [| 1 ; 2 |];;
val array1 : int array = [|1; 2|]
# let array2 = [| 3; 4 |];;
val array2 : int array = [|3; 4|]
# let stream = [ array1; array2 ];;
val stream : int array list = [[|1; 2|]; [|3; 4|]]
# main stream;;
- : int array list = [[|1; 4|]; [|9; 16|]]
# 

Even better, we can define our data type stream using the Ocaml type definition syntax:

# type 'a stream = Empty | Stream of ('a * 'a stream);;
type 'a stream = Empty | Stream of ('a * 'a stream)
# 

The farm functional semantics may therefore be defined by the function:

# 
  let rec farm f = function
    Empty -> Empty
  | Stream(x,y) -> Stream ((f x), (farm f y));;
val farm : ('a -> 'b) -> 'a stream -> 'b stream = <fun>
# 

Therefore the type of our farm of map will be correctly inferred as:

# farm (Array.map sq);;
- : int array stream -> int array stream = <fun>
#