Funkcionální programování

Funkcionální programování Scheme ale i trochu C#, Boo, Perlu, Smalltalku apod. Jiří Fišer MMVIII

Funkcionální paradigma ●

●

●

●

funkcionální paradigma je jedním z klasických paradigmat programování (podobně jako paradigma imperativní nebo logické) je založeno na striktním matematickém základě (tzv. lambda kalkulu) čistě funkcionální jazyky resp. jazyky primárně funkcionální nejsou příliš rozšířené (první jsou přibližně v druhé desítce nejužívanějších jazyků) funkcionální rysy se však vyskytují u většiny moderních jazyků (které dnes typicky podporují více paradigmat)

Základní rysy (postačující) ●

●

●

jediné výkonné entity programu jsou funkce (= uzavřené rutiny vracející nově vytvořené hodnoty) funkce nemají žádné postranní efekty (tj. mimo jiné vždy platí f(x) = f(x), při každém volání funkce f) hodnoty nejsou modifikovatelné a program nelze popsat jako posloupnost paměťových stavů (tj. neexistuje klasické přiřazení). program není lineární, ale je prováděn jako strom vyhodnocení, který navíc může být vyhodnocen i lenivě (až když je skutečně potřeba)

Další typické rysy ●

●

●

funkce jsou plnohodnotné (first-class) hodnoty, tj. lze s nimi pracovat v zásadě stejně jako s čísly, řetězci apod. (samozřejmě s jinými operacemi např. skládáním funkcí). Není např. nutné odlišovat funkci a ukazatel na funkce (delegát v názvosloví .NET). velkou roli hraje rekurze (nahrazuje cykly, jejichž běžná implementace vyžaduje změnu stavu) velkou roli hrají tzv. funkce vyšších řádů (tj. zjednodušeně funkce nad funkcemi)

Proč se učit funkcionální jazyky? ●

●

●

●

