Programowanie oparte na przepływach - Flow-based programming

W programowaniu komputerowym , programowanie oparte przepływu ( FBP ) to paradygmat programowania , który definiuje aplikacje jako sieci „czarna skrzynka” procesów , które wymieniają dane całej predefiniowanych połączeń przez przekazywanie komunikatów , w których połączenia zostały określone zewnętrznie do procesów. Te procesy czarnej skrzynki można bez końca łączyć, tworząc różne aplikacje bez konieczności ich wewnętrznej zmiany. FBP jest więc naturalnie zorientowany na komponenty .

FBP to szczególna forma programowania przepływu danych oparta na ograniczonych buforach, pakietach informacji o zdefiniowanych czasach życia, nazwanych portach i oddzielnych definicjach połączeń.

Wstęp

Programowanie oparte na przepływach definiuje aplikacje przy użyciu metafory „fabryki danych”. Postrzega aplikację nie jako pojedynczy, sekwencyjny proces, który rozpoczyna się w pewnym momencie, a następnie wykonuje jedną czynność na raz, aż do zakończenia, ale jako sieć asynchronicznych procesów komunikujących się za pomocą strumieni ustrukturyzowanych fragmentów danych, zwane „pakietami informacyjnymi” (IP). W tym widoku nacisk kładziony jest na dane aplikacji i zastosowane do nich przekształcenia w celu uzyskania żądanych wyników. Sieć jest definiowana zewnętrznie w stosunku do procesów, jako lista połączeń, która jest interpretowana przez oprogramowanie, zwykle nazywane „schedulerem”.

Procesy komunikują się za pomocą połączeń o stałej przepustowości. Połączenie jest dołączane do procesu za pomocą portu o nazwie uzgodnionej między kodem procesu a definicją sieci. Ten sam fragment kodu może wykonać więcej niż jeden proces. W dowolnym momencie dany adres IP może być „własnością” tylko jednego procesu lub przechodzić między dwoma procesami. Porty mogą być proste lub typu tablicowego, jak to jest używane np. dla portu wejściowego komponentu Sortuj opisanego poniżej. To właśnie połączenie portów z procesami asynchronicznymi pozwala na obsługę wielu długo działających prymitywnych funkcji przetwarzania danych, takich jak Sort, Merge, Summarize itp., w postaci programowych czarnych skrzynek .

Ponieważ procesy FBP mogą kontynuować wykonywanie tak długo, jak mają dane do pracy i miejsce, w którym można umieścić swoje dane wyjściowe, aplikacje FBP zwykle działają w krótszym czasie niż konwencjonalne programy i optymalnie wykorzystują wszystkie procesory na maszynie, bez konieczności specjalnego programowania osiągnąć to.

Definicja sieci jest zwykle diagramowa i jest przekształcana w listę połączeń w jakimś języku lub notacji niższego poziomu. FBP to często wizualny język programowania na tym poziomie. Bardziej złożone definicje sieci mają strukturę hierarchiczną, zbudowaną z podsieci z „lepkimi” połączeniami. Wiele innych opartych na przepływach języków/środowisk wykonawczych jest zbudowanych wokół bardziej tradycyjnych języków programowania, najbardziej godnym uwagi przykładem jest RaftLib, który używa operatorów podobnych do C++ iostream do określenia grafu przepływu.

FBP ma wiele wspólnego z Linda języku tym, że jest, w Gelernter and Carriero w terminologii, „język koordynacji”: jest zasadniczo niezależny od języka. Rzeczywiście, biorąc pod uwagę program planujący napisany w języku wystarczająco niskiego poziomu, komponenty napisane w różnych językach można połączyć w jedną sieć. FBP nadaje się zatem do koncepcji języków specyficznych dla domeny lub „mini-języków”.

FBP wykazuje „sprzężenie danych”, opisane w artykule na temat sprzężenia jako najluźniejszy rodzaj sprzężenia między komponentami. Koncepcja luźnego sprzężenia jest z kolei związana z architekturą zorientowaną na usługi , a FBP spełnia szereg kryteriów takiej architektury, choć na bardziej szczegółowym poziomie niż większość przykładów tej architektury.

