Programowanie funkcyjne

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.