Jazyk herců CAL - CAL Actor Language

Jazyk herců CAL
ParadigmaDatový tok
Poprvé se objevil2001
PlošinaNezávislé na platformě
Přípony názvu souboru.cal, .xdf
Hlavní, důležitý implementace
Otevřete kompilátor RVC-CAL, Rámec OpenDF

CAL (dále jen Cal herec jazyk) je programovací jazyk na vysoké úrovni[1] pro psaní (datový tok ) herci, což jsou stavové operátory, které transformují vstupní toky datových objektů (tokeny) na výstupní toky. Licence CAL byla kompilována do různých cílových platforem, včetně jednojádrových procesorů, vícejádrových procesorů a programovatelných Hardware. Používá se v několika aplikačních oblastech, včetně video a zpracování, komprese a kryptografie. The MPEG Překonfigurovatelné kódování videa (RVC)[2] pracovní skupina přijala CAL jako součást svého úsilí o standardizaci.

Historie a úvod

Jazyk herců CAL byl vyvinut v roce 2001 jako součást projektu Ptolemaios II na adrese University of California v Berkeley. CAL je jazyk toku dat zaměřený na celou řadu aplikačních domén, jako je zpracování multimédií, řídicí systémy, síťové zpracování atd.

Dalším běžným důvodem pro výběr toku dat je, že cílem je efektivní paralelní implementace, které by bylo obtížné nebo nemožné dosáhnout pomocí sekvenčního programovacího jazyka. Sekvenční jazyky se obecně obecně obtížně paralelizují, takže efektivní paralelní implementace budou obvykle vyžadovat významné vedení ze strany uživatele. Program toku dat CAL poskytuje jednoduché, srozumitelné a výkonné abstrakce, které umožňují specifikaci stejně nebo tak málo rovnoběžnost jak je požadováno, umožnění nástrojů k výrobě sofistikovaných implementací, které využívají souběžnou strukturu výpočtu.

Při programování v datovém toku se programátor je obvykle konstrukce souběžného popisu výpočetního systému, který se liší od běžného sekvenčního programu. Spíše než se zajímat o postupné provádění algoritmus, programátor toku dat staví systém asynchronně komunikující subjekty zvané herci. Velká část programátorského úsilí je zaměřena na nalezení dobrého faktoringu problému do aktérů a na vytvoření vhodných komunikačních vzorců mezi těmito aktéry.

Funkce CAL

Struktura aktérů

Herci provádějí svůj výpočet v posloupnosti kroků nazývaných střelby. V každém z těchto kroků:

  • 1. účastník může konzumovat žetony ze svých vstupních portů,
  • 2. může upravit svůj vnitřní stav,
  • 3. na svých výstupních portech může vyrábět žetony.

V důsledku toho popis aktéra zahrnuje popis jeho rozhraní ven, portů, struktury jeho vnitřního stavu a také kroků, které může provést, co tyto kroky dělají (z hlediska výroby a spotřeby tokenů a aktualizace herec) a jak vybrat krok, který herec udělá provést další. Tato část pojednává o některých konstrukcích v jazyce CAL, které se těmito problémy zabývají. Akce popsat věci, které se stanou během kroku, který herec provede. Ve skutečnosti lze přesně říci, že krok spočívá v provedení akce. Připomeňme, že když herec udělá krok, může spotřebovat vstupní tokeny a vyrobit výstupní tokeny.

Proto vstupní vzory dělají následující:

  • Definují počet tokenů (pro každý port), které budou spotřebovány při provedení (aktivaci) akce.
  • Deklarují variabilní symboly, kterými se v rámci akce budou odkazovat na tokeny spotřebované aktivací akce.
  • Definují podmínku střelby pro akci, tj. Podmínku, kterou musí akce splnit, aby mohla střílet.

Výstupní stránka akce je o něco jednodušší, výstupní výrazy jednoduše definují počet a hodnoty výstupních tokenů, které budou vytvořeny na každém výstupním portu při každém spuštění akce. Je povoleno vynechat explicitní pojmenování portu, na který se vztahuje vstupní vzor nebo výstupní výraz, pokud akce poskytuje tolik vstupních vzorů, kolik je vstupních portů, nebo výstupních výrazů, kolik je výstupních portů. V takovém případě se vzory nebo výrazy shodují s pozicí vůči deklarací portů.

