Programowanie funkcyjne

Prowadzący: Grzegorz Fabiański


Kategorie: informatyka

Zadania kwalifikacyjne: dodano jeden podpunkt w zad 1, poprawiono błędy w innych zadaniach.

Opis

  Zazwyczaj jakikolwiek kurs programowania zaczyna się od pojęcia zmiennej -takiej szufladki, w której jest wartość, i którą można odczytywać i zmieniać. Zaraz potem wprowadza się pojęcie pętli. I faktycznie - we wszystkich standardowych językach programowania trudno wyobrazić sobie programowanie w którym nie ma zmiennych (takich, których wartość można nadpisać). W szczególności bez nadpisywalnych zmiennych nie ma sensu pojęcie pętli - a nawet pojecie czasu (zrób coś po czymś).

   Na tych warsztatach:

  • przekonamy się, że bez tego wszystkiego da się nie tylko (prze)żyć, ale i pisać lepszy kod
  • zrozumiemy, że rozumienie programu jako "przepisu kulinarnego" (zrób coś po czymś) jest niewłaściwe - będziemy za to pisać kod trochę bardziej matematycznie - definiując (często indukcyjnie=rekurencyjnie) coraz to bardziej skomplikowane obiekty.
  • okaże się że tzw. kod funkcyjny jest często dużo krótszy i czytelniejszy, a kompilujące się programy są zazwyczaj bezbłędne.
  • poznamy bardzo silny (statyczny) system typów, którym nie trzeba (prawie) niczego jawnie typować (kod jest statycznie typowany, a wygląda jak w Pythonie!).

  Na warsztatach nie będzie długich wykładów, będzie za to dużo zadanek, które będzie rozwiązywać tak indywidualnie, jak i wspólnie (na rzutniku).

Wymagania

  1. nie bać się abstrakcji - będzie trochę matematyczno-podobnych struktur (funkcje zwracające funkcje, które pobierają funkcje...)
  2. trzeba mieć odwagę, by porzucić o prawie wszystkim co się o programowaniu wie i chcieć nauczyć się pisać kod na nowo
  3. może się przydać podstawowe obycie z programowaniem (by mieć wprawę z rozumieniem/zgadywaniem znaczenia komunikatów od kompilatora)
  4. przyda się własny laptop z linuxem (może być w maszynie wirtualnej). Będziemy pisać w Ocaml-u - jest on dostępny bezproblemowo w każdej dystrybucji.

Przydatne rzeczy

Ostatniego dnia będziemy robić coś z poniższej listy:

  • implementować 2-wymiarowe (a nawet wielo-wymiarowe) drzewo przedziałowe
  • pisać interpreter dla jakiegoś mikro-języka programowania.
  • bawić się kombinatorami punktu stałego
  • omawiać funkcyjny pomysł na strukturyzcję dużych projektów - moduły wyższych rzędów - czyli funkcyjna konkurencja dla obiektowości
  • przypatrywać się izomorfizmowi Currego-Howorda (slogan: twierdzenia=typy, dowody=programy)

Dobrze więc będzie wiedzieć jak działa drzewo przedziałowe (w tym takie dwuwymiarowe) - przydać się może ten artykuł.

Obrazek pochodzi z tej prezentacji (gorąco polecam).

Gdybyś chciał koniecznie pisać własny interpreter to polecam zapoznać się wcześniej z BNF, EBNF.