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)) =⇒ #<promise>

(define p (delay (map -’(1 2 3 4)))) p =⇒ #<promise>

(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 =⇒ #<promise>

.

.

. (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 ¹⁾

(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)) #<procedure> (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 ²⁾

(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 ³⁾ (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 ⁴⁾) (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 . #<promise>)

(display-stream s) =⇒ #<stream (1 2 3 4)>

(display-stream s 2) =⇒ #<stream (1 2)>

(stream-length s) =⇒ 4

(display-stream (stream-map -s) 2)

=⇒ #<stream (-1 -2)>

(display-stream (stream-map + s s s))

=⇒ #<stream (3 6 9 12)>

(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 . #<promise>)

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 . #<promise>)

(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 . #<promise>)

(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 ⁵⁾ (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 ⁶⁾ (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