Współprogram

Pojęcie współprogramu ma dwie odmienne definicje. Obie definicje zgodnie stwierdzają, że współprogram cechuje się posiadaniem ciągu instrukcji do wykonania i ponadto możliwością zawieszania wykonywania jednego współprogramu A i przenoszenia wykonywania do innego współprogramu B. W szczególności można wznowić pracę zawieszonego współprogramu A, a wykonywanie będzie podjęte w miejscu, w którym zostało zawieszone. Tym co różni obie definicje jest zdolność współpracy z rekurencyjnymi procedurami (W językach programowania funkcyjnego koncepcja współprogramu istnieje pod postacią kontynuacji – pojęcia wprowadzonego niemal równocześnie ze współprogramami).

Obiekt współprogramu jest quasi-wątkiem. Tak jak wątek ma ciąg instrukcji do wykonania, w odróżnieniu od wątków obiekty współprogramów nie działają równolegle. Jest niezmiennikiem systemu współprogramów to, że w każdej chwili, dokładnie jeden obiekt współprogramu wykonuje swoje instrukcje:

\color {blue}card\{coroutine:\ coroutine\ is\ Active\ \}=1.\color {black}

W literaturze znaleźć można termin włókno (ang. fiber) dla odróżnienia od wątku (ang.thread).