FBP promuje wysokopoziomowy, funkcjonalny styl specyfikacji, który upraszcza wnioskowanie o zachowaniu systemu. Przykładem tego jest model rozproszonego przepływu danych do konstruktywnego określania i analizowania semantyki rozproszonych protokołów wielostronnych.

Historia

Programowanie oparte na przepływach zostało wymyślone przez J. Paula Morrisona we wczesnych latach 70. i początkowo zaimplementowane w oprogramowaniu dla kanadyjskiego banku. Na początku swojego istnienia FBP było pod silnym wpływem niektórych języków symulacyjnych IBM z tamtego okresu, w szczególności GPSS , ale jego korzenie sięgają aż do przełomowego artykułu Conwaya na temat tego, co nazwał współprogramami .

Na przestrzeni lat FBP przeszło wiele zmian nazwy: pierwotna implementacja nosiła nazwę AMPS (Advanced Modular Processing System). Jedna duża aplikacja w Kanadzie została uruchomiona w 1975 r., a od 2013 r. jest w ciągłym użyciu produkcyjnym, codziennie, od prawie 40 lat. Ponieważ IBM uznał idee stojące za FBP „zbyt podobne do prawa natury”, aby można było je opatentować, zamiast tego umieścił podstawowe koncepcje FBP w domenie publicznej za pomocą Biuletynu Ujawnień Technicznych „Data Responsive Modular, Interleaved Task Programming System” , w 1971 roku. Artykuł opisujący jego koncepcje i doświadczenia z jego wykorzystaniem został opublikowany w 1978 roku w IBM Research IBM Systems Journal pod nazwą DSLM. Druga implementacja została wykonana jako wspólny projekt IBM Canada i IBM Japan, pod nazwą „Data Flow Development Manager” (DFDM) i została krótko wprowadzona do obrotu w Japonii pod koniec lat 80. pod nazwą „Data Flow Programming Manager”.

Ogólnie koncepcje te były określane w IBM jako „przepływ danych”, ale termin ten uznano za zbyt ogólny i ostatecznie przyjęto nazwę „Programowanie oparte na przepływach”.

Od wczesnych lat 80. do 1993 J. Paul Morrison i architekt IBM Wayne Stevens udoskonalali i promowali koncepcje stojące za FBP. Stevens napisał kilka artykułów opisujących i wspierających koncepcję FBP i zamieścił materiał na ten temat w kilku swoich książkach. W 1994 Morrison opublikował książkę opisującą FBP i dostarczającą empirycznych dowodów na to, że FBP doprowadziło do skrócenia czasu rozwoju.

Koncepcje

Poniższy diagram przedstawia główne elementy diagramu FBP (oprócz pakietów informacyjnych). Taki schemat można bezpośrednio przekształcić w listę połączeń, którą następnie może wykonać odpowiedni silnik (oprogramowanie lub sprzęt).

Prosty schemat FBP

A, B i C to procesy wykonujące komponenty kodu. O1, O2 i dwa wejścia IN to porty łączące połączenia M i N z ich odpowiednimi procesami. Dozwolone jest, aby procesy B i C wykonywały ten sam kod, więc każdy proces musi mieć swój własny zestaw pamięci roboczej, bloków sterujących itp. Niezależnie od tego, czy współdzielą kod, B i C mogą korzystać z tego samego portu nazwy, ponieważ nazwy portów mają znaczenie tylko w komponentach, do których się odwołują (i oczywiście na poziomie sieci).

M i N są często nazywane „ buforami ograniczonymi ” i mają stałą pojemność pod względem liczby adresów IP, które mogą przechowywać w dowolnym momencie.

Koncepcja portów pozwala na używanie tego samego komponentu w więcej niż jednym miejscu w sieci. W połączeniu z możliwością parametryzacji, zwaną początkowymi pakietami informacyjnymi (IIP), porty zapewniają FBP możliwość ponownego wykorzystania komponentów, dzięki czemu FBP jest architekturą opartą na komponentach . FBP wykazuje zatem to, co Raoul de Campo i Nate Edwards z IBM Research nazwali konfigurowalną modułowością .

Pakiety informacyjne lub adresy IP są alokowane w tzw. musi być wyraźnym działaniem ze strony procesu właściciela. Adresy IP przemieszczające się przez dane połączenie (właściwie to ich „uchwyty” podróżują) tworzą „strumień”, który jest generowany i konsumowany asynchronicznie – koncepcja ta ma zatem podobieństwa do koncepcji leniwych wad, opisanej w artykule Friedmana i Wise z 1976 roku.

