Systemy typów dla języków programowania - lab.

Rok akademicki 2010/11:
Plan zajęć
Lista obecności

Wyniki sprawdzianu z wykładów który odbył się 5 lutego 2011 r.

Uwaga: Proszę aby osoby zainteresowane ustaliły między sobą i zaproponowały JEDEN termin poprawki (wykładów i lab.)

Na tej stronie znajduje się opis laboratoriów do przedmiotu obieralnego Systemy typów dla języków programowania, dla studentów 7 semestru kierunku informatyka na Politechnice Poznańskiej.

Informacje na temat wykładów znajdują się na tej stronie.

Celem zajęć laboratoryjnych jest praktyczne poznanie możliwości jakie dają języki programowania, których konstrukcja opiera się na zaawansowanych systemach typów. W ramach kursu poznawać będziemy OCaml, który udostępnia nie tylko system modułów, ale także pełne wsparcie dla programowania obiektowego -- wszystko to połączone polimorficznym systemem typów z dedukcją typów. Język OCaml zainspirował Microsoft do opracowania języka F#, wariantu ML dla .NET ze składnią i semantyką podobną do podstawowej części OCaml.

Opinie autorów większych projektów w OCaml.

Przykładowe programy zaimplementowane w tym języku (wybierz w prawej zakładce dany "Topic").

Strona wiki - grupy użytkowników, firmy używające OCaml, etc.

Materiały

Materiały podstawowe do nauki programowania w OCaml:

Organizacja laboratoriów

Laboratoria

Lab 1:

