Strumenti Utente

Strumenti Sito


Questa è una vecchia versione del documento!

Introducing skeleton semantics with higher order functions

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 function, available as primitive in Ocaml and having the obvious type:

- : ('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 ( 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 ( 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:

- : ('a -> 'b) -> 'a array -> 'b array = <fun>
magistraleinformaticanetworking/spm/ocamlfs1.1300897359.txt.gz · Ultima modifica: 23/03/2011 alle 16:22 (11 anni fa) da Marco Danelutto