Współprogramy jako specjalny rodzaj klas	Współprogramy jako bogatszy rodzaj podprogramów
W językach programowania: Simula67, Loglan 82, BETA można tworzyć moduły coroutine, tj. współprogramów. Składnia współprogramu różni się od składni klasy tym, że zamiast słowa class piszemy coroutine, i co ważniejsze, wewnątrz takiego modułu wolno używać instrukcji atomowych attach oraz detach. Instrukcje takie mogą się też pojawiać wewnątrz metod zadeklarowanych we współprogramie. Stwarza to nowe i interesujące możliwości współpracy współprogramów i rekursji.	"Subroutines are special cases of ... coroutines." –Donald Knuth^[1]. W assemblerze od dawna występuje pojęcie podprogramu – nie należy go mylić z pojęciem procedury. Podprogram istnieje w kodzie programu i ma co najwyżej jedną instancję. Nie jest możliwe rekurencyjne wykonywanie podprogramów.
Przykład: Łączenie drzew BST por. [Dahl i Wang 1971 ↓] oraz [Szałas i Warpechowska 1991 ↓, s. 112–116] ${\begin{array}{l}\mathbf {var} \ T:\ arrayof\ Traverser;\\\\\left\{{\begin{array}{l}\mathbf {unit} \ Traverser:\ \mathbf {coroutine} (n:node);\\\quad \mathbf {var} \ kolejny:\ integer;\\\left\vert {\begin{array}{l}\quad \mathbf {unit} \ traverse:\ \mathbf {procedure} (m:\ node);\\\quad \mathbf {begin} \\\qquad \mathbf {if} \ m\neq none\\\qquad \mathbf {then} \\\qquad \ \ \ \mathbf {call} \ traverse(m.left);\\\qquad \ \ \ kolejny:=m.val;\\\qquad \ \ \ \mathbf {detach} ;\ \ (\ instrukcja\ \mathbf {detach} \ wznawia\\\qquad \ \qquad wspolprogram\ w,\ ktory\ ostatnio\ uaktywnil\ \\\qquad \ \qquad ten\,(\mathrm {this} )\ obiekt\ Traverser\ wykonujac\ \mathbf {attach} (.)\ )\\\qquad \ \ \ \mathbf {call} \ traverse(m.right);\\\qquad \mathbf {fi} \\\quad \mathbf {end} \ traverse;\end{array}}\right.\\\mathbf {begin} \\\quad \mathbf {return} ;\\\quad \mathbf {call} \ traverse(n)\\\mathbf {end} \ Traverser;\end{array}}\right.\\(Stworz\ drzewa\ BST,\ w\ liczbie\ np.\,k\ drzew.\ Dla\ kazdego\ drzewa\ d\ \\stworz\\T[i]:=\mathbf {new} \ Traverser(d)\\(Kolejne\ uaktywnienie\ tego\ wspolprogramu\ \mathbf {attach} (T[i])\ spowoduje\\wykrycie\ kolejnego\ co\ do\ wielkosci\ elementu\ z\ drzewa\ d)\end{array}}$	Przykład ${\begin{array}{l}\mathbf {var} \ q:=\mathbf {new} \ kolejka\\\mathbf {coroutine} \ produkuj\\\quad \mathbf {loop} \\\qquad \mathbf {while} \ q\ nie\ jest\ pelna\\\qquad \ \ stworz\ troche\ nowych\ przedmiotow\\\qquad \ \ wstaw\ przedmioty\ do\ q\\\qquad \ \ \mathbf {yield\ to} \ konsumuj\\\\\mathbf {coroutine} \ konsumuj\\\quad \mathbf {loop} \\\qquad \mathbf {while} \ q\ jest\ niepusta\\\qquad \ \ pobierz\ troche\ przedmiotow\ z\ q\\\qquad \ \ uzyj\ te\ przedmioty\\\qquad \ \ \mathbf {yield\ to} \ produkuj\end{array}}$
Uwagi. 1°.Mamy tu do czynienia z dynamicznym systemem współprogramów. Wyrażenia generujące postaci new Traverser(...) umożliwiają stworzenie wielu obiektów typu współprogram Traverser. 2°. Obiekt współprogramu Traverser wywołuje metodę traverse(). Łańcuch dynamiczny tego obiektu wydłuża się o rekord aktywacji metody traverse. Łańcuch taki może być tak długi jak gałąź odwiedzanego drzewa BST. 3°. Instrukcje attach() oraz detach mogą wystąpić nie tylko w ciągu instrukcji współprogramu, lecz także w metodach współprogramu. 4°. Przełączenie wykonywania odbywa się pomiędzy łańcuchami dynamicznymi współprogramów.	Uwagi. 1°. Ten system współprogramów jest statyczny: zawiera dwa współprogramy. Deklaracja coroutine automatycznie tworzy obiekty typu produkuj i konsumuj. 2°. W tym systemie są dwa punkty wejścia. Otrzymany graf składa się z dwu współprogramów i dwu przełączeń yield.

W latach 60 XX wieku współprogram był fragmentem kodu napisanego w assemblerze. wątki o następujących własnościach:

dokładnie jeden współprogram wykonuje swoje instrukcje, tzn. jest aktywny,
współprogram aktywny może przejść w stan pasywny wskazując przy tym na inny wątek, który ma być uaktywniony,
współprogram $x$ uaktywniony w efekcie wykonania instrukcji $attach(x)$ (w dotychczas aktywnym współprogramie $y$ ) kontynuuje wykonywanie instrukcji od odpowiedniego punktu wejścia, dokładniej: pierwsze uruchomienie instrukcji wątku współprogramu spowoduje wykonanie pierwszej instrukcji wątku, każda następna instrukcja $attach(x)$ wznawiająca wykonywanie wątku współprogramu $x$ rozpoczyna wykonywanie instrukcji od punktu wejścia wyznaczonego przez ostatnio wykonaną w nim instrukcję $attach(...).$

Zasada działania współprogramów

System współprogramów można nazwać systemem quasi-współbieżnym. Nazwa ta jest uzasadniona dwojako: liczne przykłady programów współbieżnych np. producent-konsument, czytelnicy-pisarze itd. zapisane przy pomocy współprogramów okazują się wystarczająco adekwatne do zastosowań. Inny argument wspierający użycie tej nazwy to fakt, że od bardzo dawna stosuje się współprogramy do symulacji systemów, np. w Simuli67, Loglanie'82 i in. Odpowiednia klasa Simulation dostarcza klasę wewnętrzną simproces – obiekty klas pochodnych od klasy simproces symulują rzeczywiste procesy np. pacjentów w systemie symulacji epidemii choroby, pojazdy w systemie symulacji ruchu w mieście itp.

Wielu autorów uważa, iż „współprogramy to podprogramy wykonywane w taki sposób, że sterowanie może zostać przekazywane pomiędzy nimi wielokrotnie, przy czym wywołanie danego współprogramu powoduje wykonywanie instrukcji od miejsca ostatniego przerwania wykonania (ostatniego punktu wyjścia), a nie od początku”. Nie jest to całkiem ścisłe. Podprogramy (funkcja, metoda) tworzą rekordy aktywacji. Po opuszczeniu takiego rekordu jest on automatycznie usuwany i nie ma możliwości wznowienia go. Współprogramy wymagają więc wątków i są realizowane jako obiekty odpowiednich klas, a nie jako podprogramy czy procedury. Cytowany wyżej pogląd mocno zawęża koncepcję współprogramów. Co więcej, nie można zapominać, że instrukcjami wątku współprogramu mogą być instrukcje wywołania jego prywatnych metod(procedur). Metody te mogą zawierać instrukcje $attach(...)$ przekazujące sterowanie z jednego do innego współprogramu. Dokładniej, instrukcja attach przekazując sterowanie z jednego do drugiego współprogramu przenosi je z łańcucha dynamicznego jednego współprogramu do łańcucha dynamicznego innego współprogramu.

Łańcuch dynamiczny współprogramu zawiera obiekt i wątek współprogramu i ponadto, jeśli wykonano instrukcję procedury, to do łańcucha dynamicznego dołączony jest rekord aktywacji procedury. Zakończenie wykonywania instrukcji procedury(metody) powoduje skrócenie łańcucha dynamicznego. Instrukcja $attach(x)$ wykonana w rekordzie aktywacji procedury powoduje przejście do punktu wejścia w łańcuchu dynamicznym współprogramu x. Punktem wejścia (powrotu) dla dotychczas aktywnego współprogramu jest instrukcja w rekordzie aktywacji procedury występująca bezpośrednio za instrukcją $attach(x).$ Widać stąd, że liczba punktów wejścia (powrotu) danego współprogramu może być zmienna w czasie i może nie być niczym ograniczona!

Podsumowując, współprogramy to więcej niż obiekty zwyczajnych klas, a mniej niż obiekty aktywne wątków (ang. threads).

Schemat zmian stanów obiektu współprogramu

Współprogramy w języku Loglan 82

instrukcją przenoszenia sterowania z aktywnego współprogramu do drugiego współprogramu $x$ jest $attach(x),$
moduł współprogramu jest specyficzną klasą (stosuje się słowo ‘coroutine’ zamiast ‘class’),
instrukcja $attach(x)$ może występować nie tylko w wątku współprogramu, lecz także w prywatnych metodach współprogramu(!),
punktami wejścia do współprogramu są: pierwsza instrukcja wątku współprogramu oraz każda instrukcja następna po instrukcji $attach(x),$
można też używać bezparametrowej instrukcji $detach,$ odpowiada instrukcji 'attach(ten współprogram, który ostatnio mnie wezwał)'.

Instrukcje przenoszenia sterowania między współprogramami w różnych językach programowania

Instrukcje przenoszące sterowanie z jednego do drugiego współprogramu to

attach(x) oraz detach – w językach Simula 67 i Loglan 82,
yield(x) – w nowszych językach, np. w Pythonie,
cede – w Perlu, w bibliotece Coro
instrukcja skoku – w assemblerze oraz w Fortranie, gdzie podprogram nie jest procedurą,
trzeba odnotować też implementację współprogramów w Javie, jako wyspecjalizowanych wątków Javy.

Argument x wskazuje na współprogram pasywny w danej chwili.

Przykładowe zastosowania współprogramów

historycznie pierwsze współprogramy to skaner i Analizator składniowy kompilatora[Conway 1963 ↓],
podobny schemat występuje w wielu sytuacjach np. jeden współprogram zbiera wyniki pomiarów i zapisuje je w bazie danych, a drugi współprogram opracowuje zebrane wyniki, ogólny schemat to producent-konsument,
jeżeli jakaś metoda (funkcja lub procedura) jest wykonywana wielokrotnie z tymi samymi parametrami aktualnymi, to warto utworzyć odpowiednie obiekty współprogramu (tablicę współprogramów) dla każdego zestawu parametrów aktualnych. Następnie każdą instrukcję wywołania procedury zastępujemy odpowiednią instrukcją $attach(..).$ Zysk może okazać się znaczny, ponieważ wykonanie instrukcji $attach$ jest znacznie prostsze od tworzenia rekordu aktywacji procedury.
Jeśli współprogramy są klasami wyposażonymi w instrukcję $attach(...)$ to można tworzyć hierarchie współprogramów wykorzystując dziedziczenie.
główne zastosowanie współprogramów to narzędzia symulacji, takie jak klasy Simulation w Simuli 67 i w Loglanie 82.

Przypisy

↑ Donald Ervin Knuth: The Art of Computer Programming. T. 1 Fundamental Algorithms. Addison-Wesley, 1997, s. 193–200. ISBN 0-201-89683-4.

Bibliografia

M.E. Conway. Design of a separable transition-diagram compiler. „Communications of the ACM”, July 1963.
Ole-Johann Dahl, Bjarne Myhrhaug, Kristen Nygaard: Common Base Language (Simula67). Oslo: NCC, 1970.
O.-J. Dahl, A. Wang. Coroutine sequencing in a block structured environment. „BIT”, s. 425–449, 1971.
W.M.W.M. Bartol W.M.W.M. i inni, Report on the Loglan'82 Programming Language, Warszawa Łódź: PWN, 1984 .
Andrzej Szałas, Jolanta Warpechowska: Loglan'82. Warszawa: WNT, 1991.