Omówienie zakresu laboratoriów oraz wstępne informacje nt. języka OCaml (lub F#).

Lab 2:

Wyrażenia arytmetyczne, dedukcja typów, konwersja typów, konstrukcja let .. in .., definiowanie i wołanie funkcji, typ funkcji (typ -> typ),wyrażenia lambda (np. function x -> x+1 lub fun x y -> x+y), funkcje polimorficzne i rekurencyjne (rec, zob. np. ile), dopasowanie do wzorca na przykładzie list (match .. with ..), ćwiczenia - łączenie list (append @).

    let rec ile l = 
      match l with
        [] -> 0
      | h::r -> 1 + ile r;;

    ile [1; 2; 3];;

Lab 3:

Wyrażenia lokalne/globalne (let-wiązania), referencje (zmienne) a la wskaźniki w C/C++ (ref, :=, !), funkcje zagnieżdżone, moduły (open, notacja "kropkowa"), aliasy do modułów (module), separatory ; (średnik) oraz ;; (podwójny średnik), wyrażenie warunkowe if .. then .. else ...

Lab 4:

Listy elementów (konstruktor ::, nil []), polimorficzny typ listy (np. 'a list), krotki (np. (value, ..)) i typ krotek (typ * ..), rekordy (np. {a=value; ..}) i typ rekordów (np. {a : typ; ..}) varianty (np. Etykieta value) i typ wariantów (Etykieta of typ | ..), warianty rekurencyjne (używane do definiowania drzew), warianty sparametryzowane (ze zmiennymi typów 'a, 'b, ..).

Lab 5(-6):

Dopasowanie do wzorca na złożonych typach danych (match .. with .. [ when condition ]), _ (podkreślnik), ćwiczenia - operacje na drzewach (np. zob. niżej).

    open Printf

    (* Typ polimorficzny drzewa binarnego *)

    type 'a btree = Lisc of 'a | Node of 'a btree * 'a btree 

    (* Funkcja drukująca wartości typu 'a btree *)

    let print_tree drzewo string_of =
      let rec f d =
        match d with
          Lisc i -> string_of i
        | Node(x,y) -> "Węzeł (" ^ f x ^ ", " ^ f y ^ ")"
      in
        printf "%s\n" (f drzewo);; 

    (* drukuje wartość typu int btree *)
    print_tree (Node (Node (Lisc 1, Lisc (-2)), Lisc 3)) string_of_int;;

    (* drukuje wartość typu string btree *)
    print_tree (Node (Lisc "ala", Lisc "kot")) (fun x -> x);;

Lab 6:

Proste moduły (bez funktorów), moduły-pliki, oddzielna kompilacja i łączenie (linkowanie) modułów (fragmentów kodu), open vs. notacja "kropkowa", interfejsy i sygnatury, typy abstrakcyjne, własność private, definiowanie podmodułów (typ: module type Module_type = sig ... end, implementacja: module Module_name : Module_type = struct ... end).

Przykładowa definicja modułu Tree zawierającego operacje na drzewie binarnym:

type tree = Leaf of int | Node of tree * tree
val print_tree : tree -> unit
val map : ( int -> int ) -> tree -> tree
val fold_left : ( int -> int -> int ) -> int -> tree -> int
val sum : tree -> int
znajduje się tutaj.

Lab 7a:

"Wskaźniki" na puste dane (typ option), asercje asert, wypisywanie komunikatach o błędach (failwith lub Printf.eprintf)

Lab 7b:

Co to jest programowanie funkcyjne?, funkcje wysokiego rzędu (ang. higher-order functions), domknięcie (ang. closure) = definicja funkcji + środowisko, mapowanie funkcji na złożone struktury danych (np. zob. niżej), częściowa aplikacja funkcji oraz operacja "currying", czyste programowanie funkcyjne, ścisłość vs. leniwość ewaluacji wyrażeń, typy "boxed" i "unboxed"

    let double x =
      x * 2
    in
      List.map double [ 1; 2; 3 ];;

    - : int list = [2; 4; 6]
lub:
    List.map (( * ) 2) [1; 2; 3];;

    - : int list = [2; 4; 6]

Lab 8:

Wyrażenia if..then..else, i-ty znak w łańcuchu s (s.[i]), grupowanie operacji (begin ... end lub nawiasy), pętle for i while, np.:

    let koniec = ref false in
    while not !koniec do
      print_string "Powtórzyć (t/n) ?";
      let str = read_line () in
      if str.[0] = 't' then
        koniec := true
    done;;
Iterowanie po listach: List.iter, List.map, List.filter, List.mem, List.for_all oraz List.exists, List.fold_left (oraz List.fold_right), iterowanie po łańcuchach (zob. moduł String)

Lab (wykład) 9:

Aktualizowalne rekordy (mutable), tablice, obiekty i klasy, klasy polimorficzne, dziedziczenie, klasy wirtualne, inicjalizacja, przykład "graphical widgets", koercja typów (przy dziedziczeniu ze wspólnej klasy), definiowanie obiektów bez klas, typ obiektowy

Lab (wykład) 10:

Rekurencja vs. pętle, programowanie systemowe, wyjście z rekurencji przez generowanie i obsługę wyjątków, przykład "listowanie plików w katalogach", źle kodowana rekurencja ("stack owerflow"), rekurencja "ogonowa" (ang. tail recursion)

let rec range a b =
  if a > b then []
  else a :: range (a+1) b
  ;;
let range a b =
  let rec f a b accum =
    if a > b then accum
    else f a (b-1) (b::accum)
  in
    f a b [];;

Instalacja systemu i kompilacja programów

System OCaml jest dostępny bezpłatnie dla Linux, MacOS X, oraz Microsoft Windows z tej strony. Na zajęciach będziemy korzystać z instalacji pod Linux-em.

Na początek programy w OCaml warto uruchomić korzystając z interpretera ocaml; pozwala to zobaczyć efekty pracy type checker'a i algorytmu dedukcji typów polimorficznych. Interpretacja podanych linii kodu następuje po wpisaniu ;; (podwójny średnik) i wciśnięciu Enter.

Aby skompilować program zapisany w pliku prog.ml (rozszerzenie .ml) korzystamy z polecenia ocamlc prog.ml -o prog, gdzie prog jest plikiem wykonywalnym. Zamiast ocamlc generującego bytecode (który można wykonać jeśli jest zainstalowany OCaml), można użyć ocamlopt; ten ostatni kompilator generuje samodzielny kod wykonywalny, zwykle szybszy od bytecode'u.

Poniżej krótki program na dobry początek:

print_string "Hello world!\n"

Jeśli program korzysta z dodatkowych bibliotek poza biblioteką standardową, która jest ładowana automatycznie, należy wymienić ich nazwy przy kompilacji. Na przykład, jeśli program prog używa wywołań systemowych z biblioteki unix, linia komendy ma postać:

ocamlc prog.ml unix.cma -o prog

gdzie .cma jest rozszerzeniem dla bytecode'owych bibliotek, podczas gdy .cmxa jest rozszerzeniem dla bibliotek w kodzie natywnym i ocamlopt. Więcej na temat narzędzi kompilacji programów w systemie OCaml znajduje się na tej stronie.
Pawel [dot] T [dot] Wojciechowski [at] put.poznan.pl
Last modified: Tue Nov 17 14:20:30 CET 2009