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.

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
  • Kontynuacje
• 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)
• Scheme (Ćwiczenia)