Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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)
zobacz reguły punktacji
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 2019/20" (zakończony)

Okres: 2020-02-01 - 2020-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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

Zajęcia w cyklu "Semestr letni 2020/21" (zakończony)

Okres: 2021-02-01 - 2021-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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

Zajęcia w cyklu "Semestr letni 2021/22" (jeszcze nie rozpoczęty)

Okres: 2022-02-01 - 2022-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Konrad Zdanowski
Prowadzący grup: Konrad Zdanowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.