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

Rok akademicki 2009/10:
Plan zajęć
Lista obecności

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 Objective Caml (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:

• Podręcznik programowania
• Dokumentacja systemu (włączając bibliotekę standardową)
• "Developing Applications with OCaml" - książka dostępna na WWW
• Inne materiały

Organizacja laboratoriów

• Grupy laboratoryjne.
• Rozkład zajęć (w każdej grupie do 15 osób).
• Warunkiem zaliczenia jest zrealizowanie do końca semestru mini-projektu w języku OCaml; tematy można zgłaszać w trakcie semestru, przykładowa lista zostanie opublikowana na tej stronie.
• Na ocenę z lab. składa się mini-projekt, wynik testu ze znajomości programowania w stylu ML (na przykładzie OCaml), i obecność na zajęciach lab.
• W przypadku studiów zaocznych, gdzie liczba godz. jest mniejsza o połowę, mini-projekt nie jest wymagany.

Laboratoria

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

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

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 ...

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, ..).

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

    (* definicja typu polimorficznego drzewa binarnego *)
    type 'a b_tree = Lisc of 'a | D of 'a b_tree * 'a b_tree 

    (* definicja funkcji drukującej wartości typu 'a b_tree *)
    let print_tree drzewo string_of =
      let rec f d =
        match d with
          Lisc i -> string_of i
        | D(x,y) -> "Drzewo (" ^ f x ^ "," ^ f y ^ ")"
      in
        printf "%s\n" (f drzewo);; 

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

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

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).

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

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]

    List.map (( * ) 2) [1; 2; 3];;

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

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;;

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

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 rec range2 a b accum =
  if b < a then accum
  else range2 a (b-1) (b :: accum);;
let range a b =
  range2 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"

ocamlc prog.ml unix.cma -o prog