Adresy IP są zwykle ustrukturyzowanymi porcjami danych — niektóre adresy IP mogą jednak nie zawierać żadnych prawdziwych danych, ale są używane po prostu jako sygnały. Przykładem tego są „adresy IP w nawiasach”, które mogą służyć do grupowania adresów IP danych w sekwencyjne wzorce w strumieniu, zwane „podstrumieniem”. Strumienie podrzędne mogą z kolei być zagnieżdżane. Adresy IP mogą być również łączone w łańcuchy, tworząc „drzewa IP”, które przechodzą przez sieć jako pojedyncze obiekty.

Opisany powyżej system połączeń i procesów można „rozgałęziać” do dowolnej wielkości. Podczas tworzenia aplikacji procesy monitorowania mogą być dodawane pomiędzy parami procesów, procesy mogą być „rozsadzane” do podsieci lub symulacje procesów mogą być zastąpione logiką rzeczywistego procesu. FBP nadaje się zatem do szybkiego prototypowania .

Tak naprawdę jest to obraz przetwarzania danych na linii montażowej : adresy IP przechodzące przez sieć procesów można traktować jako widżety przemieszczające się od stacji do stacji na linii montażowej. „Maszyny” można łatwo ponownie podłączyć, zdjąć z linii w celu naprawy, wymienić i tak dalej. Co dziwne, ten obraz jest bardzo podobny do tego, jaki przedstawia sprzęt rejestrujący, który był używany do przetwarzania danych przed erą komputerów, z tą różnicą, że talie kart musiały być przenoszone z jednej maszyny do drugiej.

Implementacje FBP mogą być nie-wywłaszczające lub wywłaszczające - wcześniejsze implementacje zwykle nie były wywłaszczające (mainframe i język C), podczas gdy najnowsza implementacja Javy (patrz poniżej) używa klasy Java Thread i jest wywłaszczająca.

Przykłady

„Problem z telegramem”

Komponenty FBP często tworzą komplementarne pary. W tym przykładzie zastosowano dwie takie pary. Opisany problem wydaje się bardzo prosty, jak opisano w słowach, ale w rzeczywistości jest zaskakująco trudny do zrealizowania przy użyciu konwencjonalnej logiki proceduralnej. Zadanie, nazwane „Problemem telegramu”, pierwotnie opisane przez Petera Naura , polega na napisaniu programu, który akceptuje wiersze tekstu i generuje wiersze wyjściowe zawierające jak najwięcej słów, przy czym liczba znaków w każdym wierszu nie przekracza określonej długość. Słowa nie mogą być dzielone i zakładamy, że żadne słowo nie jest dłuższe niż rozmiar linii wyjściowych. Jest to analogiczne do problemu zawijania tekstu w edytorach tekstu.

W logice konwencjonalnej programista szybko odkrywa, że ​​ani struktury wejściowe, ani wyjściowe nie mogą być używane do sterowania hierarchią wywołań przepływu sterowania . Z kolei w FBP sam opis problemu sugeruje rozwiązanie:

  • „słowa” są wyraźnie wymienione w opisie problemu, więc projektant powinien traktować słowa jako pakiety informacyjne (IP)
  • w FBP nie ma jednej hierarchii wywołań, więc programista nie ma pokusy, aby wymuszać podwzorzec rozwiązania jako najwyższy poziom.

Oto najbardziej naturalne rozwiązanie w FBP (nie ma jednego „poprawnego” rozwiązania w FBP, ale wydaje się, że to naturalne dopasowanie):

„Problem telegramu” Petera Naura

gdzie DC i RC oznaczają odpowiednio "Decompose" i "ReCompose".

Jak wspomniano powyżej, początkowe pakiety informacyjne (IIP) mogą być używane do określania informacji parametrycznych, takich jak pożądana długość rekordu wyjściowego (wymagana przez dwa skrajne prawe komponenty) lub nazwy plików. IIP to porcje danych skojarzone z portem w definicji sieci, które stają się „normalnymi” adresami IP po wysłaniu „odbioru” dla odpowiedniego portu.

Aktualizacja zbiorcza