Jeden způsob myšlení o herci je jako operátor na proudech dat - sekvence tokenů vstupují do jejích vstupních portů a sekvence tokenů ji ponechávají na výstupních portech. Když diskutujeme o operaci herce, je často užitečné dívat se na to jako na operátora streamů. Herci mohou mít parametry. Působí jako konstanty během provádění herce a mají konkrétní hodnotu, když je aktér vytvořen jako součást sítě herce. Hlavním účelem parametrů aktéra je umožnit programátorům specifikovat rodiny souvisejících aktérů, aniž by bylo nutné duplikovat hodně kódu.

Nedeterminismus

A nedeterministický herec je ten, který pro stejné vstupní sekvence umožňuje více než jeden běh a více než jeden možný výstup. Nedeterminismus může být při správném použití velmi silný, ale může být také velmi problematickým zdrojem chyb. Zvláštní obavou je, že nedeterminismus může být do herce vložen nechtěně, tj. Autor si myslí, že herec je deterministický, i když tomu tak není. Jedním z klíčových cílů designu jazyka CAL bylo umožnit popis nedeterministických aktérů a současně povolit nástroje k identifikaci možných zdrojů nedeterminismu, aby na ně mohly uživatele upozornit.

Klíčový důsledek nedeterministického herce NDMerge je, že během skutečného provedení může jeho výstup záviset na načasování jeho vstupu. Pokud jsou obě jeho vstupní fronty prázdné, a NDMerge čeká na vstup, pak jakýkoli vstup, na který dorazí další token, může být ten, který se zkopíruje vedle výstupu. V důsledku toho je plánování aktivit v síti aktéra nebo relativní rychlost podávání aktérů do herce jako NDMerge může ovlivnit výstup systému. To může být příležitostně žádoucí a jindy nemusí. V každém případě je to vlastnost, které si člověk musí být vědom.

Jedním ze způsobů, jak se dívat na nedeterminismus takového druhu, díky kterému je herec závislý na přesném načasování příchodu tokenů, je, že takový aktér se jeví jako nedeterministický, pouze pokud se na něj podíváme jako na operátora streamů, protože tento pohled abstrakt z časových vlastností provedení, a tak záměrně odstraní informace, které se používají k určení pořadí, ve kterém se akce spouští. Z pohledu jazyka CAL to není úplně přesné, ale i tak je snadné psát nedeterministické herce, kteří by nebyli determinističtí, i kdybychom věděli vše o načasování tokenů a implementaci herců - jako např. následující:

Hlídané akce

Ochranná klauzule akce obsahuje řadu výrazů, které musí být pravdivé, aby byla akce aktivovatelná. Aby byla první akce aktivovatelná, musí být příchozí token větší nebo roven nule, v takovém případě bude odeslán na výstup P. Jinak tato akce nemůže vystřelit. Naopak pro druhou akci, která má být aktivovatelná, musí být token menší než nula, v takovém případě je odeslán na výstup N. Běh tohoto herce může vypadat takto: Herec by mohl narazit na potíže, pokud by někdy narazil na nulový token, protože žádná z jeho akcí na něj nebude moci střílet.

Není protizákonné psát herce, kteří končí s určitým vstupem, a ve skutečnosti může být důležité mít některé z nich v některých systémech. Je však nutné si uvědomit úskalí. Zadruhé, podmínky stráže jsou kromě toho, že jsou vyčerpávající, také disjunktní.

Na závěr si všimněte, že podmínky stráže mohou „pokukovat“ po příchozích žetonech, aniž by je skutečně konzumovaly - pokud jsou stráže nepravdivé nebo akce není aktivována z nějakého jiného důvodu a pokud token není spotřebován jinou akcí, pak zůstane tam, kde je, a bude k dispozici pro další palbu. (Nebo tam zůstane navždy, jako v případě nulového tokenu před SplitDead, který se nikdy neodstraní, protože herec je mrtvý.)

