Programowanie funkcyjne

Forma zajęć

wykład (30 godz.) + laboratorium (30 godz.)

Opis

Celem przedmiotu jest przedstawienie programowania funkcyjnego – paradygmatu i stylu programowania, oraz towarzyszących mu technik programistycznych. Wykłady obejmują wprowadzenie do wybranego języka funkcyjnego (Ocaml) oraz podstawowe pojęcia i techniki programowania funkcyjnego. Ćwiczenia lub laboratoria obejmują praktyczną naukę programowania funkcyjnego, zwieńczoną realizacją średniej wielkości programu.

Podziękowania

Niniejsze materiały powstały na podstawie notatek do prowadzonych przeze mnie, na przestrzeni kilku lat, wykładów z Programowania funkcyjnego, oraz ze Wstępu do programowania i Metod programowania (w ramach potoku funkcyjnego). Chciałbym gorąco podziękować moim kolegom, którzy w tym czasie prowadzili ćwiczenia z tych przedmiotów, a w szczególności: Jackowi Chrząszczowi, Grzegorzowi Grudzińskiemu i Mikołajowi Konarskiemu. Ich uwagi miały wpływ na postać prowadzonych zajęć, a więc i również na te materiały. W szczególności część zamieszczonych tu zadań pochodzi od nich.

Sylabus

Autor

• Marcin Kubica

Wymagania wstępne

• Wstęp do programowania
• Metody programowania
• Logika i teoria mnogości

Zawartość

• Charakterystyka paradygmatu funkcyjnego
• Podstawowe konstrukcje wybranego funkcyjnego języka programowania
  • Przyrostowy tryb pracy
  • Wyrażenia
  • Definicje stałych
  • Definicje procedur
  • $\lambda$-abstrakcja
  • Procedury rekurencyjne
  • Definicje lokalne
  • Wyrażenia logiczne i wyrażenia warunkowe
• Typy danych
  • Proste typy wbudowane
  • Wzorce i konstruktory
  • Produkty kartezjańskie
  • Listy
  • Deklaracje typów
  • Rekordy
  • Warianty
  • Aliasy we wzorcach
• Wyjątki
  • Deklarowanie wyjątków i typ exn
  • Podnoszenie i przechwytywanie wyjątków
• Proceudry wyższych rzędów
  • Typy procedur i polimorfizm
  • Przykłady procedur wyższych rzędów
  • Zastosowania procedur wyższych rzędów
  • Procedury wyższych rzędów i listy
• Model obliczeń programów funkcyjnych (uproszczona semantyka operacyjna)
  • Środowiska i ramki
  • Semantyka definicji globalnych
  • Reprezentacja danych i procedur
  • Aplikacja procedur
  • Rekurencja ogonowa
  • Semantyka definicji lokalnych
  • Odśmiecanie
• System typów dla fragmentu języka
  • Typy i schematy typów
  • Środowiska typujące
  • Podstawowe reguły typowania
  • Polimorfizm
  • Rekurencja
  • Wyjątki
  • Konstrukcje imperatywne i słabe zmienne typowe
• Moduły i funktory
  • Struktury
  • Sygnatury i zależności między strukturami i sygnaturami
  • Funktory
  • Funktory wyższych rzędów
• Konstrukcje imperatywne
  • Referencje
  • Tablice
  • Sekwencyjne złożenie instrukcji (;),
  • Pętle
  • Przykłady ilustrujące charakter programowania imperatywnego i jego połączenie z programowaniem funkcyjnym
• Uleniwianie i spamiętywanie
  • Uleniwianie obliczeń
  • Technika spamiętywania
• Strumienie
  • Paradygmat programowania strumieniowego
  • Implementacja strumieni
  • Przykłady strumieni
  • Operacje na strumieniach
  • Uwikłane definicje strumieni
  • Iteracje jako strumienie

Literatura

• [AS] H. Abelson, G. J. Sussman, Struktura i interpretacja programów komputerowych, WNT 2002.
• [L] X. Leroy, The Objective Caml system, [1]
• [ChMP] E. Chailloux, P. Manoury, B. Pagano, Developing Applications with Objective Caml, [2]
• [R] D. Rémy, Using, Understanding and Unraveling the Ocaml Language, [3]

Moduły

• Wstęp – porównanie programowania funkcyjnego i imperatywnego
• Podstawy języka programowania Ocaml (Ćwiczenia)
• Podstawowe typy danych (Ćwiczenia)
• Procedury wyższych rzędów (Ćwiczenia)
• Procedury wyższych rzędów i listy (Ćwiczenia)
• Model obliczeń (Ćwiczenia)
• Programowanie imperatywne (Ćwiczenia)
• Moduły (Ćwiczenia)
• Funktory (Ćwiczenia)
• Techniki uleniwiania i spamiętywania (Ćwiczenia)
• Procedury jeszcze wyższych rzędów (Ćwiczenia)
• System typów (Ćwiczenia)
• Strumienie (Ćwiczenia)