Ten typ programu polega na przekazywaniu pliku „szczegółów” (zmiany, dodawanie i usuwanie) z „plikiem głównym” i generowanie (co najmniej) zaktualizowanego pliku głównego oraz jednego lub więcej raportów. Programy aktualizacyjne są generalnie dość trudne do napisania przy użyciu synchronicznego, proceduralnego kodu, ponieważ dwa (czasem więcej) strumienie wejściowe muszą być zsynchronizowane, nawet jeśli mogą istnieć mastery bez odpowiednich szczegółów lub odwrotnie.

Kanoniczna struktura „aktualizacji partii”

W FBP komponent wielokrotnego użytku (Collate), oparty na idei rekordów jednostkowych Collatora, znacznie ułatwia pisanie tego typu aplikacji, ponieważ Collate łączy dwa strumienie i wstawia adresy IP nawiasów, aby wskazać poziomy grupowania, znacznie upraszczając logikę niższego rzędu. Załóżmy, że jeden strumień (w tym przypadku „masters”) składa się z adresów IP o wartościach kluczy 1, 2 i 3, a adresy IP drugiego strumienia („szczegóły”) mają wartości kluczy 11, 12, 21, 31, 32, 33 i 41, gdzie pierwsza cyfra odpowiada wartościom klucza głównego. Używając znaków nawiasów do reprezentowania adresów IP w nawiasach, sortowany strumień wyjściowy będzie wyglądał następująco:

( m1 d11 d12 ) ( m2 d21 ) ( m3 d31 d32 d33 ) (d41)

Ponieważ nie było wzorca o wartości 4, ostatnia grupa składa się z jednego detalu (plus nawiasy).

Strukturę powyższego strumienia można zwięźle opisać za pomocą notacji podobnej do BNF , takiej jak

{ ( [m] d* ) }*

Sortuj jest czarną skrzynką wielokrotnego użytku , która musi tylko wiedzieć, gdzie znajdują się pola kontrolne w przychodzących adresach IP (nawet to nie jest bezwzględnie konieczne, ponieważ procesy transformatorowe można wstawić przed umieszczeniem pól kontrolnych w standardowych lokalizacjach) i w rzeczywistości można ją uogólnić do dowolnej liczby strumieni wejściowych i dowolnej głębokości zagnieżdżenia nawiasów. Sortuj używa portu typu tablica do wprowadzania danych, co pozwala na zmienną liczbę strumieni wejściowych.

Procesy multipleksowania

Programowanie oparte na przepływach wspiera multipleksowanie procesów w bardzo naturalny sposób. Ponieważ komponenty są tylko do odczytu, dowolna liczba wystąpień danego komponentu ("procesów") może działać asynchronicznie ze sobą.

Przykład multipleksowania

Kiedy komputery zwykle miały jeden procesor, było to przydatne, gdy odbywało się dużo operacji we/wy; teraz, gdy maszyny mają zwykle wiele procesorów, staje się to przydatne, gdy procesy również intensywnie obciążają procesor. Diagram w tej sekcji przedstawia pojedynczy proces „Load Balancer” dystrybuujący dane między trzema procesami, oznaczonymi odpowiednio S1, S2 i S3, które są instancjami pojedynczego komponentu, który z kolei jest zasilany w pojedynczy proces w , pierwszy ten lepszy”.

Prosta interaktywna sieć

Schemat ogólnej aplikacji interaktywnej

Na tym ogólnym schemacie żądania (transakcje) pochodzące od użytkowników wchodzą do diagramu w lewym górnym rogu, a odpowiedzi są zwracane w lewym dolnym rogu. „Zaplecza” (po prawej stronie) komunikują się z systemami w innych lokalizacjach, np. za pomocą CORBA , MQSeries , itp. Połączenia krzyżowe reprezentują żądania, które nie muszą przechodzić do zaplecza lub żądania, które muszą przechodzić przez sieci więcej niż jeden raz, zanim zostanie zwrócony użytkownikowi.

Ponieważ różne żądania mogą wykorzystywać różne back-endy i mogą wymagać różnej ilości czasu dla back-endów (jeśli są używane) do ich przetworzenia, należy zapewnić powiązanie zwracanych danych z odpowiednimi transakcjami żądającymi, np. tablicami mieszającymi lub pamięciami podręcznymi.

