Funkcionálne a logické programovanie


Anotácia

Poznanie základov funkcionálneho programovania  v čistých funkcionálnych jazykoch. Získanie poznatkov o metodológii funkcionálneho programovania v jazyku Haskell a jeho aplikácii pre programovacie techniky a pre implementáciu programovacích jazykov. Získanie znalosti z oblasti logického programovania a zručnosti pri tvorbe programov v jazyku Prolog.

Obsah prednášok

  1. Koncepcia funkcionálneho programovania a stratégie výpočtu.
  2. Hodnoty a typy, ich kategorizácia. Typové synonymá.
  3. Funkcie pre prácu so zoznamami.
  4. Podpora abstrakcie vo funkcionálnom programovaní. Stromy.
  5. Definícia algoritmov triedenia vo funkcionálnom jazyku.
  6. Definícia algoritmov vyhľadávania vo funkcionálnom jazyku.
  7. Princípy vyhodnocovania výrazov. Základy práce so štandardným vstupom a výstupom.
  8. Analýza a transformácia programov a jazykov.
  9. Úvod do logického programovania.
  10. Princípy logického programovania.
  11. Aritmetické predikáty, záznamy, operátory.
  12. Programovacie techniky a príklady.

Podkladom na skúšku sú odovzdané riešenia úloh z cvičení v papierovej forme.

Súčasťou ústnej časti skúšky bude overenie autorstva riešenia, odovzdaného na cvičení. 


Organizácia cvičení

Odporúča sa samostatná analýza riešených príkladov, porovnanie so základnou literatúrou a samostatná projektová práca podľa inštruktáže na úvodných prednáškach s použitím funkcionálneho jazyka Hugs98. 

Podmienka udelenia zápočtu

Cvičiacim overené samostatné riešenia nasledujúcich úloh v počte zodpovedajúcom schopnostiam študenta a ich odovzdanie vo vytlačenej podobe, každé na samostatnom hárku formatu A4, s hlavičkou

meno a priezvisko študenta               číslo riešenia                          dátum odovzdania

UPOZORNENIE: Odovzdané riešenia nesmú obsahovať žiadne komentáre. Majú obsahovať iba definície funkcií podľa nižšieuvedených šablón, ako aj ďalších funkcií, ktoré sú nevyhnutné pre riešenie danej úlohy. 

ÚLOHY

1. Lexikálny analyzátor pre jazyk zátvorkovaných výrazov lexical a zobrazenie showLex symbolickej formy lexikálnych jednotiek, podľa nasledujúcej šablóny. 

module Lexical where

data LexSym = AddL | SubL | MulL | DivL | LparL | RparL | ValL Int

type LexSyms = [LexSym]

lexical :: String -> LexSyms 

showLex ::  LexSyms  -> String 


2. Interpretátor interpreter jazyka zátvorkovaných výrazov (priama interpretácia, t.j.bez produkovania kódu na výstupe syntaktického analyzátora, podľa nasledujúcej šablóny.

module Interpreter where

import Lexical 

interpreter ::
LexSyms -> Int


3. Prekladač do postfixného kódu translate, zobrazenie postfixného kódu showCode, a jeho interpretácia eval , podľa nasledujúcej šablóny.

module TransPost where

import Lexical

data Operations = Add | Sub | Mul | Div | Push Int

type Code = [Operations] 

translate :: LexSyms -> Code

showCode :: Code -> String

eval :: Code -> Int


4. Prekladač do  syntaktického stromu translate,  zobrazenie syntaktického stromu showStree  a jeho interpretácia eval, podľa nasledujúcej šablóny.

module TransStree where

import Lexical

data Stree = Add Stree Stree | Sub Stree Stree | Mul Stree Stree | Div Stree Stree | Num Int

translate :: LexSyms -> Stree

showStree :: Stree -> String

eval :: Stree -> Int


5. Prekladač do prefixného kódu translate , zobrazenie prefixného kódu showCode  a jeho interpretácia eval, podľa nasledujúcej šablóny.

module TransPref where

import Lexical

data Operations = Add | Sub | Mul | Div | Num Int

type Code = [Operations] 

translate :: LexSyms -> Code

showCode :: Code -> String

eval :: Code -> Int


Základná literatúra

  1. Kollár Ján: Základy funkcionálneho programovania, KPI FEI TU v Košiciach, 2007, pre predmet FaLP KPI, učebné texty v elektronickej forme

Literatúra

  1. Bieliková, M., Návrat, P. Funkcionálne a logické programovanie. 1. vyd. Bratislava: STU v Bratislave, 2000.
  2. Bird, R.J., Wadler, P.: Introduction to Functional Programming.   Prentice Hall, 1988.
  3. Bratko, I. Prolog. Programming for artificial intelligence. 2. vyd. Wokingham: Addison-Wesley, 1990. [podrobnosti] vyd. Bratislava: Alfa, 1991.
  4. Kollár, J.: Funkcionálne programovanie. Elfa, Košice, 1995.
  5. Polák, J. Prolog. 1. vyd. Praha: Grada, 1992.
  6. Thompson, S.: Haskell: The Craft of Functional Programming (2nd Edition). Addison-Wesley. 1999.

Ďalšie zdroje

Funkcionálny jazyk Hugs98 (Winhugs)