získáte jiný pohled na programování (což Vám umožní podívat se na běžné jazyky zvnějšku) uvidíte elegantní způsob řešení některých algoritmů a programových obratů většinu lze navíc přímo použít i v některých moderních OOP jazycích (hlavně C# a Pythonu) navíc je dosti pravděpodobné, že se s některým z funkcionálních jazyků setkáte v dalším studiu nebo dokonce i v praxi.

Scheme ●

●

jazyk Scheme je jedním z nejrozšířenějších dialektů jazyka Lisp, což je nejstarší a stále v praxi nejrozšířenější funkcionální jazyk. jazyk Scheme je relativně jednoduchý (v oblasti syntaxe dokonce minimalistický), kvalitně navržený a snadno popsatelný (je formálně definován a standardizován) Lisp

divergence

sjednocení

Scheme 1960

1970

1980

Common Lisp

Hello, world ●

program "hello, World" lze sice napsat i ve Scheme, není však pro tento jazyk příliš typický: (display "Hello, world")

●

typičtější program (a navíc čistě funkcionální) (define delka (lambda (seznam) (cond ((null? seznam) 0) (else (+ 1 (delka (cdr seznam)))) ) ) )

Syntaxe ●

●

syntaxe jazyka Scheme je (stejně jako u Lispu) je identická se syntaxí dat, které program zpracovává podobně jako např. u strojového kódu (avšak na mnohem vyšší úrovni abstrakce) platí: data se mohou stát programem (mohou být vykonávány) a naopak program může být snadno zpracováván jako data

Atomy ●

základní syntaktickou jednotkou jsou atomy (z hlediska syntaxe nedělitelné) –

symboly (posloupnost alfanumerických znaků, včetně některých speciálních: ! $ % & * + - . / : < = > ? @ ^ _ ~).

Symbols are objects whose usefulness rests on the fact that two symbols are identical (in the sense of eqv?) if and only if their names are spelled the same way. –

číselné literály například: 2, -3, 2.5, 2.5e3, 2/3, 2+3i, #b10010, #x10FE

Atomy II –

řetězcové literály (v uvozovkách)

–

znakové literály (#\a, #\space, #\newline)

–

boolovské literály (#t, #f)

–

prázdný seznam - označovaný literálem ()

–

vektory a porty (pozornost jim budeme věnovat později)

Tečka-dvojice ●

z atomů lze budovat složitější struktury pomocí tzv. tečky-dvojice [dotted-pair], což je uspořádaná dvojice výrazů

( atom . atom ) např. ( 2 . "dvě"), ( single . #f) ●

tečka-dvojice lze samozřejmě rekurzivně vnořovat a tak lze representovat binární stromovou strukturu ((2 . 3) . (5 . (6 . 8))) 2

3

5 6

8

Seznam ●

●

pomocí rekurzivních tečka-dvojic jsou ve Scheme representovány i seznamy seznam tvořený prvky p1,p2, ... pn lze zapsat (p1 . (p2 . ( ... (pn . () ) ... ))) resp. i jednodušeji: (p1 p2 ... pn)

p1 p2 pn

()

Příklad seznamu ●

příklad víceúrovňového seznamu ( (a b) c (c) () )

c

a b

= (pomocí tečka dvojic) ((a . (b . ())) . (c . ((c . ()) . (() . ()))))

()

c

()

()

()

Shrnutí syntaxe ●

●

data zpracovávaná jazykem Scheme mají podobu tzv. s-výrazů [symbolic expression] s-výraz je: –

atom (symbol nebo literál)

–

tečka-dvojice = uspořádaná dvojice s-výrazů, která může být zapsána jako: ● ●

●

přímý (tečkový) zápis (s-výraz . s-výraz) seznamový zápis [jen struktury, jejichž listový prvek nejvíce vpravo je prázdný seznam] smíšený zápis (např. (2 3 . 5)), málo užíván (je však někdy vidět jako chybný výstup)

Vyhodnotitelné s-výrazy ●

●

určitá podmnožina s-výrazů je vyhodnotitelná jako program (tyto s-výrazy jsou označovány jako e-výrazy nebo jako form) při vyhodnocení se kromě syntaxe projevuje i sémantika (která, je odlišná od elementární sémantiky s-výrazů) (+ 2 3) –

základní sémantika: seznam o třech prvcích (z nichž první je symbol, další dva číselné literály)

–

eval-sémantika: sečtení dvou čísel (výsledek je hodnota 5) . První prvek seznamu je symbol vázaný na funkci sčitání, další dva jsou parametry)

Vázání ●

pro vyhodnocovací sémantiku (eval-sémantiku) je typické, že symboly neoznačují sami sebe, ale hodnoty které jsou na ně vázány (symbol je pouze referent jiné hodnoty) x

10

hobit

Frodo

+

stroj. kód pro sčítání

ostatní typy atomů (literály) v zásadě označuji sami sebe, resp. (přesněji) odkazují na na pevně vázanou hodnotu (literál je totiž také druhem symbolu a nikoliv přímo hodnota). Vazbu literálu není nutné definovat, nelze ji změnit (symbol 3 nemůže odkazovat na hodnotu 2), ale více různých symbolů může odkazovat stejnou hodnotu např. 200.0 a 2e2)

Prostředí ●

●

●

jako prostředí [environment] je ve Scheme označována množina aktuálních vazeb (užívá se i označení (aktuální) svět [world] po spuštění interpretu nebo překladače již existuje globální prostředí, v němž jsou navázány základní funkce na standardní symboly (např. základní aritmetické operace) vazby v globálním prostředí jsou určeny standardem jazyka (a tvoří tak nejmenší společný základ všech programů ve Scheme.

Vyhodnotitelné výrazy I ●

vyhodnotitelné atomy nejjednodušší vyhodnotitelné výrazy, vyhodnotí se na hodnotu spojenou se symbolem (= musí být předem navázán) resp. s literálem příklad: 2, 2+3i, +, sin

●

volání funkce syntakticky se jedná o seznam, v němž je prvním prvkem výraz, jenž je vyhodnocen na funkci (typicky symbol vázaný na funkci), další prvky jsou případné parametry (musí to být vyhodnotitelné výrazy). Vyhodnocují se náhodném pořadí (resp. paralelně) příklad: (sin 2) , (+ 2 3), (= (sin 3) (cos (+ 2 3))

Vyhodnotitelné výrazy II ●

speciální formy syntakticky se jedná opět o seznamy první prvek určuje sémantiku speciální formy (má podobný význam jako symbol funkce) ostatní parametry se vyhodnocují podle speciálních pravidel (některé nemusí být vůbec vyhodnoceny a jsou interpretována jako data, resp. jsou vyhodnoceny v přesně definovaném pořadí) některé jsou vestavěné, jiné jsou definovány pomocí tzv. maker. příklad: (if (< a b) 0 1), (begin (display a) (display b))

Základní speciální formy ●

define = váže symbol na hodnotu (mění prostředí) (define x 2) , naváže hodnotu symbolu 2 (paměťová representace dvojky) na symbol x první parametr (zde x) není vyhodnocen (je interpretován jako datový s-výraz)

druhý parametr vyhodnocen je (zde 2) ●

quote = nevyhodnocuje svůj první operand (umožňuje tak používat symboly a tečka-dvojice jako data uvnitř programů), srovnej podobné využití uvozovek v textu (např. slovo "je" je sloveso)

(quote a), (quote (a b)), (quote 2) [zbytečné] lze zkrátit na 'a, '(a b), '2 (zbytečné)

Funkce nad tečka-dvojicemi ●

●

●

car (první část dvojice): cons -> * (car '(a . b) ) → a cdr (druhá část dvojice): cons -> * (car '(a . b) ) → b cons (spojí dva s-výrazy do tečka dvojice) (cons 'a 'b) → (a b) názvy funkcí jsou klasické, převzaté z Lispu a souvisí s instrukčním souborem prvé lispovské platformy.

angl. výslovnost je /ˈkɑr/, resp . /ˈkʌdər/ or /ˈkʊdər/

Funkce nad seznamy ●

●

●

nad seznamy se používají stejné funkce jako nad tečkadvojicemi, je však nutné si zapamatovat jejich speciální (odvozenou) sémantiku car = první člen seznamu (head) (car '(a b)) → a cdr = seznam bez prvního prvku (zbytkový seznam, tail) (cdr '(a b)) → (b) nikoliv pouhé b !! (car (cdr '(a b)) → b (druhý člen), lze krátit na (cadr '(a b))

●

cons = přidání nového prvku zleva (na první pozici) (cons 'a '(b c)) → (a b c) přidání prvku zprava (na konec) není pomocí cons možné (cons '(a b) 'c) → ((a b) . c) což není (a b c) !!!

Seznamové operace (strom) ●

základní seznamové operace lze snadno znázornit na stromové representaci daného seznamu (důležité).

(cdr list)

(cadr list)

c

a

(car list) (caar list)

b

() (cddr list)

(cdar list)

c (cdaddr list)

()

()

()

Funkce nad čísly ●

většina funkcí nad čísly je vázána na běžně používané symboly. Pozor však na prefixovou notaci (volání začíná závorkou a symbolem funkce). Je to nezvyklé, ale nemusíte si pamatovat žádné priority.

(sin (+ 2 x (* 3 y (sqrt z)))) použít lze i relační operátory (=, <, >, >=), zbytek pod dělení (modulo, remainder), běžné transcendentální funkce, konverze (number->string, string->number), apod. Viz Revised^5 Report 6.2.

Predikáty ●

jako predikáty se označují funkce vracející logické hodnoty. Pro predikáty se používají symboly zakončené otazníkem (úzus)

predikáty shody eq? = porovnání symbolů (eq? 'a 'a) → #t, (eq? 200.0 2.0e2) → #f (!, obecně nedef.)

eqv? = hodnotové porovnání (mělké, u seznamů umístění) (eq? 200.0 2.0e2) → #t (eqv? '(1 2) '(1 2)) → #f (!) ale (define x '(1 2)) (eqv? x x) → #t

equal? = hodnotové porovnání (hluboké) (equal? '(1 2) '(1 2)) → #t

Klasifikační predikáty ●

klasifikace podle datového typu hodnoty number?, complex?, real?, string?, symbol?, boolean?, pair?, char?, procedure?

●

detailnější klasifikace null? (prázdný seznam), list? (libovolný seznam), even? (sudé číslo), zero? (nula), char-alphabetic?, apod.

Lambda forma ●

●

lambda speciální forma (λ-forma,nepřesně lambda funkce) umožňuje vytvářet hodnoty typu funkce matematická definice funkce

jméno funkce

vázané proměnné (vazba je lokální)

f(x, y) = x + y2 poziční pojmenované parametry (důležitá je pozice)

při definici funkce jako hodnoty není důležité jméno nově vytvářené funkce (= funkce je anonymní) (lambda (x, y) (+ x (* y y)) → funkce (shodná s f)

Pojmenované funkce ●

lambda formu lze využít jako první prvek v zápisu volání funkce: ((lambda (x) (* x x)) 2) → 4

pokud je však funkce využita vícekrát je lepší ji navázat na (volný) symbol: (define sqr (lambda (x) (* x x))) (sqr 2) tento zápis se používá ve Scheme velmi často (programy a knihovny jsou tvořen definicemi funkcí) a proto pro něj existuje syntaktická zkratka: (define (sqr x) (* x x))

Lokální prostředí ●

●

●

při vyhodnocování těla lambda formy (ke které dochází, až při volání příslušné funkce) jsou e-výrazy vykonávány v tzv. lokálním prostředí lokální prostředí = prostředí v lexikálním rozsahu [scope] definice funkce + vazby parametrů důležité je, že lokální prostředí je dáno prostředím v lexikálním rozsahu definice (lexikální vazba) nikoliv v okamžiku volání funkce (dynamická vazba)

(define x 'global) (define printX (lambda () (display x))) (define testWithX (lambda (x) (printX))) (define x 'new-global) (testWithX 'local) → new-global (!!!)

Lexikální vers. dynamická vazba ●

●

●

lexikální vazba je typická pro imperativní (algolské) jazyky (např. C, C# atd.). Je navíc přehlednější pro programátory (kolize identifikátorů jsou méně časté) na druhou stranu komplikuje představu (a implementaci) vazby. Symbol může mít v jednom okamžiku více navázaných hodnot (pro každý lexikální rozsah nejvýše jednu) dynamická vazba byla typická pro původní Lisp, dnes je podporována jen jako specializovaná varianta v několika málo jazycích (Common Lisp, Perl)

Dynamická vazba v Perlu $x = "global"; sub printX () { print $x; } sub testWithX ($) { local $x = shift; #prevzeti parametru printX; } $x = "new-global"; testWithX("local"); print "\n"; print $x; #pro kontrolu (globalni x nezmeneno)

Uzávěr ●

použití lexikální vazby však vede k zajímavému efektu, který lze nejsnadněji ilustrovat u funkcí vracející nově vytvořenou (anonymní) funkci

(define novyVypisovac (lambda (text) (lambda () (display text));vraci anon. fci )) (define pozdrav (novyVypisovac "ahoj")) (pozdrav) → vypíše "ahoj" Nově vytvořená (a následně pojmenovaná) funkce v sobě totiž uzavírá prostředí lexikálního rozsahu, v němž byla definována (které by zde jako lokální zaniklo tj. byly by uvolněny i vázané hodnoty parametrů ).

Funkce + prostředí lexikálního rozsahu = uzávěr [closure]

Uzávěr II ●

●

uzávěry vznikají v případě, že tělo funkce má tzv. volné symboly (tj. symboly na které nejsou vázány parametry lambda formy). Užitečné jsou především uzávěry, vzniklé z lokálního prostředí (umožňuji totiž generovat uzávěry s různými vazbami na požádání) uzávěry hrají důležitou roli ve funkcionálním programování, neboť umožňují vytvářet funkce spojené se svými daty (ty se pak nemusí předávat jako parametry). V zásadě se jedná o OOP objekt naruby (u něj jsou naopak data spojena s metodamifunkcemi)

Uzávěry v Boo ●

●

většina moderních jazyků, podporujících funkce jako first-class hodnoty, podporuje i uzávěry (např. Python, Boo, Perl, Smalltalk, Rubby [zde jsou zvlášť důležité]). Zápis v Boo:

def novyVypisovac (text as string): return { print text; } pozdrav = novyVypisovac("ahoj") pozdrav()

Mechanismus je tedy stejný jako u Scheme (syntaxe je však převzata z Pythonu)

Uzávěry v C# ●

●

●

některé další jazyky podporují uzávěry omezeně (pouze pro speciální třídu vykonávatelných entit). Například v C# jsou uzávěry podporovány pouze u anonymních delegátů (od verze 2.0, verze 3.0 přináší jednodušší syntaxi) do (uzavřeného) lexikálního prostředí zde kromě lokálních proměnných patří i objekt this (je-li uzávěr vytvořen v instanční metodě)

C# - ukázka using System; delegate void Action(); class Program { static Action NovyVypisovac(string text) { return delegate () {Console.WriteLine(text);}; } public static void Main() { Action pozdrav = NovyVypisovac("ahoj"); pozdrav(); } }

Uzávěry ve Smalltalku ●

●

v objektovém jazyce Smalltaku, hrají anonymní funkce a uzávěry centrální roli (nazývají se zde bloky) pomocí uzávěrů jsou implementovány i tak základní konstrukce jako podmíněné vykonávaní nebo cykly (částečně se tomu blíží jazyk Ruby, který však podporuje i běžné procedurální konstrukce)

num > 5 ifTrue: [num:=1] ifFalse: [num:=num+1]. oba bloky jsou parametry metody ifTrue:ifFalse, která je volána na boolovský objekt získaný vyhodnocením (num>5). Vykonán je pouze jeden z nich.

1 to: 5 do: [num| transcript print:num] zde je adresátem hlavní metody do: objekt rozsahu (1 to: 5)

Uzávěry v C++ ●

●

v jazyce C++ nejsou (prozatím) uzávěry podporovány, lze je však funkčně nahradit pomocí objektů (nesoucích uzavřené informace) implementujících operátor volání funkce (tj. i syntakticky napodobují uzávěry) v nově navrhovaném standardu jazyka (C++ 0X), jsou však uzávěry přímo podporovány (v několika verzích). http://en.wikipedia.org/wiki/C++0x#Lambda_functions_and_expressions

(pojetí je však poněkud netradiční, ale odpovídá imperativnímu charakteru jazyka)

Currying ●

standardní zápis lambda funkce např. (lambda (x, y) (+ x (* y y)) (zde s uvedením dvou pozičních parametrů) lze přepsat do tvaru (např.):

(lambda (x) (lambda (y) (+ x (* y y)))) jenž používá jen funkce o jednom parametru a odpovídá tak přímo zápisu λ-kalkulu: λx. λy. x + y2 sémantika: vnější funkce (s parametrem x) je aplikována na první parametr, a vrací další funkci-uzávěr (s parametrem y), která je následně aplikována na druhý parametr. Převod funkce s více parametry na funkce s jedním parametrem se nazývá currying. Má velký význam teoretický, a je plně podporován v Haskellu.

Podmínky I ●

●

Ve funkcionálních jazycích existují konstrukce pro podmíněné vyhodnocování (obdoba příkazu if) klasická (lispovská) speciální forma pro podmíněné výrazy je cond (a je opravdu speciální)

(cond (p1 e1) (p2 e2) ... (pn en) (else en+1) )

Nejdříve jsou vyhodnocovány postupně výrazy (podmínky) p1 až pn. Pokud je podmínka pi pravdivá pak je vyhodnocen výraz ei a vyhodnocení cond končí (hodnotou cond je hodnota ei) (= vykoná se pouze první větev s pravdivou podmínkou). Symbol else je (pouze zde) synonymem pro #t, to jest poslední (nepovinná) podmínka je splněna vždy (není-li pravdivá žádná z předchozích podmínek en+1 se vyhodnotí vždy.

Podmínky II (define (factorial n) (cond ( ( = n 1) 1) ( else (factorial (- n 1) ) )

Kromě cond(ition) existuje i speciální forma if, která odpovídá ternárnímu operátoru jazyka C (Java, C#) (if podmínka true-výraz false-výraz) nejdříve se vyhodnotí podmínka, podle výsledků pak jeden z následujících výrazů. Forma if je však méně pružná a není ani výrazně přehlednější (⇒ nebudu ji užívat)

Rekurze ●

●

rekurze hraje ve funkcionálním programování klíčovou roli, neboť kromě běžných rekurentně orientovaných algoritmů se rekurze používá jako náhrada cyklů velmi významná je především tzv. tail-rekurze, kdy je poslední vyhodnocovanou operací funkce rekurzivní volání, tj. na výsledek rekurzivně volané funkce se již neaplikuje žádná další operace (výše uvedený faktoriál je tohoto typu) Tail-rekurzi lze v imperativním jazyce snadno (ručně) přepsat na iteraci, v funkcionálním jazyce to za Vás udělá interpret či kompilátor. Paměťová náročnost se sníží z O(n) na O(1).

Rekurze II (define (spoj s1 s2) (cond ((null? s1) s2) (else (cons (car s1) (spoj (cdr s1) s2))) ) )

Tento rekurzivní algoritmus není tail-rekurze (na výsledek je volána operace cons). Je však typický, neboť rozkládá operaci na dvě fáze: 1) nejdříve se při vnořování rekurze (tj. volání dalších rekurzivních instancí funkce) rozkládá (pomocí car,cdr původní seznam, zde s1). Rekurzivní volání se volá vždy na zbytkový tj. menší podseznam) 2) při výstupu (vynořování), tj. návratu z rekurzivních volání se konstruuje nový seznam

Rekurze III ●

graf (rozpis) volání

(spoj '(a b) '(c))

vnořování / rozklad

('a . (spoj '(b) '(c)) ) ('a . ('b . (spoj '() '(c)) ) ) ('a . ('b . '(c) ) )

substituce podle koncové podmínky

('a . '(b c) ) '(a b c)

vynořování / konstrukce nového seznamu

Speciální forma and a or ●

●

funkce and resp. or by mohly být definovány jako běžné funkce nad alespoň jednou logickou hodnotou. pro efektivnější vykonávání se však jedná o speciální formy se zkráceným vyhodnocováním (u neparalelní implementace s postupným vyhodnocováním)

(and p1 p2 ... pn) výrazy pi se vyhodnocují postupně. Je-li nějaký nepravdivý pak se vyhodnocení ukončí a funkce vrací #f, pokud jsou všechny pravdivé pak #t.

Speciální forma or je definována obdobně.

Příklad (and) (define test-leaf (lambda (tree predicate) (cond ((pair? tree) (and (test-leaf (car tree) predicate) (test-leaf (cdr tree) predicate) )

)

) ((null? tree) #t) (else (predicate tree)

))

Funkce zjišťuje, zda všechny (listové) prvky stromu tečka dvojic splňují daný predikát .Nezohledňuje přitom prázdné seznamy, což umožňuje použití funkce i pro (obecně víceúrovňové) seznamy. Predikát musí mít aritu 1.

Funkcionály ●

●

●

funkcionály resp. funkce vyšších řádů jsou funkce nad funkcemi (= funkce, jejichž parametry jsou další funkce) příkladem funkcionálu je i výše uvedená funkce testleaf (lze ji chápat jako funkci nad predikátem) nejobecnějším běžně používaným funkcionálem je skládání funkcí (samozřejmě obě aritou 1): (define (compose g f) (lambda (x) (g (f x))) )

Funkcionály nad seznamy ●

●

důležitou roli v praktickém programování ve Scheme hrají funkcionály pracující se seznamy. Tyto funkcionály umožňují stručnější zápis rozsáhlé třídy algoritmů. Obecně je lze používat pro různé druhy iterací, čímž se lze vyhnout explicitnímu použití rekurze (ta není eliminována, ale je skryta v kódu funkcionálů) mezi nejčastěji používané seznamové funkcionály patří: map, zip, fold, filtr.

Map ●

●

●

nejdůležitějším seznamovým funkcionálem je map (zkratka z anglického mapping) funkce (map f list), vytváří nový seznam, který je tvořen prvky seznamu list, na něž byla aplikována unární funkce f. funkce map může být také označována jako transform (C++), collect (Smalltalk), resp. Select (LINQ) x1

x2

x3

x4

x5

f

f

f

f

f

f(x1)

f(x2)

f(x3)

f(x4)

f(x5)

Zip ●

●

funkcionál (zip f list1 list2) vrací nový seznam, který vznikne aplikováním binární funkce f na (pozičně) si odpovídající prvky seznamu list1 a list. typické využití je například pro sčítaní dvou vektorů (číselných seznamů): (zip + v1 v2) x1

x2

x3

x4

x5

f(x1, y1) f(x2, y2) f(x3, y3) f(x4, y4) f(x5, y5)

y1

y2

y3

y4

y5

Foldr ●

●

funkcionál (foldr f seznam) přejímá binární funkci a seznam. Převede seznam na jedinou hodnotu, tím, že aplikuje binární funkci f mezi prvky seznamu. Lze jej přesněji definovat rekurzivně:

(define (foldr f list) (cond ((jednoprvkovy? list) (car list)) (else (f (car list) (foldr f (cdr list)))) ) ))

foldr[+, (1 2 3)] = 1 + foldr[+, (2 3)] = = 1 + (2 + foldr[+,(3)]) = (1 + (2 + (3)) = 6 = suma[(1,2,3)] foldr = right fold = fold from right = sviň (slož) zprava

Foldr II ●

funkci foldr lze zobecnit přidáním dalšího parametru — počáteční hodnoty: (foldr f initval list)

●

pokud je tato hodnota zadána, pak se první akumulační operace provede mezi poslední hodnotou seznamu a počáteční hodnotou f

(foldr f p (x1 x2 x3 x4)) ●

x1 x2 x3 x4

f

p

zobecnění zjednoduší implementaci, vždy lze nalézt ekvivalentní volání (např. (foldr + 0 seznam) pro sumu), ale především rozšiřuje možnosti použití:

(foldr (lambda (p s) (cons (cons p s) '())) '() '(a b c d))

Foldl ●

sesterskou funkcí funkce foldr je funkce foldl (left fold), která při výpočtu postupuje z opačné strany (zleva). Nejdříve aplikuje akumulační funkci na počáteční hodnotu a první prvek hodnotu, potom na mezivýsledek a druhý prvek, atd.

(foldl + 0 '(1 2 3)) ≈ (((0 + 1) + 2) + 3) pro komutativní operace je foldl ekvivalentní funkci foldr (zde doporučuji používat foldl), jiná situace je u nekomutativních operací: (foldl (lambda (list item) (cons item list)) '() '(a b c))

Fold v programovacích jazycích ●

●

pro skupinu funkcí fold používají se i alternativní názvy: reduce (Python, JavaScript), accumulate (C++), Aggregate (LINQ), resp. inject (Rubby, Smalltalk?). Většinou se jedná o levou variantu a ve většině jazyků jsou k dispozici i ve tvaru s počáteční hodnotou. ve Scheme jsou v základní knihovně dispozici až od šesté revize (R6RS) pod jmény fold-right a fold-left (s počáteční hodnotou)

Filtr ●

funkcionál (filtr list predikát), vytváří nový seznam, v němž jsou jen prvky, pro něž je (unární) predikát pravdivý. (filtr number? '(a b 2 c)) → (2)

●

kromě jména filter (Haskell, Scheme R6RS, Python, JavaScript), se používají i varianty na remove-if (C++, CLisp), grep (Perl) resp. Where (LINQ)

Praktický příklad na funkcionály (define (prumer s) (foldr / 1 (foldr (lambda (x suma) (list (+ x (car suma)) (+ 1 (cadr suma)))) '(0 0) s)) )

výpočet pomocí: (/ (foldl + 0 s) (length s))

je také možný, vyžaduje však dvojí procházení seznamu (což zde nevadí)

Datové struktury I ●

●

v praktických programech se často vyskytuje požadavek na representaci strukturovaných údajů. Ty lze samozřejmě representovat i ve Scheme: seznamové (list-like) representace údaj je representován jako (nehomogenní) seznam přímých dat, význam údajů je dán pouze pozicí ("Frodo Pytlík" hobit #t 50)

●

slovníková (directory-like) representace údaj je representován jako seznam dvojic: identifikátor, hodnota (na pořadí nezáleží) ((jmeno . "Smíšek") (druh . hobit) (drzitel-prstenu . #f) (vek . 30))

Datové struktury II ●

●

●

explicitní využívání identifikátorů je vhodnější pro rozsáhlejší struktury (odpovídá slovníkové implementaci tříd v jazycích jako je JavaScript, Perl, Python)

pro přístup k seznamové representaci je možno použít indexaci resp. cad{0,3}r funkce pro přístup ke slovníkové representaci je nutno použít uživatelské funkce (define (field key dict) (cdar (filtr (lambda (pair) (eq? (car pair) key)) dict)) )

Funkcionály nad strukturami ●

●

pro zpracování seznamů struktur je vhodné používat funkcionály úkol: nalézt průměrný věk držitelů prstenu v seznamu postav Pána prstenů (se slovníkovou representací) (define (field-getter key) (lambda (dict) (field key dict)) ) (prumer (map (field-getter 'vek) (filtr (field-getter 'drzitel-prstenu) postavy ) ) )

●

funkce field-getter vrací uzávěr pro získaní pole se seznamu.

Funkcionály v Boo ●

funkcionály lze použít i v Boo. Příklad ukazuje výpočet hodnoty polynomum jenž je založen na Hornerově schématu (a užívá pomocného uzávěru)

def horner(x as double) as BinOp: return {acc as double, next as double | return x*acc + next} reduceWith(horner(2), 2, 3, 4) //foldr nebo foldl

kde reduceWith je uživatelská funkce, specializovaná pro zipovací funkce typu (double, double) → double [statické typování znevýhodňuje použití obecných funcionálů].

callable BinOp(x as double, y as double) as double def reduceWith(op as BinOp, *xs as (double)) as double

Funkcionály v C# (Linq) ●

nový mechanismus Linq přináší sílu funkcionálů i do jazyka C# (a to přímo na úrovni jeho syntaxe)

var result = postavy.Where(p => p.DrzitelPrstenu) .Select(p => p.Vek).Average(); OOP syntax var result = (from p in postavy where p.DrzitelPrsten query comprehension select p.Vek).Average(); syntax (SQL like)

Funkcionály v C# (II) ●

funkcionály lze v C# aplikují nad libovolným typem podporujícím generické rozhraní:

IEnumerable ●

●

vykonávání je odložené (deffered) resp. lenivé (lazy), tj. další prvky jsou z enumerátoru (iterátoru) převzaty až v okamžiku, kdy jsou potřeba některé funkcionály tak lze volat i na nekonečné (neohraničené) iterátory (viz později Haskell) integers.First(x => DokonaleCislo(x)) -- integers může být neohraničený iterátor

Scheme jako imperativní jazyk ●

●

●

●

●

●

Scheme není ve skutečnosti čistě funkcionální jazyk, ale podporuje i některé imperativní konstrukce: funkce s vedlejšími efekty (typicky IO funkce) speciální formu begin (posloupnost postupně vykonávaných funkcí) resp. podobné rozšíření formy lambda. přiřazení set! (mění se obsah paměťového místa ne vazba) cyklus do (se změnou stavu), for-each (podobně jako map ale pro postranní efekty) přímé modifikace tečka dvojic (set-car!, set-cdr!)

Scheme jako imperativní jazyk II ●

●

imperativní konstrukce (především ty tvrdé (hard), označené v identifikátoru vykřičníkem jsou sice přípustné, ale podobně jako goto ve strukturovaných jazycích mohou zcela eliminovat výhody funkcionálního zápisu. na druhou stranu mohou program podstatně zrychlit a zmenšit jeho paměťovou náročnost (významné je např. menší zatížení garbage kolektoru)

Pokračování (continuation) ●

pokračování je hodnota zapouzdřující aktuální stav výpočtu (prostředí + rámce vykonávaných funkcí).

pokračování – do hodnoty zabalená budoucnost ●

●

umožňuje ve Scheme implementovat skoky (nebezpečné), výjimky (užitečné), resp. dokonce korutiny (povznášející) pokračování jsou ve Scheme dostupná pomocí funkce call-with-current-continuation. Běžně se používá zkratka call/cc (není podporována ve standardním globálním prostředí)

Call-with-current-continuation ●

●

●

v místě, v němž si chceme zapamatovat stav provádění (k němuž se hodláme vrátit), musí být volána funkce call-with-current-continuation. tato funkce má jediný parametr, jímž je funkce, které je po vytvoření hodnoty pokračování předáno řízení a jako parametr je jí předáno pokračování (= je volána with current continuation, kde continuation je parametr) uvnitř této funkce můžeme použít pokračování jako funkci. Po jejím vyvolání s jedním parametrem, je obnoven stav v okamžiku volání funkce call-withcurrent-continuation a ta se následně ukončí s hodnotou parametru předaného pokračování.

Pokračování (return) ●

nejjednodušší použití pokračování je implementace předčasného ukončení funkce (s přenosem návratové hodnoty tj. return)

(define (search wanted? lst) (call/cc (lambda (return) (for-each (lambda (element) obnovení (if (wanted? element) pokračování (return element))) normální lst) návrat

))

#f)

Pokračování – vícenásobné vyvolání ●

●

pokračování, která jsou obnovitelná pouze z vnořených funkcí (a pouze jednou) se označují jako úniková (escape) Scheme však nabízí pokračování, která lze obnovit z libovolného místa programu a to i vícenásobně.

(define inc #f) (+ 1 (call/cc (lambda (c) (set! inc c) 1))) ;; vrátí 2 (inc 2) ;; obnoví vykonávání v místě pokračování a vrátí 3 (inc 3) ;; znovu obnoví a vrátí 4 příklad je umělý (inkrementaci lze definovat mnohem snadněji a elegantněji) je to však první krok ke korutinám.

Korutiny ●

●

●

●

korutina = rutina, která má více vstupních a výstupních bodů zpracování korutiny může být přerušeno (ve výstupním bodě) a řízení předáno jiné korutině. poté může být provádění korutiny opět obnoveno (nejčastěji ve stejném bodě, kde bylo přerušeno) korutiny jsou implementací kooperativních vláken (threadů)

Pokračování (korutiny) (define continuation #f) (define (coroutine list) (for-each (lambda (item) (display item) (set! continuation (call/cc (lambda (c) (continuation c)))) ) list )) (set! continuation (lambda (c) (set! continuation c) (coroutine '(a b c)))) ;;počáteční nastavení (coroutine '(1 2 3)) → 1a2b3c

Korutiny v C# ●

jazyk C# poskytuje jen omezenou podporu korutin. Ty jsou navíc primárně specializovány pro jediný účel: vytváření enumerátorů (přesněji generátorů) public static IEnumerable integers () { int i = 0; while(true) //nekonečný generátor yield return ++i; }

●

korutiny lze řídit (opětně volat) jen prostřednictvím metody Next rozhraní IEnumerable (to je neomezuje, jen je to nepohodlné), nemohou být přerušeny v podřízené rutině a nemohou jim být opakovaně předávány parametry (jen při jejich vytváření, tj. při prvním volání), viz http://www.python.org/dev/peps/pep-0342/ (řešení pro Python)

Scheme - striktní jazyk ●

●

●

●

●

jazyk Scheme je striktní tj. před voláním funkce jsou všechny její parametry vyhodnoceny (i když to nemusí být pro další výpočet nutné) striktní jsou svou podstatou všechny imperativní jazyky opakem striktního vyhodnocení je lenivé [lazy] vyhodnocení lenivé vyhodnocení je u většiny jazyků (včetně Scheme) omezeno na některé operátory (např. logické) ve funkcionálních jazycích lze lenivé vyhodnocení implementovat pomocí anonymních funkcí, kdy je výpočet zapouzdřen pomocí lambda formy. Musí to však být explicitním zápisem a je to nepraktické.

Striktní vyhodnocení ●

●

striktní vyhodnocení může snížit efektivitu vykonávání může však ovlivnit i výsledek programu následující (umělý) příklad ukazuje případ, kdy striktní vyhodnocení můžeš vést k zbytečné chybě.

(define (getEven x y) (cond ((even? x) x) ((even? y) y) (else (+ x y)) )) (getEvent 4 (/ 1 0)) → chyba /: division by zero při lenivém vyhodnocení chyby nevznikne (v opačném gardu parametrů však ano)

Přísliby ●

problém se striktním vyhodnocením lze řešit pomocí explicitního obalení parametru anonymní funkcí [zkuste!]

snadnější je použití tzv. příslibů, což je prostředek vyšší úrovně (implementovaný pomocí anonymní funkce) (delay e-výraz) = vrací příslib vyhodnocení e-výrazu (ale nevyhodnocuje jej) (force příslib) = vyhodnocuje příslib (define (getEven x y) (cond ((even? x) x) ((even? y) (force y)) (else (+ x (force y))) ))

(getEven 4 (delay (/1 0)) → 4 (getEven 4 (delay 5)) → 4 (getEven 4 5) ? (getEven 3 5) ?

Proudy I ●

●

●

●

využití příslibů pro funkce nad jednoduchými hodnotami je omezené (a nepříliš transparentní) hlavní oblastí využití příslibů je konstrukce neohraničených seznamů tzv. proudů. Pomocí těchto seznamů lze representovat např. nekonečné posloupnosti čísel ale i řetězců (např. potenciálně nekonečné regulární jazyky) nekonečnost je samozřejmě jen potenciální, v realitě se pracuje jen s konečným (malým) počtem prvků programy se však výrazně zjednoduší, neboť odpadá např. nutnost testování konce seznamu a i nad neohraničenými posloupnostmi lze aplikovat funcionály (i když ve speciální proudově orientované syntaxi)

Proudy II ●

pro práci s proudy slouží dvojice speciálních verzí funkcí cons a cdr (car lze použít beze změny):

(define-syntax stream-cons stream-cons musí být definován jako (syntax-rules () makro tj. jako substituce s-výrazů ((cons-stream x y) (jinak by při aplikaci došlo k nekonečné (cons x (delay y))))) rekurzi) (define (stream-cdr s) (force (cdr s))) pomocí těchto funkcí, lze např. definovat proud všech celých čísel od jisté hodnoty: (define (rangeFrom x) (stream-cons x (rangeFrom (+ x 1)))) (rangeFrom 5) → (5 . ) (stream-cdr (rangeFrom 6)) → (6 . )

Proudy III ●

vypsání proudu není příliš zajímavé, lze si však např. vynutit (=force) vypsání prvních n členů.

(define (take n s) (cond ((= n 1) (list (car s))) (else (cons (car s) (take (- n 1) (stream-cdr s)))) )) na proudy však lze aplikovat i speciální verze funkcionálů: (define (filter-stream pred lst) (cond ((null? lst) '()) ((pred (car lst)) (stream-cons (car lst) (filter-stream pred (stream-cdr lst)))) (else (filter-stream pred (stream-cdr lst)))))

Proudy IV ●

lze tak snadno definovat např. sudá přirozená čísla

(define even-ints (filter-stream even? (rangeFrom 2)) pomocí Eratosthenova síta lze definovat i proud prvočísel: (define (sieve stream) (stream-cons (car stream) musí se dodefinovat (sieve (filter-stream (lambda (x) (not (divisible? x (car stream)))) (stream-cdr stream))))) (define primes (sieve (rangeFrom 2))) definice je to elagantní, ale