Cykly vybavení

• break
• continue
• redo

break

přerušení cyklu a návrat danou hodnotou

continue

provedení další iterace (přeskočení zbytku těla)

redo

skoč na začátek těla cyklu (bez testu podmínky)

while vybaveni break

(define-macro while (lambda (condition

body (let ¹⁾ '(call/cc (lambda (break (let ,loop-name ( (if ,condition (begin ,@body (,loop-name))))))))

(let ²⁾ (while (< i 10) (set! j (+ j i)) (set! i (+ i 1)) (if (> i 5) (break))) (list i j)) Z=) (6 15) (let ³⁾ (while (>= i 0) (set! i (- i 1)) (let ⁴⁾ (while (>= j 0) (set! n (+ n j)) (break)))) n) Z=) 45 (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 3 / 31  ;� whil� vybaven� brea� � continu�

(define-macr� whil� (lambd� (conditio� � body� (le� ⁵⁾� '(call/c� (lambd� (break� (le� ,loop-nam� (� (i� ,conditio� (begi� (call/c� (lambd� (continue� ,@body)� (,loop-name))))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� � � 3�

 Příklad pouzití: (let ⁶⁾ (while (< i 10) (if (⇐ i 2) (begin (set! i (+ i 1)) (continue))) (set! j (+ j i)) (set! i (+ i 1)) (if (> i 5) (break))) (list i j)) Z=) (6 12) (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 5 / 31  ;� whil� vybaven� break� continu� � red� (PERL�

(define-macr� whil� (lambd� (conditio� � body� (le� ⁷⁾� '(call/c� (lambd� (break� (le� ,loop-nam� (� (i� ,conditio� (begi� (call/c� (lambd� (continue� (le� ⁸⁾� ,@body))� (,loop-name))))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� � � 3�

 Příklad pouzití: (let ⁹⁾ (while (< i 10) (set! j (+ j i)) (set! i (+ i 1)) (if (and (>= i 10) (< i 20)) (redo))) (list i j)) Z=) (20 190) Pro continue místo redo bychom dostali: (let ¹⁰⁾ (while (< i 10) (set! j (+ j i)) (set! i (+ i 1)) (if (and (>= i 10) (< i 20)) (continue))) (list i j)) Z=) (10 45) (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 7 / 31  (define-macr� d�

(lambd� (bindin� conditio� � body�

(le� ¹¹⁾�

'(call/c�

(lambd� (break�

(letre�

¹²⁾�

,@body))�

(,loop-nam� ,@(ma� cadd� binding))))))�

(,loop-nam� ,@(ma� cad� binding)))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� � � 3�

 Makr� realizujíc� cyklu� typ� repea� � unti� (ji� jsm� implementoval� � předchozíc� lekcích�

(define-macr� repea� (lambd� arg�

(letre� ¹³⁾�

'(le� ,loop-nam� (� ,@bod� (con� ,@(ma� (lambd� (conds�

'(,(ca� conds� (begi� ,@(cd� conds)))� (cd� limits)� (els� (,loop-name))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� � � 3�

 Makr� obohacen� � break� continu� � red�

(define-macr� repea� (lambd� arg�

(letre�

� � vazb� jak� n� předchozí� slajd�

'(call/c�

(lambd� (break�

(le� ,loop-nam� (�

(call/c�

(lambd� (continue�

(le� ¹⁴⁾�

,@body))�

(con� ,@(ma� (lambd� (conds�

'(,(ca� conds�

(begi� ,@(cd� conds)))�

(cd� limits)�

(els� (,loop-name))))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 1� � 3�

 Iterátor� (opakování� 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� � Korutiny� nedeterminismu� 1� � 3�

 (defin� generate-iterato� (lambd� (l� (letre� ¹⁵⁾)�

(loo� (cd� l)))))))� (lambd� (� (call/c� (lambd� (f� (set� retur� f� (start))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 1� � 3�

 Příklad pouzití: (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 9 Korutiny, nedeterminismus 13 / 31  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� � Korutiny� nedeterminismu� 1� � 3�

 .. � (lambd� (� (call/c� (lambd� (f� (set� retur� f�

(start))))))�

Poznámka�

u� nen� potřeb� *end-of-iteration� prohledáván� j� ukončen� (�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 1� � 3�

 Příklad pouzití: (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 9 Korutiny, nedeterminismus 16 / 31  Korutin�

korutin� � � � reprezentuj� podprogramy� kter� s� vzájemn� přepínaj� C� T� Haynes� D� P� Friedman� M� Wand� Continuation� an� Coroutines� In� Conf� AC� Symp� LIS� an� Functiona� Programming� 293298� 1984� ;� makr� n� vytvářen� koruti�

(define-macr� coroutin� (lambd� (ar� � body� '(letre� ¹⁸⁾)))�

(lambd� elem� (appl� stat� elems))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 1� � 3�

 Příklad: bez pouzití resume se chová jako normální procedura (define c (coroutine (x) (+ x 1))) (c 10) Z=) 11 Příklad: dvě korutiny, jedna přepne na druhou (define d (coroutine () (display “VOLANA D”) (newline) (resume c 10))) (d) Z=) 11 a vypíše VOLANA d) (d) Z=) nic (d 10) Z=) 10 (d 'blah) Z=) blah (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 18 / 31  Iteráto� pomoc� koruti�

;� identikáto� ukončen� iterac� � prediká� (ji� mám� implementované�

(defin� *end-of-iteration� (lambd� (� #f)� (defin� finished� (lambd� (elem� (eq� ele� *end-of-iteration*))�

;� iterátor� korutin� volajíc� dalš� korutin� (caller�

(defin� generate-iterato� (lambd� (l� (coroutin� (caller� (le� loo� ¹⁹⁾)))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 1� � 3�

 � tom� abycho� mohl� pouzíva� iteráto� potřebujem� vytvoři� dalš� korutin� (zd� s� jmenuj� � user� � kód� iterátor� t� j� � caller)� (letre� ²⁰⁾� (use� (coroutin� (� (le� ite� (� (le� ²¹⁾� (i� (no� (finished� v)�

(begi� (displa� v� (newline� (iter)))))))�

(user)�

Předchoz� bycho� mohl� zjednoduši� makre� with-iterator�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 2� � 3�

 Nedeterminismus nedeterministický operátor amb, vrací jeden z vyhodnoc. argument·, přitom mu jde o to najít aspo¬ jedno řešení (operátor nedeterministicky konverguje k řešení, pokud existuje) J. McCarthy. A Basis for a Mathematical Theory of Computation. In: P. Braort, D. Hirschberg (Eds.): Computer Programming and Formal Systems. North-Holland, 1967. (amb) Z=) Error: Tree Exhausted (amb 1 2 3 4) Z=) 1 (if (amb #f #t) 'blah (amb)) Z=) blah (let ²²⁾) (if (odd? x) (amb) x)) Z=) 2 (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 21 / 31  Nedeterminismu�

amb-fail� pomocn� procedura� jej� úče� bud� jasn� dál� be� argumentu� slouz� � vyvolán� návrat� (backtracking� � argument� nastav� hodnot� aktuálníh� návrat� n� dano� hodnot� (defin� amb-fai� (le� ²³⁾)))))�

;� inicializac� amb-fai�

(amb-fai� #f�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 2� � 3�

 O co tady jde? (amb-fail #f) (amb-fail) Z=) h(); (error …); Pi (amb-fail odd?) (amb-fail) Z=) primitivní procedura odd? (amb-fail (lambda (x) (amb-fail odd?) x)) ²⁴⁾) (call/cc (lambda (exit) (call/cc (lambda (next) (amb-fail (lambda () (amb-fail prev-fail) (next))) (exit 1))) (prev-fail)))) Z=) 1 ²⁵⁾ Z=) CHYBA: AMB: Tree Exhausted (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 24 / 31  (amb-fail #f) (let ²⁶⁾) (call/cc (lambda (exit) (call/cc (lambda (next) (amb-fail (lambda () (amb-fail prev-fail) (next))) (exit 1))) (call/cc (lambda (next) (amb-fail (lambda () (amb-fail prev-fail) (next))) (exit 2))) (prev-fail))))) Z=) 1 ²⁷⁾ Z=) 2 ²⁸⁾ Z=) CHYBA: AMB: Tree Exhausted (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 25 / 31  nex� �

(excape� (lambd� (2� (le� ²⁹⁾� (call/c� (lambd� (exit�

�

(call/c� (lambd� (next�

(amb-fai� (lambd� (� (amb-fai� prev-fail� (next))�

(exi� 2))� (prev-fail)))))�

exi� �

(excape� (lambd� (2� (le� ³⁰⁾� 2))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 2� � 3�

 failure (v P) ! h(); (amb-fail prev-fail) (next);Px i Tedy procedura při aplikaci ulozí předchozí fail ve vazbě na failure v P, aktivuje next  pokračování dalším prvkem. (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 27 / 31  ;� am� (ambiguous� operáto�

(define-macr� am� (lambd� elem� (le� ³¹⁾� '(le� ³²⁾� (call/c� (lambd� (exit� ,@(ma� (lambd� (elem� '(call/c� (lambd� (next� (amb-fai�

(lambd� (� (amb-fai� ,previous-fail� (next))�

(exi� ,elem)))� elems� (,previous-fail))))))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 2� � 3�

 (let ³³⁾) elem) Z=) 1 (let ³⁴⁾) (if (< elem 10) 'xxx) elem) Z=) 1 (let ³⁵⁾) (if (< elem 10) (amb)) elem) Z=) 15 PROBOHA PROƒ? (KI, UP Olomouc) PP 2, Lekce 9 Korutiny, nedeterminismus 29 / 31  nex� �

(excape� (lambd� (2� (le� ³⁶⁾� (call/c� (lambd� (exit�

�

(call/c� (lambd� (next�

(amb-fai� (lambd� (� (amb-fai� prev-fail� (next))�

(exi� 2))� (prev-fail)))))� (i� (� ele� 10� (amb)� elem))�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 3� � 3�

 ;� odvozen� konstrukt� asser�

(defin� asser� (lambd� (elem� (i� (no� elem� (amb)))�

Příkla� pouzit� asser� (spol� � amb�

(le� ³⁷⁾� (asser� (odd� x)� x�

(KI� U� Olomouc� P� 2� Lekc� � Korutiny� nedeterminismu� 3� � 3