Strumenti Utente

Strumenti Sito


magistraleinformaticanetworking:spm:ocamlfs1

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

Prossima revisione
Revisione precedente
magistraleinformaticanetworking:spm:ocamlfs1 [23/03/2011 alle 15:54 (11 anni fa)]
Marco Danelutto creata
magistraleinformaticanetworking:spm:ocamlfs1 [23/03/2011 alle 16:31 (11 anni fa)] (versione attuale)
Marco Danelutto
Linea 3: Linea 3:
 This is an summary of the lesson given on March 23rd.  This is an summary of the lesson given on March 23rd. 
  
-We represent the functional semantics of skeletons with higher order functions. We use [[http://caml.inria.fr/ocaml/|Ocaml]] for the examples. +We represent the functional semantics of skeletons with higher order functions. We use [[http://caml.inria.fr/ocaml/|Ocaml]] for the examples (see the [[http://caml.inria.fr/pub/docs/manual-ocaml/index.html|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:  Assuming that //data streams// are represented with Ocaml lists (just for the moment), a **farm** skeleton may be defined as follows: 
Linea 11: Linea 11:
   [] -> []   [] -> []
 | listHead::listTail -> (f listHead)::(farm f listTail);; | listHead::listTail -> (f listHead)::(farm f listTail);;
 +</code>
 +
 +Entering the farm definition in the Ocaml interpreter we get, as an answer, the type of the farm: 
 +<code>
 +val farm : ('a -> 'b) -> 'a list -> 'b list = <fun>
 +</code>
 +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:
 +<code>
 +# let sq x = x * x;;
 +val sq : int -> int = <fun>
 +# farm sq;;
 +- : int list -> int list = <fun>
 +
 +</code>
 +and applying this function to a list of integers, we get the list of squares: 
 +<code>
 +# (farm sq) [1;2;3;4;5];;
 +- : int list = [1; 4; 9; 16; 25]
 +
 +</code>
 +
 +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: 
 +<code>
 +# List.map;;
 +- : ('a -> 'b) -> 'a list -> 'b list = <fun>
 +
 +</code>
 +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: 
 +<code>
 +# farm (List.map sq);;
 +- : int list list -> int list list = <fun>
 +
 +</code>
 +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.
 +<code>
 +# 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]]
 +
 +</code>
 +
 +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:
 +<code>
 +# [|1;2|];;
 +- : int array = [|1; 2|]
 +
 +</code>
 +As for lists, a map working on arrays is pre-defined: 
 +<code>
 +# Array.map;;
 +- : ('a -> 'b) -> 'a array -> 'b array = <fun>
 +
 +</code>
 +Therefore we can re-write the //farm of map// example as follows:
 +<code>
 +
 +# 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|]]
 +
 +</code>
 +
 +Even better, we can define our data type **stream** using the Ocaml type definition syntax: 
 +<code>
 +# type 'a stream = Empty | Stream of ('a * 'a stream);;
 +type 'a stream = Empty | Stream of ('a * 'a stream)
 +
 +</code>
 +The farm functional semantics may therefore be defined by the function: 
 +<code>
 +
 +  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>
 +
 +</code>
 +Therefore the type of our //farm of map// will be correctly inferred as: 
 +<code>
 +# farm (Array.map sq);;
 +- : int array stream -> int array stream = <fun>
 +
 </code> </code>
  
magistraleinformaticanetworking/spm/ocamlfs1.1300895696.txt.gz · Ultima modifica: 23/03/2011 alle 15:54 (11 anni fa) da Marco Danelutto