Powyższy diagram jest schematyczny w tym sensie, że ostateczna aplikacja może zawierać znacznie więcej procesów: procesy mogą być wstawiane między inne procesy w celu zarządzania pamięciami podręcznymi, wyświetlania ruchu połączeń, monitorowania przepustowości itp. Również bloki na diagramie mogą reprezentować „podsieci” - małe sieci z co najmniej jednym otwartym połączeniem.

Porównanie z innymi paradygmatami i metodologiami

Programowanie strukturalne Jackson (JSP) i Rozwój systemu Jackson (JSD)

Ta metodologia zakłada, że ​​program musi być skonstruowany jako pojedyncza hierarchia proceduralna podprogramów. Punktem wyjścia jest opisanie aplikacji jako zbioru „głównych linii”, opartych na wejściowych i wyjściowych strukturach danych. Jedna z tych "głównych linii" jest następnie wybierana do sterowania całym programem, a pozostałe muszą być "odwrócone", aby przekształcić je w podprogramy (stąd nazwa "inwersja Jacksona"). Czasami prowadzi to do tak zwanej „kolizji”, wymagającej podzielenia programu na wiele programów lub współprogramów. W przypadku korzystania z FBP ten proces inwersji nie jest wymagany, ponieważ każdy element FBP można uznać za oddzielną „główną linię”.

FBP i JSP podzielają koncepcję traktowania programu (lub niektórych komponentów) jako parsera strumienia wejściowego.

W późniejszej pracy Jacksona , Jackson System Development (JSD), idee były dalej rozwijane.

W JSD projekt utrzymywany jest jako projekt sieci aż do końcowego etapu wdrożenia. Model jest następnie przekształcany w zestaw procesów sekwencyjnych do liczby dostępnych procesorów. Jackson omawia możliwość bezpośredniego wykonania modelu sieci, który istnieje przed tym krokiem, w sekcji 1.3 swojej książki (kursywa dodana):

Specyfikacja sporządzona pod koniec etapu System Timing jest w zasadzie zdolna do bezpośredniego wykonania. Niezbędne środowisko zawierałoby procesor dla każdego procesu, urządzenie odpowiadające nieograniczonemu buforowi dla każdego strumienia danych oraz niektóre urządzenia wejściowe i wyjściowe, w których system jest podłączony do świata rzeczywistego. Takie środowisko mogłoby oczywiście zapewnić odpowiednie oprogramowanie działające na wystarczająco wydajnej maszynie. Czasami takie bezpośrednie wykonanie specyfikacji będzie możliwe, a nawet może być rozsądnym wyborem.

FBP zostało uznane przez MA Jacksona za podejście zgodne z jego metodą „Dekompozycji programu na sekwencyjne procesy komunikujące się przez mechanizm podobny do współprogramu”

Programowanie aplikacyjne

WB Ackerman definiuje język aplikacyjny jako taki, który w całości wykonuje swoje przetwarzanie za pomocą operatorów zastosowanych do wartości. Najwcześniejszym znanym językiem aplikacyjnym był LISP.

Komponent FBP może być traktowany jako funkcja przekształcająca swój strumień(i) wejściowy w strumień(i) wyjściowy. Funkcje te są następnie łączone, aby tworzyć bardziej złożone przekształcenia, jak pokazano poniżej:

Dwie funkcje karmienia jednego

Jeśli oznaczymy strumienie, jak pokazano, małymi literami, to powyższy diagram można zwięźle przedstawić w następujący sposób:

c = G(F(a),F(b));

Podobnie jak w notacji funkcjonalnej F można użyć dwukrotnie, ponieważ działa tylko z wartościami, a zatem nie ma skutków ubocznych, tak w FBP dwie instancje danego komponentu mogą działać współbieżnie, a zatem komponenty FBP nie mogą mieć skutków ubocznych albo. Notacja funkcjonalna może być oczywiście używana do reprezentowania przynajmniej części sieci FBP.

Powstaje zatem pytanie, czy same komponenty FBP mogą być wyrażone za pomocą notacji funkcjonalnej. WH Burge pokazał, jak można tworzyć wyrażenia strumieniowe przy użyciu rekurencyjnego, aplikacyjnego stylu programowania, ale ta praca dotyczyła (strumieni) wartości atomowych. W FBP konieczna jest umiejętność opisywania i przetwarzania ustrukturyzowanych porcji danych (IP FBP).

