KATEDR� INFORMATIKY� PÍRODOV…DECK� FAKULT� UNIVERZIT� PALACKÉHO� OLOMOU�

PARADIGMAT� PROGRAMOVÁN� � PROUD� � VYROVNÁVAC� PAM…�

Slajd� vytvo°il� Vilé� Vychodi� � Ja� Kone£n�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Implicitn� denic� nekone£néh� proud�

denic� proudu� kter� � sob� pouºív� proud� kter� sam� denuj� následujíc� prvk� proud� jso� p°ím� zaveden� pomoc� p°edchozíc� prvk� proud� be� vytvá°en� pomocn� rekurzivn� procedur� (be� limitn� podmínky� nekone£n� prou�

(defin� pow� (le� nex� 1)))�

implicitn� denic� p°edchozíh�

(defin� pow� (cons-strea� � (stream-ma� (lambd� (x� (� � x)� pow2))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Ukázk� implicitníc� deni� proud�

prou� faktoriál�

(defin� fak-strea� (cons-strea� �

(stream-ma� � fak-strea� (stream-cd� naturals)))�

prou� Fibonaccih� £íse�

(defin� fib-strea� (cons-strea� � (cons-strea� �

(stream-ma� � fib-strea� (stream-cd� fib-stream))))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Konstrukto� nekone£nýc� proud�

nekone£n� proud� lz� vytvá°e� proceduro� build-strea� analogick� procedu°� build-list� al� nem� limitn� podmínk� (nen� pot°eb� p°edáva� délk� vytvá°enéh� streamu� ;� konstrukto� build-strea�

(defin� build-strea� (lambd� (f� (le� pro� 2))))�

P°íklad�

(defin� one� (build-strea� (lambd� (i� 1))� (defin� natural� (build-strea� (lambd� (i� (� � 1)))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

P°íklady manipulace s nekone£nými proudy ;; vytvá°ení nekone£ných proud· z nekone£ných proud· ;; aplikací po sob¥ jdoucích funkcí na kaºdý prvek (define expand-stream (lambda (stream . modifiers) (let next 3) (if (null? pending) (apply expand-stream (stream-cdr stream) modifiers) (cons-stream 4) (next (cdr pending))))))) ;; p°íklady pouºití (expand-stream ones - +) Z=) proud: -1 1 -1 1    (expand-stream ones + -) Z=) proud: 1 -1 1 -1    (expand-stream naturals + -) Z=) proud: 1 -1 2 -2 3    (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 5 / 28 P°íklady manipulace s nekone£nými proudy vytvo°ení proudu celých £ísel (define integers (build-stream (lambda (i) (if (= i 0) 0 5))))) nebo pouºitím streamu p°irozených £ísel a expand-stream (define integers (cons-stream 0 (expand-stream naturals - +))) v obou p°ípadech dostáváme integers Z=) proud: 0 -1 1 -2 2 -3 3 -4 4 -5    (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 6 / 28 P°íklad� (nesprávné� manipulac� � nekone£ným� proud�

Následujíc� m� smys� pouz� poku� j� s� kone£ný� (defin� stream-append� (lambd� (s� s2� (stream-fold� (lambd� (� y� (cons-strea� � (forc� y))� s� s1))�

druh� prou� s� neuplatní� protoº� prvn� j� nekone£n�

(stream-appen� one� (stream-ma� � ones)�

následujíc� bud� cykli�

(stream-lengt� ones�

po£íta� délk� (nekon£eného� stream� j� nesmysl� neexistuj� algoritmu� (� nikd� existova� nebude)� kter� b� pr� dan� strea� rozhodl� zda-l� j� kone£n� £� nikoli� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Prou� racionálníc� £íse�

m·ºem� vytvo°i� � prou� v²ec� racionálníc� £íse� vyuºijem� faktu� º� v²echn� kladn� racionáln� £ísl� jso� zapsán� � následujíc� tabulc� (kaºd� dokonc� nekone£n� mnoh� krát� � toho� º� tabulk� m·ºem� projí� p� poloºkác� � diagonální� sm¥r� POZNÁMKA� prou� v²ec� reálnýc� £ísel� nelz� vytvo°i� (!�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Prou� racionálníc� £íse�

;� prou� pár� (� � 1� (� � 1� (� � 2� (� � 1� �

(defin� pair�

(le� nex� 6))))�

;� prou� zlomk� 1/� 2/� 1/� 3/� 2/� 1/� �

(defin� fraction� (stream-ma� (lambd� (x� (� (ca� x� (cd� x))� pairs)�

kladn� racionáln� £ísla� zbýv� odstrani� opakujíc� s� £ísl� � fraction� (nap°íkla� 1/� j� toté� jak� 2/2� � podobn¥�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� � � 2�

Prou� racionálníc� £íse�

;� prou� kladnýc� racionálníc� £íse� ;� stejn� £ísl� jso� odstran¥n� ltrac�

(defin� positive-rational� (le� nex� 7))� f-stream))))�

;� � kone£n¥� prou� v²ec� racionálníc� £íse� ;� � -� � -� � -1/� 1/� -� � -1/� 1/� -� � -3/� 3/� �

(defin� rational� (cons-strea� � (expand-strea� positive-rational� � +))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Kd� pouºí� proudy�

Kd� pouºí� proud� míst� seznam·�

1 2 kdy� pot°ebujem� °ídi� pr·b¥� výpo£t� pomoc� da� kdy� nen� dop°ed� znám� velikos� dat� kter� chcem� zpracovávat� neb� nen� moºn� odhadnout� koli� da� budem� muse� zpracovat� ne� najdem� °e²en� (n¥jakého� problém�

P°íklad� poku� s� budem� pokou²e� nají� v� velké� soubor� sekvenc� n¥jakýc� znak� odpovídajíc� daném� vzoru� pa� nem� smys� natahova� cel� vstupn� soubo� d� pam¥ti� co� m·º� bý� dlouh� operac� (neb� � neprovediteln� operace)� protoº� hledan� °et¥ze� m·º� bý� t°eb� n¥kd� n� za£átk� souboru� Typick� pouºit� proud·�

°ízen� vstupn¥/výstupníc� operac� prác� s� soubor� pouºív� mnoh� P� (nap°íkla� C++� m� ukáºem� implementac� V/� operac� v� Schem� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Vstupn¥/výstupn� operac� v� Schem�

Schem� pouºív� p°� manipulac� s� soubor� tzv� porty� por� lz� chápa� jak� identikáto� otev°enéh� soubor� pr� detail� vi� specikac� R6R� P°íkla� ukládán� da� d� soubor�

(defin� � (open-output-fil� “soubor.txt”)� (displa� “Aho� svete!� p� (newlin� p� (displa� (ma� � '(� � � 4)� p� (newlin� p� (close-output-por� p�

P°íkla� na£ítán� da� z� soubor�

(defin� � (open-input-fil� “soubor.txt”)� (displa� (rea� p)� (displa� (rea� p)� (displa� (rea� p)� (close-input-por� p�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Jednoduch� vstupn� proud�

;� vytvo� prou� £tení� výraz� z� vstupníh� port�

(defin� input-port→strea� (lambd� (reade� port� (le� ite� (� (le� 8)� (i� (eof-object� elem�

(begi� (close-input-por� port� '()�

(cons-strea� ele� (iter))))))�

;� vytvo°� prou� otev°ení� soubor�

(defin� file→strea� (lambd� (reade� file-name�

(input-port→strea� reade� (open-input-fil� file-name)))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Zvý²ení výpo£etní efektivity pomocí proud· predikát equal-fringe? je pro dva seznamy pravdivý p. k. oba seznamy mají stejné atomické prvky pokud je projdeme zleva-doprava ;; p°ímo£aré °e²ení, které je neefektivní (define equal-fringe? (lambda (s1 s2) (define flatten ; pomocná procedura: linearizace seznamu (lambda (l) (cond 9) 10) (append (flatten (car l)) (flatten (cdr l)))) (else (cons (car l) (flatten (cdr l))))))) (equal? (flatten s1) (flatten s2)))) ;; p°íklad pouºití: (equal-fringe? '(a (b ©) () d) '(a b c (d))) Z=) #t (equal-fringe? '(a (b ©) () d) '(a b c (e))) Z=) #f (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 14 / 28 Zvý²en� výpo£etn� efektivit� pomoc� proud�

� £e� spo£ív� neefektivit� p°edchozíh� °e²ení�

1 2 b¥he� výpo£t� s� konstruuj� lineárn� seznamy� kter� s� poto� pouºij�

pouz� jednorázov� prediká� s� nechov� p°irozen¥� Poku� mám� dv� seznam� v� tvar� (� � � (� � pa� j� okamºit� jasné� º� výslede� pr� n� b� m¥� bý� #f� al� p°edchoz� procedur� j� ob� nejprv� cel� linearizuj�

Odstraním� problé� £� 2�

vstupn� seznam� budem� linearizova� d� proud� (t� jes� výsledke� linearizac� seznam� bud� prou� atom·� okamºit� budem� mí� � dispozic� nejlev¥j²� atom� ostatn� prvk� linearizovanéh� seznam� s� budo� hleda� a� kdy� p°istoupím� � dal²ím� prvk� proud� vytvo°ím� prediká� n� tes� shod� dvo� kone£nýc� proud� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Zvý²ení výpo£etní efektivity pomocí proud· Kaºdý p°íslib je roven pouze sám sob¥: (define d (delay 1)) (equal? d d) Z=) #t (equal? (delay 1) (delay 1)) Z=) #f tím pádem: (equal? (stream 'a 'b 'c) (stream 'a 'b 'c)) Z=) #f proto zavádíme predikát shodnosti dvou proud·: (define stream-equal? (lambda (s1 s2) (or (and (null? s1) (null? s2)) (and (equal? (stream-car s1) (stream-car s2)) (stream-equal? (stream-cdr s1) (stream-cdr s2)))))) (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 16 / 28 Zvý²en� výpo£etn� efektivit� pomoc� proud�

;� tém¥� dokonal� verz� equal-fringe�

(defin� equal-fringe� (lambd� (s� s2�

;� pomocn� denice� linearizac� seznam�

(defin� flatte� (lambd� (l� (con� 11))� (els� (cons-strea� (ca� l� (flatte� (cd� l))))))�

;� jso� lineárn� seznam� totoºné�

(stream-equal� (flatte� s1� (flatte� s2)))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2�

Zvý²ení výpo£etní efektivity pomocí proud· P°edchozí °e²ení má jeden malý problém P°íklad, na kterém ná² predikát selhává (define a '(a)) (set-cdr! a a) (define b '12)) (set-cdr! b b) (equal-fringe? a b) Z=) 1 (cyklí) Odstran¥ní problému (rozmyslete si pro£): místo procedury stream-append2 vytvo°íme makro (define-macro stream-append2 (lambda (s1 s2) `(let proc ((s ,s1)) (if (stream-null? s) ,s2 (cons-stream (stream-car s) (proc (stream-cdr s))))))) nový pohled: makro = procedura s lín¥ vyhodnocenými argumenty (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 18 / 28 Vyhodnocovac� proce� � vyrovnávac� pam¥t� Modelov� progra� (defin� fi� (lambd� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2)))))� Výhod� � nevýhod� p°edchozíh� kódu� výhoda� j� £ist� napsan� (vznik� p°epise� denic� b� £ísla� nevýhoda� j� neefektivn� docház� k� zbyte£ném� opakován� výpo£t� Otázka� Ja� zachova� £itelnos� kódu� al� zvý²i� efektivit� výpo£etníh� procesu� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 1� � 2� Vyhodnocovac� proce� � vyrovnávac� pam¥t� ;� iterativn� verz� procedur� ;� p°edstavuj� zrychlen� n� úko� £itelnost� kód� (defin� fi� (lambd� (n� (le� ite� ((� 1� (� 1� (� n)� (i� (<� � 1� � (ite� � (� � b� (� � 1)))))� Lep²� °e²ení� zachovám� p·vodn� kó� procedur� procedur� zabalím� d� dal²� procedur� (memoize)� kter� bud� mí� svo� vnit°n� vyrovnávac� pam¥� d� kter� bud� ukláda� výsledk� aplikac� výchoz� procedur� odstraním� ta� problé� opakovanéh� provád¥n� stejnýc� výpo£t� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� Vytvo°ím� procedur� empty-asso� � assoc� pr� správ� pam¥t� ;� prázdn� pam¥� (defin� empty-asso� (lambd� (� (con� (con� #� #f� '()))� ;� destruktivn� za°a� nov� záznam/modiku� existujíc� (defin� assoc� (lambd� (asso� ke� val� (le� ite� ((a� assoc)� (con� ((null� as� (set-cdr� asso� (con� (con� ke� val� (cd� assoc)))� ((equal� (caa� as� key� (set-cdr� (ca� as� val)� (els� (ite� (cd� as))))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� P°íklad za°azení nových záznam·: (define a (empty-assoc)) a Z=) ((#f . #f)) (assoc! a 'ahoj 10) a Z=) ((#f . #f) (ahoj . 10)) (assoc! a 'blah 20) a Z=) ((#f . #f) (blah . 20) (ahoj . 10)) (assoc! a 'ahoj 30) a Z=) ((#f . #f) (blah . 20) (ahoj . 30)) Vyhledávání lze provést pomocí klasického assoc (assoc 'blah a) Z=) (blah . 20) (assoc #f a) Z=) (#f . #f) Poznámka: pár (#f . #f) je vºdy p°ítomen kv·li mutaci (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 22 / 28 Vyhodnocovac� proce� � vyrovnávac� pam¥t� procedur� memoiz� vytvo°� obálk� na� dano� proceduro� (proved� memoizac� dan� procedury� kaºd� memoizovan� procedur� m� vlastn� pam¥� pr� úschov� výsledk� p°� volán� memoizovan� procedur� � ji� d°ív� pouºitým� argument� j� výsledn� hodnot� vyhledán� � pam¥t� (defin� memoiz� (lambd� (f� (le� ((memor� (empty-assoc))� (lambd� called-with-arg� (le� ((foun� (asso� called-with-arg� memory))� (i� foun� (cd� found� (le� ((resul� (appl� � called-with-args))� (assoc� memor� called-with-arg� result� result))))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� ;� Fibonaccih� £ísl� urychlen� pomoc� memoiz� (defin� fi� (memoiz� (lambd� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2))))))� POZOR� následujíc� b� nefungovalo� (defin� fi� (lambd� (n� � p·vodn� pomal� fi� (defin� fast-fi� (memoiz� fib)� (fast-fi� 32� bud� v� skute£nost� pomal� v� fast-fi� s� rekurzivn� vol� p·vodn� procedur� be� cach� p°� (fast-fi� 32� j� zapamatová� pouz� výslede� pr� 3� neved� k� kýºeném� zrychlen� výpo£t� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� Procedury s ke²í se chovají jinak neº b¥ºné procedury v p°ípad¥ pouºití vedlej²ího efektu (let ((cntr 0)) (define modify (lambda (x) (set! cntr (+ 1 cntr)))) (modify #f) (modify #f) cntr) Z=) 2 (let ((cntr 0)) (define modify (memoize (lambda (x) (set! cntr (+ 1 cntr))))) (modify #f) (modify #f) cntr) Z=) 1 (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pam¥´ 25 / 28 ;� vylep²en� verze� p°� p°epln¥n� pam¥t� s� pam¥� vysyp� (defin� make-memoiz� (lambd� limi� (lambd� (f� (le� ((memor� (empty-assoc)� (memory-siz� 0)� (lambd� called-with-arg� (le� ((foun� (asso� called-with-arg� memory))� (i� foun� (cd� found� (le� ((resul� (appl� � called-with-args))� (i� (an� (no� (null� limit)� (� memory-siz� (ca� limit))� (begi� (set� memory-siz� 0� (set� memor� (empty-assoc)))� (assoc� memor� called-with-arg� result� (set� memory-siz� (� memory-siz� 1)� result)))))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� ;� urychlen� fi� � pam¥t� � p¥t� bu¬kác� (defin� fi� ((make-memoiz� 5� (lambd� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2))))))� Srovnán� po£t� aktivac� vnit°n� procedur� p°� dan� velikost� pam¥t� b¥he� výpo£t� (fi� 32� velikos� pam¥t� 5� 2� 1� 1� � � � po£e� aktivac� 3� 24� 27� 170� 698� 7518� 28712� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2� Makr� pr� vytvá°en� procedu� � ke²� ;� globáln� konstant� udávajíc� velikos� pam¥t� (defin� *max-memory� 1000� ;� makr� kapp� (define-macr� kapp� (lambd� (arg� � body� `13))�

;� p°íkla� pouºití�

(defin� fi� (kapp� (n� (i� (<� � 2�

� (� (fi� (� � 1)� (fi� (� � 2)))))�

(KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pam¥� 2� � 2�

1)
las� 1)� (cons-strea� las� (nex� (� � las�
2)
� 0)� (cons-strea� (� i� (pro� (� � 1
3)
pending modifiers
4)
car pending) (stream-car stream
5)
if (even? i) + -) (quotient (+ i 1) 2
6)
su� 2� (� 1� (� 1)� (cons-strea� (con� � b� (i� (� � 1� (nex� (� su� 1� su� 1� (nex� su� (� � 1� (� � 1
7)
f-strea� fractions)� (cons-strea� (stream-ca� f-stream� (nex� (stream-filte� (lambd� (x� (no� (� � (stream-ca� f-stream
8)
ele� (reade� port
9)
null? l) '(
10)
list? (car l
11)
null� l� '()� ((list� (ca� l)� (stream-append� (flatte� (ca� l)� (flatte� (cd� l
12)
b
13)
make-memoiz� *max-memory*� (lambd� ,arg� ,@body
PAPR2/pp2a8.txt · Last modified: 2014/04/24 00:53 (external edit)
CC Attribution-Noncommercial-Share Alike 4.0 International
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0