Programowanie w logice i funkcyjne
Informacje ogólne
Kod przedmiotu: | WM-I-U-PWL |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Programowanie w logice i funkcyjne |
Jednostka: | Wydział Matematyczno-Przyrodniczy. Szkoła Nauk Ścisłych |
Grupy: | |
Strona przedmiotu: | https://zdanowski.blog.uksw.edu.pl/ |
Punkty ECTS i inne: |
0 LUB
5.00
(w zależności od programu)
|
Język prowadzenia: | polski |
Poziom przedmiotu: | zaawansowany |
Symbol/Symbole kierunkowe efektów uczenia się: | I2_W01, I2_W04, I2_W05, I2_K01 |
Skrócony opis: |
Kurs przedstawia dwa główne paradygmaty programowania inspirowane logiką. Pierwszy z nich to Programowanie w Logice. Kurs przedstawia podstawy teoretyczne paradygmatu takie jak unifkacja, metoda rezolucji dla logiki pierwszego rzędu, SLD rezolucja. Opisuje w jaki sposób stanowią one podstawę mechanizmu obliczeniowego Prologu. Następnie w ramach opisu języka Prolog student ma możliwość poznać wykorzystanie tych narzędzi oraz różnice pomiędzy implenetacją i jej teoretycznymi podstawami. W części poświęconej programowaniu funkcyjnemu przedstawione zostają podstawowe cech programowania funkcyjnego jak: przejrzystość referencyjna, niezmienność danych, bezstanowość, brak efektów ubocznych, itp. Kurs prezentuje odstawy rachunku lambda i redukcji termów. Następnie kurs przedstawia podstawowe techniki programowania w Haskellu oraz ich związki z rachunkiem lambda. |
Pełny opis: |
1. Podstawowe cechy paradygmatu programowania w logice: deklaratywny styl programowania, mechanizm wnioskowania, formuły Hornowskie, środki kontroli nad wnioskowaniem/obliczeniem. Mechanizm rezolucji dla klasycznego rachunku zdań. 2. Składnia logiki pierwszego rzędu. Uniwersum Herbranda. Formuły Hornowskie. Definicja spełniania dla formuł Hornowskich. Unifikacja i rezolucja w logice pierwszego rzędu. Twierdzenie o istnieniu najbardziej ogólnego unifikatora (MGU). 3. SLD rezolucja w logice pierwszego rzędu. Twierdzenie o pełności dla rezolucji i SLD rezolucji. Twierdzenie o nierozstrzygalności SLD rezolucji. Reprezentowanie wiedzy w Prologu. Podstawy pracy z interpreterem Prologu (Swi-Prolog). 4. Znaczenie symboli '=' i '==' w Prologu. Kontrola nad przebiegiem wykonania programu: kolejność wyboru klauzul do unifikacji, nawracanie, odcięcie (cut), wymuszenie nawrotu (fail).Sledzenie wykonania programu. Meta predykaty: clause/2, assert/1, retract/1. 5. Obsługa plików, programowanie wejścia i wyjścia. Arytmetyka w Prologu. Znaczenie 'is' oraz '=:='. 6. Negacja w Prologu. Założenie o domkniętości świata (closed world assumption). SLDNF rezolucja. Modele stabilne. 7. Reprezentowanie struktur rekurencyjnych: lista, drzewo. Technika programowania z akumulatorem. Listy różnicowe. 8. Wprowadzenie do rachunku lambda. Interpretacje wartości logicznych, instrukcji warunkowej, iloczynu kartezjańskiego w rachunku lambda. Redukcje termów. Operator punktu stałego Y. 9. Arytmetyka w rachunku lambda. Własności programowania funkcyjnego: przejrzystość referencyjna, niezmienność danych, bezstanowość, brak efektów ubocznych, funkcje jako podstawowe obiekty, rekursja, leniwa ewaluacja, typy, polimorfizm, funkcje wyższych rzędów. 10. Wprowadzenie do języka Haskell. Podstawy składni, konwencje nazewnicze i pierwsze programy. Podstawowe typy: logiczny, znakowy, typy liczbowe. Listy, pary, typy funkcji. Operacje curry i uncurry. Polimorfizm. Klasy typów. Definiowanie typów. 11. Definiowanie funkcji: wyrażenia lambda, złożenie funkcji, rekursja, dopasowywanie wzorca. Definiowanie funkcji przez równoległą rekursję. Podstawowe operacje na listach. 12. Typy rekurencyjne. Definiowanie funkcji działających na typach rekurencyjnych. Implementacja drzewa. 13. Kontynuacje i monady. Problem obsługi wejścia i wyjścia w językach funkcyjnych, efekty uboczne, niepowtarzalność wyniku. Typ IO. Obsługa plików. 14. Struktury nieskonczone w Haskellu. 15. Elementy programowania funkcyjnego w imperatywnych językach programowania. Połączenie paradygmatów: funkcyjne programowanie w logice. Język Curry. |
Literatura: |
Clocksin, Mellish, Prolog. Programowanie. Helion Nilsson, Małuszyński, Programming in Prolog, Wiley & Sons Ltd, wolny dostęp: http://www.ida.liu.se/~ulfni53/lpp/ Harold Abelson, Gerald Jay Sussman, Julie Sussman, Struktura i interpretacja programów komputerowych, WNT. Paul Hudak, John Peterson, Joseph Fasel, A Gentle Introduction to Haskell, Version 98, 2000, wolny dostęp: https://www.haskell.org/tutorial/ Richard Bird, Introduction to Functional Programming using Haskell. Simon Peyton Jones (ed.), Haskell 98. Language and Libraries. The Revised Report. 2002, wolny dostęp: https://www.haskell.org/definition/haskell98-report.pdf |
Efekty kształcenia i opis ECTS: |
Zna teoretyczne podstawy stojące za deklaratywnym i funkcyjnym paradygmatem programowania (rezolucja, uniwersum Herbranda, rachunek lambda). (I2_W01) Zna własności deklaratywnych i funkcyjnych języków programowania. (I2_W04) Zna metody analizy poprawności programów deklaratywnych wykorzystujące SLD rezolucję i funkcyjnych przez analizę termów i ich redukcję. (I2_W05) Jest świadomy potrzeby aktualizacji wiedzy dotyczącej standardów języków programowania oraz ich implementacji. (I2_K01) |
Metody i kryteria oceniania: |
egzamin pisemny |
Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)
Okres: | 2022-02-01 - 2022-06-30 |
Przejdź do planu
PN WT WYK
LAB
ŚR CZ PT |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Konrad Zdanowski | |
Prowadzący grup: | Konrad Zdanowski | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzaminacyjny | |
E-Learning: | E-Learning (pełny kurs) z podziałem na grupy |
|
Typ przedmiotu: | obowiązkowy |
|
Grupa przedmiotów ogólnouczenianych: | nie dotyczy |
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.