1 Współprogramy Andrzej Salwicki 5 stycznia 2010

2 Współprogramy I Plan: ● Motywacja ● Składnia ● Scenariusz obiektu współprogramu ● Przykłady ● Producent – konsument ( instrukcja attach ) ● Czytelnik -pisarze ( instukcja detach ) ● Łączenie drzew binarnych poszukiwań ( pojęcie łańcucha dynamicznego )

3 Składnia unit : { } coroutine( ); begin ; return; end ; W instrukcjach współprogramu można używać instrukcji przełączania: attach(obCoroutiny) i detach.

4 Semantyka – scenariusz

5 program prodcons; var prod:producer,cons:consumer,n:integer,mag:real,last:bool; unit producer: coroutine;... end producer; unit consumer: coroutine(n:integer);... end consumer; begin (* MAIN program *) prod:=new producer; read(n); cons:=new consumer(n); attach(prod); (* R *) writeln; end prodcons;

6 unit producer: coroutine; begin return; (* 1 *) do read(mag); (* mag-nonlocal variable, common store*) if mag=0 then (* end of data *) last:=true; exit fi; attach(cons); (* A *) od; attach(cons) (* B *) end producer;

7 unit consumer: coroutine(n:integer); var Buf:arrayof real; var i,j:integer; begin new_array Buf dim(1:n); return; (* 2*) do for i:=1 to n do Buf(i):=mag; attach(prod); (* C *) if last then exit exit fi; od; for i:=1 to n do (* print Buf *) write(' ',Buf(i):10:2) od; writeln; od; for j:=1 to i do write(' ',Buf(j):10:2) od; writeln; (* print the rest of Buf *) attach(main); (* D *) end consumer;

8

9 program reader_writers; (* In this example a single input stream consisting of blocks of numbers, each ending with 0, is printed on two printers of different width. The choice of the printer is determined by the block header which indicates the desired number of print columns. The input stream ends with a double 0. m1 = the width of printer_1, m2 = the width of printer_2 *) end;

10 program reader_writers; const m1=10,m2=20; var reader:reading,printer_1,printer_2:writing; var n:integer,new_sequence:boolean,mag:real; unit writing:coroutine(n:integer);... end writing; unit reading:coroutine ;... end reading; begin reader:=new reading; printer_1:=new writing(m1); printer_2:=new writing(m2); do read(n); case n when 0: exit when m1: attach(printer_1) when m2: attach(printer_2) otherwise write(" wrong data"); exit esac od end;

11 unit writing:coroutine(n:integer); var Buf: arrayof real, i,j:integer; begin new_array Buf dim (1:n); (* array generation *) return; (* return terminates coroutine initialization *) do attach(reader); (* reactivates coroutine reader *) if new_sequence then (* a new sequence causes buffer Buf to be cleared up *) for j:=1 to i do write(' ',Buf(j):10:2) od; writeln; i:=0; new_sequence:=false; attach(main) else i:=i+1; Buf(i):=mag; if i=n then for j:=1 to n do write(' ',Buf(j):10:2) od; writeln; i:=0; fi fi od end writing; end;

12 unit reading: coroutine; begin return; do read(mag); if mag=0 then new_sequence:=true; fi; detach; (* detach returns control to printer_1 or printer_2 depending which one reactivated reader *) od end reading;

13

14 Zadania ● Napisz klasę coroutine w Javie, jako rozszerzenie klasy threads. ● Napisz klasę coroutine w C++. ● Napiszcie z kolegą grę strategiczną (tzn. nie strzelankę, nie karcianą) np. “kółko i krzyżyk”, warcaby,

15 Współprogramy II W tym wykładzie pogłębimy naszą znajomość z współprogramami. Omówimy współpracę procedur rekurencyjnych i współprogramów, wprowadzimy pojęcie łańcucha dynamicznego.

