KATEDRA INFORMATIKY, PRÍRODOVEDECKÁ FAKULTA UNIVERZITA PALACKÉHO, OLOMOUC PARADIGMATA PROGRAMOVÁNÍ 2 PRÍSLIBY A LÍNÉ VYHODNOCOVÁNÍ Slajdy vytvorili Vilém Vychodil a Jan Konecný (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 1 / 24 Prísliby a líné vyhodnocování Základní myšlenka místo vyhodnocení daného výrazu pracujeme s príslibem jeho budoucího vyhodnocení príslib = nový typ elementu (element prvního rádu) Co je potreba k tomu, aby to fungovalo: 1 k dispozici je spec. forma (nejcasteji zvaná delay), která pro daný výraz vrací príslib jeho vyhodnocení 2 k dispozici je procedura (nejcasteji zvaná force), která pro daný príslib aktivuje výpocet a vrátí hodnotu vzniklou vyhodnocením prislíbeného výrazu Líné vyhodnocování: vyhodnocování založené na príslibech nekdy se nazývá «call by need» (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 2 / 24 Príklad zamýšleného použití (delay (+ 1 2)) =⇒ # (define p (delay (map -’(1 2 3 4)))) p =⇒ # (promise? p) =⇒ #t (force p) =⇒ (-1 -2 -3 -4) Poznámky: delay nemuže být z principu procedura, protože chceme, aby se prislíbený výraz vyhodnotil až pri aktivaci pomocí force pri líném vyhodnocování dochází k propagaci chyb (chyba se projeví „na jiném míste“ než „kde vznikla“) (define p (delay blah)) probehne bez problému p =⇒ # . . . (force p) =⇒ CHYBA: blah nemá vazbu (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 3 / 24 pomocí príslibu je možné „odložit casove složitý výpocet na pozdeji“ a aktivovat jej, až je skutecne potreba jej provést Modelový casove nárocný výpocet: (define fib (lambda (n) (if (<= n 2) 1 (+ (fib (n 1)) (fib (n 2)))))) Príklad použití (define p (delay (fib 30))) probehne okamžite . . . (force p) aktivace výpoctu (prodleva) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 4 / 24 Pri použití príslibu vyvstávají otázky spojené s vedlejším efektem. Príslib výrazu, který má vedlejší efekt: (define p (let ((i 0)) (delay (begin (set! i (+ i 1)) i)))) Dvojí aktivace výpoctu: (force p) =⇒ 1 (force p) =⇒ ??? Možnosti: 1 2 druhá aktivace (force p) vrací 1 druhá aktivace (force p) vrací 2, tretí vrací 3,... Ukážeme, jak implementovat líné vyhodnocování umožnující obe varianty. (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 5 / 24 Implementace príslibu a líného vyhodnocování prísliby lze plne implementovat pomocí procedur vyšších rádu, maker a vedlejších efektů Základní myšlenka: pri vytvárení procedur (vyhodnocováním -výrazu) nedochází k vyhodnocování tela nove vznikajících procedur k vyhodnocování tela procedur dochází až pri jejich aplikaci nabízí se tedy: vytvorit prísliby pomocí procedur Vysvetlující príklad (lambda () (+ 1 2)) # (define p (lambda () (+ 1 2))) náš príslib (p) aktivace (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 6 / 24 Implementace príslibu a líného vyhodnocování jednodušší verze pri každé aktivaci príslibu je prislíbený výraz vždy vyhodnocen vytvoríme makro freeze („zmraz“) a proceduru thaw („roztaj“) ;; speciální forma freeze (define-macro freeze (lambda exprs ‘(lambda () (begin ,@exprs)))) ;; procedura thaw (define thaw (lambda (promise) (promise))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 7 / 24 Príklad vytvorení príslibu (define p (let ((x 10)) (freeze (display "Hodnota: ") (display x) (newline) (set! x (+ x 1)) (list x (* x x))))) Príklad aktivace príslibu (thaw p) =⇒ (11 121) (thaw p) =⇒ (12 144) (thaw p) =⇒ (13 169) · Príslib jako soucást složitejšího výrazu (reverse (thaw p)) =⇒ (225 14) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 8 / 24 Implementace príslibu a líného vyhodnocování složitejší verze pri první aktivaci príslibu je výsledek vyhodnocení prislíbeného výraz zapamatován (uvnitr príslibu) a pri každé další aktivaci príslibu je vrácena zapamatovaná hodnota prípadné vedlejší efekty se projeví jen pri první aktivaci vytvoríme makro delay a proceduru force Nejprve príklad použití: (define p (let ((x 10)) (delay (set! x (+ x 1)) (list x (* x x))))) (force p) =⇒ (11 121) (force p) =⇒ (11 121) · (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 9 / 24 Implementace príslibu a líného vyhodnocování Speciální forma delay (define-macro delay (lambda exprs ‘(let ((result (lambda () (begin ,@exprs))) (evaluated? #f)) (lambda () (begin (if (not evaluated?) (begin (set! evaluated? #t) (set! result (result)))) result))))) ;; procedura force (totéž co thaw) (define force thaw) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 10 / 24 Proudy (angl. Streams) proudy jsou nejcasteji používanou aplikací líného vyhodnocování neformálne: proudy jsou líne vyhodnocované seznamy konstruktor cons-stream a selektory stream-car a stream-cdr ;; Konstruktor proudu cons-stream je makro (define-macro cons-stream (lambda (a b) ‘(cons ,a (delay ,b)))) ;; selektor stream-car (vrat první prvek proudu) (define stream-car car) ;; selektor stream-cdr (vrat proud bez prvního prvku) (define stream-cdr (lambda (stream) (force (cdr stream)))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 11 / 24 Definice proudu prázdný seznam je proud; každý teckový pár (e . p), kde e je libovolný element a p je príslib proudu, je proud. ;; je stream prázdný? (define stream-null? null?) ;; predikát stream? (podle definice) (define stream? (lambda (elem) (or (null? elem) (and (pair? elem) (and (promise? (cdr elem)) (stream? (force (cdr elem)))))))) predchozí predikát stream? má nevýhodu: používá force (!) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 12 / 24 ;; slabší verze predikátu stream? ;; každý pár, jehož 2. prvek je príslib nebo () je stream (define stream? (lambda (elem) (or (null? elem) (and (pair? elem) (or (promise? (cdr elem)) (null? (cdr elem))))))) Pomocné procedury: ;; zobraz stream, nanejvýš však n prvních prvku (define display-stream (lambda (stream . n) · ;; odvozené selektory (define stream-caar (lambda (x) · . . . (define stream-cddddr (lambda (x) · (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 13 / 24 Procedury pro práci s proudy ;; délka proudu (define stream-length (lambda (stream) (if (stream-null? stream) 0 (+ 1 (stream-length (stream-cdr stream)))))) ;; mapování pres proudy (mapování pres jeden stream) (define stream-map2 (lambda (f stream) (if (stream-null? stream) ’() (cons-stream (f (stream-car stream)) (stream-map f (stream-cdr stream)))))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 14 / 24 Procedury pro práci s proudy ;; mapování pres proudy (obecná verze) (define stream-map (lambda (f . streams) (if (stream-null? (car streams)) ’() (cons-stream (apply f (map stream-car streams)) (apply stream-map f (map stream-cdr streams)))))) ;; konvertuj seznam na stream (define list->stream (lambda (list) (foldr (lambda (x y) (cons-stream x y)) ’() list))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 15 / 24 Procedury pro práci s proudy ;; vytvor konecný stream daných prvku (define stream (lambda args (list->stream args))) Príklady použití predchozích procedur: (define s (stream 1 2 3 4)) s =⇒ (1 . #) (display-stream s) =⇒ # (display-stream s 2) =⇒ # (stream-length s) =⇒ 4 (display-stream (stream-map -s) 2) =⇒ # (display-stream (stream-map + s s s)) =⇒ # (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 16 / 24 Všimnete si pri práci s proudy mají jednotlivé procedury „jinou odezvu“ výpocet je rízen daty, dochází k propagaci chyb Výsledek je vrácen okamžite (define fs (stream-map fib (stream 1 · 30 31 · 50))) fs =⇒ (1 . #) prístup ke dalším prvkum se bude postupne zpomalovat ukázka propagace chyb v proudech: (define s (stream 1 2 3 4 5 ’blah 6 7)) (define r (stream-map -s)) r =⇒ (-1 . #) (display-stream r 4) =⇒ (-1 -2 -3 -4) (display-stream r 6) =⇒ (-1 -2 -3 -4 -5 CHYBA (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 17 / 24 Úskalí ;; zdánlive funkcní verze ‘foldr’ pro proudy (define stream-foldr (lambda (f nil . streams) (if (stream-null? (car streams)) nil (apply f ‘(,@(map stream-car streams) ,(apply stream-foldr f nil (map stream-cdr streams))))))) ;; následující se nechová prirozene (stream-foldr (lambda (x y) (cons-stream (-x) y)) ’() (stream 1 2 3 ’blah 4)) =⇒ CHYBA: nelze aplikovat -na symbol blah Cekali bychom, že chyba se projeví až pri pokusu pristoupit ke 4. prvku výsledného proudu (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 18 / 24 Nová verze stream-foldr procedure „f“ bude predáván místo druhého argumentu jeho príslib procedura sama rozhodne, jak bude s príslibem nakládat ;; procedura stream-folder (define stream-foldr (lambda (f nil . streams) (if (stream-null? (car streams)) nil (apply f ‘(,@(map stream-car streams) ,(delay (apply stream-foldr f nil (map stream-cdr streams)))))))) (stream-foldr (lambda (x y) (cons-stream (-x) (force y))) ’() (stream 1 2 3 ’blah 4)) =⇒ (-1 . #) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 19 / 24 Další (užitecné) odvozené procedury ;; konverze proudu na seznam (define stream->list (lambda (stream) (stream-foldr (lambda (x y) (cons x (force y))) ’() stream))) ;; filtrace prvku proudu podle vlastnosti (define stream-filter (lambda (prop? stream) (stream-foldr (lambda (x y) (if (prop? x) (cons-stream x (force y)) (force y))) ’() stream))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 20 / 24 Nekonecné proudy a jejich implicitní definice Príklad (proud jednicek) ;; rekurzivní procedura bez limitní podmínky (define ones-proc (lambda () (cons-stream 1 (ones-proc)))) ;; nekonecný proud vytvorený voláním ones-proc (define ones (ones-proc)) ;; predchozí s použitím pojmenovaného let (define ones (let proc () (cons-stream 1 (proc)))) ;; implicitní definice proudu (define ones (cons-stream 1 ones)) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 21 / 24 Nekonecné proudy a jejich implicitní definice Príklad (proud prirozených císel) ;; rekurzivní procedura bez limitní podmínky (define naturals-proc (lambda (i) (cons-stream i (naturals-proc (+ i 1))))) ;; nekonecný proud vytvorený voláním naturals-proc (define naturals (naturals-proc 1)) ;; predchozí s použitím pojmenovaného let (define naturals (let iter ((i 1)) (cons-stream i (iter (+ i 1))))) ;; implicitní definice proudu (define naturals (cons-stream 1 (stream-map + ones naturals))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 22 / 24 Nekonecné proudy Nekonecný proud neformálne: „potenciálne nekonecná lineární datová struktura“ potenciálne nekonecná znamená: opakovaným použitím stream-cdr se nedostaneme na jejich konec v každém okamžiku pruchodu nekonecným proudem máme vždy k dispozici aktuální prvek a príslib pokracování proudu lze se na nej dívat jako na nekonecnou posloupnost elementu (ei)∞ =0, to jest e0, e1, e2;:::, en􀀀1, en, en+1;::. i v praxi se konstruuje rekurzivní procedurou bez limitní podmínky ;; proud hodnot (2i)∞ i=0 (define pow2 (let next ((last 1)) (cons-stream last (next (* 2 last))))) (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 23 / 24 Nekonecné proudy Formálne lze zavést jako limity prefixových generátoru Seznam r je prefix seznamu t, pokud lze t vyjádrit jako spojení r s nejakým seznamem l (v tomto poradí). Množinu seznamu S nazveme prefixový generátor, pokud 1 2 pro každé n ∈ N, systém S obsahuje seznam délky n; pro každé dva s, t 2S platí: bud s je prefix t, nebo t je prefix s. Nekonecný proud (príslušný prefixovému generátoru S) je element reprezentující posloupnost (ei)∞ =0, kde ei je element nacházející se na i-té i pozici libovolného seznamu s 2S majícího alespon i + 1 prvku. (KI, UP Olomouc) PP2, Lekce 6 Prísliby,streamy 24 / 24