KATEDR� INFORMATIKY� PÍRODOV…DECK� FAKULT� UNIVERZIT� PALACKÉHO� OLOMOU� PARADIGMAT� PROGRAMOVÁN� � AKTUÁLN� POKRAƒOVÁN� Slajd� vytvo°il� Vilé� Vychodi� � Ja� Kone£n� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� Motivac� B¥he� posledníc� dvo� semestr� jsm� ukázali� º� � proceduram� � makr� j� moºn� pracova� jak� � daty� Dál� jsm� ukázali� º� výpo£e� lz� °ídi� dat� (streamy)� Nyn� ukáºeme� º� � výpo£etní� £asem� histori� � budoucnost� výpo£t� j� moºn� pracova� jak� � daty� Budem� pot°ebova� t°� fundamentáln� pojm� 1 2 3 Kontex� � procedur� jednoh� argument� reprezentujíc� výpo£et� kter� nastan� okamºit� p� vyhodnocen� jistéh� výraz� Únikov� procedur� � procedura� p� její� aplikac� s� ukon£� zbyl� výpo£e� � jak� výslede� j� okamºit� vrácen� hodnot� jej� aplikac� Aktuáln� pokra£ován� nebol� kontinuac� � j� únikov� procedur� vytvo°en� � kontext� aktuálníh� výraz� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� Motivac� � c� jde� aktuáln� pokra£ován� � analogi� p°íkaz� skoku� oprot� skok� j� v²a� MNOHE� mocn¥j²� umoºn� ná� vytvá°e� mnoºstv� typ� nelokálníc� skok� umoºn� (d� jist� míry� zhmotni� budoucnos� výpo£t� � manipulova� � n� jak� � dat� (nap°íkla� j� vyvola� � okamºiku� kd� u� budouc� výpo£et� prob¥h� � � jisté� smysl� s� ted� vrátím� d� minulosti)� £ase� vytvo°ím� korutin� � podprogramy� kter� s� budo� vzájemn� p°epína� paraleln� systé� � soub¥ºn� b¥� n¥kolik� výpo£t� nedeterministick� operátor� � poved� n� programy� kter� budo� schopn� sam� hleda� °e²en� problému� pouz� n� základ� jeh� popis� � mnohe� ví� � � � aktuáln� pokra£ován� � domén� jazyk� Schem� (ostatn� P� maj� je� trapn� náhraºky� t°eb� standar� POSI� denuj� longjm� � � � slab� odvar� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� POJE� 1� Kontex� Neformáln¥� Kontex� j� zhmotn¥n� zbytk� výpo£tu� kter� b� by� zaháje� okamºit� p� vyhodnocen� n¥jakéh� podvýrazu� P°íklady� kontex� podvýraz� (� 2� x� v� výraz� (� � (� � (� 2� x))� j� výpo£et� kter� prob¥hn� p� vyhodnocen� (� 2� x� � (� � (� � (� 2� x)))� t� jest� hodnot� vznikl� vyhodnocení� (� 2� x� bud� násoben� £ísle� � � tent� výslede� bud� p°i£te� � 2� kontex� podvýraz� � v� výraz� (� � (� � (� 2� x))� j� výpo£et� kter� nejprv� otestuje� zda-l� j� výsledn� hodnot� (vznikl� vyhodnocení� *� procedura� poku� ne� kon£� s� chybou� poku� ano� j� tat� procedur� aplikován� n� � � výslede� vyhodnocen� (� 2� x)� � výsledk� aplikac� j� pot� je²t� p°i£ten� 2� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� Je²t� n¥c� � kontext� Pojem� progra� � díro� (hol� � � � dír� p°edstavuj� (nespecikovaný� výraz� � jeho� kontex� s� zajímám� (� � (� � (� 2� 5))� (� � (� � 2)� (� � (� � (� 2� 5))� (� � (� � (� 2� 5))� Formáln¥� Kontex� j� procedur� jednoh� argument� reprezentujíc� výpo£et� kter� b� nasta� p� dosazen� skute£n� hodnot� míst� dír� Pr� p°edchoz� p°íklad� s� lz� p°edstavi� jak� procedur� vznikl� vyhodnocení� následujícíc� -výraz� (lambd� (2� (� � (� � 2))� (lambd� (2� (� � (� � (� 2� 5)))� (lambd� (2� (� � (� � (� 2� 5)))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� POJEM 2: Úniková procedura Procedura se nazývá úniková procedura, pokud je-li aktivována, tak zp·sobí okamºité p°eru²ení vykonávání zbytku výpo£tu a výsledkem vyhodnocení (celého vstupního výrazu, ve kterém byla pouºita) je práv¥ výsledek její aplikace Budeme p°edpokládat, ºe máme k dispozici proceduru escaper, která pro danou proceduru vrátí tutéº proceduru, která ale bude úniková (posléze ukáºeme, ºe escaper lze ve Scheme naprogramovat) * Z=) procedura násobení (escaper *) Z=) úniková procedura násobeni Pouºití na top-level je stejné (* 10 20) Z=) 200 ((escaper *) 10 20) Z=) 200, av²ak: (+ 2 (* 10 20)) Z=) 202 (+ 2 ((escaper *) 10 20)) Z=) 200 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 6 / 44 Dal²í p°íklad únikové funkce (define p (escaper (lambda (x) (if (even? x) x (- x))))) p°íklad pouºití: (p 10) Z=) 10 (p 11) Z=) -11 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 7 / 44 (define p (escaper (lambda (x) (if (even? x) x (- x))))) (define test (lambda (x) (if (= 1 (p x)) tohle-nikdy-neprobehne tohle-taky-ne))) Demonstrace toho, ºe if nikdy neprob¥hne (test 10) Z=) 10 (test 11) Z=) -11 (eval `(test 10)) Z=) 10 (eval `(test (+ 5 6))) Z=) -11 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 8 / 44 POJE� 3� Aktuáln� pokra£ován� (kontinuace� Jazy� Schem� dáv� � dispozic� procedur� call/cc� pouºití� (call/c� � receive� .)� kd� � receive� � (p°íjemce� mus� bý� procedur� jednoh� argumentu� (call/c� j� zkratk� pr� call-with-current-continuation� P°� volán� (call/c� � receive� .� s� provede� 1 2 Vytvo°� s� kontex� (call/c� � receive� .� � aktuáln� vyhodnocované� výraz� � receive� � j� zavolá� � argumente� (kter� nazývám� aktuáln� pokra£ován� nebol� kontinuace� jím� j� procedur� vznikl� vyhodnocení� (escape� � kontex� .� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� � � 4� Takº� p°� pouºit� � (call/c� (lambd� (f� � (� � )� � bud� uvnit� n� � navázán� únikov� procedura� Tut� únikovo� procedur� m·ºem� aktivova� � jední� argumentem� Poku� s� ta� stane� j� okamºit� p°eru²en� vyhodnocován� dal²íh� kód� � receiver� � bud� s� pokra£ova� vyhodnocování� kontext� (call/c� � � � hodnoto� s� ktero� byl� aplikován� f� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4� (* 2 (+ 3 (/ 25 5))) Z=) 16 Takºe nap°íklad (f není pouºito) (* 2 (call/cc (lambda (f) (+ 3 (/ 25 5))))) Z=) 16 p°edchozí si lze p°edstavit: (* 2 ((lambda (f) (+ 3 (/ 25 5))) (escaper (lambda (2) (* 2 2))))) (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 11 / 44 Dal²í p°íklad: (* 2 (call/cc (lambda (f) (+ 3 (f 5))))) Z=) 10 si lze p°edstavit: (* 2 ((lambda (f) (+ 3 (f 5))) (escaper (lambda (2) (* 2 2))))) u p°edchozího: (+ 3 ... se neuplatní, dojde k p°eru²ení výpo£tu a vyvolá se aktuální pokra£ování (násobení dvojkou) (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 12 / 44 (+ 1 (call/cc (lambda (f) 2))) Z=) 3 (+ 1 (call/cc (lambda (f) (f 2)))) Z=) 3 (+ 1 (call/cc (lambda (f) (if (even? (f 2)) 100 200)))) Z=) 3 (+ 1 (call/cc (lambda (f) (* 2 (call/cc (lambda (g) (f (g 20)))))))) Z=) 41 (+ 1 (call/cc (lambda (f) (* 2 (call/cc (lambda (g) (g (f 20)))))))) Z=) 21 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 13 / 44 Aplikace okamºité opu²t¥ní rekurze (výskok z rekurze) Modelový p°íklad ;; procedura realizující sou£in £ísel v seznamu (define list-product (lambda (l) (if (null? l) 1 (* (car l) (list-product (cdr l)))))) (list-product '(1 2 3 4 5)) Z=) 120 chceme zefektivnit výpo£et násobení £ehokoliv nulou je nula (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 14 / 44 p°idán� limitn� podmínk� pr� nul� m� nevýhodu� fáz� odvíjen� bud� po°á� probíha� (defin� list-produc� (lambd� (l� (con� ((null� l� 1� ((� (ca� l� 0� 0� (els� (� (ca� l� (list-produc� (cd� l))))))� ;� rekurzivn� verz� procedur� pouºívajíc� call/c� (defin� list-produc� (lambd� (l� (call/c� (lambd� (exit� (le� pro� ((� l)� (con� ((null� l� 1� ((� (ca� l� 0� (exi� 0)� (els� (� (ca� l� (pro� (cd� l)))))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4� ;� iterativn� verz� procedur� (defin� list-produc� (lambd� (l� (le� ite� ((� l� (accu� 1)� (i� (null� l� accu� (ite� (cd� l� (� accu� (ca� l))))))� ;� iterativn� verz� � okamºitý� opu²t¥ní� (be� call/cc� (defin� list-produc� (lambd� (l� (le� ite� ((� l� (accu� 1)� (con� ((null� l� accum� ((� (ca� l� 0� 0� (els� (ite� (cd� l� (� accu� (ca� l)))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4� Poznámk� � p°edchozí� p°ípad� jsm� zefektivn¥n� výpo£t� pomoc� okamºitéh� opu²t¥n� um¥l� ud¥la� be� call/cc� pouz� jsm� rekurzivn� procedur� nahradil� jej� iterativn� varianto� (iterac� lz� kdykoli� okamºit� p°eru²it� protoº� s� nebuduj� ºádn� nedokon£en� výpo£et)� Otázka� Nen� call/c� je� zbyte£n� luxus?� Odpov¥¤� není� p°epi� rekurz� pomoc� iterac� j� n¥kd� hodn� t¥ºk� (nap°íkla� iterativn� verz� hloubkov� rekurzivníc� procedur� vi� následujíc� odstra²ujíc� p°íkla� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4� ;; testuj vztah dvou seznam· do hloubky (define atom-prop? (lambda (aprop? l1 l2) (cond ((and (null? l1) (null? l2)) #t) ((and (pair? l1) (pair? l2)) (and (atom-prop? aprop? (car l1) (car l2)) (atom-prop? aprop? (cdr l1) (cdr l2)))) ((and (not (pair? l1)) (not (pair? l2))) (aprop? l1 l2)) (else #f)))) P°íklad pouºití: (atom-prop? <= '(1 (2 (3) 4)) '(2 (3 (4) 5))) Z=) #t (atom-prop? <= '(1 (2 (3) 4)) '(2 (3 (1) 5))) Z=) #f (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 18 / 44 ;� neb� be� pomoc� con� (je� � pouºití� an� � or� (defin� atom-prop� (lambd� (aprop� l� l2� (o� (an� (null� l1� (null� l2)� (an� (pair� l1� (pair� l2� (atom-prop� aprop� (ca� l1� (ca� l2)� (atom-prop� aprop� (cd� l1� (cd� l2))� (an� (no� (pair� l1)� (no� (pair� l2)� (aprop� l� l2))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4� ;� efektivn¥j²� verz� � okamºitý� opu²t¥ní� výpo£t� (defin� atom-prop� (lambd� (aprop� l� l2� (call/c� (lambd� (exit� (le� tes� ((l� l1� (l� l2)� (o� (an� (null� l1� (null� l2)� (an� (pair� l1� (pair� l2� (tes� (ca� l1� (ca� l2)� (tes� (cd� l1� (cd� l2))� (an� (no� (pair� l1)� (no� (pair� l2)� (aprop� l� l2)� (exi� #f))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� p°edchoz� procedu� lz� p°epsa� � iterativn¥� al� j� t� sloºit� naví� s� pon¥ku� vytrác� efektivita� protoº� rekurzivn� volán� procedur� nahrazujem� komplikovano� manipulac� s� zásobník� (defin� atom-prop� (lambd� (aprop� l� l2� (le� tes� ((s� '()� � pomocn� zásobní� pr� l� (s� '()� � pomocn� zásobní� pr� l� (l� l1� (l� l2)� (con� ((an� (null� s1� (null� s2� (null� l1� (null� l1)� #t� ((an� (null� s1� (null� s2� (no� (null� l1)� (no� (null� l2))� (tes� (con� (ca� l1� s1� (con� (ca� l2� s2� (cd� l1� (cd� l2))� ((an� (null� s1� (null� s2)� #f) (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� . . � ((o� (null� s1� (null� s2)� #f� ((an� (null� (ca� s1)� (null� (ca� s2))� (tes� (cd� s1� (cd� s2� l� l2)� ((an� (pair� (ca� s1)� (pair� (ca� s2))� (tes� (con� (caa� s1� (con� (cda� s1� (cd� s1))� (con� (caa� s2� (con� (cda� s2� (cd� s2))� l� l2)� ((o� (pair� (ca� s1)� (pair� (ca� s2))� #f� ((aprop� (ca� s1� (ca� s2)� (tes� (cd� s1� (cd� s2� l� l2)� (els� #f))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� (atom-prop? <= '((1 2) (3)) '((2 3) (4))) Z=) #t [] [] ((1 2) (3)) ((2 3) (4)) [(1 2)] [(2 3)] ((3)) ((4)) [1 (2)] [2 (3)] ((3)) ((4)) [(2)] [(3)] ((3)) ((4)) [2 ()] [3 ()] ((3)) ((4)) [()] [()] ((3)) ((4)) [] [] ((3)) ((4)) [(3)] [(4)] () () [3 ()] [4 ()] () () [()] [()] () () [] [] () () (atom-prop? <= '((1 2) (3)) '((1 1) (4))) Z=) #f [] [] ((1 2) (3)) ((1 1) (4)) [(1 2)] [(1 1)] ((3)) ((4)) [1 (2)] [1 (1)] ((3)) ((4)) [(2)] [(1)] ((3)) ((4)) [2 ()] [1 ()] ((3)) ((4)) (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 23 / 44 Úschova únikových funkcí a jejich pozd¥j²í pouºití Kontinuace jsou (únikové) procedury Kontinuace = elementy prvního °ádu (call/cc (lambda (f) f)) Z=) # (procedure? (call/cc (lambda (f) f))) Z=) #t Receiver v následujícím výrazu nejprve naváºe kontinuaci na globální symbol blah (define blah #f) (* 2 (call/cc (lambda (f) (set! blah f) 30))) Z=) 60 Kontinuaci v blah je moºné dál pouºívat (blah 1) Z=) 2 (blah 2) Z=) 4 (blah 3) Z=) 6 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 24 / 44 Úschova únikových funkcí a jejich pozd¥j²í pouºití (begin (display "JEDNOU") (newline) (* 2 (call/cc (lambda (f) (set! blah f) 30)))) Z=) 60 a vytiskne se JEDNOU (blah 10) Z=) 20 (na obrazovku se nic netiskne) (* 2 (let ((result (call/cc (lambda (f) (set! blah f) 30)))) (display "POKAZDE") (newline) result)) Z=) 60 (blah 10) Z=) 20 a vytiskne se POKAZDE (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 25 / 44 Úschova únikových funkcí a jejich pozd¥j²í pouºití Zajímavý efekt (* 2 (call/cc (lambda (f) (set! blah f) zde-udelame-zamerne-chybu))) Z=) Error Chyba nastala aº po navázání blah, takºe: (blah 10) Z=) 20 (je v po°ádku) (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 26 / 44 P°íklad� Implementac� escape� pomoc� call/c� Globáln� symbo� n� které� budem� mí� navázano� kontinuaci� vi� dal²� výra� (defin� *top-level-escaper� #f� N� *top-level-escaper� naváº� dal²� pokra£ován� cykl� REPL� (call/c� (lambd� (break� (set� *top-level-escaper� break))� Následujíc� j� implementac� escape� pomoc� call/c� (defin� escape� (lambd� (f� (lambd� arg� (*top-level-escaper� (appl� � args))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� Implementac� chybovéh� hlá²en� (defin� erro� (lambd� (pro� messag� � values� (displa� "Erro� "� (displa� (symbol->strin� proc)� (displa� "� "� (displa� message� (i� (no� (null� values)� (begi� (displa� � "� (le� ((firs� #t)� (for-eac� (lambd� (x� (i� firs� (set� firs� #f� (displa� "� ")� (displa� x)� values)� (displa� ""))� (newline� (*top-level-escaper*))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� P°íkla� pouºit� (defin� list-produc� (lambd� (l� (call/c� (lambd� (exit� (le� pro� ((� l)� (con� ((null� l� 1� ((no� (pair� l)� (erro� 'list-produc� "Give� argumen� i� no� � list� l)� ((no� (number� (ca� l))� (erro� 'list-produc� "Lis� membe� i� no� � number� (ca� l))� ((� (ca� l� 0� (exi� 0)� (els� (� (ca� l� (pro� (cd� l)))))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4� P°íklad� Systé� výjime� (procedur� thro� � makr� catch� (defin� thro� (lambd� (excptn-nam� expr� (erro� 'thro� "To� leve� thro� triggere� with� excptn-name))� (define-macr� catc� (lambd� (labe� � prgn� (le� ((exi� (gensym))� `(call/c� (lambd� (,exit� (le� ((thro� (lambd� (excptn-nam� expr� (i� (eq� ,labe� excptn-name� (,exi� expr� (thro� excptn-nam� expr))))� (begi� ,@prgn))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad pouºití (catch 'chyba (+ 1 2) (* 3 4)) Z=) 12 P°íklad pouºití (catch 'chyba (+ 1 2) (throw 'chyba 20) (* 3 4)) Z=) 20 P°íklad pouºití (catch 'chyba (+ 1 2) (throw 'neexistujici-vyjimka 20) (* 3 4)) Z=) Error (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 31 / 44 Dal²í p°íklad (define f (lambda (n) (let ((x 10)) (catch 'bar (catch 'foo (if (> n 0) (throw 'foo (set! x 40))) (if (< n 0) (throw 'bar (+ 1 2))) (set! x 100)) (* 2 x))))) (f -1) Z=) 3 (f 0) Z=) 200 (f 1) Z=) 80 (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 32 / 44 Dal²� p°íkla� o²et°ován� výjime£nýc� situací� aserc� (define-macr� asser� (lambd� (proc-nam� assertion� � body� `(con� ,@(ma� (lambd� (ass� `((no� ,(ca� ass)� (begi� (displa� "ASSER� "� (displa� ,proc-name� (displa� "� "� ,@(ma� (lambd� (x� `(displa� ,x)� (cd� ass)� (newline� (*top-level-escaper*)))� assertions� (els� (begi� ,@body))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad� faktoriá� � asercem� (defin� fa� (lambd� (n� (asser� "faktorial� (((number� n� "arg� mus� b� � number� given� � n� ((exact� n� � � mus� b� a� exac� number"� ((>� � 0� � � mus� b� � non-negativ� integer")� (i� (� � 0� � (� � (fa� (� � 1))))))� P� odlad¥n� program� j� moºn� asser� nahradit� (define-macr� asser� (lambd� (proc-nam� assertion� � body� `(begi� ,@body))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad� Jednoduch� debugge� Globáln� symbol� n� kterýc� jso� navázán� break-poin� � zastaven� (defin� *next� #f� (defin� *stop� #f� Nastaven� stopk� (call/c� (lambd� (f� (set� *stop� f))� P°eru� výpo£e� (defin� stop-executio� (lambd� (� (*stop*))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad� Jednoduch� debugge� Zapi� *next� aktuáln� pokra£ován� � dané� bod� výpo£tu� v� které� bud� zavolán� procedur� break-poin� (defin� break-poin� (lambd� (� (call/c� (lambd� (f� (set� *next� f� (stop-execution� hic-sunt-leones)))� Pokra£u� v� výpo£t� (a� � dal²ím� breakpointu� (defin� ru� (lambd� (� (*next*))� Pr� ukázk� vi� soubo� debugger.sc� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad� Iterátor� � jejic� aplikace� iteráto� � pr� dano� datovo� struktur� postupn� vrac� jej� prvk� Pomocn� denice� Identikáto� ukon£en� iterac� (defin� *end-of-iteration� (lambd� (� #f)� Implementac� chybovéh� hlá²en� Prediká� indikujíc� kone� iterac� (defin� finished� (lambd� (elem� (eq� ele� *end-of-iteration*))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� (defin� generate-iterato� (lambd� (l� (letre� ((retur� #f� (star� (lambd� (� (le� loo� ((� l)� (i� (null� l� (retur� *end-of-iteration*� (begi� (call/c� (lambd� (new-start� (set� star� new-start� (retur� (ca� l)))� (loo� (cd� l)))))))� (lambd� (� (call/c� (lambd� (f� (set� retur� f� (start))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 3� � 4� P°íklad pouºití: (define p (generate-iterator '(a b c d e))) (p) Z=) a (p) Z=) b (p) Z=) c (p) Z=) d (p) Z=) e (p) Z=) # (indikátor konce) (eq? (p) *end-of-iteration*) Z=) #t (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 39 / 44 P°íklad� Hloubkov� iteráto� (defin� generate-depth-iterato� (lambd� (l� (letre� ((retur� #f� (star� (lambd� (� (le� loo� ((� l)� (con� ((null� l� 'nejaka-hodnota� ((pair� l� (begi� (loo� (ca� l)� (loo� (cd� l)))� (els� (call/c� (lambd� (new-start� (set� star� new-start� (retur� l)))))� (retur� '())))� � (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 4� � 4� .. � (lambd� (� (call/c� (lambd� (f� (set� retur� f� (start))))))� Poznámk� u� nen� pot°eb� *end-of-iteration� prohledáván� j� ukon£en� (� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 4� � 4� P°íklad pouºití (define p (generate-depth-iterator '(a (b (c (d)) e)))) (define q (generate-depth-iterator '(((a b) ((c d))) e))) (p) Z=) a (q) Z=) a (p) Z=) b (q) Z=) b (p) Z=) c (q) Z=) c (p) Z=) d (q) Z=) d (p) Z=) e (q) Z=) e (p) Z=) () (q) Z=) () (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 42 / 44 Zvý²ení výpo£etní efektivity pomocí iterátor· 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 ((null? l) '()) ((list? (car l)) (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 (c)) () d) '(a b c (d))) Z=) #t (equal-fringe? '(a (b (c)) () d) '(a b c (e))) Z=) #f (KI, UP Olomouc) PP 2, Lekce 8 Aktuální pokra£ování 43 / 44 Nová� efektivn� verz� equal-fringe� ;� procedur� pouºív� iterátor� (defin� equal-fringe� (lambd� (s� s2� (le� ((iter� (generate-depth-iterato� s1)� (iter� (generate-depth-iterato� s2))� (le� tes� ((v� (iter1)� (v� (iter2))� (o� (an� (null� v1� (null� v2)� (an� (equal� v� v2� (tes� (iter1� (iter2)))))))� (KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 4� � 4