Níže uvedený Vybrat aktéra je dalším příkladem použití střežených akcí. Je to podobné jako u NDMerge herec v tom smyslu, že slučuje dva proudy (ty, které přicházejí k jeho vstupním portům A a B). Činí tak však podle (booleovských) hodnot tokenů, které přicházejí na jeho S vstupní port.

Herci se státem

U všech aktérů dosud nic, co by akční palba udělala, by nijak neovlivnilo následné palby akcí stejného herce. Pomocí stavových proměnných mohou akční aktivace zanechat informace za následnými aktivacemi stejné nebo jiné akce stejného aktéra. Způsob, jakým je tento herec zapsán, je výběr dalšího vstupního tokenu a skutečné kopírování tokenu na výstup jedním atomovým krokem.

Všimněte si, že vyberte a IterSelect jsou téměř, ale ne úplně, rovnocenné. Především, IterSelect provede dvakrát tolik kroků, aby mohl zpracovat stejný počet tokenů. Za druhé, ve skutečnosti čte, a proto spotřebovává vstupní token S, bez ohledu na to, zda je k dispozici odpovídající datový token A nebo B.

Rozvrhy

The IterSelect herec předchozí části ilustroval použití stavu k řízení výběru akcí. V praxi je to velmi běžná věc a jazyk CAL poskytuje pro tento účel speciální syntaxi ve formě plánů. Koncepčně lze plány považovat za kodifikaci konkrétního vzorce používání stavové proměnné - nepřidávají do jazyka nic z hlediska expresivity. Odůvodnění použití plánů je dvojí:

  1. Obvykle se snadněji používají a jsou méně náchylné k chybám než použití stavové proměnné a mnoha stráží a přiřazení.
  2. Nástroje mohou snáze využívat informace zakódované v plánu, a tak rozpoznat zákonitosti v aktérovi, které by jim mohly pomoci vytvořit efektivnější kód, nebo provést jiné analýzy, které pomohou při implementaci a návrhu.

Každý přechod stavu se skládá ze tří částí: původního stavu, seznamu značek akcí a následujícího stavu. Za zmínku stojí jedna věc, že ​​se zvýšil počet akcí - namísto původních tří má nová verze s plánem nyní čtyři akce. Důvodem je to, že akci již nelze přímo přiřadit nástupnický stát, jako tomu bylo v originále, kde by v závislosti na hodnotě stavu čtení tokenu byla přiřazena hodnota 1 nebo 2. Ve verzi s plánem, že modifikace stavu je implicitní ve struktuře stavového automatu a děje se to v závislosti na tom, která akce se aktivuje. Podle toho se podmínka, která kontroluje hodnotu tokenu, přesunula z těla akce na stráže dvou označených akcí readT a readF.

Priority

Pokud má pouze vstup na jednom ze svých vstupních portů, je vše jednoznačné. Ale stejně jako NDMerge, jakmile je vstup k dispozici na obou vstupních portech, mohl by vypálit kteroukoli ze svých dvou akcí a ve specifikaci herce není nic, co by ho předurčovalo k volbě jedné nad druhou.

Žádný z jazykových konstruktů nám to zatím nedovolil. Na rozdíl od tohoto případu plánů, na které se dalo pohlížet syntaktický cukr protože by mohly být redukovány na existující prvky jazyka (stavové proměnné, stráže a přiřazení), vyžaduje tato situace ve skutečnosti skutečné rozšíření - akční priority. Základní myšlenkou je přidat řadu nerovností, které se týkají akcí s ohledem na jejich prioritu palby.

Stejně jako v případě plánů používáme značky akcí k identifikaci akcí, na které se chceme později obrátit - tentokrát v rámci prioritní nerovnosti. Prioritní blok obsahuje pouze jednu takovou nerovnost, která spojuje konfiguraci tagu akce s jedním tagovaným procesem, čímž dává první prioritě před druhou. Samozřejmě i tato verze je stále velmi závislá na načasování. V tomto případě to nemusí být problém a ve skutečnosti je to pravděpodobně požadavek, aby tento aktér vykonával svoji funkci. Obecně je ale důležité si uvědomit, že priority, zejména pokud jsou použity jako v předchozím příkladu, musí být dobře pochopeny, aby přinesly správné výsledky. Zvláště když jsou informace o načasování komunikace v síti vágní, je pravděpodobně nejlepší považovat je za silné implementační směrnice.