16 Przykład ● Rozpatrzmy następujące zadanie: Dany jest zbiór drzew binarnych poszukiwań. Należy scalić dane zapisane w tym zbiorze i wydrukować je w porządku rosnącym. ● Przypomnijmy sobie najpierw: czym są drzewa binarnych poszukiwań? 1

17 Przykład ● Rozpatrzmy następujące zadanie: Dany jest zbiór drzew binarnych poszukiwań. Należy scalić dane zapisane w tym zbiorze i wydrukować je w porządku rosnącym. ● Przypomnijmy sobie najpierw: czym są drzewa binarnych poszukiwań BST? ● Definicja. Drzewem binarnych poszukiwań (BST) jest – drzewo binarne, skończone, zawierające elementy z pewnego zbioru E, uporządkowanego przez relację less (

18 czy to jest drzewo BST? 5 3 7 4 5 1010 9 1212 1414 2 6 2 1 4 1

19 Zadanie: scalić drzewa BST w ciąg ● Rozpatrzmy następujące zadanie: Dany jest zbiór drzew binarnych poszukiwań. Należy scalić dane zapisane w tym zbiorze i wydrukować je w porządku rosnącym. 1

20 Zadanie: scalić drzewa BST w ciąg ● Rozpatrzmy następujące zadanie: Dany jest zbiór drzew binarnych poszukiwań. Należy scalić dane zapisane w tym zbiorze i wydrukować je w porządku rosnącym. ● Niech node będzie klasą unit node: class(val: integer); (* klucz poszukiwań*) var left, right: node; unit insert: procedure(e: integer);... end insert; unit T: procedure(y: node); begin if ynone then call T(y.left); write(y.val); call T(y.right) fi end T; end node; 1

21 rozpatrzmy drzewo 7 4 5 1010 9 1212 1414 2 6 1 n

22 przykład c.d. ● Co się stanie gdy zmienna n typu node var n: node wskazuje na korzeń drzewa binarnych poszukiwań i gdy wykonamy instrukcję? call n.T(n) ● Tak, masz rację. Zostanie wydrukowany ciąg wartości val zapisanych w wierzchołkach drzewa o korzeniu n, liczby te będą wypisane od najmniejszej do największej. Dlaczego? Udowodnij odpowiedni lemat. 1

23 jednostki dynamiczne utworzone dotychczas 7 4 5 1010 9 1212 1414 2 6 n 1

24 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n y.val=7 DL

25 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n

26 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n rek. aktyw. T y = n.left.left

27 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n rek. aktyw. T y = n.left.left rek. aktyw. T y = n.left.left.left = none y.val=7 y.val=4 y.val=2

28 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n rek. aktyw. T y = n.left.left y.val=7 y.val=4 y.val=2 write(y.val) 2

29 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n y.val=7 y.val=4 write(y.val) 2 write(y.val) 4

30 wykonujemy instr. call T(n) 7 4 5 1010 9 1212 1414 2 6 n 1 rek. aktyw. T y = n 1 rek. aktyw. T y = n.left rek. aktyw. T y = n y.val=7 y.val=4 write(y.val) 2 rek. aktyw. T y = n.left.right y.val=5 write(y.val) 4

31 Lemat Wykonanie instrukcji call T(n) gdzie n wskazuje na korzeń drzewa BST spowoduje wydrukowanie wszystkich elementów zapisaych w drzewie w kolejności od najmniejszego do największego elementu Dowód. (przez indukcję ze względu na wysokość drzewa ) Dla drzew o wysokości jeden, lemat zachodzi, widać to z treści procedury T. Załóżmy więc, że lemat zachodzi dla wszystkich drzew BST o wysokości nie większej niż k. Rozpatrzmy drzewo o wysokości k+1. Z treści procedury T wynika, że najpierw wykonana zostanie instrukcja call T(n.left). To poddrzewo ma wyskość nie większą od k. Z założenia indukcyjnego wydrukowane zostaną elementy zapisane w tym poddrzewie w kolejności rosnącej. Potem wykonana zostanie instrukcja write(n.val), wydrukowana zostanie wartość większa od dotychczas wydrukowanych, bo to jest drzewo BST. Z tego samego powodu i z założenia indukcyjnego instrukcja call T(n.right) spowoduje wydrukowanie ciągu rosnącego elementów zawartych w prawym poddrzewie. Wszystkie one są większe od wartości n.val. 1

32 A teraz wyobraźmy sobie dwa współprogramy A i B: w jednym z nich, w A, wywoływana jest procedura T call T(n), a w drugim powtarzamy instrukcje attach(A). program test; var A: CA, B: CB, kolejny, n: integer; unit CA: coroutine(n: node); unit T: procedure(y: node); begin if ynone then call T(y.left); kolejny := y.val; detach; call T(y.right) fi end T; begin return;call T(n); end CA ; unit CB: coroutine; begin return; do write(kolejny); attach(A) od end CB begin A:= new CA; B:= new CB; attach(B) end test 1

33 Na tym rysunku narysować: rekord aktywacji Main, drzewo BST, obiekty współprogramów A i B, rekordy aktywacji procedury T Main 1

34 7 4 5 1010 9 1212 1414 2 6 n 1

35 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od 1

36 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL 7 1

37 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T 7 4 1

38 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T T 7 4 2 1

39 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T TT 7 4 2 none 1

40 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T T detach 7 4 1

41 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T 7 4 1

42 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T 7 4 1

43 Main 7 4 5 1010 9 1212 1414 2 6 n A B do write(kolejny); attach(A) od T DL T T 7 4 5 1

44 Lemat 2 Dla kazdego drzewa binarnych poszukiwań d współpraca dwu współprogramów A i B spowoduje wydrukowanie wszystkich elementów zapisanych w drzewie d w kolejności od najmniejszego do największego. Dowód. Wynika wprost z poprzedniego lematu i z faktu, ze instrukcja detach w nowej wersji procedury T prowadzi wprost do wykonania instrukcji write(kolejny), po niej zaś instrukcja attach(A) spowoduje wznowienie obliczeń w najnowszym rekordzie aktywacji procedury T. Po co tak dziwacznie programowac? Lemat powyzszy pozwoli nam rozwiązać zadanie scalania drzew BST. 1

45 zbiór drzew? proszę bardzo ● rozważmy tablicę var Las: arrayof node; ● utworzenie Lasu array Las dim(1:p); for i:= 1 to n do Las(i) := new node(...) od; zmienna Las(i) wskazuje na korzeń i-tego drzewa w zbiorze, należy zadbać o podanie wartości val zapisanej w korzeniu, ● napełnianie drzewa o korzeniu n wartościami e 1, e 2,..., e n polega na wykonywaniu instrukcji call n.insert(e j ) 1

46 Szkic programu ● Wczytaj liczbę n drzew BST, ● Utwórz n drzew i napełnij je danymi, ● Utwórz n wspólprogramów, ● powtarzaj aż do końca wybierz najmniejszy spośród n elementów i wydrukuj, uaktywnij odpowiedni współprogram by dostarczył kolejny większy element w tym drzewie, ● zakończ gdy wydrukowałeś wszystkie elementy 1

47 PROGRAM Merge;(* COROUTINES MERGE BINARY SEARCH TREES *) UNIT NODE : CLASS;(* NODE OF BINARY TREE *)... UNIT TRAVERS : COROUTINE (X :NODE);... VAR N,I,J,MIN,M,K : INTEGER, D : ARRAYOF NODE, TR: ARRAYOF TRAVERS; BEGIN (* czytaj N ) ARRAY D DIM(1:N); M:= maxInt; FOR I := 1 TO N DO READ(J);D(I) := NEW NODE; D(I).VAL := J; DO READ(J); CALL D(I).INS(J); (* exit gdy j=-1 *) OD; OD I; ARRAY TR DIM(1:N); MIN := 0; FOR I:= 1 TO N DO TR(I) := NEW TRAVERS(D(I));ATTACH(TR(I)); OD; K:=0; DO IF MIN = M THEN EXIT FI; (* KONIEC exit*) MIN := TR(1).VAL; J :=1; FOR I:= 2 TO N DO IF MIN>TR(I).VAL THEN MIN:= TR(I).VAL; J := I FI; OD; IF MIN < M THEN WRITE(MIN); ATTACH(TR(J));K:=K+1; FI OD; END merge 11

48 Podsumowanie ● pojęcie łańcucha dynamicznego, ● instrukcje attach i detach przełączają pomiędzy łańcuchami dynamicznymi współprogramów, ● współpraca: – struktury danych, – wspólprogramów, – procedur rekurencyjnych może dać bardzo wiele. ● program merge.log 1

49 Współprogramy III 12 stycznia 2010 Ten wykład ma na celu pokazanie kolejnej ciekawej możliwości, którą oferują współprogramy. Wspólprogramy reprezentujące wyrażenia regularne kooperują w celu wypisania języka regularnego. Drugim naszym celem jest opanowanie techniki dowodzenia przez indukcję ze względu na hierarchię klas (w tym przypadku hierarchię coroutin).

50 Wyrażenia regularne Niech A będzie ustalonym zbiorem. Jego elementy nazywać będziemy znakami alfabetu, a on sam nazywany będzie alfabetem. Niech A* oznacza zbiór wszystkich skończonych ciągów znaków alfabetu A. Zbiór A* zawiera ciąg pusty, oznaczany . Zakładamy, że znaki:  nie należą do alfabetu A. Definicja. Zbiorem wyrażeń regularnych WR nad alfabetem A jest najmniejszy zbiór wyrażeń taki, że: wr1) każdy element zbioru A jest elementem zbioru WR, wr2) jeśli dwa wyrażenia  i  należą do zbioru WR, to do zbioru WR należą też wyrażenia (  ), (  ),  * Przykłady. Niech A ={x, y, z}. Napisy x, z, ((x)  y  z  (x  y)* są wyrażeniami regularnymi, napis (x  t)* nie jest wyrażeniem regularnym nad alfabetem A. 1

51 Języki regularne Z każdym wyrażeniem regularnym  można związać zbiór |  | ciągów skończonych znaków z alfabetu A w następujący sposób. Definicja. Jeżeli  a jest atomowym wyrażeniem regularnym  A to |  | = {a}, Jeżeli  jest wyrażeniem regularnym postaci (  ) to |  jeżeli  jest wyrażeniem regularnym postaci (  ) to |  uw: u  i w  jeżeli  jest wyrażeniem regularnym postaci  *, to |  | = |  *| = {  } Elementy zbioru |  | nazywamy słowami języka regularnego |a|. Przykład. |(x  (y  z)| = {xy, xz} |(x  y)*| = {  x, y, xx, xy, yx, yy, xxy, xyx,...} ten język regularny zawiera wszystkie słowa skończone zawierające znaki x i y. 1

52 Zastosowania wyrażeń regularnych Wyrażenia i języki regularne znalazły wiele zastosowań: ● w kompilatorach, ● w opisie procesów, ● w lingwistyce formalnej, ● w teorii złożoności, ● w aplikacjach dotyczących sterowania. 1

53 Obliczanie wartości wyrażeń regularnych Na ogól chcemy znaleźć odpowiedź na pytanie czy dane słowo należy do określonego języka regularnego. Czasami jednak chcemy wypisać wszystkie słowa należące do języka regularnego opisanego wyrażeniem regularnym . Jest oczywiste, że nie da się tego zrobić dla języków opisanych wyrażeniami zawierającymi znak *. Wobec tego w dalszym ciągu tego wykładu ograniczamy się do wyrażeń regularnych, w których nie występuje operator *. 1

54 Hierarchia coroutin: regexp 1 regexpatom union concatenation

55 Klasa bazowa hierarchii: regexp unit REGEXP:coroutine; var B:BOOL; (* B  all the words of the language were shown *) begin return inner; B := true end REGEXP; 1

56 klasa Atom unit ATOM: REGEXP class(C:CHAR); begin do I:=I+1; (* update the position *) Word(I):=C; B:=TRUE; detach od end ATOM; 1

57 klasa Union unit UNION: REGEXP class(L,R:REGEXP); var M: INTEGER; begin do M:=I; do attach(L); if L.B then exit fi; detach; I:=M od; L.B:=FALSE; do detach; I:=M; attach(R); if R.B then exit fi; od; R.B:=FALSE; B:=TRUE; detach; od; end UNION; 1

58 klasa Concatenation var N,M:INTEGER; begin do M:=I; do attach(L); N:=I; do attach(R); if R.B then if L.B then exit exit else exit fi fi; detach; I:=N od; R.B:=FALSE; detach; I:=M od; R.B,L.B:=FALSE; B:=TRUE; detach od; end CONCATENATION; unit CONCATENATION: regexp class(L, R: regexp); 1

59 Twierdzenie Dla każdego obiektu o spełniającego relację o in regexp, następujący program Pr wydrukuje wszystkie słowa języka regularnego reprezentowanego przez ten obiekt o i zatrzyma się. Pr: I:=0; do attach(o); drukuj zawartość tablicy Word for J:=1 to I do write(Word(J)) od; writeln; if W.B then exit fi od 1

60 Lemat Załóżmy, że miejsca tablicy Word są wypełnione aż do pozycji I. Załóżmy ponadto, że pewne słowa z języka L(o) zostały już wcześniej wytworzone i wydrukowane przez wcześniejsze aktywowanie współprogramu o. (W tablicy Word nie ma więc już po nich śladu.) Wykonanie instrukcji attach(o) ma następujący efekt: kolejne słowo języka L(o) zostanie dopisane do tablicy Word poczynając od pozycji Word(I+1). Atrybut B przyjmie wartość true wtedy i tylko wtedy gdy wszystkie słowa języka L(o) zostaną wydrukowane. 1

61 dowód lematu Obiekt o należy do klasy Atom, lub do klasy Union lub do klasy Concatenation. W każdym z tych przypadków jest on korzeniem pewnego drzewa obiektów. Dowód będzie przebiegać ze względu na wysokość tego drzewa. W przypadku gdy obiekt o jest atomem, drzewo ma wysokość zero, i zachodzi następujący Fakt. Wykonanie instrukcji attach(o) zastosowanej do obiektu o takiego, że o in Atom spowoduje umieszczenie litery C na I+1 miejscu tablicy Word i atrybut B w tym obiekcie przyjmie wartość true. 1

62 dowód Faktu 1 Word  1|... | 8| a|... | h| I C char j B boolean false o atom return; do I := I+1; Word[I] := C; detach; od; B := true

63 dowód Faktu 1 Word  1|... | 8| 9| a|... | h|. | I C char j B boolean false o atom return; do I := I+1; Word[I] := C; detach; od; B := true

64 dowód Faktu 1 Word  1|... | 8| 9| a|... | h| j | I C char j B boolean false o atom return; do I := I+1; Word[I] := C; detach; od; B := true

65 dowód Faktu 1 Word  1|... | 8| 9| a|... | h| j | I C char j B boolean false o atom return; do I := I+1; Word[I] := C; detach; od; B := true

66 dowód lematu c.d. Pozostaje nam do wykazania, że jeśli lemat jest spełniony dla obiektów L i R będących korzeniami lewego i prawego poddrzewa drzewa o korzeniu o, to lemat jest spełniony dla samego obiektu o. Przypadek A) o in Union Struktura instrukcji we współprogramie o jest następująca while nie wyczerpano języka L do attach(L) od -- z zalożenia indukcyjnego (* tu L.B = true*) L.B := false; while nie wyczerpano języka R do attach(R) od (* R.B = true *) R.B := false; (* B= true *) B := false; 1

67 dowód lematu c.d. unit Union: regexp class(L, R: regexp); var M: integer; begin do M:=I; (* I is the position of the lastly generated letter. *) do attach(L) (* by the inductive assumption this statement causes that one word will be generated of the language L and it will be concatenated to the content of WORD(1),..., WORD(I) *) if L.B then exit fi; detach; I:=M (* reestablish the position in the table WORD for the next word *) od; L.B:=FALSE; (* restart language L *) do detach; I:=M; (* reestablish the position in the table WORD for the next word *) attach(R); (* by the inductive assumption this statement causes that one word will be generated of the language R and it will be concatenated to the content of WORD(1),..., WORD(I) *) if R.B then exit fi; od; R.B:=FALSE; (* restart language R *) B:=TRUE; detach; od; end Union; 1

68 dowód union 1 Word  1|... | 8| a|... | h| I L regexp R regexp M integer o union while nie wyczerpano języka L do attach(L) od (* tu L.B = true*) L.B := false; while nie wyczerpano języka R do attach(R) od (* R.B = true *) R.B := false; (* B= true *) B := false;

69 dowód union 1 Word  1|... | 8| a|... | h| kolejne słowo z L I L regexp R regexp M integer o union while nie wyczerpano języka L do attach(L) od (* tu L.B = true*) L.B := false; while nie wyczerpano języka R do attach(R) od (* R.B = true *) R.B := false; (* B= true *) B := false;

70 dowód lematu c.d. Przypadek B) o in Concatenation Struktura instrukcji we współprogramie o jest następująca while nie wyczerpano języka L do zapamietaj I; attach(L); -- słowo z języka L attach(R); -- a po nim słowo z języka R detach; -- a więc słowo z języka (L  R) odtwórz I; od; 1

