Język aktora CAL
| Paradygmat | Przepływ danych |
|---|---|
| Po raz pierwszy pojawiły się | 2001 |
| Platforma | Niezależne od platformy |
| Rozszerzenia nazw plików | .cal, .xdf |
| Główne wdrożenia | |
| Open RVC-CAL Compiler, framework OpenDF | |
CAL ( Cal Actor Language ) to język programowania wysokiego poziomu do pisania ( przepływu danych ) aktorów , które są operatorami stanowymi, które przekształcają wejściowe strumienie obiektów danych (tokeny) w strumienie wyjściowe. Licencja CAL została skompilowana na różne platformy docelowe, w tym procesory jednordzeniowe, procesory wielordzeniowe i programowalny sprzęt . Był używany w kilku obszarach zastosowań, w tym w wideo i przetwarzaniu, kompresji i kryptografii . Grupa robocza MPEG Reconfigurable Video Coding (RVC) przyjęła CAL w ramach swoich działań standaryzacyjnych .
Historia i wprowadzenie
CAL Actor Language został opracowany w 2001 roku jako część projektu Ptolemeusz II na Uniwersytecie Kalifornijskim w Berkeley . CAL to język przepływu danych ukierunkowany na różne dziedziny aplikacji, takie jak przetwarzanie multimediów, systemy sterowania, przetwarzanie sieciowe itp .
Innym częstym powodem wyboru przepływu danych jest to, że celem jest wydajna implementacja równoległa, która byłaby trudna lub niemożliwa do osiągnięcia przy użyciu sekwencyjnego języka programowania. Języki sekwencyjne są ogólnie trudne do zrównoleglenia, więc wydajne implementacje równoległe będą zwykle wymagały znacznych wskazówek od użytkownika. Program przepływu danych CAL zapewnia proste, zrozumiałe i wydajne abstrakcje, które umożliwiają specyfikację tak dużej lub małej równoległości , jak jest to wymagane, umożliwiając narzędziom tworzenie zaawansowanych implementacji wykorzystujących współbieżną strukturę obliczeń.
Podczas programowania w przepływie danych programista zwykle konstruuje współbieżny opis systemu obliczeniowego, który różni się od zwykłego programu sekwencyjnego. Zamiast zajmować się wykonywaniem krok po kroku algorytmu , programista przepływu danych buduje system asynchronicznie komunikujących się podmiotów zwanych aktorami. Większość wysiłków związanych z programowaniem jest ukierunkowana na znalezienie dobrego rozłożenia problemu na aktorów oraz na zaprojektowanie odpowiednich wzorców komunikacji między tymi aktorami.
Funkcje licencji CAL
Struktura aktorów
Aktorzy wykonują swoje obliczenia w sekwencji kroków zwanych wypalaniami. W każdym z tych kroków:
- 1. aktor może konsumować tokeny ze swoich portów wejściowych,
- 2. może modyfikować swój stan wewnętrzny,
- 3. może produkować tokeny na swoich portach wyjściowych.
W związku z tym opisanie aktora obejmuje opisanie jego interfejsu na zewnątrz, portów, struktury jego stanu wewnętrznego, a także kroków, które może wykonać, co te kroki robią (w zakresie produkcji i konsumpcji tokenów oraz aktualizacji stan aktora) i jak wybrać krok, który aktor wykona jako następny. W tej sekcji omówiono niektóre konstrukcje w języku CAL, które zajmują się tymi problemami. Akcje opisują rzeczy, które dzieją się podczas kroku, który wykonuje aktor. Właściwie można powiedzieć, że krok polega na wykonaniu akcji. Pamiętaj, że kiedy aktor wykonuje krok, może zużyć żetony wejściowe i wyprodukować żetony wyjściowe.
Dlatego wzorce wejściowe wykonują następujące czynności:
- Określają liczbę tokenów (dla każdego portu), które zostaną zużyte, gdy akcja zostanie wykonana (odpalona).
- Deklarują zmienne symbole, za pomocą których żetony zużyte podczas strzelania akcji będą odnosić się do akcji.
- Określają warunek wystrzelenia akcji, czyli warunek, który musi być spełniony, aby akcja mogła wystrzelić.
Strona wyjściowa akcji jest nieco prostsza, wyrażenia wyjściowe po prostu definiują liczbę i wartości tokenów wyjściowych, które będą generowane na każdym porcie wyjściowym przy każdym uruchomieniu akcji. Dopuszczalne jest pominięcie jawnego nazewnictwa portu, do którego odnosi się wzorzec wejściowy lub wyrażenie wyjściowe, jeśli akcja zapewnia tyle wzorców wejściowych, ile jest portów wejściowych lub wyrażeń wyjściowych, ile jest portów wyjściowych. W takim przypadku wzorce lub wyrażenia są dopasowywane według pozycji do deklaracji portów.
Jednym ze sposobów myślenia o aktorze jest bycie operatorem strumieni danych — sekwencje tokenów wchodzą do niego na jego portach wejściowych, a sekwencje tokenów opuszczają go na portach wyjściowych. Omawiając działanie aktora, często warto spojrzeć na niego jako na operatora w strumieniach. Aktorzy mogą mieć parametry. Działają jako stałe podczas wykonywania aktora i otrzymują konkretną wartość, gdy instancja aktora jest tworzona jako część sieci aktorów. Głównym celem parametrów aktora jest umożliwienie programistom określania rodzin powiązanych aktorów bez konieczności powielania dużej ilości kodu.
Brak determinizmu
Aktor niedeterministyczny to taki, który dla tych samych sekwencji wejściowych dopuszcza więcej niż jeden przebieg i więcej niż jedno możliwe wyjście. Niedeterminizm może być bardzo potężny, gdy jest używany odpowiednio, ale może być również bardzo kłopotliwym źródłem błędów. Szczególnym problemem jest to, że niedeterminizm może zostać wprowadzony do aktora nieumyślnie, tj. autor myśli, że aktor jest deterministyczny, chociaż tak nie jest. Jednym z kluczowych celów projektowych języka CAL było umożliwienie opisu aktorów niedeterministycznych, przy jednoczesnym umożliwieniu narzędziom identyfikacji możliwych źródeł niedeterminizmu, tak aby mogły ostrzegać o nich użytkownika.
Kluczową konsekwencją niedeterministycznego aktora, takiego jak NDMerge , jest to, że podczas rzeczywistego wykonania jego dane wyjściowe mogą zależeć od czasu jego wejścia. Jeśli obie jego kolejki wejściowe są puste, a NDMerge czeka na dane wejściowe, to każde wejście, do którego dotrze następny token, może być tym, które jest kopiowane obok wyjścia. W związku z tym planowanie działań w sieci aktorów lub względne prędkości aktorów zasilających aktora, takiego jak NDMerge , mogą wpływać na wydajność systemu. Czasami może to być pożądane, a innym razem może nie. W każdym razie jest to właściwość, której trzeba być świadomym.
Jednym ze sposobów spojrzenia na niedeterminizm tego rodzaju, który uzależnia aktora od dokładnego czasu nadejścia żetonów, jest to, że taki aktor wydaje się być niedeterministyczny tylko wtedy, gdy patrzymy na niego jako na operatora strumieni, ponieważ ten pogląd jest abstrakcyjny. z czasowych właściwości wykonania, a tym samym celowo usuwa informacje, które służą do określenia kolejności, w jakiej akcje się uruchamiają. Z perspektywy języka CAL nie jest to całkowicie dokładne, ale mimo to łatwo jest napisać niedeterministycznych aktorów, którzy nie byliby deterministyczni, nawet gdybyśmy wiedzieli wszystko o czasie tokenów i implementacji aktora — na przykład następujące:
Działania strzeżone
Klauzula ochronna akcji zawiera pewną liczbę wyrażeń, z których wszystkie muszą być prawdziwe, aby akcja mogła zostać uruchomiona. Aby pierwsza akcja mogła zostać uruchomiona, przychodzący token musi być większy lub równy zeru, w takim przypadku zostanie wysłany na wyjście P . W przeciwnym razie ta akcja nie może wystrzelić. I odwrotnie, aby druga akcja mogła zostać uruchomiona, token musi być mniejszy od zera, w którym to przypadku jest wysyłany do wyjścia N. Przebieg tego aktora może wyglądać tak: Aktor może wpaść w kłopoty, jeśli kiedykolwiek napotka żeton zerowy, ponieważ żadna z jego akcji nie będzie mogła na niego wystrzelić.
Pisanie aktorów, które kończą się na niektórych danych wejściowych, nie jest nielegalne, aw rzeczywistości może być ważne, aby mieć kilka z nich w niektórych systemach. Ale jest to pułapka, której trzeba być świadomym. Po drugie, warunki ochrony są również rozłączne, oprócz tego, że są wyczerpujące.
Na koniec zauważ, że warunki strażników mogą „podglądać” nadchodzące żetony bez faktycznego ich zużywania — jeśli strażnicy okażą się fałszywi lub akcja nie zostanie uruchomiona z jakiegoś innego powodu, a żeton nie zostanie zużyty przez inną akcję, to pozostaje na swoim miejscu i będzie dostępny do następnego strzału. (Albo pozostanie tam na zawsze, jak w przypadku żetonu zerowego przed SplitDead , który nigdy nie jest usuwany, ponieważ aktor nie żyje.)
Poniższy wybór aktora to kolejny przykład użycia akcji chronionych. Jest podobny do NDMerge w tym sensie, że łączy dwa strumienie (te docierające do jego portów wejściowych A i B). Jednak robi to zgodnie z (boolowskimi) wartościami tokenów docierających do jego portu wejściowego S.
Aktorzy z państwem
U wszystkich dotychczasowych aktorów nic, co wystrzeliło z akcji, nie wpłynęłoby w żaden sposób na kolejne wystrzelenia z akcji tego samego aktora. Wykorzystując zmienne stanu, wystrzeliwania akcji mogą pozostawiać informacje dla kolejnych wypalań tej samej lub innej akcji tego samego aktora. Sposób, w jaki ten aktor jest zapisany, wybór następnego tokena wejściowego i faktyczne skopiowanie tokena na wyjście to jeden niepodzielny krok.
Zauważ, że Select i IterSelect są prawie, ale nie całkowicie, równoważne. Po pierwsze, IterSelect wykonuje dwa razy więcej kroków, aby przetworzyć tę samą liczbę tokenów. Po drugie, faktycznie odczytuje, a zatem zużywa token wejściowy S, niezależnie od tego, czy pasujący token danych jest dostępny na A czy B .
Harmonogramy
Aktor IterSelect z poprzedniej sekcji zilustrował użycie stanu do kontrolowania wyboru akcji. Jest to niezwykle powszechna czynność w praktyce, a język CAL zapewnia do tego celu specjalną składnię w postaci harmonogramów. Pod względem koncepcyjnym można myśleć o harmonogramach jako o kodyfikacji określonego wzorca używania zmiennej stanu — nie dodają one niczego do języka pod względem wyrazistości. Uzasadnienie stosowania harmonogramów jest dwojakie:
- Są one zwykle łatwiejsze w użyciu i mniej podatne na błędy niż używanie zmiennej stanu oraz wielu strażników i przypisań.
- Narzędzia mogą łatwiej wykorzystywać informacje zakodowane w harmonogramie, a tym samym rozpoznawać prawidłowości w aktorze, co może pomóc im w stworzeniu wydajniejszego kodu lub przeprowadzeniu innych analiz pomocnych we wdrażaniu i projektowaniu.
Każde przejście stanu składa się z trzech części: stanu pierwotnego, listy znaczników akcji i stanu następującego po nim. Warto zauważyć, że zwiększyła się liczba akcji — zamiast pierwotnych trzech, nowa wersja z harmonogramem ma teraz cztery akcje. Powodem jest to, że akcji nie można już bezpośrednio przypisać stanu następcy, jak to miało miejsce w oryginale, gdzie w zależności od wartości stanu odczytu tokena byłaby przypisywana albo wartość 1 albo 2. W wersji z harmonogramem to modyfikacja stanu jest niejawna w strukturze maszyny stanów i dzieje się to w zależności od tego, która akcja zostanie uruchomiona. W związku z tym warunek, który sprawdza wartość tokena, został przeniesiony z treści akcji do strażników dwóch akcji oznaczonych readT i readF .
Priorytety
Dopóki ma wejście tylko na jednym ze swoich portów wejściowych, wszystko jest jednoznaczne. Ale, podobnie jak NDMerge, gdy tylko wejście jest dostępne na obu portach wejściowych, może uruchomić jedną z dwóch akcji, aw specyfikacji aktora nie ma nic, co predysponowałoby go do wybrania jednej z nich.
Żadna z dotychczasowych konstrukcji językowych nie pozwoliła nam na to. W przeciwieństwie do tego przypadku harmonogramów, które można by uznać za cukier syntaktyczny , ponieważ można je zredukować do istniejących elementów języka (zmienne stanu, strażników i przypisań), ta sytuacja faktycznie wymaga prawdziwego rozszerzenia — priorytetów działań. Podstawową ideą jest dodanie szeregu nierówności, które dotyczą działań w odniesieniu do ich pierwszeństwa strzelania.
Podobnie jak w przypadku harmonogramów, tagów akcji używamy do identyfikacji działań, do których chcemy się później odnieść – tym razem w ramach nierówności priorytetów. Blok priorytetów zawiera tylko jedną taką nierówność, odnoszącą działanie otagowane config do jednego otagowanego procesu, dając temu pierwszemu pierwszeństwo przed drugim. Oczywiście nawet ta wersja jest nadal bardzo zależna od czasu. W tym przypadku nie musi to stanowić problemu, aw rzeczywistości jest prawdopodobnie wymogiem, aby ten aktor mógł pełnić swoją funkcję. Ale generalnie ważne jest, aby zrozumieć, że priorytety, zwłaszcza gdy są używane tak jak w poprzednim przykładzie, muszą być dobrze zrozumiane, aby dawały prawidłowe wyniki. Zwłaszcza gdy informacje o czasie komunikacji w sieci są niejasne, prawdopodobnie najlepiej jest myśleć o nich jako o silnych dyrektywach implementacyjnych.
Oświadczenia i wyrażenia
Poprzedni rozdział koncentrował się przede wszystkim na tych konstrukcjach w CAL, które są powiązane z koncepcjami specyficznymi dla aktora — wejście i wyjście tokena, akcje, kontrolowanie wyboru akcji i tak dalej. W tej sekcji omówiono bardziej „piesze” części licencji CAL, instrukcje i wyrażenia używane do manipulowania obiektami danych i wyrażania (sekwencyjnych) algorytmów. Ta część języka jest podobna do tego, co można znaleźć w wielu językach programowania proceduralnego (takich jak C , Pascal , Java , Ada ), więc skupimy się na obszarach, które mogą być nieco inne w CAL.
Wyrażenia
W przeciwieństwie do języków takich jak C, CAL wyraźnie rozróżnia instrukcje i wyrażenia. Mają bardzo różne role, bardzo różne znaczenia i nigdy nie mogą być używane zamiennie. Wyrażenie w CAL to fragment kodu, którego jedynym celem jest obliczenie wartości. Mówimy również, że wyrażenie ma wartość lub że ma wartość. W przypadku większości wyrażeń wartość, na jaką są oceniane, będzie zależała od wartości jednej lub większej liczby zmiennych w momencie obliczania wyrażenia. Ponieważ wartości zmiennych mogą zmieniać się w czasie, to samo wyrażenie może mieć różne wartości, gdy jest oceniane w różnych momentach.
Wyrażenia atomowe
Prawdopodobnie najbardziej podstawowymi wyrażeniami są stałe. Kolejną grupą podstawowych wyrażeń są odwołania do zmiennych. Składniowo zmienną jest dowolna sekwencja liter i cyfr . Jedną z ważnych właściwości wyrażeń jest to, że gwarantują one, że nie zmienią zmiennych (mówimy też, że nie mają skutków ubocznych) — w konsekwencji wielokrotne odwołania do tej samej zmiennej w obrębie wyrażenia zawsze dadzą ten sam wynik.
Proste wyrażenia złożone
Licencja CAL udostępnia operatory dwóch rodzajów do budowania wyrażeń: jednoargumentowe i binarne . Operator jednoargumentowy w CAL jest zawsze operatorem przedrostkowym, tzn. występuje przed swoim pojedynczym operandem. Operator binarny występuje między dwoma operandami.
Sprawozdania
W pewnym sensie instrukcje w CAL są przeciwieństwem wyrażeń: nie mają „wartości zwracanej”, ale mogą zmieniać wartości zmiennych. Rzeczywiście, zmiana wartości zmiennych jest całym celem instrukcji. Instrukcje są wykonywane w ścisłej kolejności i jeśli nie określono inaczej, wykonywanie instrukcji przebiega w kolejności, w jakiej pojawiają się w tekście programu, co oznacza, że wszelkie zmiany zmiennych wywołane przez instrukcję mogą wpływać na wykonywanie kolejnych instrukcji.
Kontrola przepływu
Podobnie jak w większości innych języków programowania, istnieją konstrukcje kontrolujące kolejność wykonywania instrukcji w programie. Część tej pętli, która następuje bezpośrednio po słowie foreach , jest generatorem, podobnie jak w wyrażeniach listowych.
Działanie
- Wzorce wprowadzania danych: deklarowanie zmiennych
- Strażnik: określanie warunków włączania
- Wyrażenia wyjściowe: obliczanie tokenów wyjściowych
- Ciało: modyfikowanie stanu aktora