Výroky a výrazy

Předchozí kapitola se zaměřila primárně na ty konstrukce v CAL, které souvisejí s koncepty specifickými pro aktéry - vstup a výstup tokenu, akce, řízení výběru akce atd. Tato část pojednává o „chodčích“ částech licence CAL, příkazech a výrazech používaných k manipulaci s datovými objekty a expresních (sekvenčních) algoritmech. Tato část jazyka je podobná té, kterou lze nalézt v mnoha procedurálních programovacích jazycích (např C, Pascal, Jáva, Ada ), takže se zaměříme na oblasti, které se mohou v CAL mírně lišit.

Výrazy

Na rozdíl od jazyků, jako je C, CAL výrazně rozlišuje mezi příkazy a výrazy. Mají velmi odlišné role, velmi odlišné významy a nikdy je nelze zaměnitelně použít. Výraz v CAL je část kódu, jejíž jediným účelem je vypočítat hodnotu. Také říkáme, že výraz má hodnotu, nebo že je vyhodnocen na hodnotu. U většiny výrazů bude hodnota, kterou vyhodnotí, záviset na hodnotách jedné nebo více proměnných v době, kdy je výraz vyhodnocen. Vzhledem k tomu, že se proměnné hodnoty mohou v průběhu času měnit, může mít stejný výraz při vyhodnocení v různých časových bodech různé hodnoty.

Atomové výrazy

Pravděpodobně nejzásadnější výrazy jsou konstanty. Další skupinou základních výrazů jsou proměnné odkazy. Syntakticky je proměnnou jakákoli posloupnost písmen a číslice. Jedna důležitá vlastnost výrazy je to, že zaručeně nemění proměnné (říkáme také, že nemají žádné vedlejší účinky) - následně v rámci výrazu více odkazů na stejnou proměnnou vždy přinese stejný výsledek.

Jednoduché složené výrazy

CAL poskytuje operátorům dvou druhů pro vytváření výrazů: unární a [[Binární operace} binární]]. Unární operátor v CAL je vždy operátor předpony, tj. Objeví se před jeho jediným operandem. Binární operátor nastane mezi jeho dvěma operandy.

Prohlášení

V některých ohledech, prohlášení v CAL jsou pravým opakem výrazů: nemají „návratovou hodnotu“, ale mohou měnit hodnoty proměnných. Změna hodnot proměnných je vlastně celý bod příkazů. Příkazy jsou prováděny v přísném pořadí, a pokud není uvedeno jinak, provádění příkazů probíhá v pořadí, v jakém se objevují v textu programu, což znamená, že jakékoli změny proměnných vytvořené příkazem mohou ovlivnit provádění následujících příkazů.

Řízení toku

Stejně jako ve většině ostatních programovacích jazyků existují konstrukce, které řídí pořadí, ve kterém jsou příkazy v programu prováděny. Část této smyčky, která přímo navazuje napro každého klíčové slovo je generátor, podobně jako v seznamu s porozuměním.

Akce

  • Vstupní vzory: deklarace proměnných
  • Stráž: upřesnění podmínek povolení
  • Výstupní výrazy: výpočet výstupních tokenů
  • Body: modifikace stavu aktéra

Podpůrné nástroje

Rámec OpenDF

Otevřete kompilátor RVC-CAL

Reference

  1. ^ Zpráva o jazyce CAL: Specifikace jazyka herce CAL, Johan Eker a Jörn W. Janneck, technické memorandum č. UCB / ERL M03 / 48, University of California, Berkeley, CA, 94720, USA, 1. prosince 2003
  2. ^ Přehled rámce MPEG Reconfigurable Video Coding Framework, Shuvra S.Bhattacharyya, Johan Eker, Jörn W. Janneck, Christophe Lucarz, Marco Mattavelli, Mickaël Raulet, Journal of Signal Processing Systems, 2009, Springer

externí odkazy