Co więcej, większość systemów aplikacyjnych zakłada, że ​​wszystkie dane są dostępne w pamięci w tym samym czasie, podczas gdy aplikacje FBP muszą być w stanie przetwarzać długotrwałe strumienie danych przy jednoczesnym wykorzystaniu ograniczonych zasobów. Friedman i Wise zasugerowali sposób, aby to zrobić, dodając koncepcję „leniwych wad” do pracy Burge'a. To usunęło wymóg, aby oba argumenty „przeciw” były dostępne w tym samym momencie. „Leniwe wady” nie budują strumienia, dopóki oba argumenty nie zostaną zrealizowane – wcześniej po prostu rejestruje „obietnicę”, aby to zrobić. Pozwala to na dynamiczną realizację strumienia z przodu, ale z niezrealizowanym tyłem. Koniec strumienia pozostaje niezrealizowany do samego końca procesu, a początek jest coraz dłuższym ciągiem elementów.

Linda

Wydaje się, że wiele koncepcji zawartych w FBP zostało odkrytych niezależnie w różnych systemach na przestrzeni lat. Wspomniana powyżej Linda jest jedną z takich. Różnicę między tymi dwiema technikami ilustruje technika równoważenia obciążenia Linda „szkoła piranii” – w FBP wymaga to dodatkowego komponentu „równoważenia obciążenia”, który kieruje żądania do komponentu na liście, który ma najmniejszą liczbę adresów IP oczekujących na być przetwarzane. Najwyraźniej FBP i Linda są ze sobą blisko spokrewnieni i jedno można łatwo wykorzystać do symulacji drugiego.

Programowanie obiektowe

Obiekt w OOP można opisać jako pół-autonomiczną jednostkę zawierającą zarówno informację, jak i zachowanie. Obiekty komunikują się za pomocą „wywołań metod”, które są zasadniczo wywołaniami podprogramów, wykonywanymi pośrednio przez klasę, do której należy obiekt odbierający. Dostęp do wewnętrznych danych obiektu można uzyskać tylko za pomocą wywołań metod, więc jest to forma ukrywania informacji lub „enkapsulacji”. Jednakże enkapsulacja poprzedza OOP – David Parnas napisał jeden z przełomowych artykułów na ten temat we wczesnych latach 70-tych – i jest podstawową koncepcją w informatyce. Enkapsulacja jest istotą komponentu FBP, który można traktować jako czarną skrzynkę , dokonującą pewnej konwersji danych wejściowych na dane wyjściowe. W FBP częścią specyfikacji komponentu są formaty danych i struktury strumieni, które może akceptować oraz te, które będzie generować. Jest to forma projektu na podstawie umowy . Ponadto dostęp do danych w adresie IP jest możliwy tylko bezpośrednio przez aktualnie posiadany proces. Enkapsulacja może być również zaimplementowana na poziomie sieci, ponieważ zewnętrzne procesy chronią wewnętrzne.

Praca C. Ellisa i S. Gibbsa rozróżnia obiekty aktywne i pasywne. Przedmioty pasywne zawierają informacje i zachowanie, jak wspomniano powyżej, ale nie mogą określać czasu tego zachowania. Z drugiej strony mogą to robić aktywne obiekty. W swoim artykule Ellis i Gibbs stwierdzają, że obiekty aktywne mają znacznie większy potencjał rozwoju systemów konserwowalnych niż obiekty pasywne. Aplikacja FBP może być postrzegana jako połączenie tych dwóch typów obiektów, gdzie procesy FBP odpowiadają obiektom aktywnym, podczas gdy adresy IP odpowiadają obiektom pasywnym.

Model aktora

FBP uważa aktora Carla Hewitta za proces asynchroniczny z 2 portami: jednym dla komunikatów wejściowych i jednym dla sygnałów sterujących. Sygnał kontrolny jest emitowany przez samego aktora po każdej rundzie egzekucji. Celem tego sygnału jest uniknięcie równoległego wykonywania ciała aktora, a tym samym umożliwienie dostępu do pól obiektu aktora bez synchronizacji.

Zobacz też

Bibliografia

Zewnętrzne linki