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 ¹⁾ Z=) 202 (+ 2 ²⁾ 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 ³⁾) (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 ⁴⁾) (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� ⁵⁾))))�

;� rekurzivn� verz� procedur� pouºívajíc� call/c� (defin� list-produc� (lambd� (l� (call/c� (lambd� (exit� (le� pro� ⁶⁾)))))))�

(KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 1� � 4�

 ;� iterativn� verz� procedur�

(defin� list-produc� (lambd� (l� (le� ite� ⁷⁾))))�

;� iterativn� verz� � okamºitý� opu²t¥ní� (be� call/cc�

(defin� list-produc� (lambd� (l� (le� ite� ⁸⁾)))))�

(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 ⁹⁾ #t) ¹⁰⁾ (and (atom-prop? aprop? (car l1) (car l2)) (atom-prop? aprop? (cdr l1) (cdr l2)))) ¹¹⁾ (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� ¹²⁾�

(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� ¹³⁾�

(tes� (con� (ca� l1� s1� (con� (ca� l2� s2� (cd� l1� (cd� l2))�

¹⁴⁾� (tes� (cd� s1� (cd� s2� l� l2)� ¹⁵⁾�

(tes� (con� (caa� s1� (con� (cda� s1� (cd� s1))� (con� (caa� s2� (con� (cda� s2� (cd� s2))� l� l2)�

¹⁶⁾� #f� ¹⁷⁾))�

(KI� U� Olomouc� P� 2� Lekc� � Aktuáln� pokra£ován� 2� � 4�

 (atom-prop? ⇐ '¹⁸⁾ '¹⁹⁾) Z=) #t [] [] ^{20) 21)} [(1 2)] [(2 3)] ^{22) 23)} [1 (2)] [2 (3)] ^{24) 25)} [(2)] [(3)] ^{26) 27)} [2 ()] [3 ()] ^{28) 29)} [()] [()] ^{30) 31)} [] [] ^{32) 33)} [(3)] [(4)] () () [3 ()] [4 ()] () () [()] [()] () () [] [] () () (atom-prop? ⇐ '³⁴⁾ '³⁵⁾) Z=) #f [] [] ^{36) 37)} [(1 2)] [(1 1)] ^{38) 39)} [1 (2)] [1 (1)] ^{40) 41)} [(2)] [(1)] ^{42) 43)} [2 ()] [1 ()] ^{44) 45)} (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=) #<continuation> (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 ⁴⁶⁾)) (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� ⁴⁷⁾� (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� ⁴⁸⁾�

(erro� 'list-produc�

“Lis� membe� i� no� � number�

(ca� 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� ⁵⁰⁾�

`(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�

⁵¹⁾))))�

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� ⁵²⁾)�

(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=) #<procedura> (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� ⁵³⁾)�

(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 '⁵⁴⁾) 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 ^{55) 56)} (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 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� ⁵⁷⁾� (le� tes� ⁵⁸⁾� (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