71 dowód lematu c.d. unit CONCATENATION: REGEXP class(L,R:REGEXP); var N,M:INTEGER; begin do M:=I; (*begin of first language word position *) do attach(L); N:=I; (* begin of the second language word position *) do attach(R); if R.B then if L.B then exit exit else exit fi fi; detach; I:=N (* restart language R word generation position *) od; R.B:=FALSE; (* restart language R *) detach; I:=M (* restart language L word generation position *) od; R.B,L.B:=FALSE; B:=TRUE; detach od; end CONCATENATION; 1

72 Program główny const N=50; (* DIMENSION FOR ARRAY WORD *) var A,B,C,D,E,W,V,L,O,G,II,NN:REGEXP, I,J,N,M:INTEGER; (* I = GLOBAL POSITION POINTER FOR ARRAY WORD *) var WORD: arrayof CHAR; (* BUFFER FOR WORDS GENERATION *) begin A:=new ATOM('A'); B:=new ATOM('B'); C:=new ATOM('C'); D:=new ATOM('D'); E:=new ATOM('E'); L:=new ATOM('L'); G:=new ATOM('G'); II:=new ATOM('I'); NN:=new ATOM('N'); O:=new ATOM('O'); W:=new UNION(A,L); W:=new CONCATENATION(W,new UNION(D,O)); V:=new CONCATENATION(II,C); V:=new UNION(V,new CONCATENATION(L,new CONCATENATION(A,NN))); V:=new CONCATENATION(G,V); V:=new UNION(A,V); W:=new CONCATENATION(W,V); writeln(" WE HAVE LANGUAGE DEFINED BY THE FOLLOWING EXPRESSION"); writeln(" (A  L)  (D  O)  (A  G  (I  C  L  A  N))"); array WORD dim(1:N); do attach(W); write(" "); for J:=1 to I do write(WORD(J)) od; if W.B then exit fi od end 1

73 Czy wiemy co wydrukuje ten program? Czy potrzebne jest nam do tego wykonanie programu? ================================= przeczytaj i uruchom program z pliku: treegen.log dodaj klasę iteration pochodna klasy regexp 1