Implicitní definice nekonečného proudu

definice proudu, který v 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�

(define pow (let next ¹⁾ (cons-stream last (next (� � last )))))

implicitní definice předchozího

(define pow2 (cons-stream � (stream-ma� (lambda (x) (� � x)� pow2))�

Ukázka implicitních definic proudů

proud faktoriálů

(define fak-stream (cons-stream �

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

prou� Fibonaccih� číse�

(define fib-stream (cons-stream � (cons-stream �

(stream-ma � fib-stream (stream-cdr fib-stream))))�

Konstruktor nekonečných proud�

nekonečný proud� lze vytvářet 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�

(define build-stream (lambda (f) (let pro� ²⁾)))�

Příklad�

(define one� (build-stream (lambda (i) 1))� (define natural� (build-stream (lambda (i) (� � 1)))�

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 ³⁾ (if (null? pending) (apply expand-stream (stream-cdr stream) modifiers) (cons-stream ⁴⁾ (next (cdr pending))))))) ;; příklady použití (expand-stream ones - +) ;⇒ proud: -1 1 -1 1


(expand-stream ones + -) ;⇒ proud: 1 -1 1 -1


(expand-stream naturals + -) ;⇒ proud: 1 -1 2 -2 3

Příklady manipulace s nekonečnými proudy vytvoření proudu celých čísel (define integers (build-stream (lambda (i) (if (= i 0) 0 ⁵⁾)))) 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 ;⇒ proud: 0 -1 1 -2 2 -3 3 -4 4 -5

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�

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

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

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

�

(defin� pair�

(le� nex� ⁶⁾)))�

;� 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ě�

Proud racionálních čísel

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

(defin� positive-rational� (le� nex� ⁷⁾)� 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� � +))�

Kdy použít proudy?

Kdy použít proudy místo 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�

Scheme používá při manipulaci se soubory tzv. porty� port lze chápat jako identifikátor otevřeného souboru pro detaily viz specifikaci R6RS Příklad ukládáni dat do souboru

(define � (open-output-file “soubor.txt”)� (display “Ahoj svete!� p� (newlin� p� (displa� (ma� � '(� � � 4)� p� (newlin� p� (close-output-por� p�

Příklad načítání dat ze souboru

(define � (open-input-file “soubor.txt”)� (display (read p)� (display (read p)� (display (read p)� (close-input-port p�

Jednoduché vstupní proudy

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

(define input-port→stream (lambda (reader port� (let iter (� (let ⁸⁾� (if (eof-object� elem�

(begin (close-input-port port� '()�

(cons-stream elem (iter))))))�

;; vytvoří proud otevřením souboru

(define file→stream (lambda (reader file-name)

(input-port→stream readr (open-input-file file-name))))

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 ((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))) ;=> #t 
equal-fringe? '(a (b (c)) () d) '(a b c (e))) ;=> #f 
(

Zvýšení výpočetní efektivity pomocí proudu

V čem spočívá neefektivita předchozího ř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�

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) ;=> #t 
(equal? (delay 1) (delay 1)) ;=> #f 

tím pádem:

(equal? (stream 'a 'b 'c) (stream 'a 'b 'c)) ;=> #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)))))) 

Zvýšen� výpočetn� efektivit� pomoc� proud�

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

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

;; pomocné definice linearizace seznamu

(define flatten (lambda (l) (cons ⁹⁾ (flatten (cdr l)))) (else (cons-stream (car l� (flatten (cdr l))))))�

;; jsou lineární seznam� totožné�

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

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 '((b))) (set-cdr! b b) 
(equal-fringe? a b) ;=> 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

Vyhodnocovací proces � vyrovnávací pamět�

Modelov� progra�

(define fib (lambda (n� (if (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2))))))

Výhody a nevýhody předchozího 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�

Vyhodnocovaci proces � vyrovnávac� pamět�

;; iterativni verze procedury ;; představuje zrychlení na úkor čitelnosti kódu

(define fib

(lambda (n)

(let iter ¹⁰⁾)))�

Lepší řešení�

zachováme původní kód procedury proceduru zabalíme do další procedury (memoize)� která bude mít svou vnitřní vyrovnávací paměť do ktere bude ukládat výsledky aplikací výchoz� procedur� odstraníme tak problém opakovaného provádění stejných výpočtů

Vytvoříme proceduru empty-assoc � 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� ¹¹⁾)� ¹²⁾))))�

Příklad zařazení nových záznamů: (define a (empty-assoc)) a ;⇒ ¹³⁾ (assoc! a 'ahoj 10) a ;⇒ ¹⁴⁾ (assoc! a 'blah 20) a ;⇒ ¹⁵⁾ (assoc! a 'ahoj 30) a ;⇒ ¹⁶⁾ Vyhledávání lze provést pomocí klasického assoc (assoc 'blah a) ;⇒ (blah . 20) (assoc #f a) ;⇒ (#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� ¹⁷⁾�

(lambd� called-with-arg�

(le� ¹⁸⁾�

(i� foun�

(cd� found�

(le� ¹⁹⁾�

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

Procedury s keší se chovají jinak než běžné procedury v případě použití vedlejšího efektu (let ²⁰⁾ (define modify (lambda (x) (set! cntr (+ 1 cntr)))) (modify #f) (modify #f) cntr) ;⇒ 2 (let ²¹⁾ (define modify (memoize (lambda (x) (set! cntr (+ 1 cntr))))) (modify #f) (modify #f) cntr) ;⇒ 1

;; vylepšen� verze� př� přeplněn� pamět� s� pamě� vysyp�

(defin� make-memoiz�

(lambd� limi�

(lambd� (f�

(le� ²²⁾�

(i� foun�

(cd� found�

(le� ²³⁾�

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

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

;� 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